Database Reference
In-Depth Information
2.3
PUL Streaming Application
Given a document represented as a sequence of events
E
,aPULismodeledasan
event
transformer
, which transforms
E
in a new sequence of events corresponding to one of
the obtainable documents. An empty PUL corresponds to an identity transformation.
Each operation in a non-empty PUL requires some event transformation. The order in
which transformations must be applied on the events of a node
v
is the same as in the
staged execution of an XQU expression.
Example 2.
Consider the PUL
Δ
=
{
repC
(2
,
[])
,
ren
(2
,
"issues"
)
}
and the document in Fig.
1. The first operation requires to remove any non-attribute event which occurs between
sElem
(
2
, )and
eElem
(
2
, ). The second one requires to alter these two events re-
placing the name. The transformed event sequence is:
sDoc
()
,
sElem
(1
,
"SigmodRecord"
)
,
sElem
(2
,
"issues"
)
,
attr
(9
,
volume
,
"33"
)
,
attr
(10
,
number
,
"2"
)
,
eElem
(2
,
"issues"
)
, ...,
eDoc
()
.
3
PUL Inverse
In this section we discuss the inversion of operations and PULs.
3.1
Operation Inversion
The inversion of an operation
op
applicable on a document
D
produces one or more
operations that revert the modifications made by
op
on
D
. To revert the effects of a
single operation, multiple operations may be required. Consider the case of a list of
subtrees inserted through a single
ins
: each single subtree must be separatedly deleted.
Definition 1 (Operation Inverse).
Let
op
be an operation applicable on a document
D
. An inverse of
op
on
D
is a PUL
Δ
−
1
op
∀D
∈O
(
op, D
):
O
(
Δ
−
1
op
,D
)=
{D}
s.t:
.
Different PULs can be identified to revert the effects of each operation. The following
approach has been devised:
ins
is reverted by removing all inserted subtrees,
repV
/
ren
by restoring the original value/name of the target node,
repC
by restoring the origi-
nal node children. For node deletions and replacements the introduced nodes must be
deleted, while removed nodes must be placed back in their original position. Attribute
nodes are inserted by an
insA
, while other nodes through
ins
→
, if an adjacent left
sibling exists in
D
, through an
ins
otherwise. Table 3 defines inverse operations.
Example 3.
Consider the document in Fig. 1 and the following operations (the node
identifier is reported as superscript of the node).
op
1
=
ren
(5
,
“
title
”)
,
op
2
=
del
(7)
,
op
3
=
ins
(4
,<
author
>
X
25
<
/
author
>
24
,<
author
>
Y
27
<
/
author
>
26
)
.The inverses are:
Δ
−
1
op
1
=
{
ren
(5
,
“
name
”)
}
,
Δ
−
1
op
2
=
{
ins
→
(5
,<
author
>
B
.
Catania
8
<
/
author
>
7
)
}
,
Δ
−
1
op
3
=
{
del
(24)
,
del
(26)
}
, respectively.
Proposition 1 (Correctness of Operation Inversion).
For any operation
op
applica-
ble on a document
D
,let
Δ
−
1
op
be the inverse PUL obtained according to Table 3. Then
Δ
−
1
op
is an inverse of
op
on
D
, according to Definition 1.
Proof Sketch.
This can be straightforwardly proved by individually considering the
semantics of each operation and of the corresponding inverse as defined in Table 3.
