KR2025Proceedings of the 22nd International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning

Melbourne, Australia. November 11-17, 2025.

Edited by
  1. Magdalena Ortiz
  2. Renata Wassermann
  3. Torsten Schaub

ISSN: 2334-1033
ISBN: 978-1-956792-08-9

Sponsored by
Published by

Copyright © 2025 International Joint Conferences on Artificial Intelligence Organization

About the Multi-Head Linear Restricted Chase Termination

  1. Lukas Gerlach(Knowledge-Based Systems Group, TU Dresden)
  2. Lucas Larroque(Inria, DI ENS, ENS, CNRS, PSL University, Paris)
  3. Jerzy Marcinkowski(University of Wrocław)
  4. Piotr Ostropolski-Nalewaja(University of Wrocław)
PDF
BibTeX
https://doi.org/10.24963/kr.2025/34

Keywords

  1. Existential Rules
  2. Tuple-generating Dependencies
  3. Chase
  4. Decidability
  5. Linear Rules
  6. Multi Head
  7. Monadic Second Order Logic

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.