Edinburgh Research Explorer

Chase Termination for Guarded Existential Rules

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

Related Edinburgh Organisations

Open Access permissions



  • Download as Adobe PDF

    Accepted author manuscript, 69.4 KB, PDF document

    Licence: Creative Commons: Attribution (CC-BY)

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 (CEUR-WS.org)
Number of pages6
Publication statusPublished - 2015


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.

Download statistics

No data available

ID: 28081860