Complexity Dichotomies in Ontology-Mediated Querying

26 concepts17 papers1 proposal

When evaluating queries over a database, the computational cost typically depends on the size of the data. In Ontology-Based Data Access (OBDA), this task is complicated by an ontology—a set of logical rules that allows the system to infer missing information.

Traditionally, computer scientists evaluated the difficulty of this task by looking at an entire logical language as a whole. If a language allows even a single highly complex ontology, the entire language is branded as computationally intractable (for example, coNP-hard). This worst-case perspective can be overly pessimistic. In practice, a database administrator works with one specific ontology at a time, and many real-world ontologies avoid the worst-case traps of their language.

To bridge this gap, a major research direction has shifted toward non-uniform complexity analysis. Instead of characterizing a logic family as a whole, this approach evaluates the computational difficulty at the level of individual ontologies and queries. The foundational discovery of this field is that the computational landscape does not form a smooth gradient of difficulty. Instead, it fractures into sharp, discrete buckets—a phenomenon known as a complexity dichotomy or trichotomy. Every single ontology is either highly efficient to query or fundamentally intractable, with absolutely no intermediate difficulty levels in between.

The Core Intuition: Why Dichotomies Exist

In general complexity theory, Ladner’s Theorem states that if $\text{P} \neq \text{NP}$, there must exist an infinite hierarchy of problems with intermediate difficulty between polynomial time ($\text{PTIME}$) and $\text{NP}$-complete. Why, then, do individual ontologies refuse to occupy this middle ground?

The answer lies in a deep mathematical connection to Constraint Satisfaction Problems (CSPs) and Monadic Monotone Existential Second-Order Logic (MMSNP). As established by Balder ten Cate et al. in Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP, ontology-mediated query answering can frequently be mapped directly to CSPs.

Because CSPs are known to exhibit a strict dichotomy—a breakthrough property originally conjectured by Feder and Vardi—the structural constraints of logical ontologies inherit this same clean split. When you fix the ontology and vary only the underlying data, the logical interactions either remain simple enough to resolve using standard database techniques or they form complex, interconnected constraints that immediately trigger intractability. As a result, as shown by André Hernich et al. in Dichotomies in Ontology-Mediated Querying with the Guarded Fragment, individual ontologies within theoretically hard languages remain perfectly tractable in practice, bypassing intermediate complexity gaps entirely.

The Trichotomy of EL and Database Rewritability

To understand how this works in practice, we can look at the description logic $\mathcal{EL}$, which forms the backbone of massive biomedical ontologies like SNOMED CT. In a series of papers, including Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability and A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic EL, Carsten Lutz et al. proved that every query in this space falls into exactly one of three distinct complexity classes.

What makes this trichotomy beautiful is that each complexity class corresponds precisely to how the query can be translated (or "rewritten") into a standard database language:

  1. $AC^0$ (First-Order Rewritable): The ontology and query can be compiled down into standard SQL. The execution time is independent of the database size under parallel processing, making it exceptionally scalable.
  2. $\text{NL}$-complete (Linear Datalog Rewritable): The query cannot be expressed in pure SQL but can be compiled into linear Datalog (the theoretical equivalent of linear recursion in SQL). This handles graph-like reachability problems efficiently.
  3. $\text{PTIME}$-complete (Monadic Datalog Rewritable): The query requires full, non-linear recursion to evaluate but remains solvable in polynomial time.
[ All Possible Queries in EL ]
       │
       ├─► Can be compiled to pure SQL? ────────► AC⁰ (Extremely Fast)
       │
       ├─► Requires linear recursion? ──────────► NL-complete (Graph Reachability)
       │
       └─► Requires full recursion? ────────────► PTIME-complete (Polynomial Time)

By proving that no queries exist between these boundaries, the authors provided a predictable framework for query optimization. If a query falls outside of $AC^0$, a developer knows exactly what kind of recursive database engine is required to execute it.

Robustness Across Hybrid and Uncertain Worlds

This non-uniform dichotomy paradigm is not a quirk of simple description logics; it is a robust property that holds even when databases are extended with real-world complexities.

Open vs. Closed Worlds

Traditional ontology querying operates under the Open World Assumption (OWA), meaning missing data is treated as unknown. Real-world applications, however, often require a hybrid approach where some predicates are known to be complete (the Closed World Assumption). In Mixing Open and Closed World Assumptionin Ontology-Based Data Access: Non-Uniform Data Complexity and The Data Complexity of Ontology-Mediated Queries with Closed Predicates, the authors demonstrated that introducing closed predicates causes a sharp, binary transition. Query answering remains either highly efficient or immediately jumps to $\text{coNP}$-complete, with no middle ground.

Concrete Datatypes and Web Schemas

When ontologies incorporate concrete data types like numerical ranges or linear orders on rational numbers, the same behavior emerges. André Hernich et al. demonstrated in Query Answering in DL-Lite with Datatypes: A Non-Uniform Approach that datatype constraints split cleanly into tractable and intractable categories based on their algebraic properties. This mathematical boundary also governs web-scale semantic frameworks like Schema.org, where queries either scale seamlessly using standard database engines or hit severe performance bottlenecks (André Hernich et al., Schema.org as a Description Logic).

Probabilistic Data

Even when data is uncertain or noisy, the non-uniform lens reveals a clean divide. In Ontology-Based Access to Probabilistic Data, Carsten Lutz et al. proved that computing exact answer probabilities over probabilistic databases bypasses intermediate difficulties entirely. The problem is either solvable in polynomial time ($\text{PTIME}$) or is fundamentally intractable ($\text{\#P}$-hard).

Summary

Non-uniform complexity analysis changes how we evaluate the feasibility of semantic technologies. By shifting the focus from the worst-case limits of an entire language to the structural properties of individual ontologies, this line of research proves that the computational world is largely binary. For practitioners, these dichotomy and trichotomy theorems guarantee that query optimization is a predictable science: queries will either yield to elegant database rewritings or demand specialized, heavy-duty solvers, with no unexpected complexities lurking in between.

Key Foundational Work

Mixing Open and Closed World Assumptionin Ontology-Based Data Access: Non-Uniform Data Complexity (2012) — contributed 2 concept elements to this direction.
Non-Uniform Data Complexity of Query Answering in Description Logics (2011) — contributed 2 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_complexity_dichotomy_e788fca8,
  title = {complexity dichotomy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/complexity-dichotomy/rdr_e788fca8acbe4382bbc50ea762e5d4d5},
  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_complexity_dichotomy_e788fca8_v1,
  title = {complexity dichotomy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/complexity-dichotomy/rdr_e788fca8acbe4382bbc50ea762e5d4d5/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