# Query Rewriting and Optimization for Ontological Databases

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2014.

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

- [Multimodal Query Suggestion with Multi-Agent Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2402.04867/) (2024)
- [Materializing Knowledge Bases via Trigger Graphs](https://mlsanity.com/paper/2102.02753/) (2021)
- [Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying](https://mlsanity.com/paper/2209.02464/) (2022)
- [Extending Sticky-Datalog+/- via Finite-Position Selection Functions: Tractability, Algorithms, and Optimization](https://mlsanity.com/paper/2108.00903/) (2021)
- [Scalable Query Answering under Uncertainty to Neuroscientific Ontological Knowledge: The NeuroLang Approach](https://mlsanity.com/paper/2202.11333/) (2022)

## Abstract (arXiv)

Ontological queries are evaluated against a knowledge base consisting of an extensional database and an ontology (i.e., a set of logical assertions and constraints which derive new intensional knowledge from the extensional database), rather than directly on the extensional database. The evaluation and optimization of such queries is an intriguing new problem for database research. In this paper, we discuss two important aspects of this problem: query rewriting and query optimization. Query rewriting consists of the compilation of an ontological query into an equivalent first-order query against the underlying extensional database. We present a novel query rewriting algorithm for rather general types of ontological constraints which is well-suited for practical implementations. In particular, we show how a conjunctive query against a knowledge base, expressed using linear and sticky existential rules, that is, members of the recently introduced Datalog+/- family of ontology languages, can be compiled into a union of conjunctive queries (UCQ) against the underlying database. Ontological query optimization, in this context, attempts to improve this rewriting process so to produce possibly small and cost-effective UCQ rewritings for an input query.