Database Reference
In-Depth Information
SM
dtd
(
Proposition 13.5
,
=)
whose source DTD is
nested-relational, the target DTD has nested-relational rules except one of the form a
There is a schema mapping
M ∈
↓
→
bbb, and a query Q
∈
CTQ(
↓
,
=)
so that
CERTAIN
M
(
Q
)
is
CO
NP
-complete.
Proof
This time, the mapping itself is defined so that a solution for
S
ϕ
corresponds to a
selection of (at least) one literal for each clause in
. The query only asks if the selection
contains a variable and its negation. Thus the existence of a solution falsifying the query
implies the existence of a well-defined (partial) assignment that satisfies the formula
ϕ
.
The source DTD
D
s
is as in the proof of
Proposition 13.4
, and the target DTD
D
t
is:
ϕ
C
∗
V
∗
r
→
V
:@
a
1
,
@
a
2
C
→
LLL
L
:@
b
L
→
K
?
The st-tgds
Σ
st
are:
r
/
C
[
L
1
(
x
)
,
L
2
(
y
)
,
L
3
(
z
)]
→
r
/
C
[
L
(
x
)
,
L
(
y
)
,
L
(
z
)
,
L
/
K
]
,
r
/
V
(
x
,
y
)
→
r
/
V
(
x
,
y
)
.
Essentially, we copy
S
ϕ
in the target, and with a
K
-child we indicate the chosen literals. As
we demand that in each clause at least one literal be chosen, a solution gives a valuation
satisfying the formula, provided that we have chosen consistently. This is verified by the
query, which is defined as
yr
V
(
x
,
y
)
,
C
/
L
(
x
)
/
K
,
C
/
L
(
y
)
/
K
.
∃
x
∃
Clearly, the query is true if a variable and its negation are chosen.
The examples in the two propositions above involve a lot of guessing on where patterns
could be put in a target tree. If the mapping is specific enough, this is not possible. In
terms of schemas this restriction is well captured by the notion of nested-relational DTDs
(for instance, there is no explicit disjunction). Thus, in the analysis of the remaining two
parameters, st-tgds
and queries, we will be assuming that schemas are given by nested-
relational DTDs.
Hardness due to st-tgds
Even under nested-relational DTDs guessing can be enforced by st-tgds: allowing wild-
card, descendant, or next-sibling leads to intractability.
Proposition 13.6
There exist queries Q
1
,
Q
2
,
Q
3
∈
CTQ(
↓
,
=)
and mappings
SM
nr
(
• M
1
∈
↓
, ,
=)
,
SM
nr
(
+
,
=)
, and
• M
2
∈
↓
,
↓
SM
nr
(
• M
3
∈
↓
,
→
,
=)
such that
CERTAIN
M
i
(
Q
i
)
is
CO
NP
-complete for i
= 1
,
2
,
3
.
