# Sound, Complete and Minimal UCQ-Rewriting for Existential Rules

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2013.

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

- [Parallelisable Existential Rules: a Story of Pieces](https://mlsanity.com/paper/2107.06054/) (2021)
- [Query Rewriting with Disjunctive Existential Rules and Mappings](https://mlsanity.com/paper/2306.05973/) (2023)
- [Normalisations of Existential Rules: Not so Innocuous!](https://mlsanity.com/paper/2206.03124/) (2022)
- [Consistent Query Answering for Existential Rules with Closed Predicates](https://mlsanity.com/paper/2401.05743/) (2024)
- [Controlled Query Evaluation through Epistemic Dependencies](https://mlsanity.com/paper/2405.02458/) (2024)
- [The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules](https://mlsanity.com/paper/2407.14384/) (2024)
- [CQE under Epistemic Dependencies: Algorithms and Experiments (extended version)](https://mlsanity.com/paper/2507.17487/) (2025)
- [Abstractions of Queries in Ontology-Based Data Access](https://mlsanity.com/paper/2606.24618/) (2026)

## Abstract (arXiv)

We address the issue of Ontology-Based Data Access, with ontologies represented in the framework of existential rules, also known as Datalog+/-. A well-known approach involves rewriting the query using ontological knowledge. We focus here on the basic rewriting technique which consists of rewriting the initial query into a union of conjunctive queries. First, we study a generic breadth-first rewriting algorithm, which takes as input any rewriting operator, and define properties of rewriting operators that ensure the correctness of the algorithm. Then, we focus on piece-unifiers, which provide a rewriting operator with the desired properties. Finally, we propose an implementation of this framework and report some experiments.