Databases Reference
In-Depth Information
a
b
c
d
Fig. 5.3
Several solutions for the companies scenario
inclusion constraint, but it does not fully determine the content of the target. To give
an example, besides solution (b) in Fig.
5.3
, the two target instances (c) and (d) are
also solutions for the same source instance.
By looking at these solutions, we notice two things: (1) solution (c) is more
compact than solution (b); it can be seen that the grayed tuples in solution (b) are
somehow “redundant,” since they do not add any information to that contained in
solution (c); (2) solution (d) contains a tuple (the one with a gray background) with
a ground value (
80;000
) that does not belong to the source instance. In essence, the
space of solutions is quite various: on one side, solutions may have different sizes;
intuitively, we prefer those of smaller size; on the other side, some of them may
contain some “arbitrary” values that do not really follow from the content of the
source instance and from the constraints in
˙
st
[
˙
t
.
It is natural to state a couple of quality requirements for solutions to a mapping
scenario:
First, we would like to restrict our attention to those solutions - which we call
universal
- that only contain information that follows from
I
and
˙
st
[
˙
t
;
Among universal solutions, we would like to select the ones of the smallest size -
called the
core universal solutions
.
To formalize these two notions, we introduce the notion of a
homomorphism
among
solutions. Given two instances
J
,
J
0
over a schema
T
,a
homomorphism
h
J
0
is a mapping of the values of
dom
.J/
to the values in
dom
.J
0
/
such that it maps each
constant to itself, i.e., for each
c
W
J
!
2
const()
.J/
,
h.c/
D
c
, and it maps each tuple in
J
to a tuple in
J
0
, i.e., for each
t
D
R.A
1
W
v
1
;:::;A
k
W
v
k
/
in
J
it is the case that
h.v
k
//
belongs to
J
0
.
h
is called an
endomorphism
h.t/
D
R.A
1
W
h.v
1
/;:::;A
k
W
if
J
0
J
;if
J
0
J
it is called a
proper endomorphism
.
In essence, a homomorphism is a constant-preserving mapping that can be used
to turn one instance into a subset of another. Whenever a homomorphism
h
turns
