Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets
This work provides foundational insights for researchers in knowledge representation and database theory, advancing analytic understanding of existential rules, though it is incremental in nature.
The paper tackles the problem of characterizing decidable existential rule sets by establishing that greedy bounded-treewidth sets (gbts) coincide with cycle-free derivation graph sets (cdgs), and similarly for their weak variants, using proof-theoretic arguments.
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.