Database Reference
In-Depth Information
Fig. 4.
Update DAG for re-la
selected by the query //h//b to
abeling all the nodes of the document shown in Fig.1 that
z
are
(1)
for each non-leaf no
de U
i
in UD do
ng_GD_node( U
i
) ;
i
, I, N
k
) in GD
I, U
k
) to any node U
k
exists in UD) add (U
i
, I, N
k
) to UD
(2)
{ N
i
= correspondin
(3)
for each edge ( N
i
(4)
if (no edge (U
i
, I
D
(5)
}
(6)
EUD = UD ;
(7)
Perform updates on E
EUD as described in Section 3.4.
es on EUD as described in Section 3.5.
node Ni in GD do
oming edges ) delete Ni and all outgoing edges of Ni
(8)
Share identical node
(9)
Top-down for each n
(10)
if ( Ni has no inco
(11)
return EUD ;
Algorithm 1.
Upd
date DAG (UD) isolation from a grammar DAG (GD)
For each non-leaf node U
the grammar DAG, i.e., U
i
that different nodes of the u
outgoing edge (N
i
, I, N
k
) of
add an edge (U
i
,
I
, N
k
) to t
from U
i
to the GD node N
node U
i
for which an edge
not yet exist, such that fina
as the GD. On the UD wi
sharing operations describe
the EUD and performing a
GD edges are reachable by
reachable GD nodes and G
(10)). The remaining and r
result of isolating the origi
resulting EUD.
U
i
in the update DAG, let N
i
be the corresponding node
and N
i
belong to the same grammar rule Gi (line (2)). N
update DAG may correspond to the same node N
i
. For e
f N
i
for which no edge (U
i
, I, U
k
) exists in the update DA
the update DAG (lines (3)-(4)). That is, an outgoing e
N
k
representing Gi's I
th
non-terminal is added to each
e to a UD node U
k
representing Gi's I
th
non-terminal d
ally the UD represents the same number of grammar pa
ith this extensions, called EUD (line (6)), the update
d in the following sections are performed. After comput
all the update and sharing operations, some GD nodes
y a path from the UD root and others are not. As the n
GD edges are useless, they are deleted from GD (lines (
returned extended update DAG (line (11)) represents
inal UD from the GD and performing the updates on
e in
Note
each
AG,
edge
UD
does
aths
and
ting
and
non-
(9)-
the
the
