Database Reference
In-Depth Information
Membership in NP is a corollary of Lemma 21.9 . Thus, we only need to prove that this
problem is NP-hard, for which we reduce from the problem of Boolean conjunctive query
containment. Let
( y ) be two Boolean conjunctive queries, and assume that
U is a fresh relation symbol whose arity is equal to the number of variables in x .Moreover,
let
x
ϕ
( x ) and
y
ψ
M
be the mapping defined by a set of st-tgds consisting of the following dependencies:
U ( x )
ϕ
( x )
U ( x )
→∃
y
ψ
( y ) .
We claim that
M
is definable by a finite set of full st-tgds if and only if
x
ϕ
( x ) is contained
in
y
ψ
( y ). First, assume that
x
ϕ
( x ) is contained in
y
ψ
( y ). Then it is easy to see that
M
is defined by U ( x )
ϕ
( x ). Second, assume that
x
ϕ
( x ) is not contained in
y
ψ
( y ).
In this case, we need to show that
M
cannot be defined by a finite set of full st-tgds. Given
that
x
ϕ
( x ) is not contained in
y
ψ
( y ), there exists an instance T such that
x
ϕ
( x ) holds
in T and
y
ψ
( y ) does not hold in T . Thus, we have that T
|
=
ϕ
( a ), for some tuple a of
constants, but T
|
=
y
ψ
( y ), from which we conclude that ( S , T )
∈M
for a source instance
S such that U S =
.Let T 1 , T 2 be two isomorphic copies of the canonical universal
solution for S under the mapping defined by st-tgd U ( x )
{
a
}
D OM ( T 2 )=0. Then given that T 1 and T 2 mention only null values, we also have that
D OM ( T 1 )
→∃
y
ψ
( y ) such that D OM ( T 1 )
D OM ( T )=/0andD OM ( T 2 )
D OM ( T )=0. But then we have that ( T
T 1 )
and ( T
T 2 ) is not a solution for S
under M as this intersection is equal to T . We conclude that M is not closed under target
intersection and, hence, we conclude by Theorem 21.6 that
T 2 ) are solutions for S under
M
,but( T
T 1 )
( T
M
cannot be defined by a finite
set of full st-tgds, which was to be shown.
We conclude this chapter by considering a similar problem but this time with LAV st-
tgds. That is, we deal with the problem defined below.
P ROBLEM : L V-E QUIVALENCE
I NPUT : Mapping M given by st-tgds
Q UESTION : s
M given by LAV st-tgds?
M
equivalent to a mapping
Again, a priori it is not even clear whether the problem is decidable, but now we can
use the characterizations presented in the previous section to see that this problem reduces
to the problem of checking whether
M
is closed under union. This gives us the desired
complexity bound.
Theorem 21.11
The problem LAV-E QUIVALENCE is NP -complete.
Proof Assume that
M
is a mapping from a source schema R s to a target schema R t
Σ st of LAV st-tgds as follows. For
defined by a finite set
Σ st of st-tgds. Then define a set
every st-tgd
( x , y ) mentions exactly one predicate symbol
U , then do the following. First, assume that U has arity and that U ( u 1 ), U ( u 2 ), ... , U ( u n )
is the sequence of atomic formulae mentioned in
ϕ
( x , y )
→∃
z
ψ
( x , z ) in
Σ st ,if
ϕ
( x , y ). Moreover, the i -th component
of a tuple u of variables is denoted by u i , and for a variable substitution
ϕ
ξ
and variables
Search WWH ::




Custom Search