Introduction
Ontology-Based Query Answering (OBQA) has emerged as a vital paradigm for data integration over the past fifteen years. By allowing users to query data using a familiar high-level vocabulary while leveraging ontological semantics to fill in missing information, OBQA bridges the gap between heterogeneous data sources and user-centric information needs. Michaël Thomazo’s Habilitation à Diriger des Recherches (HDR) dissertation explores the theoretical boundaries of this field, moving beyond simple Boolean conjunctive queries to address expressivity, navigational capabilities, and data provenance.
The Problem: Beyond "Yes/No" Queries
In a world of fragmented and heterogeneous data, OBQA acts as a logical bridge. It allows users to query data using a high-level ontology while a reasoning engine fills in the gaps—for example, knowing that a query for "hormones" should also return results for "oxytocin."
However, the field has historically focused on a narrow subset: Boolean conjunctive queries (essentially asking "does this pattern exist?"). Thomazo identifies three critical gaps that this research addresses:
- Expressivity: Understanding the limits of what existential rules can describe compared to other logic languages.
- Functionality: Real-world users need to navigate graphs (path queries) and aggregate data (counting), tasks that are significantly harder to compute than simple pattern matching.
- Explainability: In complex systems, users need to know why an answer was returned (provenance), a task that becomes mathematically complex when recursion is involved.
Methodological Framework
The author employs several sophisticated logical and algorithmic tools to push these boundaries:
- The Chase: A central algorithmic procedure used to "complete" a database according to ontological rules. The paper analyzes different flavors (oblivious, restricted, etc.) and their termination properties.
- Descriptive Complexity: The research uses logical formalisms to characterize computational complexity classes (like PTime), specifically looking at how Datalog variants relate to these classes.
- Linearization: To handle complex "guarded rules" in path queries, the author uses a technique to reduce them to simpler "linear rules" that are easier to reason about.
- Interlacing: A novel tool introduced to provide upper bounds for the complexity of counting queries by "unravelling" models into tree-like structures.
- Semiring Provenance: The author adapts the algebraic framework of semirings to Datalog, allowing the system to "tag" data and track how these tags propagate through recursive rules.
Key Insights and Theoretical Findings
The Necessity of Negation
One of the most counter-intuitive findings is that even for queries that are "homomorphism-closed" (meaning they don't seem to involve "not" logic), having access to a form of negation (semipositivity) is actually necessary to express certain polynomial-time queries in Datalog.
Unpredictability of the Chase
The paper highlights that the restricted chase—a common reasoning method—can behave strangely. For instance, a "Datalog-first" strategy (applying simple rules before complex ones) doesn't always guarantee the process will finish, even if a finishing sequence exists.
The Complexity of Counting
Moving from "is there a result?" to "how many results are there?" drastically changes the computational landscape. The author identifies a "trichotomy" in certain description logics where counting is either very easy (TC0), equivalent to finding a perfect matching in a graph, or significantly harder (co-NP-complete).
Robust Provenance
When tracking the "why" behind an answer in recursive languages like Datalog, different mathematical definitions lead to different results. The author proposes "rationality properties" to evaluate these definitions, finding that a "Non-Recursive Tree" (NRT) approach is often the most robust.
Key Results
- Expressive Completeness: A major result proves that any decidable, homomorphism-closed query can be expressed by existential rules where the reasoning process (the chase) is guaranteed to terminate.
- Complexity Classification: The work successfully classifies the data complexity of "role cardinality queries" (counting relationships) across various description logics, providing a roadmap for which counting tasks are computationally feasible.
- Logic Mapping: The research provides a definitive mapping of how different Datalog extensions (negation, linear order) relate to each other and to the class of polynomial-time queries.
Limitations and Future Work
A fundamental wall remains: determining if the reasoning process (the restricted chase) will terminate for a given set of rules is itself an undecidable problem. Furthermore, while the paper makes strides in counting for simple ontologies, extending these results to more expressive logics remains an open challenge. Finally, while the author identifies robust ways to define provenance, some of the most accurate methods are currently "provably hard to compute," suggesting a need for more efficient approximations or specialized algorithms.
Summary updated