Database Reference
In-Depth Information
as element 2 is not in
G
T
.However,(
S
,
T
)
It is clear that (
S
,
T
)
∈M
∈M ◦M
1
◦M
since
for the instances
T
1
,
S
1
of R
2
and R
1
, respectively, such that:
F
T
1
E
S
1
=
{
(1
,
3)
}
=
{
(1
,
4)
,
(4
,
3)
}
G
T
1
{
}
=
2
we have that (
S
,
T
1
)
∈ M
, (
T
1
,
S
1
)
∈ M
1
and (
S
1
,
T
)
∈M
. Thus, we conclude that
M
1
does not satisfy condition (2) in
Proposition 20.21
, from which we conclude that
M
1
is not
M
a maximum recovery of
.
As we pointed out before, the main motivation for the introduction of the notion of max-
imum recovery is to have an inverse operator that is defined for every mapping specified
by st-tgds. Here, we identify the class of mappings for which this operator is defined by
providing a necessary and sufficient condition for the existence of maximum recoveries.
In particular, we use this condition to show that every mapping specified by a finite set of
st-tgds admits a maximum recovery.
Recall that in
Section 20.1
we introduced the notion of a strong witness to characterize
invertibility for the class of mappings that are total and closed-down on the left. More
precisely, given a mapping
from a schema R
1
to a schema R
2
and instances
S
,
T
of R
1
and R
2
, respectively,
T
is a strong witness for
S
under
M
if for every instance
S
of R
1
M
S
OL
M
(
S
), it holds that
S
⊆
such that
T
S
. It turns out that by weakening this condition,
one can characterize the existence of maximum recoveries. Formally, given a mapping
∈
M
from a schema R
1
to a schema R
2
and instances
S
,
T
of R
1
and R
2
, respectively,
T
is a
witness
for
S
under
if for every instance
S
of R
1
such that
T
S
OL
M
(
S
), it holds that
M
∈
S
OL
M
(
S
). Moreover,
T
is a witness solution for
S
under
⊆
M
S
OL
M
(
S
)
if
T
is both a
M
solution and a witness for
S
under
.
The notion of a witness is indeed weaker than the notion of a strong witness, as the next
result shows.
Proposition 20.23
is a finite set of st-tgds,
S an instance of
R
1
and T an instance of
R
2
. Then every strong witness for S under
Let
M
=(R
1
,
R
2
,
Σ
)
be a mapping, where
Σ
M
is
a witness for S under
M
.
Proof
The proposition is a corollary of the fact that if
M
=(R
1
,
R
2
,
Σ
), with
Σ
asetof
st-tgds, and
S
1
,
S
2
are instances of R
1
such that
S
1
⊆
⊆
S
2
,thenS
OL
M
(
S
2
)
S
OL
M
(
S
1
).
Proposition 20.24
is a finite set of st-tgds,
and S an instance of
R
1
. If T is a universal solution for S under
M
, then T is a witness
solution for S under
M
.
Let
M
=(R
1
,
R
2
,
Σ
)
be a mapping, where
Σ
Proof
In the proof of
Proposition 20.8
, we show that if
T
is a universal solution for
S
S
OL
M
(
S
) (this is a corollary of the fact
that a mapping specified by a finite set of st-tgds is closed under target homomorphisms,
as shown in
Proposition 21.1
in
Section 21.1
). Thus, we have already provided a proof of
the proposition.
S
OL
M
(
S
),thenS
OL
M
(
S
)
under
M
and
T
∈
⊆
