Edinburgh Research Explorer

Oblivious Chase Termination: The Sticky Case

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

Related Edinburgh Organisations

Open Access permissions



  • Download as Adobe PDF

    Submitted manuscript, 704 KB, PDF document

  • Download as Adobe PDF

    Accepted author manuscript, 658 KB, PDF document

  • Download as Adobe PDF

    Rights statement: © Marco Calautti and Andreas Pieris; licensed under Creative Commons License CC-BY

    Final published version, 590 KB, PDF document

    Licence: Creative Commons: Attribution (CC-BY)

Original languageEnglish
Title of host publication22nd International Conference on Database Theory (ICDT 2019)
EditorsPablo Barcelo, Marco Calautti
Number of pages18
Publication statusPublished - 19 Mar 2019
Event22nd International Conference on Database Theory - Lisbon, Portugal
Duration: 26 Mar 201929 Mar 2019

Publication series

ISSN (Electronic)1868-8969


Conference22nd International Conference on Database Theory
Abbreviated titleICDT 2019
Internet address


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.

    Research areas

  • Chase procedure, tuple-generating dependencies, stickiness, termination, computational complexity, logic and databases


22nd International Conference on Database Theory


Lisbon, Portugal

Event: Conference

Download statistics

No data available

ID: 74614346