Database Reference
In-Depth Information
Algorithm 1.
Inversion
Require:
APUL
Δ
applicable on a document D
1.
Δ
−
1
=
∅
;
(
o, v
o
)=(
⊥, ⊥
)
2.
;
3. let
(
Δ
v
1
, ..., Δ
v
n
)
be the partition of
Δ
according to the preorder of their target node;
4.
for
i
=1
to
n
do
if not
((
o
=
pAttr
∧v
i
/
¬a
d
5.
v
o
)
∨
(
o
=
rAttr
∧v
i
/
d
v
o
))
then
6.
Δ
v
i
=
applyLocalOverrideRules
(
Δ
v
i
)
;
7.
delOp
=
{o|o ∈ Δ
v
i
,τ
(
v
i
)=
e
,o
(
o
)
∈{
repC
,
repN
,
del
}}
;
(
pAttr
,v
i
)
if
repC
∈ delOp
(
rAttr
,v
i
)
if
repN
∈ delOp ∨
del
∈ delOp
9.
Δ
−
1
=
Δ
−
1
∪ applySInversionRules
(
Δ
v
i
,D
)
10.
end if
11.
end for
12.
Δ
−
1
=
Δ
−
1
∪ applyGInversionRules
(
Δ, D
)
Ensure:
Δ
−
1
is an inverse of
Δ
on
D
according to Definition 2
8.
(
o, v
o
)=
Proof Sketch.
The algorithm first requires to sort the PUL according to the pre-order
traversal of their target nodes, which can be performed in
, employing the
labeling information and standard algorithms. Overridden operation removal then re-
quires a single scan of the PUL, thus
O
(
n
log
n
)
O
(
n
)
. The application of inversion rules of class
S requires to consider each remaining operation and might identify up to
n
+
r
op-
erations,
(
O
(
n
+
r
))
. Finally, the application of the inversion rules of class G might
require, for each operation, to determine the left sibling/parent of the operation target
node in D. Assuming this cost
s
,thecostis
O
(
sn
)
, and, thus, the algorithm complexity
is
O
(
n
log(
n
)+
sn
+
r
)
.
4
Completed PULs
The approach discussed in the previous section, starting from a PUL
Δ
, identifies an-
other PUL
Δ
−
1
which reverts the effects of
Δ
. An alternative approach is to extend the
operations presented in Table 2 with auxiliary information to allow their inverse (i.e.,
backward) application. These extended operations are reported in the last column of
Table 2 and are referred to as
completed operations
. The PUL obtained from
Δ
by re-
placing its operations with the corresponding completed operations is named
completed
PUL
and denoted by
Δ
↔
. Completed PULs can be applied either forward (obtaining
the same effect of the original PUL
Δ
) or backward (obtaining the same effect of one
of its inverses). This approach does not require the explicit identification of an inverse
PUL and avoids to access the document. Indeed, all required data is already contained
in the completed PUL, which can be applied in streaming in both directions.
The forward application of a completed PUL simply consists in the streaming appli-
cation of the corresponding PUL, i.e., ignoring additional information included in com-
pleted operations. The definition of obtainable documents is trivially extended to com-
pleted PULs:
O
(
Δ
↔
,D
)=
O
(
Δ, D
)
. The backward application of a completed PUL
can be performed by applying a different set of transformations on event sequences.
