Mitigating Query Size Explosion in Ontology Mediated Querying

115 concepts91 papers4 proposals

Ontology-Based Data Access (OBDA) allows users to query relational databases using high-level conceptual models (ontologies) that capture domain knowledge. To execute these queries on standard relational database management systems (RDBMS), a common paradigm is query rewriting. This process compiles the semantic rules of the ontology directly into the user's query, producing a standard database query (such as SQL or Datalog) that can be evaluated over the raw data.

While theoretically elegant, query rewriting faces a severe practical bottleneck: combinatorial query size explosion. When translating high-level logical queries into executable database code, the size of the rewritten query can grow exponentially, or even triple-exponentially, relative to the input query and ontology. This text explores why this explosion happens and the structural mechanisms researchers use to mitigate it.


The Root of the Explosion: Combinatorial Expansion

To understand why rewritten queries bloat, consider how an ontology expands a simple query. Suppose a user queries a database for instances of a concept $A$. If the ontology contains rules stating that both $B$ and $C$ are sub-concepts of $A$ ($B \rightarrow A$ and $C \rightarrow A$), the rewritten query must look for $A$, $B$, or $C$.

As the query grows to include multiple variables (conjunctive queries) and the ontology deepens into complex hierarchies, this expansion multiplies combinatorially. A simple multi-join query can easily expand into a massive Union of Conjunctive Queries (UCQ) containing thousands of sub-queries.

Naive Expansion (UCQ):
Query(x) :- A(x), Y(x) 
  ├── Rule 1: B -> A, C -> A
  └── Rule 2: D -> Y, E -> Y

Resulting Flat Union:
(A AND D) OR (A AND E) OR (B AND D) OR (B AND E) OR (C AND D) OR (C AND E)

This lack of succinctness is not just a minor overhead; it represents a fundamental theoretical barrier. As shown by Lutz et al. in their work on the $\mathcal{EL}$ description logic (Deciding FO-Rewritability in EL), even when a query is theoretically rewritable into standard first-order logic (SQL), the resulting expression can experience a triple-exponential increase in size. Artale et al. observed a similar phenomenon in temporal ontology-mediated queries (First-Order Rewritability of Temporal Ontology-Mediated Queries), where long-term dependencies and periodic events trigger exponential growth that overwhelms standard database optimizers.

The problem intensifies when ontologies move beyond simple hierarchies. For instance, Gerasimova et al. demonstrated that introducing a single disjunctive "covering axiom" (e.g., stating that every element of $A$ must be either a $B$ or a $C$) causes a double-exponential size explosion in first-order rewritings (A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom).


Solution 1: Structure Sharing via Datalog

The primary reason first-order rewritings explode is that standard SQL unions force the duplication of shared subexpressions. If a query fragment is reused across multiple branches of an expansion, a flat UCQ must copy that fragment explicitly every time.

To bypass this limitation, researchers shift the target language from first-order logic to Datalog. Datalog allows for the definition of intermediate predicates, enabling structure sharing. Instead of expanding every combination into a flat union, a Datalog program can define a subexpression once and reference it multiple times, functioning similarly to a Boolean circuit with high reuse.

Structure-Sharing (Datalog):
NewPredicate1(x) :- A(x) OR B(x) OR C(x)
NewPredicate2(x) :- D(x) OR E(x) OR F(x)

Final Compact Query(x) :- NewPredicate1(x), NewPredicate2(x)

By leveraging this mechanism, Horrocks et al. developed a two-step rewriting technique for $\mathcal{EL}$ ontologies that separates the rewriting of the ontology from the user query (Small Datalog Query Rewritings for EL). This separation prevents the combinatorial mixing of query variables and ontology axioms, yielding compact, efficiently executable Datalog programs.

Similarly, Xiao et al. introduced Drewer (Practical Datalog Rewriting for Existential Rules), a system that uses graph-based structure sharing to compress rewritings for complex existential rules into succinct Datalog programs, avoiding the variable explosion that typically cripples standard execution engines.


Solution 2: The Combined Approach

When query rewriting alone cannot prevent size explosion due to the inherent complexity of the logic, an alternative paradigm is the combined approach.

Instead of shifting the entire reasoning burden onto the query, the combined approach splits the work between data preprocessing (materialization) and query filtering:

  1. Data Materialization: The database is pre-populated by evaluating a subset of the ontological rules, computing a partial "canonical model" of the data.
  2. Query Filtering: Because the data now explicitly contains some of the semantic implications, the rewritten query does not need to account for every possible logical path. The query can remain significantly smaller and simpler.

Lutz et al. pioneered this hybrid strategy to achieve linear-time query rewriting over $\mathcal{EL}$ ontologies without triggering an exponential blowup (Conjunctive Query Answering in EL using a Database System). Further expanding this paradigm, Feier and Carral extended the combined approach to highly expressive Role Safety Acyclic (RSA) ontologies (The Combined Approach to Query Answering Beyond the OWL 2 Profiles), demonstrating that strategic data materialization successfully insulates the query engine from unmanageable query bloat.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 86 papers
  2. Version 1 · 2026-10-04 · 87 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_exponential_query_expansion_d62959e8,
  title = {exponential query expansion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/exponential-query-expansion/rdr_d62959e8ecac4b219026b14f8e453f50},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_exponential_query_expansion_d62959e8_v2,
  title = {exponential query expansion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/exponential-query-expansion/rdr_d62959e8ecac4b219026b14f8e453f50/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake