[Back]

M. Calautti, G. Gottlob, A. Pieris:
"Chase Termination for Guarded Existential Rules";
Talk: 9th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2015), Lima, Peru; 2015-05-06 - 2015-05-08; in: "Proceedings of the 9th Alberto Mendelzon International Workshop on Foundations of Data Management, Lima, Peru, May 6 - 8, 2015", A. Cali, M. Vidal (ed.); CEUR Workshop Proceedings, 1378 (2015), Paper ID 28, 6 pages.

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 contexts 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.

http://ceur-ws.org/Vol-1378/AMW_2015_paper_28.pdf

Project Head Reinhard Pichler:
Heterogene Information Integration

Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions

Project Head Stefan Woltran:
START