In modern data management, we often want to query relational databases not just for the raw facts they contain, but for the logical implications of those facts. This paradigm, known as Ontology-Based Data Access (OBDA), pairs a database with an ontology—a set of logical rules or description logic axioms that define relationships within a domain.
When a user executes an ontology-mediated query (OMQ), a naive system would have to use a heavy-duty semantic reasoner at runtime to compute all logical implications. This does not scale to massive datasets. The ideal alternative is First-Order (FO) rewritability: compiling the ontology's rules directly into the query itself, transforming it into a standard First-Order logic query (i.e., standard SQL). If a query is FO-rewritable, we can hand it off to a traditional, highly optimized relational database engine and get the correct answers instantly.
However, not every ontology-mediated query can be flattened into SQL. Some rules introduce recursive dependencies or open-world disjunctions that standard SQL cannot natively express. This creates a critical meta-problem: How do we decide whether a given ontology-mediated query is FO-rewritable?
The Computational Toll of Optimization
Before an optimizer can rewrite a query, it must first determine if a valid rewriting even exists. This decision problem is a massive computational bottleneck, often dwarfing the complexity of standard query evaluation. The difficulty depends entirely on the expressiveness of the underlying description logic and the constraints placed on the database vocabulary.
For simpler description logics like $\mathcal{EL}$ (the logic underpinning large biomedical ontologies like SNOMED CT), Carsten Lutz et al. demonstrated in Deciding FO-Rewritability in EL that the complexity of this decision hinges on the data signature—the set of allowed symbols in the database. If the signature is unrestricted, deciding rewritability is PSPACE-complete. If the signature is fixed and restricted, the problem escalates to EXPTIME-complete. To make this check viable in practice, Carsten Lutz et al. later designed a structure-sharing decomposed algorithm in Query Rewriting under EL TBoxes: Efficient Algorithms to bypass brute-force bottlenecks.
When moving to highly expressive description logics like the $\mathcal{ALC}$ family, which allows full negation and disjunction, the complexity explodes. Antti Kuusisto et al. proved in FO-Rewritability of Expressive Ontology-Mediated Queries that deciding FO-rewritability for these logics is 2NEXPTIME-complete.
Ontology Expressiveness & Decision Complexity
[ Simple Horn Logics (e.g., EL) ] ---------> PSPACE / EXPTIME-complete
[ Expressive Logics (e.g., ALC) ] ---------> 2NEXPTIME-complete
As Cristina Feier et al. detailed in Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics, this extreme complexity jump occurs because moving from simple atomic queries to unions of conjunctive queries forces the decision procedure to evaluate an exponential combination of relational interactions across hypothetical database states.
What Makes a Query Non-Rewritable?
To understand why deciding rewritability is so difficult, we have to look at the semantic mechanisms that break first-order logic: unbounded recursion and disjunctive uncertainty.
Unbounded Recursion and Boundedness
First-order logic can look down a path of fixed length, but it cannot track paths of arbitrary, unknown lengths (which requires recursion, like Datalog or SQL's WITH RECURSIVE). If an ontology contains recursive rules, it is only FO-rewritable if it is bounded—meaning the recursion always terminates within a fixed number of steps regardless of the data.
Stanislav Kikot et al. settled a long-standing open question in database theory in Deciding boundedness of monadic sirups by proving that deciding the boundedness of even a monadic single-rule datalog program (a sirup) is 2EXPTIME-hard. This shows that even the simplest recursive structures can mimic highly complex Turing machines, making it incredibly difficult to detect when recursion can be safely flattened.
Disjunctive Uncertainty and the Covering Axiom
When an ontology includes a "covering axiom" (for example, stating that every Patient must be either Inpatient or Outpatient), it introduces disjunction. This forces the query processor to reason about multiple parallel possibilities.
Olga Gerasimova et al. isolated this behavior in A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom, showing that disjunction drives the complexity of deciding rewritability to 2EXPTIME-hardness. However, by analyzing the precise syntactic structure of how these queries interact with the covering axiom, the authors established a complete tetrachotomy in A tetrachotomy of ontology-mediated queries with a covering axiom. They proved that every such query falls into one of four distinct data complexity classes: $AC^0$ (fully FO-rewritable), $NL$, $P$, or $coNP$-complete.
The Mechanics of Deciding Rewritability
To establish these boundaries and build automated optimizers, researchers rely on three primary theoretical bridges: Constraint Satisfaction Problems, Cost Automata, and Proof-Theoretic Interpolation.
1. The Combinatorial Bridge: CSPs and MMSNP
One of the most powerful tools for analyzing query rewritability is translating the problem into a Constraint Satisfaction Problem (CSP) or its logical equivalent, Monadic Monotone SNP (MMSNP).
In Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP, Balder ten Cate et al. proved that many expressive ontology-mediated queries are completely equivalent to the complements of MMSNP sentences. This connection allows researchers to use combinatorial graph-coloring and homomorphism techniques to determine rewritability. For instance, Pierre Bourhis leveraged this framework in Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics to prove that query containment and rewritability share the same 2NEXPTIME-complete complexity ceiling, because both fundamentally validate whether a database instance can be mapped into a forbidden canonical structure.
2. The Automata Bridge: Cost Automata
For frontier-guarded queries—where logical rules can span multiple variables but are constrained by a "guard" atom—traditional tree automata fail because database graphs can contain complex cycles.
To solve this, Pablo Barcelo et al. turned to cost automata in First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries. Instead of simply accepting or rejecting a tree structure, a cost automaton counts resources—in this case, tracking the depth of the logical dependencies generated by the ontology rules. If the counter remains bounded across all valid database trees, the query is FO-rewritable. This technique successfully pinned the decision complexity for frontier-guarded queries at 2EXPTIME-complete.
3. The Proof-Theoretic Bridge: Beth Definability
Instead of using combinatorial structures or automata, one can look directly at the properties of classical logic. If a concept is FO-rewritable, it means the ontology implicitly defines the query predicates using only the explicit database vocabulary.
In First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics, David Toman 0001 and Grant E. Weddell combined Beth definability and Craig interpolation to analyze Horn description logics.
[Implicit Definition via Ontology]
│
▼ (Beth Definability Theorem)
[Explicit First-Order Formula] ───(Craig Interpolation)───► [Synthesized SQL Query]
By constructing a interpolant between the query and the ontology's background constraints, their framework does not just abstractly decide if a first-order rewriting exists within EXPTIME; it constructively extracts the exact SQL query required for database execution.
Key Foundational Work
Deciding FO-Rewritability in EL (2012) — contributed 1 concept elements to this direction.
SPARQL Query Containment Under SHI Axioms (2012) — contributed 1 concept elements to this direction.
Rewriting queries using views in the presence of arithmetic comparisons (2006) — contributed 1 concept elements to this direction.