Database Reference
In-Depth Information
Proof
Let
S
be an instance of R
1
and
T
a universal solution for
S
under
M
(such a
is specified by a set of st-tgds). Assume that
S
is an instance of
solution exists since
M
S
OL
M
(
S
). Next we show that
S
⊆
R
1
such that
T
∈
S
.
S
OL
M
(
S
),wehavethatS
OL
M
(
S
)
S
OL
M
(
S
).Toseewhythisisthe
Given that
T
∈
⊆
case, let
T
be a solution for
S
under
M
. Given that
T
is a universal solution for
S
under
M
,
we have that there exists a homomorphism from
T
into
T
. Thus, given that
T
S
OL
M
(
S
)
∈
and
is closed under target homomorphisms (see
Proposition 21.1
in
Section 21.1
), we
conclude that
T
∈
S
OL
M
(
S
).
Since
M
M
is invertible, we know that
M
satisfies the subset property. Thus, given
S
OL
M
(
S
),wehavethat
S
⊆
S
, which concludes the proof of the propo-
that S
OL
M
(
S
)
⊆
sition.
In the following theorem, it is shown that the notion of strong witness can be used to
characterize invertibility for the class of mappings that are total and closed-down on the
left.
Theorem 20.9
Let
M
be a mapping from a schema
R
1
toaschema
R
2
, which is total
and closed-down on the left. Then
M
is invertible if and only if every instance of
R
1
has a
strong witness solution under
M
.
The complexity of invertibility
Given that inverses are not guaranteed to exist for the class of mappings specified by st-
tgds, a second basic question about this notion of inverse is whether invertibility is a de-
cidable condition for this class of mappings. If it is decidable, we would like to know its
complexity.
The subset property we have seen earlier can be used to prove that this is indeed a
decidable condition: if a mapping
specified by a set of st-tgds does not have an inverse,
then there exists a polynomial-size counter-example showing that
M
M
does not satisfy the
subset property. This leads to the following complexity result.
Theorem 20.10
The problem of checking, given a mapping
M
specified by a set of st-
tgds, whether
M
is invertible is
CO
NP
-complete.
Proof
We show here the membership of the problem in
CO
NP, and leave
CO
NP-hardness
as an exercise for the reader (see
Exercise 22.3
). Given a mapping
Σ
12
) that
is not invertible, a pair (
S
1
,
S
2
) of instances of R
1
is said to be a witness for the noninvert-
ibility of
M
=(R
1
,
R
2
,
M
if S
OL
M
(
S
1
)
⊆
S
OL
M
(
S
2
) but
S
2
⊆
S
1
(notice that such a pair shows that
M
does not satisfy the subset property). Then it is shown here that for every mapping
M
specified by a set of st-tgds, if
M
is not invertible, then there exists a witness (
S
1
,
S
2
) for
2
), fromwhich the membership
the noninvertibility of
M
such that
S
1
+
S
2
is
O
(
Σ
12
of the problem in
CO
NP immediately follows.
Let
is not in-
vertible. Then we have by
Theorem 20.7
that there exist instances
S
1
,
S
2
of R
1
such that
S
OL
M
(
S
1
)
M
=(R
1
,
R
2
,
Σ
12
),where
Σ
12
is a set of st-tgds, and assume that
M
P
S
2
⊆
S
OL
M
(
S
2
) but
S
2
⊆
S
1
. Thus, there exist
P
in R
1
and
t
0
∈
such that
