Databases Reference
In-Depth Information
00
M
W
Takes
.s;m;
co
/ !9C.
Takes
00
.s;m;C/^
Course
.C;
co
//:
00
is the reverse of the direction of
Note first that in the figure the direction of
M
M
00
imply a data flow from the
schema
S
to the schema
S
00
, where facts over
S
00
are required to exist based on facts
over
S
. To enable the application of the same composition techniques as we used for
target evolution, we first need to invert the mapping
the original mapping
M
. Intuitively, the assertions of
M
00
. After inversion, we can
then combine the result, via composition, with the previously obtained
M
ı
M
0
.
From a practical point of view, the important (and ideal) requirement that we need
from an inverse is to be able to recover the original source instance. Concretely, if we
apply the mapping
M
00
on some source instance I and then we apply the candidate
inverse on the result of
M
00
, we would like to obtain the original source instance I.
Here, applying a schema mapping
to an instance I means generating the instance
chase
M
.I/. The next definition captures the requirements of such an inverse.
M
Definition 2
(Exact chase-inverse).
Let
M
be a GLAV schema mapping from a
M
is a GLAV schema mapping from
S
2
to
S
1
with the following property: for every
instance I over S
1
,wehavethatI D
chase
M
.
chase
M
.I//.
M
is an
exact chase-inverse
of
schema
S
1
to a schema
S
2
. We say that
M
if
M
00
:
For our example, consider the following candidate inverse of
M
W
Takes
00
.s;m;c/^
Course
.c;
co
/ !
Takes
.s;m;
co
/
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
,wehavethat
chase
M
.
chase
M
00
.I// equals I.
M
is an exact chase-inverse of
M
00
.
Thus,
M
Since
is a GAV mapping, we can now apply Corollary
1
and compose
M
M
ı
M
0
to obtain a schema mapping from
S
00
to
T
0
. The result of this
composition is the following (GLAV) schema mapping:
with
M
ı
M
ı
M
0
W
Takes
00
.s;m;c/^
Course
.c;
co
/ ^
Takes
00
.s;m
0
;c
0
/ ^
Course
.c
0
;
co
0
/
!9G
Takes
0
.s;m
0
;
co
;G/
3.3
A More General Notion of Chase-Inverses
M
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 schema mapping
