Database Reference
In-Depth Information
Algorithm 2.
Completed PUL streaming backward application
Require:
A completed PUL
Δ
↔
applicable on a document
D
, the sequence of events
[
e
1
, ..., e
n
]
for a document
D
∈O
(
Δ
↔
,D
)
1.
I
=
{V
(
p
(
op
))
|o
(
op
)
∈{
ins
,
repN
,
repC
}∧op ∈ Δ
↔
}
be the nodes inserted by
Δ
↔
2.
R
=
{T
(
t
(
op
))
|o
(
op
)
∈{
del
,
repN
}∧op ∈ Δ
↔
}∪{T
(
γ
(
t
(
op
))
|o
(
op
)=
repC
,op ∈
Δ
↔
}
be the subtrees removed by
Δ
↔
3.
for
i
=1
to
n
do
4.
if
e
i
=
sDoc
()
then
5.
emit
e
i
6.
else if
e
i
=
eDoc
()
then
T
if
∃ T ∈ R
s.t.
T
is the document root
∅
7.
R
root
=
otherwise
8.
emit
Events
(
R
root
)
,
e
i
9.
else
n
if
∃
ren
(
e
i
.v, n, n
)
∈ Δ
↔
e
i
.n
otherwise
s
if
∃
repV
(
e
i
.v, s, s
)
∈ Δ
↔
e
i
.s
otherwise
10.
n
=
s
=
11.
if
e
i
=
sElem
(
v, n
)
then
{T
1
, ..., T
n
}
if
∃
[
T
1
, ..., T
n
]
removal group in
R
s.t.
R
(
T
n
)
s
v
12.
R
←
=
∅
otherwise
if
v
∈ I
s.t.
v/
c
v
then
emit
Events
(
R
←
)
end-if
13.
14.
R
attr
=
{T
1
, ..., T
n
|∀i,
1
≤ i ≤ n, T
i
∈ R,R
(
T
i
)
/
a
v}
15.
if
v∈ I
then
emit
sElem
(
v, l, n
)
,Events
(
R
attr
)
end-if
16.
R
=
R \
(
R
←
∪ R
attr
)
17.
else if
e
i
=
eElem
(
v, n
)
then
{T
1
, ..., T
n
}
if
∃
[
T
1
, ..., T
n
]
removal group in
R
s.t.
R
(
T
n
)
/
c
v
18.
R
=
∅
otherwise
19.
if
v∈ I
then
emit
Events
(
R
)
,
eElem
(
v, n
)
end-if
R
=
R \ R
20.
else if
e
i
=
attr
(
v, n, s
)
then
21.
22.
if
v∈ I
then
emit
attr
(
v, n, s
)
end if
23.
else if
e
i
=
text
(
v, s
)
then
{T
1
, ..., T
n
}
if
∃
[
T
1
, ..., T
n
]
removal group in
R
s.t.
R
(
T
n
)
s
v
24.
R
←
=
otherwise
25.
if
v
∈ I
s.t.
v/
c
v
then
emit
Events
(
R
←
)
end-if
26.
R
=
R \ R
←
27.
if
v∈ I
then
emit
text
(
v, s
)
end if
28.
end if
29.
end if
30.
end for
Ensure:
The sequence of events emitted models the document
D
.
∅
Proof Sketch.
The inverse application of a completed PUL
Δ
↔
must (
i
)removeall
inserted nodes; (
ii
) restore the original value and name of nodes, and (
iii
) insert back in
the document any removed node in its original position. When the updated document
is processed any node that has been inserted by
Δ
↔
(the nodes in
I
) is not emitted
(removed). Otherwise the node is emitted back with its original value and name, which
is retrieved considering the
ren
and
repV
operations in
Δ
↔
. In this process, the node
labels and the set of removed subtrees R are used to determine if any node must be
