Semi-Oblivious Chase Termination: The Sticky Case

Marco Calautti, Andreas Pieris

Research output: Contribution to journalArticlepeer-review

Abstract

The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A key problem concerning the chase procedure is all-instances termination: for a given set of tuple-generating dependencies (TGDs), is it the case that the chase terminates for every input database? In view of the fact that this problem is undecidable, it is natural to ask whether known well-behaved classes of TGDs, introduced in different contexts such as ontological reasoning, ensure decidability. We consider a prominent paradigm that led to a robust TGD-based formalism, called stickiness. We show that for sticky sets of TGDs, all-instances 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 a graph-based syntactic characterization of chase termination that is of independent interest.
Original languageEnglish
Pages (from-to)84 - 121
Number of pages38
JournalTheory of Computing Systems
Volume65
Issue number1
Early online date17 Aug 2020
DOIs
Publication statusPublished - 1 Jan 2021

Keywords

  • Chase procedure
  • Tuple-generating dependencies
  • Stickiness
  • Termination
  • Computational complexity

Fingerprint Dive into the research topics of 'Semi-Oblivious Chase Termination: The Sticky Case'. Together they form a unique fingerprint.

Cite this