Database Reference
In-Depth Information
T(s) = T(s, ab) T(s, ac)
U
T(s, ab)
T(s, ac)
s
s
s
1
1
1
n
1
n
1
n
1
4
a
b
a
b
a
c
2
2
4
2
5
n
2
n
3
n
2
n
3
n
2
n
3
e
f
2
3
n
4
n
4
Fig. 3.
An example of
T
(
s
)
(a) T(s) = T(s, ac*) T(s, bc*)
U
(b) G
bc*
T(s, ac*)
T(s, bc*)
t
1
t
2
t
3
s
1
s
1
s
1
c
n
1
n
1
n
1
b
c
a
3
n
4
c
6
n
6
c
6
a
3
n
4
c
6
n
6
c
6
b
4
n
3
c
6
n
5
c
6
q
I
b
4
c
6
n
2
n
2
n
2
e
2
g
2
h
3
f
3
g
2
h
3
g
2
h
3
n
3
n
5
n
7
n
3
n
5
n
7
n
4
n
6
Fig. 4.
(a)
T
(
s
) and (b) Glushkov automaton
G
bc∗
subtrees
t
1
, ··· ,t
m
.Foratree
t
,by
t
(
a
i
) we mean the tree obtained from
t
by
replacing the label of the root of
t
by
a
i
.
We now define
T
(
a, r
) formally. For a label
a
and
r ∈ E
(
d
(
a
)),
T
(
a, r
)isaset
of trees defines as follows. We assume that every tree in
T
(
a, r
) is unordered.
{n
(
F, F
a
1
, ··· ,F
a
m
)
T
(
a, r
)=
| n
is a node satisfying (A),
F
is a forest satisfying (B),
F
a
1
, ··· ,F
a
m
},
are forests satisfying (C)
(A)
l
(
n
)=
a
1
and
type
(
n
)=
r
.
(B) Let
sym
(
r
#
)
.Then
F
=
t
1
(
a
1
)
, ··· ,t
k
(
a
k
),
where
t
i
∈ T
((
a
i
)
,r
i
)and
r
i
∈ E
(
d
((
a
i
)
)) (1
\ sym
∗
(
r
#
)=
{a
1
, ··· ,a
k
}
≤ i ≤ k
).
(C) Let
sym
∗
(
r
#
)=
{a
1
, ··· ,a
m
}
.Then
F
a
i
=
t
1
(
a
i
)
, ··· ,t
k
i
(
a
i
)(1
≤ i ≤ m
),
=
T
((
a
i
)
)=
r∈E
(
d
((
a
i
)
))
T
((
a
i
)
,r
).
where
{t
1
, ··· ,t
k
i
}
Example 2.
Let
D
=(
d, s
) be a DTD, where
d
(
s
)=(
a|b
)
c
∗
,
d
(
a
)=
e|f
,
d
(
c
)=
g|h
,
d
(
b
)=
d
(
g
)=
d
(
h
)=
.
T
(
s
)=
T
(
s, ac
∗
)
∪ T
(
s, bc
∗
) is shown in Fig. 4(a).
We need one more definition. Let
S
be a set of nodes in a tree
t
.The
s-partition
of
S
is a partition of
S
such that for any nodes
n, n
∈ S
,
n
and
n
belong to the
same subset
iff
n
and
n
are siblings in
t
. Thus, for the s-partition
P
1
, ··· ,P
k
of
S
, every node in
P
i
has the same parent node, say
n
p
, for any 1
≤ i ≤ k
,and
n
p
is called the
parent
of
P
i
.
