# Query Rewriting with Disjunctive Existential Rules and Mappings

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 47 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 4 of 4)

- [Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP](https://mlsanity.com/paper/1301.6479/) (2013)
- [Sound, Complete and Minimal UCQ-Rewriting for Existential Rules](https://mlsanity.com/paper/1311.3198/) (2013)
- [First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries](https://mlsanity.com/paper/2011.09314/) (2020)
- [Parallelisable Existential Rules: a Story of Pieces](https://mlsanity.com/paper/2107.06054/) (2021)

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

- [Abstractions of Queries in Ontology-Based Data Access](https://mlsanity.com/paper/2606.24618/) (2026)

## Abstract (arXiv)

We consider the issue of answering unions of conjunctive queries (UCQs) with disjunctive existential rules and mappings. While this issue has already been well studied from a chase perspective, query rewriting within UCQs has hardly been addressed yet. We first propose a sound and complete query rewriting operator, which has the advantage of establishing a tight relationship between a chase step and a rewriting step. The associated breadth-first query rewriting algorithm outputs a minimal UCQ-rewriting when one exists. Second, we show that for any ``truly disjunctive'' nonrecursive rule, there exists a conjunctive query that has no UCQ-rewriting. It follows that the notion of finite unification sets (fus), which denotes sets of existential rules such that any UCQ admits a UCQ-rewriting, seems to have little relevance in this setting. Finally, turning our attention to mappings, we show that the problem of determining whether a UCQ admits a UCQ-rewriting through a disjunctive mapping is undecidable. We conclude with a number of open problems.