Databases Reference
In-Depth Information
we point out that an important property of this chase is that it always generates
different values (nulls) for different arguments to the Skolem functions. Hence, for
our example, the equality f.n/D f.n
0
/ can happen only if n D n
0
. As a result, the
above reduces to the following SO tgd:
0
W9f.
Takes
.n;m;
co
/ !
Takes
0
.f.n/;n;
co
//:
The above SO tgd is much simpler and more intuitive than the earlier .Justby
looking at the diagram in Fig.
7.6
, one would expect the overall adapted mapping
from
S
to
T
0
to be as close as possible to an identity schema mapping. The SO tgd
0
accomplishes this desideratum while still incorporating the id generation behavior
via f.n/that is given in the original mapping
.
The reduction algorithm implemented in
Yu and Popa
[
2005
] systematically
replaces every equality between two Skolem terms with the same function sym-
bol by the equalities of their arguments, until all equalities that involve such Skolem
terms are eliminated. The algorithm also eliminates every implication where the
left-hand side contains an equality between two Skolem terms that use different
Skolem functions. Intuitively, such equalities cannot be satisfied during the chase;
hence, the implications that contain them can be dropped. Finally, the algorithm uses
conjunctive-query minimization [
Chandra and Merlin 1977
] type of techniques to
eliminate any redundant relational atoms in the resulting mappings. For example,
in the above , once we replace f.n/ D f.n
0
/ with n D n
0
, the second
Takes
atom becomes
Takes
.n;m
0
;
co
0
/; it can then be eliminated, since it is subsumed by
the first
Takes
atom, and neither m
0
nor
co
0
is used in the right-hand side of the
implication.
The main observation behind this reduction algorithm is that its output SO tgd
(e.g.,
0
)is
chase-equivalent
to the input SO tgd (e.g., ).
M
Definition 7.
Let
M
2
be two schema mappings from
S
to
T
that are spec-
ified by SO tgds (or in particular by GLAV mappings). We say that
M
1
and
M
2
are
chase-equivalent
if, for every source instance I,wehavethat
chase
M
1
.I/ $
chase
M
2
.I/.
M
1
and
Theorem 5
(
Yu and Popa 2005
).
Every SO tgd
is chase-equivalent to its reduced
form
0
.
We note that the above
0
is not logically equivalent to the input . In general, the
notion of chase-equivalence is a relaxation of the concept of logical equivalence. A
systematic study of relaxed notions of equivalence of schema mappings appeared
later in
Fagin et al.
[
2008a
]. For schema mappings specified by GLAV mappings or,
more generally, by SO tgds, the above notion of chase-equivalence turns out to be
the same as the notion of
CQ-equivalence
of schema mappings studied in
Fagin et al.
[
2008a
]. There, two schema mappings
M
2
are CQ-equivalent if for every
source instance I,the
certain answers
of a conjunctive query q are the same under
both
M
1
and
M
1
M
2
. For our example, the CQ-equivalence of
0
and
and is another
argument of why we can use
0
instead of .
