Complexity Dichotomies in Ontology Mediated Querying

This direction is split into other directions: constraint satisfaction mapping, complexity dichotomy. Its last version stays readable and citable here.

Version 1 of 144 papers64 conceptsfrozen 2026-10-04

In computational complexity theory, we often expect a smooth spectrum of difficulty. Ladner’s Theorem famously suggests that if $P \neq NP$, there must exist an infinite hierarchy of problems with intermediate complexity—tasks that are harder than polynomial time but not quite NP-complete.

However, in the specialized world of database theory and description logics, this spectrum often collapses. Researchers have discovered that for many classes of queries, a "dichotomy" (or sometimes a "trichotomy") exists: a query is either extremely efficient to solve or fundamentally intractable, with no middle ground. This phenomenon allows us to draw a sharp "tractability frontier," identifying exactly which logical constraints and data structures make information retrieval scale.

The Shift to Non-Uniform Complexity

Traditionally, researchers classified the complexity of an entire logic family (e.g., "Querying in OWL 2 QL is in PTime"). However, this "uniform" approach can be misleadingly pessimistic. Even if a logic is hard in the worst case, many individual ontologies within that logic might be easy to query.

Carsten Lutz and Frank Wolter pioneered a "non-uniform" approach in Non-Uniform Data Complexity of Query Answering in Description Logics. Instead of asking how hard a logic is, they ask: for a specific ontology, how hard is it to answer a query? They proved that for several description logics, every single ontology is either solvable in polynomial time or is coNP-complete. This binary landscape simplifies optimization, as it guarantees that any query not hitting a specific "hard" structural pattern will remain efficient.

The Trichotomy of EL Ontologies

The description logic $\mathcal{EL}$ is widely used in biomedical ontologies (like SNOMED CT) because it balances expressivity with efficiency. In Ontology-Mediated Querying with the Description Logic EL: Trichotomy and Linear Datalog Rewritability, Carsten Lutz and Leif Sabellek established a three-tiered landscape for these queries:

  1. $AC^0$: The query is "FO-rewritable," meaning it can be translated into standard SQL and executed extremely fast.
  2. NL-complete: The query requires "linear Datalog" (recursive SQL) to solve.
  3. PTime-complete: The query requires full Datalog or general polynomial-time algorithms.

Crucially, they showed there are no gaps between these levels. This trichotomy provides a definitive map for query engines, telling developers exactly which "language" (SQL vs. Datalog) is required to get the right answer.

Probabilistic Data and the #P-Hard Frontier

The dichotomy phenomenon extends beyond logic into the realm of uncertain data. In probabilistic databases, we don't just want to know if an answer exists; we want to know the probability that it is true.

Carsten Lutz and Jean Christoph Jung demonstrated in Ontology-Based Access to Probabilistic Data with OWL QL that this task follows a sharp dichotomy between PTime and #P-hardness. This boundary is often determined by the "hierarchical" structure of the query. If a query can be decomposed into a simple tree-like structure, the probability can be computed efficiently. If it contains "cycles" or complex overlaps, the problem becomes as hard as counting all possible satisfying assignments to a logic formula.

Interestingly, Ismail Ilkan Ceylan, Adnan Darwiche, and Guy Van den Broeck found that this dichotomy persists even when moving from a "closed-world" to an "open-world" assumption in Open-World Probabilistic Databases. The inherent difficulty of the query structure is a property of the logic itself, regardless of whether we assume missing data is false or merely unknown.

Why Structure Dictates Complexity

Why do these dichotomies exist? The answer usually lies in the structural properties of the query and the ontology, often viewed through the lens of graph theory.

  • Tree-width and Hypertree-width: Queries that look like trees (or can be thickened into trees) are generally tractable. Hubie Chen has shown that for counting answers or learning queries, the boundary of tractability is often defined by algebraic properties like "congruence modularity" or structural metrics like "domination width" (The tractability frontier of well-designed SPARQL queries).
  • Guardedness: In the "Guarded Fragment" of first-order logic, complexity is kept in check because quantifiers are "guarded" by atoms. André Hernich and colleagues showed in Dichotomies in Ontology-Mediated Querying with the Guarded Fragment that this guarding mechanism creates a clear split between PTime and NP-hard instances.

Practical Implications

While these results are theoretical, they have profound practical consequences. Jörg Schönfisch analyzed over a million real-world SPARQL queries in Analyzing real-world SPARQL queries in the light of probabilistic data and found that 99.7% of them fall on the "safe" side of the dichotomy.

By identifying the exact mathematical features that trigger intractability—such as "closed roles" in an ontology (Ontology-Mediated Queries with Closed Predicates) or specific "covering axioms"—researchers provide a roadmap for building database systems that are both expressive and reliably fast.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_complexity_dichotomies_in_ontology_media_67ba0e60,
  title = {Complexity Dichotomies in Ontology Mediated Querying},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/complexity-dichotomies-in-ontology-mediated-querying/rdr_67ba0e60e9a248859a106bd79afa8ddb},
  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_dichotomies_in_ontology_media_67ba0e60_v1,
  title = {Complexity Dichotomies in Ontology Mediated Querying},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/complexity-dichotomies-in-ontology-mediated-querying/rdr_67ba0e60e9a248859a106bd79afa8ddb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}