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

From International Center for Computational Logic

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

##### Jean-François BagetJean-François Baget, Marie-Laure MugnierMarie-Laure Mugnier, Sebastian RudolphSebastian Rudolph

Jean-François Baget, Marie-Laure Mugnier, Sebastian Rudolph

**Bounded Treewidth and the Infinite Core Chase – Complications and Workarounds toward Decidable Querying***Proceedings of the 42nd Symposium on Principles of Database Systems (PODS'23)*, to appear**Kurzfassung****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

This paper starts out from the – desirable and prima facie plausible – conjecture 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 conjectured 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*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.*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.**Projekt:****Project:**DeciGUT**Forschungsgruppe:****Research Group:**Computational Logic

```
@inproceedings{BMR2023,
author = {Jean-Fran{\c{c}}ois Baget and Marie-Laure Mugnier and Sebastian
Rudolph},
title = {Bounded Treewidth and the Infinite Core Chase {\textendash}
Complications and Workarounds toward Decidable Querying},
booktitle = {Proceedings of the 42nd Symposium on Principles of Database
Systems (PODS'23)},
year = {2023}
}
```