Database Reference
In-Depth Information
Ta b l e 3 .
Operation inverses
Operation
Inverse
Condition
ins
r
(
v,
[
T
1
, ..., T
n
])
{
del
(
R
(
T
1
))
, ...,
del
(
R
(
T
n
))
}
r ∈{←,→, ↓,,,
A
}
repV
(
v, s
)
{
repV
(
v, ν
(
v
))
}
ren
(
v, l
)
{
ren
(
v, λ
(
v
))
}
{
repN
(
v
,γ
(
v
))
}
{
ins
↓
(
v, γ
(
v
))
}
v
=[]
v
=[]
repC
(
v, v
)
{
insA
(
P
(
v
)
,T
(
v
))
}
{
ins
→
(
LS
(
v
)
,T
(
v
))
}
{
ins
(
P
(
v
)
,T
(
v
))
}
τ
(
v
)=
a
τ
(
v
)
=
a
∧ LS
(
v
)
=
⊥
τ
(
v
)
=
a
∧ LS
(
v
)=
⊥
del
(
v
)
/
repN
(
v,
[])
repN
(
v,
[
T
1
, ..., T
n
])
{
repN
(
R
(
T
1
)
,T
(
v
))
,
del
(
R
(
T
2
))
, ...,
del
(
R
(
T
n
))
}
3.2
PUL Inversion
Starting from the operation inverse, we define the PUL inverse.
Definition 2 (PUL Inverse).
Let
Δ
be a PUL applicable on a document
D
. An inverse
of
Δ
on
D
is a PUL
Δ
−
1
s.t.
∀D
∈O
(
Δ, D
):
O
(
Δ
−
1
,D
)=
{D}
.
In inverting a PUL
Δ
, the following properties must be guaranteed: (
i
) each inverse
operation must be applicable in all the obtainable documents; (
ii
) in case an operation
in
Δ
is overridden (that is, it has no effect on the document), its inverse must have no
effect; and, finally, (
iii
) the relative order of the nodes removed by
Δ
must be restored by
its inverse. As shown by the following example, simply inverting each single operation
in
Δ
independently does not allow to guarantee these properties.
Example 4.
Consider the PUL
Δ
=
{
del
(5)
,
repV
(6
,
“
VLDB04
”)
,
repN
(7
,<
author
>
X
25
<
/
author
>
24
}
applicable on the document in Fig. 1. The inverse of
Δ
, obtained by inverting each sin-
gle operation independently is
Δ
−
1
=
{op
1
,op
2
,op
3
,op
4
}
where
op
1
=
ins
(4
,<
name
>
EDBT04 W
...
6
<
/
name
>
5
)
,
op
2
=
repV
(6
,
“
EDBT04 W
...
”)
,
op
3
=
del
(24)
,
op
4
=
ins
(4
,<
author
>
B
.
Catania
8
<
/
author
>
7
)
}
.
Δ
−
1
exhibits two problems: (
i
) the overridden operation
repV
(6
,
“
VLDB04
”)
has been inverted as
op
2
, that is both unnecessary (the value of node 6 is restored by
op
1
) and not applicable, as node 6 does not belong to any document
D
∈O
(
Δ, D
)
;
(
ii
) the order of the restored nodes
5
and
7
may not be the one in the original document.
To guarantee the first two properties, overridden operations in
Δ
should be removed.
For the last property, special treatment should be devoted to operations
del
and
repN
when their targets are adjacent siblings. In this case, insertion operations of the same
kind with the same target might not preserve the insertion order. To obtain the correct
order,
repN
and
del
operations on adjacent siblings should be grouped together.
Definition 3 (Removal Group).
Given a PUL
Δ
, we denote as a removal group of
Δ
a non-empty ordered sublist
S
=[
op
1
,
..., op
n
]
of
Δ
s.t.
-
o
(
op
i
)
∈{
repN
,
del
},
1
≤ i ≤ n
and
t
(
op
1
)
s
t
(
op
2
)
s
...
s
t
(
op
n
)
,
{op
1
,
.., op
n
}
S
⊃{op
1
,
.., op
n
}
s.t.
S
is a removal group of
Δ
.
-
is maximal, that is,
Example 5.
Consider the PUL
Δ
=
{
del
(7)
,
ren
(5
,
“
title
”
)
,
repN
(5
,<
a
>X <
/
a
>
)
,
del
(11)
}
on
the document in Fig. 1. The removal groups are
[
repN
(5
,<
a
>X <
/
a
>
)
,
del
(7)]
and
[
del
(11)]
.
