Database Reference
In-Depth Information
According to this processing model, there are two alternative approaches to revert
the effects of an update expression. The first one is to invert a PUL through a PUL
inversion operator. This operator, given a PUL
Δ
on a document
D
, produces another
PUL
Δ
−
1
, that, when executed on the document updated according to
Δ
, returns the
original document
D
, thus undoing the updates in
Δ
. This approach however requires
to access document
D
for producing the inverse. An important feature of the PUL op-
erators in [3], by contrast, is document independence: operators on PULs should not
require, whenever possible, to access the document. They rely on structural informa-
tion on the document that is incorporated in the PUL itself through a labeling scheme.
Thus, an alternative approach, to be exploited in contexts where the need of reverting
update effects is known to be likely to arise, is to modify the evaluation of XQU expres-
sions so that they produce
completed PULs
rather than PULs. A completed PUL
Δ
↔
contains the information for being applied either forward (to actually apply updates) or
backward (to revert their effects), and in both cases it can be applied in streaming.
The paper investigates both approaches, proposing a set of inversion rules and a PUL
inversion algorithm, defining completed PULs, and discussing their forward and back-
ward streaming application. Both approaches have been implemented, by modifying
the Qizx [14] library to produce PULs and completed PULs (both represented as XML
documents) and to accept them as input.
The paper is organised as follows. Section 2 introduces some preliminary notions
on XML documents and PULs. PUL inversion is discussed in Section 3, whereas Sec-
tion 4 introduces completed PULs and their backward and forward application. Sec-
tion 5 experimentally compares the two approaches. Section 6 contrasts our approach
with related work. Some concluding remarks are finally presented.
2
Preliminaries
In this section we introduce the adopted representations of XML documents, define
PULs of operations, their semantics, and discuss their streaming evaluation.
2.1
XML Document Representations
A document can be represented as a labeled tree. A document
D
is a tuple
(
V, γ, λ, ν
)
where:
V
is a set of nodes representing elements, attributes or text nodes (for simplicity,
only these types among those in [15] are considered);
γ
is a function associating with
each node its children;
λ
and
ν
are labeling functions associating with each element
and attribute node a name in a set
N
and with each text and attribute node a value in a
set
denote the nodes and the root(s) of a
single tree
D
or of a collection of trees, respectively, and
τ
assigns to each node
v
in
V
a value in the set
V
, respectively. Auxiliary functions
V
and
R
denoting its type. Moreover, auxiliary functions
LS
,
P
and
T
assign to each node its adjacent left sibling, parent and subtree, respectively, when
they exists (
{
e
,
a
,
t
}
, otherwise). Coherently with the XDM model, the attribute value is seen
as a property of the attribute node, whereas textual contents of elements are modeled by
separate nodes. A unique and immutable identifier is associated with each node in
V
,
and, wherever no confusion arises, we do not distinguish nodes from their identifiers.
⊥
