8x 8y Department(x) ^ M anaged(x; y) ! Employee(y) 8x Employee(x) ! 9 y W orksF or(x; y) 8x 8y W orksF or(x; y) ! 9 z M anaged(y; z)
The Chase is a xpoint algorithm enforcing satisfaction of data dependencies (also called constraints) in databases. It has been proposed more than thirty years ago [2,18] and has seen a revival of interest in recent years in both database theory and practical applications. Indeed, the availability of data coming from di erent sources easily results in inconsistent or incomplete data (i.e., data not satisfying data dependencies) and, therefore, techniques for xing inconsistencies are crucial [1,3,5,7,8,13,17].
The chase algorithm is used, directly or indirectly, on an everyday basis by people who design databases, and it is used in commercial systems to reason about the consistency and correctness of a data design. New applications of the chase in meta-data management, ontological reasoning, data exchange, data cleaning, and query optimization have been proposed as well [6,9].
The chase algorithm solves possible violations of constraints by inserting new tuples, possibly containing null values [4]. The following example shows a case where a given database does not satisfy a set of tuple generating dependencies (TGDs) and the application of the chase algorithm produces a new consistent database by adding tuples with nulls.
and their employees:
Consider the database D = fDepartment(d); M anaged(d; m)g. Since the rst constraint is not satis ed, the tuple Employee(m) is inserted. This update operation res the second constraint to insert the tuple W orksF or(m; 1), which in turn res the third constraint so that the tuple M anaged( 1; 2) is added to the database ( 1 and 2 are new labeled nulls). At this point, the chase terminates since the database is consistent, that is, all dependencies are satis ed. 2
Unfortunately, the chase algorithm may not terminate. For instance, in Example 1 if we delete from the rst constraint the atom Department(x), the chase never terminates and adds an in nite number of tuples to the database. It has been formally proved in [12] that the problem of deciding whether the chase procedure terminates is semi-decidable. The rst and basic e ort concerning the formalization of a (decidable) su cient condition guaranteeing chase termination is weak acyclicity [11]. Informally, it checks whether the constraints do not allow for nulls to cyclically propagate inside predicates' positions. Considering the example above, we have that a value in the second position of predicate M anaged is copied to Employee (denoted by M2 ! E1). This forces the introduction of a new null value in the second position of W orksF or, (denoted as E1 ! W F2); this value is then copied in the rst position of M anaged (W F2 ! M1) and it also forces the introduction of a new null value in the second position of M anaged (W F2 ! M2). Since it is possible to reach position M2 from itself through a connection of the form !, an in nite number of nulls could be introduced during the chase procedure.
Di erent extensions of weak acyclicity have been proposed. Safety [20] and super-weak acyclicity [19] identify the positions in which null values can be propagated. Strati cation-based approaches [10,20,16] analyse whether dependencies may re each other and thus propagate null values from one to another. See [14] for a comprehensive survey on this topic. Nevertheless, despite the previously mentioned results, there are still important classes of terminating data dependencies which are not identi ed by any of the previously mentioned criteria: Example 1 showed one such a case. To overcome such limitations, rewriting techniques have been proposed [15,16]. In the following section we give an overview on them and show how the constraints of Example 1 can be rewritten by using predicate adornments in order to allow simple termination conditions (even the simplest one, weak-acyclicity) to understand that the chase procedure terminates. Issues regarding the extension of these techniques to managing also equality generating dependencies (EGDs) are discussed in Section 3. 2
We start by introducing the basic idea of the Adn technique [15], which can be used in conjunction with current termination criteria, enabling us to detect more sets of constraints as terminating. The technique consists of rewriting a set of TGDs into a new set which is \better" than the original one for the purpose of checking termination. Rather than applying a termination criterion to , the new set is used and if satis es the criterion then chase termination for is guaranteed. This allows us to recognize larger classes of constraints for which chase termination is guaranteed: if satis es chase termination criterion C, then the rewritten set satis es C as well, but the vice versa is not true, that is, there are signi cant classes of constraints for which satis es C and does not.
Example 2. Consider again the set of TGDs 1. The Adn technique rst rewrites
TGDs by associating strings of b symbols to body atoms and to head positions
containing universally quanti ed variables. Then, f symbols are associated for
existentially quanti ed variables. This new set of TGDs is denoted by Base(
At this point, the generation of Derived(
In the previous sections, we have considered the case where all constraints are TGDs. In this section, we show how the chase termination problem radically changes when we allow also EGDs.
Given a set of TGDs for which the chase does not terminate, we can show that the addition of EGDs to may allow to have a terminating chase sequence. On the other hand, if the chase always terminates for , adding EGDs to may make the chase of non-terminating.
Example 3. Consider the following two sets of constraints (right): 3 (left) and and the database D = fN (a)g. The chase applied to the database D and the subset of TGDs fr1; r2g of 3 is not terminating as it introduces an in nite number of tuples E( 1; 2); E( 3; 1); ::: The introduction of the EGD r3 allows to have a terminating sequence, which produces the universal solution fN (a); E(a; a)g.
The subset of TGDs fr10; r20; r30g of 30 is terminating for all database
instances as recognized by several criteria (e.g., super-weak acyclicity). However,
the chase xpoint applied to 30 and the database D is non-terminating as it
introduces an in nite number of tuples S(a; 1; 1); T (a; 1; 1); N (
As shown in the previous example, when for a set of dependencies it is not the case that every chase sequence is terminating, the existence of at least one terminating chase sequence, for every database, might still be guaranteed. Thus, one could extend rewriting techniques such as Adn+ to sets of TGDs and EGDs, in order to nd whether there exists, for every database, at least one terminating chase sequence. In order to cope with the aforementioned issues, algorithm Adn+ can be extended in such a way that some adornments generated by rewriting TGDs are changed in order to satisfy the head equalities of EGDs. Speci cally, the algorithm rst tries to adorn as many EGDs as possible, and then consider the rewriting of a single TGD. The basic idea is illustrated in the following example.
Example 4. Consider the set of dependencies 3 of Example 3. As initially EGD r4 cannot be adorned, TGD r1 is rewritten into: and r2 is rewritten into:
8x Ab(x) ! 9y N f1 (y) 8x N b(x) ! 9y Ebf2 (x; y)
Now, EGD r4 can be used to \merge" distinct symbols. This is accomplished by constructing the following adorned version of r4 using the atom Ebf2 (x; y): 8x 8y Ebf2 (x; y) ! x = y
This indicates that every occurrence of the symbol f2 in the obtained adorned dependencies has to be replaced with b, thereby obtaining: Then, TGD r3 is adorned, obtaining:
8x Ab(x) ! 9y N f1 (y) 8x 8y N b(x) ! 9y Ebb(x; y) 8x 8y Ebb(x; y) ! x = y
8x 8y Ebb(x; y) ! N b(y) 8x 8y N f1 (x) ! 9y Ef1f3 (x; y) Consequently, f3 is replaced with f1 and we get:
8x 8y Ef1f1 (x; y) ! N f1 (y)
At this point, the rewriting stops, since no new adorned dependency can be
constructed. Intuitively, the algorithm identi es the existence of a terminating chase
sequence because symbols f1; f2; f3, which represent nulls constructed w.r.t. the
symbols occurring in the body of the TGD, are not \cyclic" in the following
sense. Symbol f1 \depends on" symbol b in body(r1), f2 depends on symbol b
in body(r2), and f3 depends on symbol f1. Since no pair of symbols fi; fj in the
nal set of dependency is such that fi depends on fj and vice versa, the set 3
has a terminating chase sequence. 2
11. R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: semantics and
query answering. Th. Comp. Sc., 336(
In ICALP, pages 293{304, 2014.
13. G. Greco, S. Greco, and E. Zumpano. A logical framework for querying and
repairing inconsistent databases. TKDE, 15(
PVLDB, 3(
PODS, pages 13{22, 2009. 20. M. Meier, M. Schmidt, and G. Lausen. On chase termination beyond strati cation.
CoRR, abs/0906.4228, 2009.