Database Reference
In-Depth Information
r
C
C
V
(1,2)
V
(3,4)
V
(5,6)
V
(7,8)
L
1
(1)
L
2
(6)
L
3
(7)
L
1
(3)
L
2
(5)
L
3
(8)
Each
V
node has two attribute values encoding a variable and its negationwith two different
values. For example
V
(1
,
2) indicates that
x
1
is encoded by the data value '1' and
x
1
by
'2'. Also for each clause in the formula we have a
C
node that has three children labeled
L
1
,
L
2
,
L
3
.The
L
i
node holds the data value encoding the
i
th literal in the clause. In the
example above, the second literal of the first clause is
¬
¬
x
3
and hence the data value of
L
1
under the middle
C
node is '6'.
Let us first see that disjunction in schemas leads to intractability.
SM
dtd
(
Proposition 13.4
,
=)
whose source DTD is
nested-relational, the target DTD combines nested-relational rules and rules of the form
a
There is a schema mapping
M ∈
↓
→
b
|
c, and a query Q
∈
UCTQ(
↓
,
=)
so that
CERTAIN
M
(
Q
)
is
CO
NP
-complete.
Proof
Let
D
s
, the source DTD, be
C
∗
V
∗
r
→
V
:@
a
1
,
@
a
2
C
→
L
1
L
2
L
3
L
i
:@
b
where
i
= 1
,
2
,
3. The target DTD
D
t
is defined as
r
→
C
∗
V
∗
V
:@
a
1
,
@
a
2
C
→
L
1
L
2
L
3
L
i
:@
b
L
i
→
K
|
N
where
i
= 1
,
2
,
3. The st-tgds
Σ
st
simply copy the tree
S
ϕ
in the target, guessing a
K
-node
or an
N
-node under each
L
i
-node:
r
/
C
[
L
1
(
x
)
,
L
2
(
y
)
,
L
3
(
z
)]
→
r
/
C
[
L
1
(
x
)
,
L
2
(
y
)
,
L
3
(
z
)]
,
r
/
V
(
x
,
y
)
→
r
/
V
(
x
,
y
)
.
K
means that the literal is set to
true
,
N
means it is set to
false
. Now we need to check
that either a variable and its negation is set to
true
, or there is a clause with all literals set
to
false
. This is done by the following query:
Q
=
yr
V
(
x
,
y
)
,
C
/
L
i
(
x
)
/
K
,
C
/
L
j
(
y
)
/
K
∪
i
,
j
∃
x
∃
r
/
C
[
L
1
/
N
,
L
2
/
N
,
L
3
/
N
]
.
It is easy to verify that
certain
M
(
Q
,
S
ϕ
) is false iff
ϕ
is satisfiable.
Next, we show that setting a fixed number of children (greater than 1) with the same
label can lead to intractability.
