Chase Termination for Guarded Existential Rules

Marco Calautti, Georg Gottlob, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

The chase procedure is considered as one of the most fundamental algorithmic
tools in database theory. It has been successfully applied to different database problems such as data exchange, and query answering and containment under constraints, to name a few. One of the central problems regarding the chase procedure is all-instance termination, that is, given a set of tuple-generating dependencies (TGDs) (a.k.a. existential rules), decide whether the chase under that set terminates, for every input database. It is well-known that this problem is undecidable, no matter which version of the chase we consider. The crucial question that comes up is whether existing restricted classes of TGDs, proposed in different such as ontological reasoning, make the above problem decidable. In this work, we focus our attention on the oblivious and the semi-oblivious versions of the chase procedure, and we give a positive answer for classes of TGDs that are based on the notion of guardedness.
Original languageEnglish
Title of host publicationProceedings of the 9th Alberto Mendelzon International Workshop on Foundations of Data Management, Lima, Peru, May 6 - 8, 2015.
PublisherCEUR Workshop Proceedings (
Number of pages6
Publication statusPublished - 2015


Dive into the research topics of 'Chase Termination for Guarded Existential Rules'. Together they form a unique fingerprint.

Cite this