Database Reference
In-Depth Information
op
1
=
op
(
v,
)
op
2
=
op
(
v,
)
Δ ∪{op
1
,op
2
}→
1
Δ ∪{op
2
}
op ∈{
ren
,
repV
,
repC
,
del
,
ins
,
ins
,
ins
↓
,
insA
}
op
∈{
repN
,
del
}
O1)
op
1
=
op
(
v,
)
op
2
=
repC
(
v,
)
Δ ∪{op
1
,op
2
}→
1
Δ ∪{op
2
}
op ∈{
ins
,
ins
↓
,
ins
}
O2)
op
1
=
op
(
v,
)
op
2
=
op
(
v
,
)
Δ ∪{op
1
,op
2
}→
1
Δ ∪{op
2
}
op
∈{
repN
,
del
},v /
d
v
O3)
op
1
=
op
(
v,
)
op
2
=
repC
(
v
,
)
Δ ∪{op
1
,op
2
}→
1
Δ ∪{op
2
}
v /
¬
d
v
O4)
op
=
ins
r
(
v,
[
T
1
, ..., T
n
])
Δ
=
{
del
(
R
(
T
1
))
, ...,
del
(
R
(
T
n
))
}
Δ ∪{op},Δ
−
1
→
2
Δ, Δ
−
1
∪ Δ
S5)
r ∈{←,→, ↓,,,A}
repN
(
t, γ
(
v
))
t
=[]
ins
↓
(
v, γ
(
v
))
otherwise
Δ ∪{op},Δ
−
1
→
2
Δ, Δ
−
1
∪{op
}
if
op
=
repC
(
v, t
)
op
=
S6)
op
=
repV
(
v, s
)
op
=
repV
(
v, ν
(
v
))
Δ ∪{op},Δ
−
1
→
2
Δ, Δ
−
1
∪{op
}
S7)
op
=
ren
(
v, n
)
op
=
ren
(
v, λ
(
v
))
Δ ∪{op},Δ
−
1
→
2
Δ, Δ
−
1
∪{op
}
S8)
Δ
=
{
insA
(
P
(
v
)
,T
(
v
))
}∪{
del
(
R
(
u
))
| u ∈ p
(
op
)
}
Δ ∪{op},Δ
−
1
→
2
Δ, Δ
−
1
∪ Δ
S9)
t
(
op
)=
v, τ
(
v
)=
a
,o
(
op
)
∈{
repN
,
del
}
Δ
=
{
ins
→
(
LS
(
v
1
)
,
[
T
(
v
1
)
, ..., T
(
v
n
)]
}∪
{
del
(
u
)
| u ∈
i
=1
..n
R
(
p
(
op
i
))
}
Δ ∪{op
1
, ..., op
n
},Δ
−
1
→
2
Δ, Δ
−
1
∪ Δ
{v
1
,...,v
n
}
are the operation targets
,
[
op
1
,...,op
n
] is a removal group
,
τ
(
v
1
)
=
a
,LS
(
v
1
)
=
⊥
G10)
Δ
=
{
ins
(
P
(
v
1
)
,
[
T
(
v
1
)
, ..., T
(
v
n
)]
}∪
{
del
(
u
)
| u ∈
i
=1
..n
R
(
p
(
op
i
))
}
Δ ∪{op
1
, ..., op
n
},Δ
−
1
→
2
Δ, Δ
−
1
∪ Δ
{v
1
, ..., v
n
}
are the operation targets
,
[
op
1
, ..., op
n
] is a removal group
,
τ
(
v
1
)
=
a
,LS
(
v
1
)=
⊥
G11)
Fig. 2.
Inversion rules
The inversion of a PUL
Δ
is computed through the set of inversion rules in Fig. 2. Rules
are categorized in the following three classes:
O Rules that remove overridden operations. Specifically, rule O1 and O3 consider the
case in which a
repN
or a
del
operation on a node
v
overrides other operations
in the subtree rooted at
v
. Rules O2 and O4, are similar in purpose, but consider
the case in which a
repC
is the overriding operation. In all cases, rules in this class
maintain the
repN
,
repC
,or
del
operation and removes the overridden operation.
S Rules that compute the inverses of
ins
,
repC
,
repV
,
ren
, as specified in Table 3.
G Rules that compute the inverse of a removal group. Specifically, rules G10 and G11
produce a deletion for each introduced node and a single insertion for all removed
nodes ensuring the restoration of their original order.
A basic algorithm for computing the inversion consists in the application of the rules
in two stages. When rules in the first stage cannot be applied any more, rules of the
second stage are considered. The rules of class O are considered in the first stage to
remove overridden operations from
Δ
. The rules of classes S and G are considered in
the second stage on a pair of PULs,
Δ
and
Δ
−
1
, the PUL to invert and the inverted
PUL (initially empty). The application of a rule of classes S and G removes one or
more operations from
Δ
and introduces the corresponding inverse operation(s) in
Δ
−
1
.
Example 6.
Consider the PUL
Δ
=
{
del
(5)
,
repV
(6
,
“
VLDB04
”)
,
repN
(7
,<
author
>
X
25
<
/
author
>
24
}
of Example 4. Its inverse, obtained through the application of rules in Fig. 2 is
Δ
−
1
=
