# Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP

arXiv: https://arxiv.org/abs/1301.6479 · HTML: https://mlsanity.com/paper/1301.6479/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2013.

## Built on by (most cited first, 15 of 15)

- [Frontiers and Exact Learning of ELI Queries under DL-Lite Ontologies](https://mlsanity.com/paper/2204.14172/) (2022)
- [How to Approximate Ontology-Mediated Queries](https://mlsanity.com/paper/2107.05369/) (2021)
- [Fitting Description Logic Ontologies to ABox and Query Examples](https://mlsanity.com/paper/2508.08007/) (2025)
- [Cybonto: Towards Human Cognitive Digital Twins for Cybersecurity](https://mlsanity.com/paper/2108.00551/) (2021)
- [Characterizing the Program Expressive Power of Existential Rule Languages](https://mlsanity.com/paper/2112.08136/) (2021)
- [Query Rewriting with Disjunctive Existential Rules and Mappings](https://mlsanity.com/paper/2306.05973/) (2023)
- [Current and Future Challenges in Knowledge Representation and Reasoning](https://mlsanity.com/paper/2308.04161/) (2023)
- [Towards Consistent Language Models Using Declarative Constraints](https://mlsanity.com/paper/2312.15472/) (2023)
- [On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)](https://mlsanity.com/paper/2501.13762/) (2025)
- [Characterising Fixed Parameter Tractability of Query Evaluation over Guarded TGDs](https://mlsanity.com/paper/2101.11727/) (2021)
- [Conservative Extensions for Existential Rules](https://mlsanity.com/paper/2202.05689/) (2022)
- [Ontology-Mediated Querying on Databases of Bounded Cliquewidth](https://mlsanity.com/paper/2205.02190/) (2022)
- [Decidability of Querying First-Order Theories via Countermodels of Finite Width](https://mlsanity.com/paper/2304.06348/) (2023)
- [Description Logics with Abstraction and Refinement](https://mlsanity.com/paper/2306.03717/) (2023)
- [Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology](https://mlsanity.com/paper/2306.07662/) (2023)

## Abstract (arXiv)

Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database query coupled with an ontology. In this paper, we study several classes of ontology-mediated queries, where the database queries are given as some form of conjunctive query and the ontologies are formulated in description logics or other relevant fragments of first-order logic, such as the guarded fragment and the unary-negation fragment. The contributions of the paper are three-fold. First, we characterize the expressive power of ontology-mediated queries in terms of fragments of disjunctive datalog. Second, we establish intimate connections between ontology-mediated queries and constraint satisfaction problems (CSPs) and their logical generalization, MMSNP formulas. Third, we exploit these connections to obtain new results regarding (i) first-order rewritability and datalog-rewritability of ontology-mediated queries, (ii) P/NP dichotomies for ontology-mediated queries, and (iii) the query containment problem for ontology-mediated queries.