Database Reference
In-Depth Information
Specifically:
remove
a node and its subtree from the sequence (for removing any in-
serted node);
restore
a subtree in its original position in the sequence (for restoring any
removed subtree);
rename
a node (for inverting
ren
operations);
change value
to a node
(for inverting
repV
operations). Consider a completed PUL
Δ
↔
applicable on a docu-
ment
D
, and a document
D
∈O
(
Δ
↔
,D
)
. The algorithm for the backward application
of
Δ
↔
on
D
identifies a set of transformations for
Δ
↔
and applies them on the event
sequence corresponding to
D
, obtaining the sequence of events corresponding to
D
.
Note that no transformation must be applied on a restored subtree, since it is already
restored as in the original document.
Example 7.
Consider the completed PUL
Δ
↔
=
{
del
(5
,<
name
>
EDBT04 W
...
6
<
/
name
>
5
)
,
repV
(6
,
”
VLDB04
”
,
”
EDBT04 W
...
”)
,
repN
(7
,<
author
>
X
25
<
/
author
>
24
,<
author
>
B
.
Catania
8
<
/
author
>
7
}
applicable
to the document in Fig. 1. To backward apply
Δ
↔
, the inserted subtree (rooted at node
24
) must be removed, while the removed subtrees (rooted at node 5 and 7) must be rein-
troduced. The inverse application of an overridden operation poses no problem, since
the corresponding transformation has no effect. For instance, the inversion
repV
re-
quires to change back the value of node
6
, but node
6
will not be considered, as it is
restored by another transformation.
Algorithm 2 realize the backward application of a completed PUL
Δ
↔
, applicable on
a document
D
, on a document
D
∈O
(
Δ
↔
,D
)
, identifying the sequence of events
corresponding to
D
.Given
Δ
↔
and the sequence of events
E
corresponding to
D
,the
algorithm produces the sequence of events
E
corresponding to
D
.The
emit
e
1
, ..., e
n
directive is employed to indicate that the events
e
1
, ..., e
n
are generated. For the sake of
conciseness, we denote the node, name, and value components of an event
e
,as
e.v
,
e.n
,
and
e.s
, respectively. Function
Events
is used to associate a set of subtrees, considered
according to the pre-order traversal of their roots in
D
, with the corresponding sequence
of events. The algorithm works as follows. First, the sets
I
and
R
of the nodes inserted
(that must be removed) and removed (that must be restored) by
Δ
↔
are identified. Then,
the algorithm processes the document. The
sDoc
event is simply emitted back when
encountered, while the other events are distinguished and the transformation applied.
When the
eDoc
event is encountered, in case the root of
D
is present in
R
(denoted
R
root
), it is restored before emitting back
eDoc
. For each other event
e ∈ E
,the
original name and value of node
e.v
are determined (undefined if
e.v
does not have
a name/value property), then one of the following steps is performed:
In case
e
is
sElem
or
text
: if the parent of
e.v
is not being removed, any removed preceding
siblings of
e.v
in
R
(denoted
R
←
) is emitted. Afterwards, if node
e.v
should not be
removed
e
is emitted with the original name and value of
e.v
, (followed by the attributes
of
e.v
in
R
, denoted
R
attr
,if
e
is a
sElem
).
(
i
)
In case
e
is
eElem
:if
e.v
should not
be removed, the children of node
e.v
in
R
(denoted
R
) are emitted, followed by
e
with
the original name and value of
e.v
.
(
ii
)
In case
e
is
attr
:
e
is emitted with the original
name and value of
e.v
, unless
e.v
has to be removed. To avoid restoring multiple times
the same subtree, subtrees are removed from
R
when restored.
(
iii
)
Proposition 4 (Correctness).
Let
Δ
↔
be a completed PUL applicable on a document
D
, and let
D
be a document in
O
(
Δ
↔
,D
)
. The application of Algorithm 2 on
Δ
↔
and
D
produces
D
.
