Database Reference
In-Depth Information
we know that the answer to GAV-E
QUIVALENCE
is positive if and only if
M
is closed
under target intersection.
We use this observation to analyze GAV-E
QUIVALENCE
. As a first useful step, we need
the following result.
Σ
of st-tgds from a source
Lemma 21.9
The problem of verifying, given finite sets
Σ
,
Σ
is
NP
-complete.
schema
R
s
toatargetschema
R
t
,whether
Σ
logically implies
The proof of this lemma is left as an exercise for the reader (see
Exercise 22.3
). We now
move to the proof of the main result of this section for the case of GAV mappings.
Theorem 21.10
The problem
GAV-E
QUIVALENCE
is
NP
-complete.
Proof
Given that every full st-tgd can be transformed in polynomial time into an equiv-
alent set of GAV st-tgds, and every GAV st-tgd is a full st-tgd, to prove the theorem it is
enough to show that the problem of checking, given a mapping
M
specified by a finite set
of st-tgds, whether
can be specified by a finite set of full st-tgds is NP-complete. In this
proof, we focus into the latter problem.
Assume that
M
M
is a mapping from a source schema R
s
to a target schema R
t
defined
Σ
st
as the “full” part of
Σ
st
is the
by a finite set
Σ
st
of st-tgds. Let us define
Σ
st
. Formally,
mapping obtained from
Σ
st
by dropping the existential quantifiers and the conjuncts with
existentially quantified variables from the right-hand side of each dependency in
Σ
st
.We
Σ
st
and
show next that
M
can be defined by a set of full st-tgds if and only if
Σ
st
define the
same mapping from R
s
to R
t
.
Clearly, if
Σ
st
and
Σ
st
define the same mapping from R
s
to R
t
,then
M
can be defined by
a finite set of full st-tgds. To prove the opposite direction, assume that
M
can be defined
M
be the mapping from R
s
to R
t
defined by
Σ
st
.
by a finite set of full st-tgds, and let
∈M
. For the converse, assume that (
S
,
T
)
∈M
,and
Clearly, (
S
,
T
)
∈M
implies (
S
,
T
)
let
T
be the canonical universal solution for
S
under
M
(see
Section 6.3
for the definition
of this universal solution). Moreover, let
T
1
be the canonical universal solution for
S
under
M
,let
h
be a function that maps every constant in
T
1
to itself and every null value in
T
1
to a fresh constant, and let
T
2
be an instance of R
t
obtained by replacing every value
a
in
T
1
by
h
(
a
). Then, from the fact that
h
is the identity on the constants and (
S
,
T
1
)
∈M
,we
obtain (
S
,
T
2
)
is closed under target homomorphisms that are the identity on
constants (by
Theorem 21.6
). Thus, given that
T
=
T
1
∩
T
2
by definition of these instances
and of
∈M
since
M
Σ
st
, we conclude that (
S
,
T
)
is closed under target intersection (by
Theorem 21.6
). Therefore, given that there exists a homomorphism from
T
to
T
that is
the identity on constants (as
T
is a universal solution for
S
under
∈M
since
M
M
and (
S
,
T
)
∈M
)
and (
S
,
T
)
∈M
, we conclude that (
S
,
T
)
∈M
by using again the fact that
M
is closed
under target homomorphisms that are the identity on constants.
We show next that the problem of verifying, given a finite set
Σ
st
of st-tgds, whether
Σ
st
define the same mapping is NP-complete. From this proof and
the previous discussion, we conclude that the theorem holds as
Σ
st
and its full part
Σ
st
can be constructed in
polynomial time from
Σ
st
.
