The Circuit Complexity of Query Rewriting

This direction is merged into another direction: exponential query expansion, circuit complexity mapping. Its last version stays readable and citable here.

Version 1 of 18 papers17 conceptsfrozen 2026-10-04

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:

  1. Queries as Functions: A query can be viewed as a Boolean function that returns "true" if the data satisfies the query and "false" otherwise.
  2. 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.
  3. 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.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_circuit_complexity_of_query_rewritin_d180cc6b,
  title = {The Circuit Complexity of Query Rewriting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-circuit-complexity-of-query-rewriting/rdr_d180cc6bbc45499fb3152c8694cf2d6d},
  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_the_circuit_complexity_of_query_rewritin_d180cc6b_v1,
  title = {The Circuit Complexity of Query Rewriting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-circuit-complexity-of-query-rewriting/rdr_d180cc6bbc45499fb3152c8694cf2d6d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}