# A Journey to the Frontiers of Query Rewritability

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2020.

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

- [Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying](https://mlsanity.com/paper/2209.02464/) (2022)
- [The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules](https://mlsanity.com/paper/2407.14384/) (2024)

## Abstract (arXiv)

This paper is about (first order) query rewritability in the context of theory-mediated query answering. The starting point of our journey is the FUS/FES conjecture, saying that if a theory is core-terminating (FES) and admits query rewriting (BDD, FUS) then it is uniformly bounded. We show that this conjecture is true for a wide class of "local" BDD theories. Then we ask how non-local can a BDD theory actually be and we discover phenomena which we think are quite counter-intuitive.