In the world of data management, there is a fundamental tension between expressiveness and efficiency. On one hand, we have ontologies—rich logical frameworks like Description Logics (DL) that allow us to model complex domain knowledge and infer missing information. On the other hand, we have relational databases (SQL), which are incredibly fast at querying massive amounts of explicit data but lack the "reasoning" capabilities of an ontology.
Ontology-Mediated Querying (OMQ) attempts to bridge this gap by allowing users to ask queries that take the ontology's rules into account. The holy grail of this field is First-Order (FO) Rewritability: the ability to transform a complex, reasoning-heavy query into a standard SQL query that can be executed directly by a traditional database engine.
The Intuition of Rewriting
Imagine you have a database of family relationships and an ontology that defines a "Grandparent" as a "Parent of a Parent." If you ask for all grandparents, a standard database might return nothing if the "Grandparent" relationship isn't explicitly stored. However, an OMQ system uses the ontology to "rewrite" your request. It transforms the query into a search for anyone who is a parent of someone who is also a parent.
As Carsten Lutz, Frank Wolter, and Meghyn Bienvenu explored in Deciding FO-Rewritability in EL, the core challenge is determining when this translation is possible. If a query can be rewritten into First-Order logic (the language of SQL), we can leverage decades of database optimization to answer it instantly.
The Complexity Trichotomy
Not every query can be simplified. Some queries require recursive reasoning that SQL simply cannot handle. Carsten Lutz and Leif Sabellek established a "trichotomy" theorem in Classifying the Complexity of Ontology-Mediated Queries in EL, showing that queries in the $\mathcal{EL}$ logic fall into three distinct buckets of difficulty:
- $AC^0$ (The SQL Zone): These queries are FO-rewritable. They are the fastest to execute because they can be turned into standard relational queries.
- NL-complete (The Datalog Zone): These queries are not FO-rewritable but can be rewritten into linear Datalog. They require a bit more power than SQL, typically involving path-like recursion.
- PTIME-complete: These are the most complex, requiring full Datalog or specialized reasoners.
This classification is powerful because it tells us exactly what kind of "engine" we need to answer a specific question.
Scaling to Expressive Logics
While simple logics like $\mathcal{EL}$ are well-understood, modern research pushes into more expressive territory. Antti Kuusisto, Cristina Feier, and Carsten Lutz showed in FO-Rewritability of Expressive Ontology-Mediated Queries that even for very complex logics, the problem of deciding if a rewriting exists remains decidable, though the computational cost to find that rewriting can be extremely high (up to 2NExpTime-complete).
Similarly, Pablo Barcelo, Andreas Pieris, and Gérald Berger have extended these boundaries to "frontier-guarded existential rules." Their work in First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries provides the theoretical limits for optimizing queries that involve complex relational dependencies.
From Theory to Synthesis
Knowing a rewriting exists is one thing; actually constructing it is another. Researchers have turned to classical logic tools to bridge this gap. David Toman 0001 and Grant E. Weddell demonstrated in First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics how concepts like Beth definability and Craig interpolation can be used to automatically synthesize these SQL rewritings.
In practice, even when the theory suggests extreme complexity, clever algorithms can make rewriting feasible. Peter Hansen developed backwards-chaining methods in Computing FO-Rewritings in EL in Practice that successfully translate complex conjunctive queries into SQL for real-world ontologies, proving that the "theoretical ceiling" doesn't always block practical progress.
Why It Works
The success of FO-rewritability rests on the idea that for many practical ontologies, the "reasoning" required is local or finite. If the influence of the ontology rules doesn't propagate infinitely or create circular dependencies that can't be unrolled, we can capture the entire logic of the ontology within the query itself. By shifting the burden from the database engine to the query compiler, we gain the ability to perform semantic reasoning at the scale of modern web databases.