Database Reference
In-Depth Information
23
we can take
For
M
M
U
, except that we skip the dependency
r
[
I
1
(
x
,
y
)
,//
R
/
R
(
x
)]
−→ ⊥
as we want to allow arbitrary initial values of the first register.
The mapping
12
ensures that the first register is initialized with the number encoded
in the source tree
T
n
. Recall that
M
M
U
uses the data values stored in subsequent
R
-
nodes as values of the registers:
n
is encoded as the
n
th data value in this path, count-
ing from the root. Therefore, to encode the value of the first register properly in
T
n
,we
enforce concrete values in the initial
n
nodes of this path. The source DTD of
12
is
{
r
→
R
;
R
→
R
| }
where
R
has a single attribute. For
T
n
we take the tree given by
the pattern
r
/
R
(
a
1
)
/
R
(
a
2
)
/.../
R
(
a
n
)
/
where
a
1
,
a
2
,...,
a
n
are arbitrary pairwise differ-
ent data values. The dependencies say that the initial segment of register values is copied
correctly,
M
r
/
R
(
x
)
−→
r
/
R
(
x
)
,
r
//
R
(
x
)
/
R
(
y
)
−→
r
//
R
(
x
)
/
R
(
y
)
,
and that the first register is initialized to the
n
th value of this segment,
r
//
R
(
x
)
/
−→ ∃
yr
/
I
1
(
x
,
y
)
.
M
U
contains a depen-
To see that the copying dependencies work as intended, recall that
dency
r
//
R
(
x
)
//
R
(
x
)
−→ ⊥
, which ensures that the values copied from
T
n
are stored in
the initial segment of the path.
The remaining reductions can be obtained analogously, by modifying corresponding
reductions to the consistency problem (see
Exercise 22.3
)
Theorem 19.15
suggests one possible way of expressing compositions of XML map-
pings: restrict the use of data comparisons. The following result shows that without data
comparisons the composition problem is decidable, but the complexity goes up compared
to the relational case.
Theorem 19.16
C
OMPOSITION
(
M
12
,
M
23
)
is
in
E
XPTIME
for
all
mappings
M
12
,
M
23
∈
SM(
⇓
,
⇒
)
.
{
ϕ
i
→
ψ
i
i
=
Proof
Let
M
12
=(
S
1
,
S
2
,
Σ
12
) and
M
23
=(
S
2
,
S
3
,
Σ
23
), with
Σ
12
=
{
γ
j
→
δ
j
1
,
2
,...,
n
}
and
Σ
23
=
j
= 1
,
2
,...,
m
}
. Given trees
S
|
=
S
1
and
T
|
=
S
3
,we
have to check if there is an interpolating tree
U
.
For a start, consider a variable-free situation. What are the constraints on the interpolat-
ing tree? Clearly, what is imposed by
S
is that some of the target sides of st-tgds from
Σ
12
have to be satisfied in
U
. In contrast, what is imposed by
T
, is that some source sides
of st-tgds from
Σ
23
are
not
satisfied in
U
: indeed,
U
|
=
γ
=
⇒
T
|
=
δ
is equivalent to
T
|
=
δ
=
⇒
U
|
=
γ
. Therefore, the existence of an interpolating tree
U
is equivalent to
