License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2019.17
URN: urn:nbn:de:0030-drops-103197
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10319/
Go to the corresponding LIPIcs Volume Portal

Calautti, Marco ; Pieris, Andreas

Oblivious Chase Termination: The Sticky Case

pdf-format:
LIPIcs-ICDT-2019-17.pdf (0.6 MB)

Abstract

The chase procedure is one of the most fundamental algorithmic tools in database theory. A key algorithmic task is uniform chase termination, i.e., given a set of tuple-generating dependencies (tgds), is it the case that the chase under this set of tgds terminates, for every input database? In view of the fact that this problem is undecidable, no matter which version of the chase we consider, it is natural to ask whether well-behaved classes of tgds, introduced in different contexts such as ontological reasoning, make our problem decidable. In this work, we consider a prominent decidability paradigm for tgds, called stickiness. We show that for sticky sets of tgds, uniform chase termination is decidable if we focus on the (semi-)oblivious chase, and we pinpoint its exact complexity: PSpace-complete in general, and NLogSpace-complete for predicates of bounded arity. These complexity results are obtained via graph-based syntactic characterizations of chase termination that are of independent interest.

BibTeX - Entry

@InProceedings{calautti_et_al:LIPIcs:2019:10319,
  author =	{Marco Calautti and Andreas Pieris},
  title =	{{Oblivious Chase Termination: The Sticky Case}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{17:1--17:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Pablo Barcelo and Marco Calautti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10319},
  doi =		{10.4230/LIPIcs.ICDT.2019.17},
  annote =	{Keywords: Chase procedure, tuple-generating dependencies, stickiness, termination, computational complexity}
}

Keywords: Chase procedure, tuple-generating dependencies, stickiness, termination, computational complexity
Collection: 22nd International Conference on Database Theory (ICDT 2019)
Issue Date: 2019
Date of publication: 19.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI