Database Reference
In-Depth Information
relation
R
. More precisely,
Σ
34
consists of the following st-tgd:
P
2
(
x
)
∧
F
2
(
x
,
y
)
∧
G
2
(
x
,
y
)
∧
F
2
(
y
,
z
1
)
∧
G
2
(
y
,
z
2
)
→
R
(
z
1
,
z
2
)
.
The output of the algorithm is the sequence of mappings
M
12
,
M
23
,
M
34
, which satisfies
that (
M
12
◦M
23
)
◦M
34
is defined by SO tgd
σ
.
We conclude this section by pointing out that the algorithm sketched in the previous
example can be generalized to any SO tgd. In fact, assume that the nesting depth of an
SO tgd
. For instance, the
nesting depth of SO tgd
(19.4)
is 2 as the depth of the terms
f
(
x
),
g
(
x
) is 1 and the depth
of the terms
f
(
g
(
x
)),
g
(
f
(
x
)) is 2. Then the generalization of the algorithm generates a
sequence of
r
+1 mappings when the input is an SO tgd of nesting depth
r
.
σ
is defined to be the largest depth of the terms that appear in
σ
19.4 Complexity of XML composition
Complexity analysis gave us a key to relational composition, suggesting the formalism of
SO tgds. Is the XML case similar? Are SO tgds sufficient as well? If not, is there another
formalism we could use?
A complexity argument gives a negative answer to these questions: there is no reason-
able formalism at all, unless additional restrictions are imposed.
Theorem 19.15
below
states that the composition problem for XML mappings can be undecidable if data compar-
isons are allowed. This means that there is no decidable formalism capable of expressing
compositions of XML mappings.
Of course later we shall present a class that is not only closed under compositions but
also makes it possible to compute compositions within reasonable time bounds. This, how-
ever, will require restrictions on axes used in mappings, as well as schemas for source and
target documents.
For now, we present the negative result.
+
,
=)
such
Theorem 19.15
There
are
mappings
M
12
and
M
23
in
SM(
↓
,
↓
that
+
,
C
OMPOSITION
(
M
12
,
M
23
)
is undecidable. The same holds for the classes
SM(
↓
,
↓
=)
,
SM(
↓
,
→
,
=)
and
SM(
↓
,
→
,
=)
.
Proof
Our argument relies upon a particular property of the reductions used to show
undecidability in the proof of
Theorem 18.4
: halting of a two-register machine
M
is there
reduced to consistency of a mapping
Σ
st
) all of whose dependencies had
only a conjunction of equalities or inequalities on the target side. For such dependencies,
the target side's satisfaction does not depend on the target tree.
Now we need two fixed mappings for which the composition problem is undecidable.
It is well known that there exists a universal two-register machine
U
, such that it is un-
decidable if for a given
n
the machine accepts with registers initialized to (
n
,
0).Weshall
construct mappings
M
M
=(
D
s
,
D
t
,
12
and
23
and trees
T
n
so that (
T
n
,
r
)
12
23
M
M
∈
M
◦
M
iff and only
if
U
accepts with registers initialized to (
n
,
0).
