When querying large enterprise databases or structured web data—such as the Schema.org specifications analyzed by André Hernich et al. in Schema.org as a Description Logic—we often rely on ontologies to provide background knowledge. Ontologies allow us to define domain rules, hierarchies, and existential constraints, such as "Every department must have a manager, who is also an employee."
The challenge arises when we want to execute a query over a database while respecting these rules. This paradigm is known as Ontology-Mediated Query Answering (OMQA). To avoid modifying the underlying data, we must inject the ontology's logic directly into the query itself—a process called query rewriting.
The Limits of First-Order Rewriting
For simple ontologies, a query can be rewritten into First-Order (FO) logic, which translates directly into a standard SQL Union of Conjunctive Queries (UCQ). However, as Héctor Pérez-Urbina et al. observe in Practical Aspects of Query Rewriting for OWL 2, when we move to more expressive ontology languages like OWL 2 EL, greedy unfolding into UCQs causes an exponential explosion in query size.
Worse, if the ontology contains recursive rules (e.g., "A manager's manager is also a manager"), a static SQL union cannot handle the infinite depth of potential reasoning paths.
The Core Idea: Leveraging Datalog for Compact Recursion
Instead of flattening the query into a massive union of all possible logical paths, why not rewrite the query and the ontology into a recursive language? This is the core insight behind Datalog-based query rewriting.
As Lucas Larroque et al. explain in Ontology-Based Query Answering over Datalog-Expressible Rule Sets is Undecidable, this strategy decouples background knowledge from data storage by compiling the ontology and the query into a single Datalog program. Because Datalog natively supports recursion, it can represent complex, deep logical relationships in a highly compact form.
To make this practical, systems like Drewer, introduced by Peng Xiao et al. in Practical Datalog Rewriting for Existential Rules, utilize graph-based structure sharing and separation techniques. This allows them to generate compact Datalog programs that off-the-shelf deductive database engines can execute efficiently, bypassing the size bottlenecks of traditional methods.
Why It Works: Bridging Datalog to SQL Recursion
If we rewrite queries into Datalog, do we lose the ability to use standard relational database management systems (RDBMS)?
The bridge between theoretical Datalog and practical SQL lies in a specific fragment called linear Datalog, where the body of each rule contains at most one recursive predicate. In two foundational papers, Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability and Ontology-Mediated Querying with EL: Trichotomy and Linear Datalog Rewritability, Carsten Lutz et al. mapped the exact computational boundaries of the popular description logic $\mathcal{EL}$. They proved a strict trichotomy of data complexity: every query falls into either $AC_0$, PTIME-complete, or NL-complete.
Crucially, the authors demonstrated that queries in the NL-complete class are precisely those that can be rewritten into linear Datalog. Because linear Datalog is the exact theoretical equivalent of SQL's linear recursion (WITH RECURSIVE), these complex ontological queries can be compiled directly into standard recursive SQL statements. This allows them to run natively on existing relational database infrastructure.
Similarly, Georg Gottlob et al. show in Beyond SPARQL under OWL 2 QL Entailment Regime: Rules to the Rescue that advanced recursive rules can be safely executed by reducing them to linear existential Datalog under a syntactic constraint called wardedness, ensuring PTIME-complete efficiency.
Handling Expressive and Non-Horn Logics
Datalog rewriting is flexible enough to handle highly expressive logical features that go far beyond basic hierarchies:
- Inverse Roles and Number Restrictions: Thomas Eiter et al. demonstrate in Query Rewriting for Horn-SHIQ Plus Rules that complex queries over Horn-$\mathcal{SHIQ}$ ontologies can be successfully compiled into standard Datalog programs while maintaining polynomial-time data complexity.
- Disjunction and Covering Axioms: When an ontology includes "covering axioms" (e.g., stating that an employee must be either full-time or part-time), the logic becomes non-Horn. To tackle this, Olga Gerasimova et al. in On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom and David Carral et al. in Rewriting the Description Logic ALCHIQ to Disjunctive Existential Rules show that these queries can be rewritten into disjunctive Datalog, producing polynomial-sized rule sets that ensure predictable performance.
- Closed Predicates: In real-world scenarios, we often mix open-world assumptions (incomplete web data) with closed-world assumptions (complete local database tables). Shqiponja Ahmetaj et al. show in Polynomial Datalog Rewritings for Expressive Description Logics with Closed Predicates that such hybrid queries can be compiled into disjunctive Datalog with negation, offloading the hybrid reasoning to optimized rule engines.
The Theoretical Boundaries
Despite its power, Datalog rewriting faces fundamental mathematical limits. Can we build a universal compiler that automatically translates any ontology-mediated query into Datalog?
The answer is a definitive no. In Ontology-Based Query Answering over Datalog-Expressible Rule Sets is Undecidable (Extended Abstract), Lucas Larroque et al. proved that even if we know a query is theoretically expressible in Datalog, determining the answer to that query remains generally undecidable.
Because a universal algorithm is impossible, research instead focuses on structural translations. For instance, Stanislav Kikot et al. in On monotonic determinacy and rewritability for recursive queries and views introduce a forward-backward method that converts queries into Tree Automata based on treewidth bounds, translating them back into Datalog programs only when the automaton recognizes a valid rewriting.
Key Foundational Work
Practical Aspects of Query Rewriting for OWL 2 (2009) — contributed 2 concept elements to this direction.
Query Rewriting for Horn-SHIQ Plus Rules (2012) — contributed 1 concept elements to this direction.