All-Instances Restricted Chase Termination

Tomasz Gogacz, Jerzy Marcinkowski, Andreas Pieris

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

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.
Original languageEnglish
Title of host publicationProceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 20)
PublisherAssociation for Computing Machinery (ACM)
Pages245-258
Number of pages14
ISBN (Electronic)9781450371087
DOIs
Publication statusPublished - 14 Jun 2020
Event2020 ACM SIGMOD/PODS International Conference on Management of Data - Portland, United States
Duration: 14 Jun 202019 Jun 2020
https://sigmod2020.org/

Conference

Conference2020 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD/PODS 2020
Country/TerritoryUnited States
CityPortland
Period14/06/2019/06/20
Internet address

Keywords

  • restricted chase
  • chase termination
  • tuple-generating dependencies
  • guardedness
  • stickiness
  • decidability

Fingerprint

Dive into the research topics of 'All-Instances Restricted Chase Termination'. Together they form a unique fingerprint.

Cite this