Edinburgh Research Explorer

Oblivious Chase Termination: The Sticky Case

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

  • Download as Adobe PDF

    Submitted manuscript, 704 KB, PDF-document

  • Download as Adobe PDF

    Accepted author manuscript, 657 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)

http://drops.dagstuhl.de/opus/volltexte/2019/10319/
Original languageEnglish
Title of host publication22nd International Conference on Database Theory (ICDT 2019)
EditorsPablo Barcelo, Marco Calautti
Number of pages18
DOIs
Publication statusPublished - 19 Mar 2019
Event22nd International Conference on Database Theory - Lisbon, Portugal
Duration: 26 Mar 201929 Mar 2019
http://edbticdt2019.inesc-id.pt/

Publication series

NameLIPICS
Volume127
ISSN (Electronic)1868-8969

Conference

Conference22nd International Conference on Database Theory
Abbreviated titleICDT 2019
CountryPortugal
CityLisbon
Period26/03/1929/03/19
Internet address

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.

    Research areas

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

Event

22nd International Conference on Database Theory

26/03/1929/03/19

Lisbon, Portugal

Event: Conference

Download statistics

No data available

ID: 74614346