Databases Reference
In-Depth Information
then give the general definition of a chase-inverse [
Fagin et al. 2009b
] and discuss
its properties and its application in the context of schema evolution.
We observe that the schema mapping
M
00
in Sect.
3.2
is similar to the following
general pattern:
P.x;y/ !9
z
.Q.x;
z
/ ^ Q
0
.
z
;y//:
Here, for simplicity, we focus on schema mappings on binary relations. (In partic-
ular,
M
00
can be forced into this pattern if we ignore the major field in the two
relations
Takes
and
Takes
00
.) 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
0
is the same as Q.Thus,let
M
be the following schema mapping:
M
W
P.x;y/ !9
z
.Q.x;
z
/ ^ Q.
z
;y//:
M
is a natural candidate inverse of
The following schema mapping
M
:
M
W
Q.x;
z
/ ^ Q.
z
;y/! P.x;y/:
Consider now the source instance I = fP.1;2/;P.2;3/g. Then the result of applying
M
to I is
chase
M
.I/ DfQ.1;n
1
/;Q.n
1
;2/;Q.2;n
2
/;Q.n
2
;3/g;
where n
1
and n
2
are two nulls introduced by the chase (for the existentially
quantified variable
z
). Furthermore, the result of applying
M
to the previous
instance is
chase
M
.
chase
M
.I// DfP.1;2/;P.2;3/;P.n
1
;n
2
/g:
Thus, we recovered the two original facts of I but also the additional fact P.n
1
;n
2
/
(via joining Q.n
1
;2/and Q.2;n
2
/). Therefore,
M
is not an exact chase-inverse
of
. Nevertheless, since n
1
and n
2
are nulls, the extra fact P.n
1
;n
2
/ 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 above type of equivalence between instances with nulls is captured, in
general, by the notion of
homomorphic equivalence
. Recall that two instances I
1
and I
2
are homomorphically equivalent, with notation I
1
$ I
2
,ifthereexist
homomorphisms in both directions between I
1
and I
2
.
We are now ready for the main definition in this section.
M
Definition 3
(Chase-inverse).
Let
M
be a GLAV schema mapping from a schema
M
is a GLAV
schema mapping from
S
2
to
S
1
with the following property: for every instance I
over S
1
,wehavethatI $
chase
M
.
chase
M
.I//.
M
is a
chase-inverse
of
S
1
to a schema
S
2
. We say that
M
if
