Bounded Treewidth and the Infinite Core Chase – Complications and Workarounds toward Decidable Querying
Bounded Treewidth and the Infinite Core Chase – Complications and Workarounds toward Decidable Querying
Talk by Sebastian Rudolph
- Location: APB room 3027
- Start: 2. November 2023 at 11:00 am
- End: 2. November 2023 at 12:00 pm
- Event series: Research Seminar Logic and AI
- iCal
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 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.
The talk will take place in a hybrid fashion, physically in the APB room 3027, and online through the link:
https://bbb.tu-dresden.de/b/pio-zwt-smp-aus