About the Multi-Head Linear Restricted Chase Termination

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-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 languageEnglish
Title of host publicationProceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning (KR 2025)
EditorsMagdalena Ortiz, Renata Wassermann, Torsten Schaub
PublisherIJCAI Organization
Pages346–355
Number of pages10
ISBN (electronic)978-1-956792-08-9
Publication statusPublished - 1 Oct 2025
Peer-reviewedYes

Publication series

SeriesProceedings of the International Conference on Principles of Knowledge Representation and Reasoning
ISSN2334-1025

External IDs

Mendeley fb30ba6a-20b0-3fab-aee9-c289b5e2f874