Bounded Treewidth and the Infinite Core Chase textendash: Complications and Workarounds toward Decidable Querying
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
The core chase, a popular algorithm for answering conjunctive queries (CQs) over existential rules, is guaranteed to terminate and compute a finite universal model whenever one exists, leading to the equivalence of the universal-model-based and the chase-based definitions of finite expansion sets (fes)-a class of rulesets featuring decidable CQ entailment. In case of non-Termination, however, it is non-Trivial to define a ''result'' of the core chase, due to its non-monotonicity. This causes complications when dealing with advanced decidability criteria based on the existence of (universal) models of finite treewidth. For these, sufficient chase-based conditions have only been established for weaker, monotonic chase variants. This paper investigates the-prima facie plausible-hypothesis that the existence of a treewidth-bounded universal model and the existence of a treewidth-bounded core-chase sequence coincide-which would conveniently entail decidable CQ entailment whenever the latter holds. Perhaps surprisingly, carefully crafted examples show that both directions of this hypothesized correspondence fail. On a positive note, we are still able to define an aggregation scheme for the infinite core chase that preserves treewidth bounds and produces a finitely universal model, i.e., one that satisfies exactly the entailed CQs. This allows us to prove that the existence of a treewidth-bounded core-chase sequence does warrant decidability of CQ entailment (yet, on other grounds than expected). Hence, for the first time, we are able to define a chase-based notion of bounded treewidth sets of rules that subsumes fes.
Details
Originalsprache | Englisch |
---|---|
Titel | PODS 2023 - Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |
Redakteure/-innen | Floris Geerts, Hung Q. Ngo, Stavros Sintos |
Herausgeber (Verlag) | ACM Press |
Seiten | 291-302 |
Seitenumfang | 12 |
ISBN (elektronisch) | 9798400701276 |
Publikationsstatus | Veröffentlicht - 18 Juni 2023 |
Peer-Review-Status | Ja |
Externe IDs
Scopus | 85156178185 |
---|
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- chase, existential rules, treewidth, tuple-generating dependencies, universal models