Database Reference
In-Depth Information
del
(24)
}
. In this case, differ-
ently from what happened in Example 4, the overridden operation
repV
(6
,
“
VLDB04
”)
{
ins
(4
,<
name
>
EDBT04 W
...
6
<
/
name
>
5
<
author
>
B
.
Catania
8
<
/
author
>
7
)
,
has
not been inverted and the order of the restored nodes
5
and
7
is preserved.
Proposition 2 (Correctness of the Inversion Rules).
Let
Δ
be a PUL applicable on a
document
D
.ThePUL
Δ
−
1
obtained through the application of the inversion rules in
Fig.2isaninverseof
Δ
according to Definition 2.
Proof Sketch.
Consider a PUL
Δ
applicable on a document
D
and the inverse
Δ
−
1
generated by the inversion rules. The proof of this proposition requires that: (
i
)
Δ
−
1
is
applicable on each document in
O
(
Δ, D
)
,(
ii
) no pairs of incompatible operations are
generated, (
iii
) no partially overridden operation either in
Δ
or
Δ
−
1
exists, (
iv
) nodes
removed by
Δ
are placed back in the correct positions by
Δ
−
1
,(
v
)
Δ
−
1
is determin-
istic. The proof of (
i
) is a straightforward consequence of the removal of overridden
operations and of the operations definition. (
ii
) can be proved considering the algorithm
definition and the applicability of
Δ
on
D
, while (
iii
) considering the operations defini-
tion. The proof of the other points comes directly from the definition of the algorithm,
specifically (
iv
) is ensured by the class G rules, while (
v
) follows from the analysis of
the generated operations.
3.3
Inversion Algorithm
Algorithm 1 presents an efficient procedure for computing the inverse of a PUL
Δ
.The
following functions are exploited in the algorithm:
applyLocalOverrideRules
(
Δ
)
to
apply the reduction rules O1 and O2 in Fig. 2 on
Δ
;
applySInversionRules
(
Δ, D
)
and
applyGInversionRules
(
Δ, D
)
to apply the inversion rules of class S and G.
The inversion algorithm works as follows. An empty PUL
Δ
−
1
is first initialized,
then operations in
Δ
are ordered according to the pre-order traversal of their target
nodes and grouped together. Note that, if an overriding operation
op
is present in a
group, the groups of the overridden operations immediately follow that of
op
. Then,
for each group of operations
Δ
v
i
on a node
v
i
, the algorithm performs the following
steps. (
i
) It checks whether the operations
Δ
v
i
are overridden by operations specified
on an ancestor of
v
i
, in this case they are discarded (this corresponds to the application
of rules O3 and O4), otherwise, the
applyLocalOverrideRules
function is applied on
the operations of
v
i
.(
ii
) Whenever in
Δ
v
i
there is an operation
op
that may override
operations in the subtree rooted at
v
i
,
v
i
is stored along with the relevant information
about
op
.(
iii
) The rules of class S are applied on the remaining operations on
v
i
through
applySInversionRules
, updating
Δ
v
i
and adding the computed inverses to
Δ
−
1
.
When all the partitions have been processed, the remaining operations in
Δ
are all
and only those that belong to a removal group and each removal group is composed
of operations that are contiguous in
Δ
. Function
applyGInversionRules
can thus be
efficiently applied on
Δ
, adding the inverses to
Δ
−
1
.
Proposition 3 (Complexity).
Let
Δ
be a PUL applicable on a document
D
,removing
r
nodes. The complexity of the Algorithm 1 is
where
n
is the size
of
Δ
and
s
the cost of identifying the left sibling/parent of a node in
D
.
O
(
n
log(
n
)+
sn
+
r
)
