Reducing Ontology Mediated Queries to Constraint Satisfaction Problems

16 concepts13 papers1 proposal

Ontology-Based Data Access (OBDA) allows users to query relational databases through a rich conceptual layer called an ontology. However, answering these ontology-mediated queries (OMQs) is significantly more complex than executing standard SQL queries. Because ontologies operate under the Open World Assumption—where missing data is treated as unknown rather than false—the system must reason about all possible valid states of the world.

To make OBDA practical, researchers must answer two fundamental questions: When is an OMQ computationally tractable to evaluate? And when can an OMQ be rewritten into a standard database language like SQL or Datalog? The core insight unifying this body of research is that these logical challenges can be systematically reduced to Constraint Satisfaction Problems (CSPs). By mapping logical queries to constraint networks, researchers can leverage powerful algebraic and combinatorial tools to map out the exact boundaries of query tractability and rewritability.

The Homomorphism Connection

Why does a reduction from logic to constraints work so cleanly? The connection lies in the concept of a homomorphism. Evaluating a query over a database under the constraints of an ontology can be reframed as checking whether a database instance can be mapped into a target structure that satisfies the ontology's rules.

In Non-Uniform Data Complexity of Query Answering in Description Logics, Carsten Lutz et al. demonstrated that query answering under specific description logic ontologies can be modeled as a CSP by reducing the problem to checking for a homomorphism to a finite template structure. A CSP asks whether there is an assignment of values to variables that satisfies all constraints, which is mathematically identical to finding a graph homomorphism. By establishing this link, Balder ten Cate et al. in Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP proved that OBDA, disjunctive Datalog, and CSPs share deep logical equivalences. The data complexity of evaluating an OMQ is thus fundamentally governed by the structural properties of its corresponding CSP template.

Unlocking the Complexity Dichotomy

Traditionally, computational complexity is analyzed at the level of entire logic families (e.g., "Description Logic $X$ is coNP-complete"). However, this blanket classification is often too pessimistic; many individual ontologies within a complex language remain easy to query.

By adopting a "non-uniform" approach, researchers began evaluating the complexity of individual ontologies. In The Data Complexity of Description Logic Ontologies, Carsten Lutz et al. showed that reducing query evaluation to CSPs allows the direct application of the CSP Dichotomy Theorem (formerly the Feder-Vardi Conjecture). This theorem proves that every finite CSP is either solvable in polynomial time (PTime) or is NP-complete. Applied to the co-problem of query answering, this means every individual ontology is either "easy" (PTime) or "hard" (coNP-hard), with no intermediate complexity classes.

This dichotomy provides a clear mathematical boundary. For example, André Hernich et al. used this framework in Schema.org as a Description Logic to analyze structured web data, identifying the exact structural conditions under which web schemas remain tractable to query.

Determining Rewritability via Duality

While knowing a query's complexity is valuable, the ultimate goal for database engines is rewritability: the ability to compile an OMQ directly into standard First-Order logic (FO, which corresponds to SQL) or Datalog. If a query is FO-rewritable, it can be executed efficiently by existing relational database management systems.

The CSP mapping solves the rewritability problem through combinatorial duality. In constraint satisfaction, a template exhibits tree duality if the absence of a homomorphism can be proven entirely by looking for tree-structured obstructions. In Query Rewriting Beyond DL-Lite, Carsten Lutz showed that mapping OMQ rewriting to CSPs allows researchers to use tree duality to determine whether a query can be expressed in standard database languages.

For highly expressive description logics, the translation requires intermediate meta-languages. Antti Kuusisto et al. in FO-Rewritability of Expressive Ontology-Mediated Queries and Cristina Feier et al. in Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk) demonstrated that complex queries can be transformed into monadic disjunctive Datalog programs or Monadic Monotone Existential Second-Order Logic (MMSNP). By reducing these expressive frameworks to generalized CSPs, the authors successfully transferred decidability results from constraint theory to prove exactly when an expressive ontology query can be compiled down to SQL or Datalog (see also Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics and From Conjunctive Queries to SPARQL Queries in Ontology-Mediated Querying).

Adapting to Real-World Constraints

Real-world knowledge bases often require features that go beyond standard open-world description logics, such as closed predicates, covering axioms, or concrete datatypes. The power of the CSP reduction lies in its adaptability to these variations:

  • Closed Predicates: In practice, some data is complete (e.g., a database of company employees), requiring a partial Closed World Assumption. In Ontology-Mediated Queries with Closed Predicates and The Data Complexity of Ontology-Mediated Queries with Closed Predicates, Carsten Lutz et al. showed that introducing closed predicates shifts the problem from standard CSPs to surjective CSPs, where the homomorphism must map onto the entire target domain. This mapping allows algebraic logic to predict exactly when closing a predicate causes query complexity to jump to coNP-complete.
  • Covering Axioms: When ontologies include disjunctive choices (e.g., stating that every Employee must be either FullTime or PartTime), query answering becomes more difficult. In On the Data Complexity of Ontology-Mediated Queries with a Covering Axiom, Olga Gerasimova et al. proved that answering queries with covering axioms is polynomially equivalent to solving specific classes of disjunctive CSPs, integrating these queries into the broader complexity dichotomy.
  • Datatypes: Ontologies frequently handle concrete data types like integers or rational numbers. In Query Answering in DL-Lite with Datatypes: A Non-Uniform Approach, André Hernich et al. mapped OMQs to the complement of a CSP over infinite datatype domains. This reduction provides a precise taxonomy of datatype usage, isolating the exact mathematical structures that cause a query to transition from tractable to intractable.

Key Foundational Work

Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP (2013) — contributed 2 concept elements to this direction.
Non-Uniform Data Complexity of Query Answering in Description Logics (2011) — 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_constraint_satisfaction_mapping_53f050a9,
  title = {constraint satisfaction mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constraint-satisfaction-mapping/rdr_53f050a9976841be9a2b4843f475cbbe},
  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_constraint_satisfaction_mapping_53f050a9_v1,
  title = {constraint satisfaction mapping},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constraint-satisfaction-mapping/rdr_53f050a9976841be9a2b4843f475cbbe/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