Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2023

Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying

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.
Fichier principal
Vignette du fichier
main-pods.pdf (758.29 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-04320944 , version 1 (04-12-2023)

Identifiers

Cite

Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph. Bounded Treewidth and the Infinite Core Chase: Complications and Workarounds toward Decidable Querying. SIGMOD/PODS 2023 - International Conference on Management of Data, Jul 2023, Seattle, WA, United States. pp.291-302, ⟨10.1145/3584372.3588659⟩. ⟨lirmm-04320944⟩
29 View
9 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More