Chase inverse

These were introduced in Fagin et al. [2009b] under a different name universal-faithful inverses. However, the term relaxed chase-inverses, which we use in this paper, is a more suggestive term that also reflects the relationship with the chase-inverses. 

Definition 2 (Exact chase-inverse). Let At be a GLAV schema mapping from a schema Si to a schema S2. We say that M is an exact chase-inverse of M if M is a GLAV schema mapping from S2 to S2 with the following property for every instance I over S 1 we have that I = chasem (chase... 

As it turns out, this candidate inverse satisfies the above requirement of being able to recover, exactly, the source instance. Indeed, it can be immediately verified that for every source instance I over S, we have that chaseMf (chasem" CD) equals I. Thus, Mt is an exact chase-inverse of M". 

The schema mapping Mt used in Sect. 3.2 is an exact chase-inverse in the sense that it can recover the original source instance I exactly. In general, however, equality with I is too strong of a requirement, and all we need is a more relaxed form of equivalence of instances, where intuitively the equivalence is modulo nulls. In this section, we start with a concrete example to show the need for such relaxation. We... 

Here, for simplicity, we focus on schema mappings on binary relations. (In particular, At" can be forced into this pattern if we ignore the major field in the two relations Takes and Takes".) The important point about this type of mappings is that they always have an exact chase-inverse. Consider now a variation on the above pattern, where Q is the same as Q. Thus, let M be the following schema mapping ... 

Thus, we recovered the two original facts of I but also the additional fact P(ni, n2) (via joining 2( i,2) and 2(2> 2))- Therefore, M is not an exact chase-inverse of M. Nevertheless, since n and n2 are nulls, the extra fact P(n, n2) does not add any new information that is not subsumed by the other two facts. Intuitively, the last instance is equivalent (although not equal) to the original source instance I. 

The existence of a chase-inverse for M implies that M has no information loss, since we can recover an instance that is the same modulo homomorphic equivalence as the original source instance. At the same time, a chase-inverse is a relaxation of the notion of an exact chase-inverse hence, it may exist even when an exact chase-inverse does not exist. 

Both examples of chase-inverses that we have given, namely Mt in Sect. 3.2 and M in this section, are GAV mappings. This is not by accident. As the following theorem shows, we do not need the full power of GLAV mappings to express a chase-inverse whenever there is a chase-inverse, there is a GAV chase-inverse. The main benefit of this theorem is that it may keep composition simpler. In particular, we may still be able to apply Corollary 1 as opposed to the more complex composition techniques of Sect. 4. 

We conclude this section with a corollary that summarizes the applications of chase-inverses together with the earlier Corollary 1 to our schema evolution context. 

We note that a chase-inverse may not exist in general, since a schema mapping may lose information and hence it may not be possible to find a chase-inverse. The above corollary depends on the fact that the schema mapping M" has a chase-inverse. In Sect. 5, we shall address the more general case where M" has no chase-inverse. 

Additionally, the above theorem also applies in the context of source schema evolution, provided that the source evolution mapping M" has a chase-inverse. We summarize the applicability of Theorem 3 to the context of schema evolution as follows. 

The important remaining restriction in the above corollary is that the source evolution mapping M" must have a chase-inverse and, in particular, that M" is a lossless mapping. We address next the case where M" is lossy and, hence, a chase-inverse does not exist. 

First of all, it can be verified that is not a chase-inverse for M". In particular, if we start with a source instance 1 for Takes where the source tuples contain some constant values for the ma j or field, and then apply the chase with M" and then the reverse chase with, we obtain another source instance U for Takes where the... 

As it can be seen, the recovered source instance U is not homomorphically equivalent to the original source instance there is a homomorphism from U to 7, but no homomorphism can map the constant CS in 7 to the null X in U. Intuitively, there is information loss in the evolution mapping M", which does not export the major field. Later on, in Sect. 5.2, we will show that in fact M" has no chase-inverse thus, we cannot recover a homomorphically equivalent source instance. 

At the same time, it can be argued, intuitively, that the source instance U that is recovered by in this example is the best source instance that can be recovered, given the circumstances. We will make this notion precise in the next paragraphs, leading to the definition of a relaxed chase-inverse. In particular, we will show that is a relaxed chase-inverse. 

Somewhat surprisingly, having just the third condition is too loose of a requirement for a good notion of a relaxation of a chase-inverse. As we show next, we need to add an additional requirement of homomorphic containment. 

Putting it all together, we now formally capture the two desiderata discussed above (data exchange equivalence and homomorphic containment) into the following definition of a relaxed chase-inverse. 

The notion of relaxed chase-inverse originated in Fagin et al. [2009b], under the name of universal-faithful inverse. The definition given in Fagin et al. [2009b] had, however, a third condition called universality, which turned out to be redundant (and equivalent to homomorphic containment). Thus, the formulation given here for a relaxed chase-inverse is simpler. 

Coming back to our example, it can be verified that the above satisfies the conditions of being a relaxed chase-inverse of M", thus reflecting the intuition that is a good approximation of an inverse in our scenario. 

It is fairly straightforward to see that every chase-inverse is also a relaxed chase-inverse. This follows from a well-known property of the chase that implies that whenever U I we also have that U I Thus, the notion of relaxed... 

Theorem 4. Let M be a GLAV schema mapping from a schema St to a schema S2 that has a chase-inverse. Then the following statements are equivalent for every GLAV schema mapping M from S2 to Sj ... 

As an immediate application of the preceding theorem, we conclude that the schema mapping M" in Sect. 5.1 has no chase-inverse, because A41 is a relaxed chase-inverse of M" but not a chase-inverse of M". 

In Sect. 3.3, we pointed out that chase-inverses coincide with the extended inverses that are specified by GLAV constraints. For schema mappings that have no extended inverses, a further relaxation of the concept of an extended inverse has been considered, namely, the concept of a maximum extended recovery [Fagin et al. 2009b]. It follows from results established in Fagin et al. [2009b] that relaxed chase-inverses coincide with the maximum extended recoveries that are specified by GLAV constraints. 

The above quasi-inverse M also happens to be a chase-inverse of M. In general, however, quasi-inverses differ from chase-inverses (or relaxed chase-inverses), and one may find quasi-inverses with nonintuitive behavior (e.g., a quasi-inverse that is not a chase-inverse, even when a chase-inverse exists). We note that the PRISM development preceded the development of chase-inverses or relaxed chase-inverses. 

---