Database Reference
In-Depth Information
this instance. The second condition in
Proposition 20.21
is a desirable property for an in-
verse mapping. Intuitively, given a mapping
M
from a schema R
1
to a schema R
2
and
M
from R
2
to R
1
, mapping
M
does not lose information when bringing
a mapping
back the data exchanged by
M
, if the space of solutions of every instance of R
1
does not
M ◦M
. That is, for every instance
S
of R
1
, it should hold that
change after computing
M◦M
◦M
). In general, recov-
eries do not satisfy this condition, but
Proposition 20.21
shows that maximum recoveries
satisfy it. And not only that, it also shows that the notion of maximum recovery can be
characterized in terms of this condition.
S
OL
M
(
S
)=S
OL
(
S
) (or more succinctly,
M
=
M◦M
◦M
Example 20.22 (
Example 20.20
continued) Recall that the mapping
M
in
Example
20.20
is specified by the following st-tgd:
E
(
x
,
z
)
∧
E
(
z
,
y
)
→
F
(
x
,
y
)
∧
G
(
z
)
,
while recovery
M
4
of
M
is specified by the following tgds:
F
(
x
,
y
)
→∃
z
(
E
(
x
,
z
)
∧
E
(
z
,
y
))
,
G
(
z
)
→∃
x
∃
y
(
E
(
x
,
z
)
∧
E
(
z
,
y
))
.
Next we use
Proposition 20.21
to show that
M
4
is a maximum recovery of
M
. Given that
M
4
is a recovery of
M
,wehavethat
M ⊆M◦M
4
◦M
. Thus, given that D
OM
(
M
)=R
1
,
we conclude from
Proposition 20.21
that to prove that
M
4
is a maximum recovery of
M
,
we only need to show that
M ◦M
4
◦M ⊆M
.
Let (
S
,
T
)
∈ M ◦M
4
◦M
. To prove that (
S
,
T
)
∈ M
, we need to show that (
S
,
T
)
satisfies the st-tgd that specifies
, that is, we have to prove that for every pair of tuples
(
a
,
b
), (
b
,
c
) in
E
S
,where
a
,
b
,
c
are not necessarily distinct elements, it holds that (
a
,
c
)
M
∈
F
T
and
b
G
T
. To prove this, first notice that given that (
S
,
T
)
∈
∈M ◦M
4
◦M
,thereexist
instances
S
1
of R
1
and
T
1
of R
2
such that (
S
,
T
1
)
∈M
, (
T
1
,
S
1
)
∈M
4
and (
S
1
,
T
)
∈M
.
Thus, given that (
a
,
b
), (
b
,
c
) are elements of
E
S
, we conclude that (
a
,
c
)
F
T
1
and
b
G
T
1
.
∈
∈
Hence, from the definition of
M
4
and the fact that (
T
1
,
S
1
)
∈M
4
, we conclude that there
exist elements
d
,
e
and
f
such that:
E
S
1
.
{
(
a
,
d
)
,
(
d
,
c
)
,
(
e
,
b
)
,
(
b
,
f
)
}⊆
F
T
and
b
G
T
,whichwasto
Therefore, given that (
S
1
,
T
)
∈M
, we conclude that (
a
,
c
)
∈
∈
be shown.
On the other hand, it is claimed in
Example 20.20
that the mapping
M
1
specifiedbythe
dependency
F
(
x
,
y
)
→∃
z
(
E
(
x
,
z
)
∧
E
(
z
,
y
)) is not a maximum recovery of
M
(although
it is a recovery of
). To see why this is the case, let
S
,
T
be instances of R
1
and R
2
,
respectively, such that:
M
E
S
F
T
=
{
(1
,
2)
,
(2
,
3)
}
=
{
(1
,
3)
}
G
T
=
{
4
}
.
