About the Multi-Head Linear Restricted Chase Termination

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

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

OriginalspracheEnglisch
TitelProceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning (KR 2025)
Redakteure/-innenMagdalena Ortiz, Renata Wassermann, Torsten Schaub
Herausgeber (Verlag)IJCAI Organization
Seiten346–355
Seitenumfang10
ISBN (elektronisch)978-1-956792-08-9
PublikationsstatusVeröffentlicht - 1 Okt. 2025
Peer-Review-StatusJa

Publikationsreihe

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

Externe IDs

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