In Ontology-Based Data Access (OBDA), users query a database through the lens of an ontology—a set of logical rules that describe a domain and allow the system to infer missing information. To evaluate these queries using standard database engines, a common strategy is query rewriting: compiling the query and the ontology together into a single, expanded query (written in a language like SQL or Datalog) that can be executed directly against the raw data.
However, these rewritings often suffer from a massive "size explosion." Why do some ontologies allow compact, polynomial-sized rewritings, while others force an exponential blow-up?
To answer this, a powerful research direction bridges database theory and structural complexity theory. By establishing a formal isomorphism between query rewriting and Boolean circuit construction, researchers can use established lower bounds from circuit theory to determine the exact limits of logical expressivity.
The Isomorphism: Queries as Circuits
To understand why this connection works, think of a database as a vector of Boolean inputs. Each position in the vector indicates whether a specific fact (such as Teaches(Alice, ComputerScience)) is present or absent in the database.
An ontology-mediated query is fundamentally a Boolean function that maps this input vector to a single output: True if the data and the ontology together satisfy the query, and False otherwise. When we rewrite a query into a target database language, we are constructing a program to compute this Boolean function.
As demonstrated by Podolskii et al., different target query languages map directly to specific classes of Boolean circuits:
- First-Order (FO) rewritings (the theoretical equivalent of standard SQL queries) correspond to shallow Boolean formulas or circuits of bounded depth ($NC^1$).
- Datalog rewritings (which allow recursive rules) correspond to monotone Boolean circuits. They are strictly monotone because Datalog lacks negation; adding new facts to a database can never cause a previously true query answer to become false.
By framing query rewriting as circuit construction, the size and depth of a rewritten query become fundamentally bounded by the minimum circuit complexity required to compute that underlying Boolean function.
Translating Circuit Lower Bounds to Query Sizes
This mapping allows researchers to import powerful lower-bound techniques from circuit complexity to prove exactly when and why query rewritings must explode in size.
For instance, Kikot et al. proved that query rewritings in the standard web ontology language OWL 2 QL can suffer from an unavoidable exponential size blow-up. They achieved this by constructing specific ontologies where answering a query is mathematically equivalent to solving a known hard problem in circuit theory, such as determining the existence of a graph clique. Because computing a clique requires exponentially large monotone circuits, the corresponding logical rewriting must be exponentially large.
Using a similar reduction, Kikot et al. distinguished between "pure" rewritings and "impure" rewritings (which are allowed to introduce new constants). While pure rewritings face exponential blow-ups, the authors demonstrated that real-world ontologies often lack the complex structural features ("twisty roles") that trigger these worst-case circuit bounds, explaining why query rewriting remains highly viable in practice.
The Monotonicity Constraint of Datalog
The circuit perspective is equally powerful for understanding recursive query languages like Datalog. Because Datalog rules cannot express negation, its reasoning power is strictly constrained by the limitations of monotone circuits.
Cuenca Grau et al. leveraged this constraint to show that certain highly expressive "non-Horn" ontologies cannot be rewritten into Datalog. Because Datalog lacks the non-monotone mechanisms required to handle specific types of logical proofs (such as reasoning by cases), it is structurally incapable of capturing these ontologies. Crucially, this impossibility persists even under the assumption that $P = NP$, because the barrier is structural rather than purely computational.
Similarly, Rudolph et al. settled a long-standing question about Datalog's expressivity limits by reducing query evaluation to monotone circuits. The authors proved that even if Datalog is enhanced with an order-invariant mechanism, it still cannot capture all polynomial-time monotonic queries. If a query's evaluation inherently requires a super-polynomial monotone circuit, Datalog simply lacks the structural capacity to express it.
Equivalence to Deep Open Problems
Perhaps the most striking consequence of this research direction is that determining the exact limits of query rewriting is often mathematically equivalent to resolving some of the deepest, unsolved problems in computer science.
When analyzing "shallow" ontologies (which contain very short chains of implications), Kikot et al. demonstrated that deciding whether polynomial-sized first-order rewritings always exist is equivalent to proving whether the complexity class $NL/poly$ is contained within $NC^1$ (a major open question regarding non-deterministic log-space versus shallow circuits).
Subsequent work by Kikot et al., Kikot et al., and Kikot et al. mapped out a comprehensive "succinctness landscape" for various query shapes (such as tree-like queries). They showed that the existence of compact rewritings hinges directly on containment relationships between complexity classes like $NP/poly$, $SAC^1$, and $NC^1$.
This means that finding a universal, efficient way to rewrite queries isn't just an engineering challenge—it is fundamentally bounded by the same structural limits that separate the core complexity classes of theoretical computer science.
Key Foundational Work
Computing Datalog Rewritings beyond Horn Ontologies (2013) — contributed 3 concept elements to this direction.
Exponential Lower Bounds and Separation for Query Rewriting (2012) — contributed 2 concept elements to this direction.
Long Rewritings, Short Rewritings (2012) — contributed 1 concept elements to this direction.