Databases Reference
In-Depth Information
5
The Case of Lossy Mappings
We have seen earlier that
chase-inverses
, when they exist, can be used to recover the
original source data either
exactly
, in the case of exact chase-inverses, or
modulo
homomorphic equivalence
, in general. However, chase-inverses do not always exist.
Intuitively, a schema mapping may drop some of the source information, by either
projecting or filtering the data, and hence it is not possible to recover the same
amount of information. In this section, we look at relaxations of chase-inverses,
which we call
relaxed chase-inverses
[
Fagin et al. 2009b
], and which are intended
for situations where there is information loss. Intuitively, a relaxed chase-inverse
recovers the original source data as well as possible.
5.1
Relaxed Chase-Inverses
We consider a variation of the scenario described in Fig.
7.2
. In this variation, the
evolved source schema
S
00
is changed so that it no longer contains the
major
field.
The new source evolution scenario is illustrated graphically in Fig.
7.4
a. The source
evolution mapping
M
00
is now given as:
00
W
Takes
.s;m;
co
/ !9C.
Takes
00
.s;C/ ^
Course
.C;
co
//:
M
The natural “inverse” that one would expect here is the following mapping:
M
W
Takes
00
.s;c/ ^
Course
.c;
co
/ !9M
Takes
.s;M;
co
/:
M
00
. In particular, if
we start with a source instance I for
Takes
where the source tuples contain some
constant values for the
major
field, and then apply the chase with
M
is not a chase-inverse for
First of all, it can be verified that
M
00
andthenthe
M
, we obtain another source instance U for
Takes
where the
reverse chase with
a
b
Schema S
′′
Schema S
M
¢¢
I
Takes
′′
Takes
(007, CS, CS101)
Takes
†
sid
M
J = chase
M
″
(I)
cid
si
major
course
M
¢¢
Takes
′′
(007, c1, CS101)
Course
Course (c1, CS101)
U = chase
M
†
(J)
cid
course
Takes
(007, X, CS101)
Fig. 7.4
(
a
) A case where
M
00
is a lossy mapping. (
b
) Recovery of an instance U such that
U $
M
00
I