Database Reference
In-Depth Information
are set to 0
r
[
//
I
i
(
x
,
y
)
/,//
R
/
R
(
x
)]
−→ ⊥
r
[
//
I
i
(
x
,
y
)
/,//
R
/
R
(
y
)]
−→ ⊥
.
The obtained mapping (
D
s
,
D
t
,
Σ
st
) is consistent iff there is a halting run of the given two-
register machine. Thus we have proved that C
ONS
(
+
,
=) is undecidable.
↓
,
↓
Consistency with nested-relational DTDs
We have seen in Part III that quite a few tasks related to XML data exchange become easier
computationally if the schemas are given by nested-relational DTDs (see
Definition 10.5
on page
139
). We start with the case of mappings that do not use =
,
= comparisons. Here
in the case of vertical navigation, we achieve tractability of the consistency problem. When
horizontal navigation is added, the problem becomes intractable again, even with nested
relational DTDs. We leave the proof of these results as an exercise (see
Exercises 22.3
and
22.3
).
Proposition 18.5
For schemas restricted to nested-relational DTDs
•
C
ONS
(
⇓
)
is solvable in polynomial (cubic) time;
•
C
ONS
(
⇓
,
→
)
is
P
SPACE
-complete.
When comparisons are allowed, the situation is somewhat similar: with vertical naviga-
tion, we recover decidability, but when horizontal navigation is added, it is lost again.
Theorem 18.6
Under the restriction to nested-relational DTDs:
•
the problem
C
ONS
(
⇓
,
∼
)
is
N
EXPTIME
-complete;
•
the problem
C
ONS
(
↓
,
→
,
∼
)
is undecidable.
Proof
A modification of the two-register machine reduction gives the undecidability re-
sult (
Exercise 22.3
) and a modification of the reduction in the proof of
Theorem 12.28
gives N
EXPTIME
-hardness already for C
ONS
(
↓
, ,
=) (
Exercise 22.3
). Let us concentrate
on the algorithm giving the upper bound.
Let
Σ
st
) be a schema mapping with the source and target schema given
by nested-relational DTDs,
D
s
and
D
t
. First observe that tree pattern formulae (even with
= and
M
=(
D
s
,
D
t
,
,if
T
is
=) are monotone in the following sense: for any tree pattern formula
ϕ
obtained from
T
by erasing some subtrees and
T
|
. Roughly speaking,
this allows us to consider the smallest tree conforming to the source schema. We define
an operation
◦
on DTDs as turning each
∗
and
?into
=
ϕ
,then
T
|
=
ϕ
and each
+
into
. The mapping
ε
M
=(
D
s
,
D
t
,
M
Σ
st
) is consistent. Since disjunctions are not allowed
in productions, we have only one tree conforming to
D
s
(uptodatavaluesstoredinthe
attributes). The size of this tree is at most
b
s
=
is consistent iff
D
s
D
s
.
=
D
s
,and
T
is a solution for
S
. We shall trim
T
to obtain a single-exponential
Suppose
S
|
