Projects per year
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, introduced in different contexts such as ontological reasoning, ensure decidability. We consider a prominent paradigm that led to a robust TGD-based formalism, called stickiness. We show that for sticky sets of TGDs, all-instances 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 a graph-based syntactic characterization of chase termination that is of independent interest.
Original language | English |
---|---|
Pages (from-to) | 84 - 121 |
Number of pages | 38 |
Journal | Theory of Computing Systems |
Volume | 65 |
Issue number | 1 |
Early online date | 17 Aug 2020 |
DOIs | |
Publication status | Published - 1 Jan 2021 |
Keywords
- Chase procedure
- Tuple-generating dependencies
- Stickiness
- Termination
- Computational complexity
Fingerprint
Dive into the research topics of 'Semi-Oblivious Chase Termination: The Sticky Case'. Together they form a unique fingerprint.-
-
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research