Databases Reference
In-Depth Information
Somewhat surprisingly, having just the third condition is too loose of a require-
ment 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.
Relaxed chase-inverse: Stronger requirement.
We illustrate the need for the extra
condition by using our example. Refer again to the schema mapping
M
00
in Fig.
7.4
a
M
introduced earlier. As shown in Fig.
7.4
b,
given the source instance I, the mapping
and the natural candidate inverse
M
recovers an instance U such that U
and I are data exchange equivalent with respect to
M
00
. However, there can be many
other instances that are data exchange equivalent to I but intuitively are incorrect.
Consider, for example, the following instance:
U
0
Df
Takes
.007;007;CS101/g
Like U , the instance U
0
is data exchange equivalent to I with respect to
M
00
.(The
only difference from U is in the
major
field, which is not used by the chase with
M
00
.) Furthermore, such instance U
0
would be obtained if we use the following
“inverse” instead of
M
:
M
1
W
Takes
00
.s;c/ ^
Course
.c;
co
/ !
Takes
.s;s;
co
/:
M
1
Intuitively, the instance U
0
and the mapping
are not what we would expect from
a natural inverse. In the instance U
0
,the
sid
value 007 is artificially copied into the
major
field, and the resulting
Takes
fact represents
extra
information that did
not appear in the original source instance I. We can rule out bad “inverses” such
as
M
1
by requiring any recovered instance to also have a homomorphism into I.
Intuitively, this is a soundness condition saying that the recovered instance does not
have extra facts that were not present in I. Note that the earlier instance U does
have a homomorphism into I.
Putting it all together, we now formally capture the two desiderata discussed
above (data exchange equivalence and homomorphic containment) into the follow-
ing definition of a
relaxed chase-inverse
.
Definition 6
(Relaxed chase-inverse).
Let
M
be a GLAV schema mapping from a
schema
S
1
to a schema
S
2
. We say that
M
is a GLAV schema mapping from
S
2
to
S
1
such that, for every instance I over S
1
,
the following properties hold for the instance U D
chase
M
.
chase
M
.I//:
(a)
U $
M
I
M
is a
relaxed chase-inverse
of
M
if
(data exchange equivalence w.r.t.
M
),
(b)
U ! I
(homomorphic containment).
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.
