Database Reference
In-Depth Information
Ta b l e 2 .
Update operations
Operation
Description
Conditions
Completed Operation
ins
←
(
v, P
)
ins
→
(
v, P
)
Insert the trees in
P
before/after
τ
(
v
)
=
a
,
∀r∈R
(
P
)
τ
(
r
)
=
a
idem
node
v
ins
(
v, P
)
ins
(
v, P
)
Insert the trees in
P
as first/last chil-
τ
(
v
)=
e
,
∀r∈R
(
P
)
τ
(
r
)
=
a
idem
dren of node
v
ins
↓
(
v, P
)
Inserts the trees in
P
as children of
τ
(
v
)=
e
,
∀r∈R
(
P
)
τ
(
r
)
=
a
idem
node
, in an implementation de-
fined position
v
insA
(
v, P
)
Inserts the trees in
P
as attributes of
node
v
τ
(
v
)=
e
,
∀r∈R
(
P
)
τ
(
r
)=
a
idem
del
(
v
)
Deletes node
v
del
(
v, T
(
v
))
repN
(
v, P
)
Replaces node
v
with the trees in
P
∀r ∈R
(
P
)(
τ
(
r
)=
τ
(
v
)=
a
)
∨
(
τ
(
v
)
=
a
∧τ
(
r
)
=
a
)
repN
(
v, P, T
(
v
))
(possibly none)
repV
(
v, s
)
Replaces the value of node
v
with
s∈V
τ
(
v
)
∈{
t
,
a
}
repV
(
v, s, ν
(
v
))
repC
(
v, v
)
τ
(
v
)=
e
∧
(
v
=[]
∨ τ
(
v
)=
t
)
repC
(
v, v
,T
(
γ
(
v
)))
Replaces the children of node
v
v
or with nothing
with text node
ren
(
v, n
)
Renames node
v
with
n∈N
τ
(
v
)
∈{
e
,
a
}
ren
(
v, n, λ
(
v
))
(undefined if
o
(
op
)=
del
). An operation
op
is applicable on a document
D
if its target
belongs to
D
and the applicability conditions (identified in [3]) of
op
hold. The meaning
of last column will be discussed in Section 4.
A
pending update list
(
PUL
) [15] is an unordered list of operations among those
in Table 2. Since the order of operations is irrelevant, some pairs of operations cannot
occur in the same PUL. Specifically, no pairs of replacement operations of the same
type with the same target (referred to as
incompatible operations
) can occur. For a PUL
to be applicable on a document (cf. function
applyUpdates
in [15]) it must contain
no incompatible operations and all its operations must be applicable on the document.
Operation semantics is specified in [1]. The semantics of operation
ins
↓
is non-
deterministic since the actual position of the inserted nodes group in the target node
is not univocally specified. Thus, the application of an operation
op
to a document
D
produces one document in a set of
obtainable documents
, denoted as
.
The semantics of a PUL
Δ
on a document
D
is obtained by applying the operations
in
Δ
in five stages [1]. At each stage, a subset of the operations are applied to enforce
the precedence relation on operation types specified in [15]. The order of application of
operations within each stage is not prescribed by [15]. Thus, when multiple insertion
operations of the same type with the same target appear in the same PUL, the relative
order of the inserted groups of nodes is not fixed as well. Therefore, the cardinality
of
O
(
op, D
)
is greater than one when
ins
↓
occurs in
Δ
or
Δ
contains more than one
insertion operation of the same type on the same target.
O
(
Δ, D
)
Example 1.
Let
D
be the document in Fig. 1. Operation
op
1
=
del
(14)
is deterministic
and thus
is a singleton. Operation
op
2
=
ins
↓
(16
,<
author
>
G
.
Guerrini
<
/
author
>
)
,
by contrast, may lead to inserting the element as first, second, or last author of the sec-
ond paper, thus
O
(
op
1
,D
)
for
Δ
=
{
ins
↓
(16
,<
author
>
G
.
Guerrini
<
/
author
>
)
,
ins
(4
,<
initP
>
132
<
/
initP
>
)
,
ins
(4
,<
lastP
>
134
<
/
lastP
>
)
}
.
O
(
op
2
,D
)
contains three documents. Finally,
|O
(
Δ, D
)
|
=6
