About the Multi-Head Linear Restricted Chase Termination
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
The chase is a ubiquitous algorithm in database theory. However, for existential rules (aka tuple-generating dependencies), its termination is not guaranteed, and even undecidable in general. The problem of termination becomes particularly difficult for the restricted (or standard) chase, for which the order of rule application matters. Thus, decidability of restricted chase termination is still open for many well-behaved classes such as linear or guarded multi-headed rules. We make a step forward by showing that all-instances restricted chase termination is decidable in the linear multi-headed case.
Details
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning (KR 2025) |
| Editors | Magdalena Ortiz, Renata Wassermann, Torsten Schaub |
| Publisher | IJCAI Organization |
| Pages | 346–355 |
| Number of pages | 10 |
| ISBN (electronic) | 978-1-956792-08-9 |
| Publication status | Published - 1 Oct 2025 |
| Peer-reviewed | Yes |
Publication series
| Series | Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning |
|---|---|
| ISSN | 2334-1025 |
External IDs
| Mendeley | fb30ba6a-20b0-3fab-aee9-c289b5e2f874 |
|---|