Database Reference
In-Depth Information
C
T
2
and, therefore,
T
2
is not a solution for
S
1
under
have that
b
∈
M
. We conclude that
= S
OL
M
(
S
2
).
6. Finally, assume that
A
S
1
=
A
S
2
, and that there exists
b
S
OL
M
(
S
1
)
B
S
2
A
S
1
∈
such that
b
∈
and
B
S
1
. Then we conclude that S
OL
M
(
S
1
)
= S
OL
M
(
S
2
) as in the previous case.
Now, for the sake of contradiction, assume that
M
is an invertible mapping, and let
M
be
a mapping from R
2
to R
1
such that
b
∈
M◦M
= Id
R
1
. Then for every pair
S
1
,
S
2
of instances
of R
1
such that S
OL
M
(
S
1
)
⊆
S
OL
M
(
S
2
), it holds that
S
2
⊆
S
1
. To see why this is the case,
first notice that if S
OL
M
(
S
1
)
⊆
S
OL
M
(
S
2
),thenS
OL
M◦M
(
S
1
)
⊆
S
OL
M◦M
(
S
2
). Thus,
M ◦M
= Id
R
1
,wehavethatS
OL
Id
R
1
(
S
1
)
given that
⊆
S
OL
Id
R
1
(
S
2
). Hence, from the fact
that
S
1
∈
S
OL
Id
R
1
(
S
2
) and, therefore,
S
2
⊆
S
1
.
Next we use the property shown above to obtain a contradiction. Assume that
S
1
and
S
2
are instances of R
1
such that:
A
S
1
=
S
OL
Id
R
1
(
S
1
), we conclude that
S
1
∈
A
S
2
= 0
{
1
}
B
S
1
= 0
B
S
2
=
{
1
}
Then we have that S
OL
M
(
S
1
)
⊆
S
OL
M
(
S
2
), which contradicts the property shown above
since
S
2
⊆
S
1
.
In
Example 20.6
, we introduced a second condition that invertible mappings satisfy, and
that is stronger that the unique-solutions property. Formally, a mapping
from a schema
R
1
to a schema R
2
is said to satisfy the
subset property
if for every pair
S
1
,
S
2
of instances
of R
1
,wehave
M
S
OL
M
(
S
1
)
⊆
S
OL
M
(
S
2
)=
⇒
S
2
⊆
S
1
.
It turns out that this condition is a necessary and sufficient condition for the existence of
inverses for the class of mappings specified by st-tgds.
Theorem 20.7
Let
M
be a mapping specified by a finite set of st-tgds. Then
M
is invert-
ible if and only if
M
satisfies the subset property.
The previous result does not extend to the entire class of mappings that are total and closed-
down on the left. In fact, a characterization of invertibility requires a stronger condition,
which is defined as follows. Let
be a mapping from a schema R
1
to a schema R
2
,
S
be
an instance of R
1
and
T
be an instance of R
2
.Then
T
is a
strong witness
for
S
under
M
if for every instance
S
of R
1
such that
T
∈
M
S
OL
M
(
S
), it holds that
S
⊆
S
. Moreover,
T
is
a strong witness solution for
S
under
M
if
T
is both a solution and a strong witness for
S
under
.
To give some intuition about the notion of strong witness, we show in the following
proposition a way to construct strong witnesses for invertible mappings that are specified
by st-tgds.
M
Proposition 20.8
be an invertible mapping from a schema
R
1
toaschema
R
2
that is specified by a set of st-tgds. Then for every instance S of
R
1
, each universal solution
T for S under
Let
M
M
is a strong witness solution for S under
M
.
