Chase Termination Beyond Polynomial Time
Aus International Center for Computational Logic
Chase Termination Beyond Polynomial Time
Vortrag von Philipp Hanisch
- Veranstaltungsort: APB 3027
- Beginn: 30. Mai 2024 um 11:00
- Ende: 30. Mai 2024 um 12:00
- Forschungsgruppe: Wissensbasierte Systeme
- Event series: Research Seminar Logic and AI
- iCal
The chase is a widely implemented approach to reason with tuple-generating dependencies (tgds, aka. existential rules), used in data exchange, data integration, and ontology-based query answering. However, it is merely a semi-decision procedure, which may fail to terminate. Many decidable conditions have been proposed for tgds to ensure chase termination, typically by forbidding some kind of “cycle” in the chase process. We propose a new criterion that explicitly allows some such cycles, and yet ensures termination of the standard chase under reasonable conditions. This leads to new decidable fragments of tgds that are not only syntactically more general but also strictly more expressive than the fragments defined by prior acyclicity conditions. Indeed, while known terminating fragments are restricted to PTime data complexity, our conditions yield decidable languages for any 𝑘-ExpTime. We further refine our syntactic conditions to obtain fragments of tgds for which an optimised chase procedure decides query entailment in PSpace or 𝑘-ExpSpace, respectively.
- Weitere Infos unter: https://arxiv.org/abs/2403.16712
