# Capturing Homomorphism-Closed Decidable Queries with Existential Rules

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2021.

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

- [Efficient Dependency Analysis for Rule-Based Ontologies](https://mlsanity.com/paper/2207.09669/) (2022)
- [Normalisations of Existential Rules: Not so Innocuous!](https://mlsanity.com/paper/2206.03124/) (2022)
- [Decidability of Querying First-Order Theories via Countermodels of Finite Width](https://mlsanity.com/paper/2304.06348/) (2023)

## Abstract (arXiv)

Existential rules are a very popular ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize properties that are preserved under homomorphisms. In this paper, we show the converse: every decidable query that is closed under homomorphism can be expressed by an existential rule set for which the standard chase universally terminates. Membership in this fragment is not decidable, but we show via a diagonalisation argument that this is unavoidable.