Semi-oblivious chase termination: the sticky case (Q2035470)

The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. The authors consider a prominent paradigm that led to a robust Tuple-Generating Dependencies (TGD) based formalism, called stickiness. It is shown that for sticky sets of TGDs, all-instances chase termination is decidable if focus is on the (semi-) oblivious chase, and its exact complexity is discussed. The complexity results are obtained via a graph-based syntactic characterization of chase termination that is of independent interest.