Database Reference
In-Depth Information
). We conclude that (
f
−
1
=
f
−
1
)=
f
−
1
for
{
u
1
,
u
2
,...,
u
n
}
◦
λ
)
◦
ρ
◦
(
λ
◦
ρ
◦
(
f
◦
σ
)=
σ
.
Thus, given that
S
U
(
a
)
|
=
ϕ
(
σ
(
x
)
,
σ
(
y
)),wehavethat
((
f
−
1
(
x
))
,
(
f
−
1
S
U
(
a
)
|
=
ϕ
◦
λ
)(
ρ
◦
λ
)(
ρ
(
y
)))
.
Σ
st
(given that (
S
,
T
)
Σ
st
,where
Σ
st
is a set of LAV st-tgds
But we have (
S
U
(
a
)
,
T
)
|
=
|
=
Σ
st
, from
and
S
U
(
a
)
⊆
(
x
)
,
→∃
(
x
)
,
z
) is a LAV st-tgd in
S
), and also that
ϕ
(
ρ
ρ
(
y
))
z
ψ
(
ρ
((
f
−
1
|
∃
◦
λ
(
x
))
,
z
). Therefore, by using again the fact
which we conclude that
T
=
z
ψ
)(
ρ
that (
f
−
1
(
x
)
,
z
), which was to be shown.
We show next that the problem of verifying, given a finite set
◦
λ
)
◦
ρ
equals
σ
, we conclude that
T
|
=
∃
z
ψ
(
σ
st
of st-tgds, whether
Σ
st
and Σ
st
define the same mapping is NP-complete. From this proof and the previous
discussion, we conclude that the theorem holds as
Σ
Σ
st
can be constructed in polynomial
time from
Σ
st
.
The membership of the problem mentioned in the previous paragraph in NP is a corol-
lary 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
∃
x
ϕ
(
x
) and
∃
(
y
) be two Boolean conjunctive queries, and assume that
U
,
V
are fresh unary relation
symbols. Moreover, let
y
ψ
M
be the mapping defined by a set
Σ
st
of st-tgds consisting of the
following dependencies:
U
(
z
)
→∃
x
ϕ(
x
)
U
(
z
)
∧
V
(
z
)
→∃
y
ψ
(
y
)
.
We claim that
M
is definable by a finite set of LAV st-tgds if and only if
∃
x
ϕ
(
x
) is con-
tained 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
(
z
)
→∃
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 LAV
st-tgds. Given that
∃
x
ϕ
(
x
) is not contained in
∃
y
ψ
(
y
), there exists a target instance
T
such
that
∃
x
ϕ
(
x
) holds in
T
and
∃
y
ψ
(
y
) does not hold in
T
.Thenlet
S
1
,
S
2
be source instances
such that:
U
S
1
V
S
1
=
{
a
}
=
0
U
S
2
V
S
2
=
0
=
{
a
}
.
We have t ha t (
S
1
,
T
)
|
=
Σ
st
and (
S
2
,
T
)
|
=
Σ
st
,since
T
|
=
∃
x
ϕ
(
x
) and neither
S
1
nor
S
2
satisfies
U
(
a
)
∧
V
(
a
). However, we have that (
S
1
∪
S
2
,
T
)
|
=
Σ
st
,since
S
1
∪
S
2
|
=
U
(
a
)
∧
V
(
a
) and
T
|
=
∃
y
ψ
(
y
). We conclude that
M
is not closed under union and, hence, we
conclude by
Theorem 21.5
that
M
cannot be defined by a finite set of LAV st-tgds, which
was to be shown.
