All-Instances Restricted Chase Termination

Tomasz Gogacz; Jerzy Marcinkowski; Andreas Pieris

doi:10.1145/3375395.3387644

All-Instances Restricted Chase Termination

Tomasz Gogacz, Jerzy Marcinkowski, Andreas Pieris

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

Abstract / Description of output

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 ensure decidability. We consider here the main paradigms that led to robust TGD-based formalisms, that is, guardedness and stickiness. Although all-instances termination is well-understood for the oblivious version of the chase, the more subtle case of the restricted (a.k.a. the standard) chase is rather unexplored. We show that all-instances restricted chase termination for guarded and sticky single-head TGDs is decidable.

Original language	English
Title of host publication	Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 20)
Publisher	Association for Computing Machinery (ACM)
Pages	245-258
Number of pages	14
ISBN (Electronic)	9781450371087
DOIs	https://doi.org/10.1145/3375395.3387644
Publication status	Published - 14 Jun 2020
Event	2020 ACM SIGMOD/PODS International Conference on Management of Data - Portland, United States Duration: 14 Jun 2020 → 19 Jun 2020 https://sigmod2020.org/

Conference

Conference	2020 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated title	SIGMOD/PODS 2020
Country/Territory	United States
City	Portland
Period	14/06/20 → 19/06/20
Internet address	https://sigmod2020.org/

Keywords / Materials (for Non-textual outputs)

restricted chase
chase termination
tuple-generating dependencies
guardedness
stickiness
decidability

Access to Document

10.1145/3375395.3387644Licence: All Rights Reserved

All-Instances Restricted_GOGACZ_DOA08032020_AFVAccepted author manuscript, 1.02 MB

https://dl.acm.org/doi/10.1145/3375395.3387644Licence: All Rights Reserved

Efficient Querying of Inconsistent Data
Pieris, A. & Libkin, L.
EPSRC
1/09/18 → 31/08/23
Project: Research

Cite this

@inproceedings{8f2f108c6d0d46f8ba494852fae7542e,

title = "All-Instances Restricted Chase Termination",

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 ensure decidability. We consider here the main paradigms that led to robust TGD-based formalisms, that is, guardedness and stickiness. Although all-instances termination is well-understood for the oblivious version of the chase, the more subtle case of the restricted (a.k.a. the standard) chase is rather unexplored. We show that all-instances restricted chase termination for guarded and sticky single-head TGDs is decidable.",

keywords = "restricted chase, chase termination, tuple-generating dependencies, guardedness, stickiness, decidability",

author = "Tomasz Gogacz and Jerzy Marcinkowski and Andreas Pieris",

year = "2020",

month = jun,

day = "14",

doi = "10.1145/3375395.3387644",

language = "English",

pages = "245--258",

booktitle = "Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 20)",

publisher = "Association for Computing Machinery (ACM)",

address = "United States",

note = "2020 ACM SIGMOD/PODS International Conference on Management of Data, SIGMOD/PODS 2020 ; Conference date: 14-06-2020 Through 19-06-2020",

url = "https://sigmod2020.org/",

}

Gogacz, T, Marcinkowski, J & Pieris, A 2020, All-Instances Restricted Chase Termination. in Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 20). Association for Computing Machinery (ACM), pp. 245-258, 2020 ACM SIGMOD/PODS International Conference on Management of Data, Portland, Oregon, United States, 14/06/20. https://doi.org/10.1145/3375395.3387644

TY - GEN

T1 - All-Instances Restricted Chase Termination

AU - Gogacz, Tomasz

AU - Marcinkowski, Jerzy

AU - Pieris, Andreas

PY - 2020/6/14

Y1 - 2020/6/14

N2 - 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 ensure decidability. We consider here the main paradigms that led to robust TGD-based formalisms, that is, guardedness and stickiness. Although all-instances termination is well-understood for the oblivious version of the chase, the more subtle case of the restricted (a.k.a. the standard) chase is rather unexplored. We show that all-instances restricted chase termination for guarded and sticky single-head TGDs is decidable.

AB - 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 ensure decidability. We consider here the main paradigms that led to robust TGD-based formalisms, that is, guardedness and stickiness. Although all-instances termination is well-understood for the oblivious version of the chase, the more subtle case of the restricted (a.k.a. the standard) chase is rather unexplored. We show that all-instances restricted chase termination for guarded and sticky single-head TGDs is decidable.

KW - restricted chase

KW - chase termination

KW - tuple-generating dependencies

KW - guardedness

KW - stickiness

KW - decidability

U2 - 10.1145/3375395.3387644

DO - 10.1145/3375395.3387644

M3 - Conference contribution

SP - 245

EP - 258

BT - Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 20)

PB - Association for Computing Machinery (ACM)

T2 - 2020 ACM SIGMOD/PODS International Conference on Management of Data

Y2 - 14 June 2020 through 19 June 2020

ER -

All-Instances Restricted Chase Termination

Abstract / Description of output

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

Efficient Querying of Inconsistent Data

Cite this