Database Reference
In-Depth Information
ˆ
and (
p
1
,
,and
p
4
σ
4
p
5
σ
5
p
6
σ
6
is obtained from
p
1
σ
1
p
2
σ
2
p
3
σ
3
by performing a transition of
M
.Note
that
p
1
=
p
2
=
p
3
=
σ
1
,
p
2
,
σ
2
,...,
p
6
,
σ
6
)
∈
δ
iff at most one of
p
1
,
p
2
,
p
3
is not equal to
⊥
⊥
and
p
4
=
⊥
is possible as long as
σ
4
is not marked with
.Note
ˆ
that
can be computed in polynomial time.
The source DTD is given as
δ
r
→
zero one q
0
q
1
···
q
f
⊥
τ
1
τ
2
···
τ
m
zero
,
one
→
bit
A
=
where
{
τ
1
,
τ
2
,...,
τ
}
and each label except
r
,
zero
,
one
has a single attribute. The
m
target DTD is given as
r
→
a
1
b
1
tr
1
tr
2
···
tr
d
tr
i
→
tr
a
j
,
b
j
→
a
j
+1
b
j
+1
a
2
n
,
b
2
n
→
cell
tr
:
@st
1
@sym
1
@sym
2
@sym
2
···
@sym
6
@sym
6
cell
:@
a
1
@
a
2
···
@
a
2
n
@
st
@
sym
ˆ
for
i
= 1
,
2
,...,
d
,
j
= 1
,
2
,...,
2
n
.The
cell
nodes store in binary a config-
uration number and a cell number, as well as a state and a decorated tape symbol. The
tr
nodes store
−
1, and
d
=
|
δ
|
ˆ
δ .
The source tree
T
is any tree conforming to the source schema storing a different data
value in each node. The children of the root store data values encoding the states and
tape symbols used in
ˆ
ˆ
δ
. To ensure that
δ
is stored properly on the target side, for each
ˆ
(
p
1
,
σ
1
,
p
2
,
σ
2
,...,
p
6
,
σ
6
)
∈
δ
add a dependency
r
[
p
1
(
u
1
)
,
σ
1
(
v
1
)
,
p
2
(
u
2
)
,
σ
2
(
v
2
)
,...,
p
6
(
u
6
)
,
σ
6
(
v
6
)]
−→
−→
r
/ /
tr
(
u
1
,
v
1
,
u
2
,
v
2
,...,
u
6
,
v
6
)
.
Note that
d
different dependencies are introduced, so each
tr
node in the target tree con-
tains a tuple from
ˆ
.
The data values stored in
T
in two
bit
nodes are used to address the configurations
and their cells. This is done by means of three auxiliary patterns,
First
(
x
),
Last
(
x
),and
Succ
(
x
,
y
) with
x
=
x
1
,
x
2
,...,
x
n
,
y
=
y
1
,
y
2
,...,
y
n
, which roughly speaking implement a
binary counter over
n
bits. In the auxiliary patterns we use disjunction, but since we are
only going to apply them on the source side of dependencies, disjunction can be easily
δ
