Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP

Meghyn Bienvenu, Balder ten Cate, Carsten Lutz, Frank Wolter

Introduction

Ontology-Based Data Access (OBDA) has emerged as a paradigm-shifting approach to managing large-scale, heterogeneous, and incomplete data. By overlaying a conceptual layer—an ontology—on top of existing data sources, OBDA allows users to query information using a high-level vocabulary without needing to understand the underlying physical schemas. This paper provides a rigorous theoretical exploration of OBDA, establishing deep connections between Description Logics (DLs), Disjunctive Datalog, and Constraint Satisfaction Problems (CSPs).

Problem Statement: The Complexity of Incompleteness

The primary challenge in OBDA is the "Open World Assumption." Unlike traditional databases where missing information is assumed to be false, OBDA systems must account for what could be true based on the ontology's rules. This makes evaluating Ontology-Mediated Queries (OMQs) computationally demanding, often reaching coNP-complete data complexity.

Researchers seek to answer three fundamental questions:

  1. How can we characterize the expressive power of OMQs using established logic programming languages?
  2. Can we identify a "dichotomy" that separates "easy" (PTIME) queries from "hard" (coNP-hard) ones?
  3. Under what conditions can a complex OMQ be "rewritten" into a standard SQL query (First-Order rewritability)?

Theoretical Foundations

The study focuses on Description Logics (DLs), which are formal languages used to define ontologies. These languages are essentially fragments of First-Order Logic (FOL) designed to balance expressivity and decidability.

Examples of logical formulas in First-Order Logic (left) and their equivalent Description Logic syntax (right).

As shown in Figure 1, DLs use a concise syntax to represent complex relationships. For instance, the rule that a finding of Erythema Migrans implies a diagnosis of Lyme Disease can be expressed as a simple inclusion axiom ($\sqsubseteq$). The paper investigates how these axioms interact with query languages like Unions of Conjunctive Queries (UCQs).

Methods: Building Logical Bridges

The authors employ a translation-based approach to link disparate fields:

  • Monadic Disjunctive Datalog (MDDlog): The paper proves that for the common logic $\mathcal{ALC}$, OMQs have the same expressive power as MDDlog. This allows for the compilation of ontologies into logic programs.
  • Constraint Satisfaction Problems (CSPs): By mapping OBDA to CSPs, the authors leverage the Feder-Vardi dichotomy conjecture. This mapping reveals that the difficulty of answering a query is often tied to the structural properties of the constraints defined in the ontology.
  • Guarded Fragments: For more expressive ontologies, the authors introduce GMSNP (Guarded Monadic SNP), a logic that captures the power of queries mediated by the Guarded Fragment (GF) of FOL.

Key Results and Insights

The research yields several landmark results in database theory:

  • Expressivity Equivalence: It is formally established that $(\mathcal{ALC}, UCQ)$ is equivalent to MDDlog, and $(GF, UCQ)$ is equivalent to frontier-guarded disjunctive datalog.
  • Complexity Dichotomies: The paper demonstrates that for many OBDA languages, query evaluation follows a PTIME/coNP dichotomy. This means there are no "intermediate" complexity levels; a query is either efficiently solvable or inherently difficult.
  • Decidability and Rewritability: The authors prove that determining the containment of one OMQ within another is decidable for major logic fragments. However, they also identify a "danger zone": adding functional roles (e.g., "each person has exactly one SSN") makes the problem of determining SQL-rewritability undecidable.
  • Rewritability Complexity: Deciding if an $\mathcal{ALC}$-based query can be simplified into SQL or standard Datalog is shown to be NEXPTIME-complete.

Conclusion and Future Directions

This study provides a comprehensive map of the landscape of Ontology-Mediated Queries. By proving the equivalence between DLs, Datalog, and CSPs, it offers a unified framework for understanding query complexity.

Despite these advances, challenges remain. The current characterizations focus heavily on UCQs; extending these results to standard Conjunctive Queries (CQs) is a significant open problem. Furthermore, while the theoretical foundations for translation are now solid, developing optimized, production-ready algorithms to perform these rewritings in real-time remains a critical goal for the OBDA community.

Summary updated

BibTeX
@article{bienvenu2014ontology,
  author = {Meghyn Bienvenu and Balder ten Cate and Carsten Lutz and Frank Wolter},
  title = {{Ontology-based data access: a study through disjunctive datalog, CSP, and MMSNP}},
  journal = {ACM Trans. Database Syst.},
  year = {2014},
  doi = {10.1145/2661643},
}
Figure