Datalog Rewriting for Ontology Mediated Queries

18 concepts13 papers

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:

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.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 12 papers
  2. Version 1 · 2026-10-04 · 16 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_datalog_based_query_rewriting_fe96105f,
  title = {datalog-based query rewriting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/datalog-based-query-rewriting/rdr_fe96105f9bf74deda5fce239cf5f05eb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_datalog_based_query_rewriting_fe96105f_v2,
  title = {datalog-based query rewriting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/datalog-based-query-rewriting/rdr_fe96105f9bf74deda5fce239cf5f05eb/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake