In the paradigm of Ontology-Based Data Access (OBDA), we treat a database not just as a collection of tables, but as a window into a richer conceptual world. When a user asks a question, the system uses an ontology (a set of logical rules) to "fill in the blanks" of the underlying data.
The most common way to implement this is through query rewriting. Instead of modifying the data, we modify the query. We take a simple Conjunctive Query (CQ) and the ontology, then transform them into a new, expanded query—usually in SQL or Datalog—that can be executed directly by a standard database engine.
The fundamental challenge, explored extensively by researchers like Stanislav Kikot, Vladimir Podolskii, and Michael Zakharyaschev, is succinctness: how large does that rewritten query need to be?
The Explosion of Pure Rewritings
Intuitively, an ontology adds "hidden" ways to satisfy a query. If an ontology says "Every Professor is a Teacher," a query for "Teachers" must be rewritten to look for both "Teachers" and "Professors." As the ontology grows more complex, the number of these combinations can explode.
In Long Rewritings, Short Rewritings, the authors identify a critical distinction between "pure" and "impure" rewritings. A pure rewriting uses only the symbols found in the original query and the ontology. The authors proved that for certain ontologies in OWL 2 QL (a standard language for OBDA), pure rewritings inevitably suffer from an exponential blow-up in size.
However, if we allow impure rewritings—which introduce new constants or use more powerful target languages like Datalog—we can often keep the query size polynomial. This suggests that the "size" of a query is not just a matter of string length, but a reflection of the computational work required to resolve the logic.
Mapping Logic to Boolean Circuits
To understand why some queries stay small while others explode, Kikot, Podolskii, and Meghyn Bienvenu established a formal bridge between mathematical logic and Boolean circuit complexity.
The intuition is as follows:
- Queries as Functions: A query can be viewed as a Boolean function that returns "true" if the data satisfies the query and "false" otherwise.
- Rewritings as Circuits: A rewritten query is essentially a recipe for computing that function. The size of the query corresponds to the size of a Boolean circuit (a network of AND/OR gates) needed to evaluate it.
- The Complexity Link: By translating logical entailment into hypergraph programs, as shown in On the Succinctness of Query Rewriting over OWL 2 QL Ontologies with Shallow Chases, researchers can apply decades of results from circuit theory to database queries.
This mapping reveals that the limits of query optimization are not just engineering hurdles; they are tied to deep, unsolved problems in computer science.
The Frontiers of Succinctness
The research demonstrates that the existence of polynomial-sized rewritings for certain classes of tree-like queries is equivalent to proving specific relationships between complexity classes, such as whether NL/poly is contained within NC1 (Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries).
In simpler terms, if we could always find a small, efficient way to rewrite these queries, we would simultaneously solve major open questions about the power of parallel computation. This "succinctness landscape" tells us that for some ontologies, an exponential blow-up is mathematically mandatory unless a fundamental breakthrough in complexity theory occurs.
Why It Works in Practice
If the theoretical worst-case is so bleak, why does OBDA work at all? Roman Kontchakov and colleagues point out in Ontology-Mediated Queries: Combined Complexity and Succinctness of Rewritings via Circuit Complexity that real-world ontologies rarely trigger these worst-case scenarios.
The exponential blow-up often requires "twisty roles"—complex, recursive relationships that are common in theoretical proofs but rare in practical data modeling. Most practical ontologies have "shallow chases," meaning the logical implications don't chain together in the infinitely complex ways required to force a massive query. By understanding the circuit complexity of these structures, researchers can design optimizers that navigate the boundary between what is theoretically possible and what is practically efficient.