All-Instances Restricted Chase Termination for Linear TGDs
- PDF / 1,410,780 Bytes
- 9 Pages / 595.276 x 790.866 pts Page_size
- 71 Downloads / 155 Views
TECHNICAL CONTRIBUTION
All‑Instances Restricted Chase Termination for Linear TGDs Tomasz Gogacz1 · Jerzy Marcinkowski2 · Andreas Pieris3 Received: 6 March 2020 / Accepted: 2 September 2020 © The Author(s) 2020
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 chase 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, in general, undecidable, it is natural to ask whether well-behaved classes of TGDs, introduced in different contexts, ensure decidability. It has been recently shown that the problem is decidable for the restricted (a.k.a. standard) version of the chase, and linear TGDs, a prominent class of TGDs that has been introduced in the context of ontological query answering, under the assumption that only one atom appears in TGD-heads. We provide an alternative proof for this result based on Monadic Second-Order Logic, which we believe is simpler that the ones obtained from the literature.
1 Introduction The chase procedure (or simply chase) is a fundamental algorithmic tool that has been successfully applied to several database problems such as computing data exchange solutions [14], query answering under constraints [9], containment of queries under constraints [1], and checking logical implication of constraints [5, 22], to name a few. It accepts as an input a database D and a set T of constraints—which, for this work, are tuple-generating dependencies (TGDs) of the form ∀̄x∀̄y(𝜙(̄x, ȳ ) → ∃̄z 𝜓(̄x, z̄ )) with 𝜙 and 𝜓 being conjunctions of atoms – and, if it terminates, its result is a finite instance DT that is a universal model of D and T , i.e., is a model that can be homomorphically mapped into every other model of D and T . This is the reason for the ubiquity of the chase in database theory. Indeed, many key * Andreas Pieris [email protected] Tomasz Gogacz [email protected] Jerzy Marcinkowski [email protected] 1
Institute of Informatics, University of Warsaw, Warsaw, Poland
2
Institute of Computer Science, University of Wroclaw, Wroclaw, Poland
3
School of Informatics, University of Edinburgh, Edinburgh, UK
database problems can be solved by simply exhibiting a universal model. And this is not only in theory. Despite the fact that the instance constructed by the chase can be very large, efficient implementations of the chase procedure have been successfully applied during the last few years in many different contexts [6, 20, 25, 26]. Given a database D and a set T of TGDs, roughly speaking, the chase adds new atoms to D (possibly involving null values that act as witnesses for the existentially quantified variables) until the final result satisfies T . Here is a simple example of how the chase procedure works. Example 1 Given the database D = {R(c)} , and the TGDs
∀x(R(x) → ∃y P(x, y))
and
∀x∀y(P(x, y) → R(y)),
the database
Data Loading...
