Recursive Query Rewriting for Expressive Ontologies

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 216 papers21 conceptsfrozen 2026-10-04

In modern data management, we often face a gap between how data is stored (flat relational tables) and how we think about it (rich hierarchies and logical rules). Ontology-Mediated Query Answering (OMQA) attempts to bridge this gap by allowing users to query data through a conceptual lens—an ontology.

The challenge is execution. If you ask a database for all "Employees," but the ontology knows that "Managers" and "Interns" are also "Employees," the system must account for those rules. The most efficient way to do this is Query Rewriting: transforming the high-level query and the ontology into a single, complex query that a standard database engine can execute directly.

The Limits of Simple Rewriting

For simple ontologies, like those in the OWL 2 QL profile, we can rewrite a query into a Union of Conjunctive Queries (UCQ)—essentially a large set of SELECT statements joined by UNION. However, as Héctor Pérez-Urbina, Ian Horrocks, and Boris Motik demonstrate in Practical Aspects of Query Rewriting for OWL 2, this approach hits a wall when ontologies become more expressive.

When rules involve recursion (e.g., "the ancestor of a parent is an ancestor") or existential constraints, the number of UNION clauses needed can explode exponentially. To handle more complex logic—like the transitive roles and number restrictions found in Horn-SHIQ—researchers like Thomas Eiter and Mantas Simkus argue in Query Rewriting for Horn-SHIQ Plus Rules that we must move beyond simple SQL to Datalog.

Datalog as a Compact Bridge

Datalog is a rule-based language that naturally supports recursion. By rewriting an ontology-mediated query into a Datalog program rather than a UCQ, we gain two major advantages:

  1. Compactness: Instead of listing every possible combination of subclasses, we can define recursive rules. Peng Xiao and Kewen Wang show in Practical Datalog Rewriting for Existential Rules that Datalog rewritings are significantly smaller and more manageable for standard engines.
  2. Expressivity: Datalog can handle "covering axioms" (e.g., an Employee must be either FullTime or PartTime) and complex role hierarchies that are impossible to express in basic SQL. Olga Gerasimova and Michael Zakharyaschev explore this in On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom, showing how recursive Datalog maintains efficiency even when the logic gets "heavy."

From Theory to SQL Recursion

The ultimate goal is to run these queries on existing Relational Database Management Systems (RDBMS). Modern SQL supports a feature called WITH RECURSIVE, which is a limited form of Datalog.

A breakthrough in this area comes from Carsten Lutz and Leif Sabellek. In Ontology-Mediated Querying with EL: Trichotomy and Linear Datalog Rewritability, they identify a "trichotomy" of complexity. They prove that queries falling into the NL (Nondeterministic Logspace) complexity class are exactly those that can be rewritten into Linear Datalog.

Linear Datalog is the theoretical equivalent of SQL's linear recursion. This means that for a large class of ontologies (like the $\mathcal{EL}$ family used in medical terminologies), we can "compile" the logic into standard recursive SQL that runs on any modern database. This isn't just for ontologies; Dimitrije Jankov and Christopher Jermaine demonstrate in Declarative Recursive Computation on an RDBMS that this same recursive unrolling can even power distributed machine learning within a database.

The Boundaries of Rewritability

While Datalog rewriting is powerful, it is not a universal solvent. Lucas Larroque and David Carral recently proved in Ontology-Based Query Answering over Datalog-Expressible Rule Sets is Undecidable that we cannot create a general-purpose algorithm to decide if any given query is Datalog-rewritable.

Instead, the field focuses on identifying specific "safe" fragments—like the "warded" rules proposed by Georg Gottlob and Andreas Pieris in Beyond SPARQL under OWL 2 QL Entailment Regime—where we can guarantee that complex, recursive reasoning will always be transformable into a format that our existing database infrastructure can handle efficiently.

Papers in this version

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 1, frozen text):

@misc{lacuna_recursive_query_rewriting_for_expressive_fe96105f_v1,
  title = {Recursive Query Rewriting for Expressive Ontologies},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-query-rewriting-for-expressive-ontologies/rdr_fe96105f9bf74deda5fce239cf5f05eb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}