Structural Depth Thresholds in Ontology Mediated Querying

26 concepts15 papers1 proposal

In Ontology-Based Data Access (OBDA) and Ontology-Mediated Querying (OMQ), a database is paired with an ontology containing logical rules to uncover implicit facts. To execute a query, systems often use query rewriting, translating the query and ontology into a single, comprehensive query (such as SQL or Datalog) that can be evaluated directly over the database. However, this process frequently suffers from a "size explosion," where the rewritten query grows exponentially.

What determines whether a query can be rewritten compactly or if it will explode? A cohesive body of research demonstrates that the primary driver is not the overall size of the ontology, but its structural depth—the nesting depth of quantifiers, existential dependencies, or layers of inferred objects. This depth creates sharp complexity thresholds, or "cliffs," where adding just a single layer of inference transforms highly tractable problems into intractable ones.

The Mechanism: Unrolling Layers of Inference

To understand why depth matters, consider how an ontology generates new information. An existential rule (e.g., "Every Person has a Parent who is a Person") allows a system to infer the existence of an object not explicitly named in the database. If this rule is applied repeatedly, it creates a chain of inferred entities.

The structural depth of an ontology represents the maximum number of these inferred layers that a query can explore. As shown by Vladimir Podolskii et al. in Circuit Complexity Meets Ontology-Based Data Access, the process of query rewriting is fundamentally equivalent to constructing Boolean circuits. Each layer of existential inference in the ontology corresponds to an additional layer of depth in the circuit. When the depth parameter increases, the rewritten query must account for all combinatorial paths through these layers, causing shifts into significantly higher complexity classes.

The Depth-1 vs. Depth-2 Complexity Cliff

The most dramatic manifestation of this phenomenon occurs at the boundary between "shallow" ontologies of depth 1 and depth 2.

In Query Rewriting over Shallow Ontologies, Stanislav Kikot et al. demonstrated that ontologies restricted to a single layer of existential dependencies (depth 1) allow for manageable, polynomial-sized query rewritings. However, moving to just depth 2 triggers a worst-case exponential blowup in the size of the rewritten query.

The authors expanded on this in On the succinctness of query rewriting over shallow ontologies, linking these structural bounds directly to circuit complexity. An ontology of depth 1 matches the expressive power of nondeterministic branching programs, keeping query rewriting within logarithmic space. Increasing the depth to two levels elevates the expressive capacity to match nondeterministic Boolean circuits. This minor structural change causes a sharp transition from logarithmic space to non-deterministic polynomial time (NP), meaning even simple linear queries can necessitate superpolynomial rewriting sizes (Stanislav Kikot et al., Succinctness of Query Rewriting in OWL 2 QL: The Case of Tree-like Queries).

Unbounded Depth and Infinite Inference Loops

When ontologies contain cycles of existential constraints, the structural depth effectively becomes infinite. This completely removes the performance guarantees typical of standard relational databases.

As established by Stanislav Kikot et al. in Combined Complexity of Answering Tree-like Queries in OWL 2 QL, bounding the ontology depth ensures that the combined complexity of answering tree-shaped queries remains highly tractable (falling into classes like NL or LOGCFL). However, removing these depth restrictions causes the complexity to jump upward by a step in the hierarchy, making query answering NP-hard.

The authors further demonstrated in The Complexity of Ontology-Based Data Access with OWL 2 QL and Bounded Treewidth Queries that existential cycles create infinite depth, representing a critical threshold where standard efficient reasoning techniques fail to maintain polynomial-time performance. Similarly, in existential rule languages with a finite chase, Heng Zhang et al. showed in Existential Rule Languages with Finite Chase: Complexity and Expressiveness that while data complexity remains polynomial, the combined complexity increases exponentially with every additional level of functional nesting allowed during reasoning.

The Collapse of Logical Simplification

Beyond query rewriting size, nesting depth dictates whether an ontology can be simplified into a more efficient fragment. A common optimization strategy is to rewrite a complex ontology into a "Horn" form, which guarantees polynomial-time (PTIME) query evaluation.

However, André Hernich et al. demonstrated that this capability is highly sensitive to quantifier nesting. In Horn Rewritability vs PTime Query Answering for Description Logic TBoxes and Horn-Rewritability vs PTime Query Evaluation in Ontology-Mediated Querying, the authors showed that while polynomial-time query evaluation and Horn-rewritability align perfectly for shallow structures (nesting depth of 1), this equivalence completely collapses at higher nesting depths. Beyond this threshold, an ontology may permit efficient querying but become structurally impossible to reduce to a Horn fragment, blocking standard optimization pathways. This sensitivity is also a primary driver of complexity when querying with the Guarded Fragment (André Hernich et al., Dichotomies in Ontology-Mediated Querying with the Guarded Fragment).

A Universal Driver of Complexity

This sensitivity to nesting and structural depth is not unique to description logics; it is a universal bottleneck across structured data paradigms:

Ultimately, the interaction between a query and an ontology expands the query's underlying structure—often inflating its treewidth beyond tractable limits (Carsten Lutz et al., The Complexity of Answer Counting for Ontology-Mediated Queries Based on Guarded TGDs (Extended Abstract)). By treating structural depth as a primary parameter, researchers can map out exactly where automated reasoning remains scalable and where it falls off a computational cliff.

Key Foundational Work

Containment of Nested XML Queries (2004) — contributed 1 concept elements to this direction.
Debugging Incoherent Terminologies (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_ontology_depth_complexity_60b3e222,
  title = {ontology depth complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ontology-depth-complexity/rdr_60b3e222c29f4c58b217d88242a70c9b},
  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_ontology_depth_complexity_60b3e222_v1,
  title = {ontology depth complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ontology-depth-complexity/rdr_60b3e222c29f4c58b217d88242a70c9b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake