Database Reference
In-Depth Information
Example 20.2 Let R
1
be a schema consisting of a unary relation
S
,letR
2
be a schema
consisting of unary relations
U
and
V
,andlet
M
be a mapping from R
1
to R
2
specified by
st-tgds
S
(
x
)
is invertible since all the information
in the source relation
S
is transferred to both relations
U
and
V
in the target. In fact, the
mapping
→
U
(
x
) and
S
(
x
)
→
V
(
x
). Intuitively,
M
M
specified by dependency
U
(
x
)
M ◦M
=
→
S
(
x
) is an inverse of
M
since
M
specified by the dependency
V
(
x
)
Id
R
1
. But not only that, the mapping
→
S
(
x
) is also
an inverse of
M
, which shows that there need not be a unique inverse.
When is a mapping invertible?
The first basic question about any schema mapping operator is for which class of mappings
it is defined. In particular, for the case of the inverse operator, one would like to know for
which classes of mappings it is guaranteed to exist. We now present existence conditions
for the inverse operator, and use them to show that inverses are not guaranteed to exist for
all the mappings specified by st-tgds.
Let
M
be a mapping from a schema R
1
to a schema R
2
. Then:
• M
satisfies the
unique-solutions property
if for every pair of instances
S
1
,
S
2
of R
1
,we
have
S
OL
M
(
S
1
)=S
OL
M
(
S
2
)=
⇒
S
1
=
S
2
.
• M
is
closed-down on the left
if
and
S
1
⊆
(
S
1
,
S
2
)
(
S
1
,
S
2
)
∈M
S
1
=
⇒
∈M
.
• M
is
total
if S
OL
M
(
S
)
= 0 for every instance
S
of R
1
.
We can use these properties to give a necessary condition for the existence of inverses.
Proposition 20.3
Let
M
be a mapping that is total and closed-down on the left. If
M
is
invertible, then
M
satisfies the unique-solutions property.
Proof
Assume that
M
is a mapping from a schema R
1
to a schema R
2
,andlet
M
be
a mapping from R
2
to R
1
such that
M ◦M
= Id
R
1
is
invertible). Moreover, assume that
S
1
and
S
2
are instances of R
1
such that S
OL
M
(
S
1
)=
S
OL
M
(
S
2
). We need to show that
S
1
=
S
2
.
Given that S
OL
M
(
S
1
)=S
OL
M
(
S
2
),wehavethatS
OL
M◦M
(
S
1
)=S
OL
M◦M
(
S
2
).
Thus, given that
(such a mapping exists since
M
M ◦M
= Id
R
1
, we conclude that S
OL
Id
R
1
(
S
1
)=S
OL
Id
R
1
(
S
2
).There-
fore, from the fact that
S
1
∈
S
OL
Id
R
1
(
S
1
) and
S
2
∈
S
OL
Id
R
1
(
S
2
), we conclude that
S
1
∈
S
OL
Id
R
1
(
S
2
) and
S
2
∈
S
OL
Id
R
1
(
S
1
). But this implies that (
S
2
,
S
1
)
∈
Id
R
1
and (
S
1
,
S
2
)
∈
Id
R
1
and, hence, we conclude from the definition of Id
R
1
that
S
2
⊆
S
1
and
S
1
⊆
S
2
. This con-
cludes the proof of the proposition.
Proposition 20.3
tells us that the spaces of solutions for distinct source instances under an
invertible mapping must be distinct. Thus, one can prove that a mapping does not admit an
inverse by showing that it does not satisfy the preceding condition.
