# Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 27 references that are in the map.
- First posted on arXiv 17 Jul 2023.

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

- [Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying](https://mlsanity.com/paper/2209.02464/) (2022)

## Abstract (arXiv)

This paper establishes alternative characterizations of very expressive classes of existential rule sets with decidable query entailment. We consider the notable class of greedy bounded-treewidth sets (gbts) and a new, generalized variant, called weakly gbts (wgbts). Revisiting and building on the notion of derivation graphs, we define (weakly) cycle-free derivation graph sets ((w)cdgs) and employ elaborate proof-theoretic arguments to obtain that gbts and cdgs coincide, as do wgbts and wcdgs. These novel characterizations advance our analytic proof-theoretic understanding of existential rules and will likely be instrumental in practice.