Database Reference
In-Depth Information
Example 20.20 Let R
1
be a schema consisting of a binary relation
E
, R
2
a schema
consisting of a binary relation
F
and a unary relation
G
,and
M
=(R
1
,
R
2
,
Σ
) with
Σ
aset
of st-tgds consisting of the following dependency:
E
(
x
,
z
)
∧
E
(
z
,
y
)
→
F
(
x
,
y
)
∧
G
(
z
)
.
(20.5)
Let
M
1
be a mapping from R
2
to R
1
specifiedbytgd:
F
(
x
,
y
)
→∃
z
(
E
(
x
,
z
)
∧
E
(
z
,
y
))
.
(20.6)
It is straightforward to prove that
M
1
is a recovery of
M
. In fact, if
S
is an instance of R
1
and
T
is the canonical universal solution for
S
under
M
, then we have that (
S
,
T
)
∈M
and
(
T
,
S
)
∈M
1
, from which we conclude that (
S
,
S
)
∈M◦M
1
. Similarly, if
M
2
is a mapping
from R
2
to R
1
specified by tgd:
G
(
z
)
→∃
x
∃
y
(
E
(
x
,
z
)
∧
E
(
z
,
y
))
,
(20.7)
then we also have that
M
2
is a recovery of
M
. On the other hand, if
M
3
is a mapping from
R
2
to R
1
specifiedbytgd:
F
(
x
,
y
)
∧
G
(
z
)
→
E
(
x
,
z
)
∧
E
(
z
,
y
)
,
(20.8)
then we have that
M
3
is not a recovery of
M
. To see why this is the case, consider an
instance
S
of R
1
such that:
E
S
=
{
(1
,
1)
,
(2
,
2)
}
.
Next we show that (
S
,
S
)
∈ M ◦M
3
. By the sake of contradiction, assume that (
S
,
S
)
∈
M ◦M
3
,andlet
T
be an instance of R
2
such that (
S
,
T
)
∈M
3
.Given
that (
S
,
T
) satisfies st-tgd
(20.5)
,wehavethat(1
,
1), (2
,
2) are elements of
F
T
and 1, 2 are
elements of
G
T
. But then given that (
T
,
S
) satisfies tgd
(20.8)
, we conclude that the tuples
(1
,
2), (2
,
1) are elements of
E
S
, which leads to a contradiction.
Finally, let
∈M
and (
T
,
S
)
M
4
be a mapping from R
2
to R
1
specified by tgds
(20.6)
and
(20.7)
.In
this case, it is possible to prove that
.Infact,nextwe
introduce some characterizations of the notion of maximum recovery that can be used to
prove this fact.
M
4
is a maximum recovery of
M
M
is an inverse of a mapping
To check whether a mapping
M
, a condition that depends
M
is
equal to the identity mapping. A similar situation holds for the case of the notion of quasi-
inverse. On the other hand, verifying whether a mapping
M
needs to be checked, namely that the composition of
only on
M
and
M
with
M
is a maximum recovery of a
M
with every other recovery of
mapping
. Given that such a test
is more complicated, it would be desirable to have an alternative condition for this notion
that depends only on the input mappings. The next proposition gives one such condition.
M
requires comparing
M
M
a
Proposition 20.21
Let
M
be a mapping from a schema
R
1
toaschema
R
2
, and
M
is a maximum recovery of
recovery of
M
.Then
M
if and only if:
