Database Reference
In-Depth Information
3 Parallel Updates on
n the Compressed Data
3.1 Basic Update Concep
pts and Parallel Update Problem Definition
The grammar DAG (GD
terminal position within wh
grammar DAG (GD), there
edge (N
1
,I,N
2
) from node N
rule G2 within the gramm
outgoing edge of N
1
refers
hand side of G1. For examp
D):
The grammar DAG (GD) visualizes from which n
hich grammar rule other grammar rules are called. In
e is one node Ni for each grammar rule Gi, and there is
N
1
to node N
2
for each occurrence of a call of the gramm
mar rule G1, such that (counted from left to right) the
to N
2
, if G2 is the I
th
non-terminal occurring in the rig
ple, the GD of Grammar 3 is shown in Figure 3.
non-
the
one
mar
e I
th
ght-
Fig.
3.
Grammar DAG (GD) of Grammar 3
Each prefix P of a g
corresponds to one path in
updates on G.
For any given current c
following elementary upda
complex update operation
operations: delete ccn (de
SubTree as first-child of cc
(newNS(SubTree)).
rammar path GP=[P:t] through the given grammar
the GD. Based on this observation, we use GD for para
r G
allel
context node ccn of the XML document, we simulate
ate operations on the compressed grammar G, as m
ns can be constructed from these elementary upd
el), re-label ccn with the new label y (reLTo(y)), in
n (newFC(SubTree)), insert SubTree as next-sibling of
the
more
date
nsert
ccn
The Update Path (UP):
Fo
newFC(SubTree), newNS(S
document node being repre
define a corresponding upda
The update path contains a
we represent edges in the u
edge (N
k
',t,U) from the copy
the terminal symbol in the
operation U shall be applied
update operation U applied t
For example, let the up
//h//b to z. Then, we get
(JB(X)',2,reLTo(z))
or each elementary update operation U
{ reLTo(z), del
SubTree)) } that is applied to a single selected XM
sented by a grammar path GP=[N
1
,I
1
,…,N
k-1
,I
k-1
,N
k
: t],
ate path UP = [ (N
1
',I
1
,N
2
'), …, (N
k-1
',I
k-1
',N
k
') , (N
k
',t,U
new copy N
i
' of each grammar path node Ni. Furthermo
update path as triples (Start,Index,End). Finally, we add
y N
k
' of the last non-terminal N
k
with the index position
e grammar rule represented by N
k
' to which the upd
d. As a result, the final node of the update path contains
to the t
th
terminal of N
k
'.
pdate operations be re-labeling all the nodes selected
the update paths [ (S',2,HGE(X)'), (HGE(X)',1,JB(X
and
∈
lete,
ML
we
U) ] .
ore,
d an
t of
date
the
d by
X)'),
,
]
[
(S'',4,HGE(X)''),
(HGE(X)'',1,JB(X)'')
(JB(X)'',2,reLTo(z)) ].
