Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Combining Existential Rules and Transitivity: Next Steps
We consider existential rules (aka Datalog+) as a formalism for specifying ontologies. In recent years, many classes of existential rules have been exhibited for which conjunctive query (CQ) entailment is decidable. Howe…
On the k-Boundedness for Existential Rules
The chase is a fundamental tool for existential rules. Several chase variants are known, which differ on how they handle redundancies possibly caused by the introduction of nulls. Given a chase variant, the halting probl…
Conservative Extensions for Existential Rules
We study the problem to decide, given sets T1,T2 of tuple-generating dependencies (TGDs), also called existential rules, whether T2 is a conservative extension of T1. We consider two natural notions of conservative exten…
Finite-Cliquewidth Sets of Existential Rules: Toward a General Criterion for Decidable yet Highly Expressive Querying
In our pursuit of generic criteria for decidable ontology-based querying, we introduce 'finite-cliquewidth sets' (FCS) of existential rules, a model-theoretically defined class of rule sets, inspired by the cliquewidth m…
Model-theoretic Characterizations of Existential Rule Languages
Existential rules, a.k.a. dependencies in databases, and Datalog+/- in knowledge representation and reasoning recently, are a family of important logical languages widely used in computer science and artificial intellige…
model