View article

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 () and a new, generalized variant, called weakly gbts (). Revisiting and building on the notion of derivation graphs, we define (weakly) cycle-free derivation graph sets () and employ elaborate proof-theoretic arguments to obtain that and coincide, as do and . These novel characterizations advance our analytic proof-theoretic understanding of existential rules and will likely be instrumental in practice.