Relaxed 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. 

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... 

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. 

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. 

Definition 6 (Relaxed chase-inverse). Let M be a GLAV schema mapping from a schema Si to a schema S2. We say that M is a relaxed chase-inverse of M if M is a GLAV schema mapping from S2 to Si such that, for every instance I over Si, the following properties hold for the instance U = chasem (chaseM(I)) ... 

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... 

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. 

---