Oblivious Chase Termination: The Sticky Case

Marco Calautti; Andreas Pieris

doi:10.4230/LIPIcs.ICDT.2019.17

Oblivious Chase Termination: The Sticky Case

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	22nd International Conference on Database Theory (ICDT 2019)
Editors	Pablo Barcelo, Marco Calautti
Number of pages	18
DOIs	https://doi.org/10.4230/LIPIcs.ICDT.2019.17
Publication status	Published - 19 Mar 2019
Event	22nd International Conference on Database Theory - Lisbon, Portugal Duration: 26 Mar 2019 → 29 Mar 2019 http://edbticdt2019.inesc-id.pt/

Publication series

Name	LIPICS
Volume	127
ISSN (Electronic)	1868-8969

Conference

Conference	22nd International Conference on Database Theory
Abbreviated title	ICDT 2019
Country/Territory	Portugal
City	Lisbon
Period	26/03/19 → 29/03/19
Internet address	http://edbticdt2019.inesc-id.pt/

Keywords / Materials (for Non-textual outputs)

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

Access to Document

10.4230/LIPIcs.ICDT.2019.17Licence: Creative Commons: Attribution (CC-BY)

Oblivious Chase Termination pre-printSubmitted manuscript, 704 KB
Oblivious Chase TerminationAccepted author manuscript, 658 KB
Oblivious Chase Termination_CALAUTTI_DoA280518_VoR_CC-BY
© Marco Calautti and Andreas Pieris; licensed under Creative Commons License CC-BY
Final published version, 590 KBLicence: Creative Commons: Attribution (CC-BY)

http://drops.dagstuhl.de/opus/volltexte/2019/10319/Licence: Creative Commons: Attribution (CC-BY)

Efficient Querying of Inconsistent Data
Pieris, A. & Libkin, L.
EPSRC
1/09/18 → 31/08/23
Project: Research
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
EPSRC
1/04/15 → 30/09/20
Project: Research

Cite this

@inproceedings{335ba5bfed4541dba1223bbda3ed4aa5,

title = "Oblivious Chase Termination: The Sticky Case",

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.",

keywords = "Chase procedure, tuple-generating dependencies, stickiness, termination, computational complexity, logic and databases",

author = "Marco Calautti and Andreas Pieris",

year = "2019",

month = mar,

day = "19",

doi = "10.4230/LIPIcs.ICDT.2019.17",

language = "English",

isbn = "978-3-95977-101-6",

series = "LIPICS",

editor = "Pablo Barcelo and Marco Calautti",

booktitle = "22nd International Conference on Database Theory (ICDT 2019)",

note = "22nd International Conference on Database Theory, ICDT 2019 ; Conference date: 26-03-2019 Through 29-03-2019",

url = "http://edbticdt2019.inesc-id.pt/",

}

TY - GEN

T1 - Oblivious Chase Termination

T2 - 22nd International Conference on Database Theory

AU - Calautti, Marco

AU - Pieris, Andreas

PY - 2019/3/19

Y1 - 2019/3/19

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

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

KW - Chase procedure

KW - tuple-generating dependencies

KW - stickiness

KW - termination

KW - computational complexity

KW - logic and databases

U2 - 10.4230/LIPIcs.ICDT.2019.17

DO - 10.4230/LIPIcs.ICDT.2019.17

M3 - Conference contribution

SN - 978-3-95977-101-6

T3 - LIPICS

BT - 22nd International Conference on Database Theory (ICDT 2019)

A2 - Barcelo, Pablo

A2 - Calautti, Marco

Y2 - 26 March 2019 through 29 March 2019

ER -

Oblivious Chase Termination: The Sticky Case

Abstract

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

Efficient Querying of Inconsistent Data

VADA: Value Added Data Systems: Principles and Architecture

Cite this