Database Reference
In-Depth Information
The notion of completed PULs is inspired by completed deltas proposed by [11] in
the context of XML versioning. The goal of the two notions is the same, in that they both
aim at having a compact representation of changes that can be applied either forward (to
actually apply them) or backward (to revert their effects). However, completed deltas
are obtained by comparing two document versions (through diff algorithms) and do not
represent the effects of XQU expressions. As a consequence, both the set of primitive
operations and the associated semantics are different. A peculiar aspect in inverting
updates expressed as PUL is indeed related to the XQU snapshot semantics by which a
PUL is a unordered list of operations, that have to be applied on documents according
to some precedence among operators prescribed by [15] and formalized in a five stage
semantics in [1]. The inversion mechanism proposed in the paper is designed according
to that semantics. By contrast, completed deltas refer to sequences of non-conflicting
operations.
Though our approach is not specifically targeted to a transactional context, the ability
of reverting the effects of XML updates could also be useful in that setting. The no-
tion of compensating transaction as a transaction that semantically undoes the partial
effects of a transaction without performing cascading aborts of dependent transactions,
restoring the system to a consistent state, has been proposed in the context of long-lived
transaction [6,7,10] and is particularly relevant in the context of workflows and web ser-
vices [13]. These types of compensation range from traditional undo, at one extreme, to
application-dependent, special-purpose compensating transactions, at the other extreme.
XML transactions have been investigated in [5,8,9] but the focus was on isolation levels
and lock mechanisms. An approach to atomicity for XML transactions relying on state-
ment undos is proposed in [2]. They consider the update operations in a PUL as separate
transactions and discuss how individual operations can be undone. However, interactions
among different operations in a PUL, e.g., overriding, neither on the same node nor on
nodes bound by hierarchical relationships in the tree, are considered.
7
Concluding Remarks
In this paper we considered updates on XML documents expressed through XQU ex-
pressions and the corresponding dynamic model of updates based on PULs. We in-
vestigated the issue of reverting the effects of an update expression, referring to the
case in which PUL production is decoupled from their application. Two alternative
approaches have been considered: the first one is the inversion of a PUL through an in-
version operator. The second one is the extension of the PUL model (completed PULs)
so that the required information for both a forward and a backward (inverse) applica-
tion are included. We presented, discussed, and implemented in the Qizx library the
algorithms for both inverting a PUL and for the streaming backward application of a
completed PUL. Finally, we contrasted the two proposed approaches through an exper-
imental evaluation. As future work we plan to investigate the correlation between the
inversion operators presented in this paper with the operations proposed in [3] in order
to identify an algebra on PULs. Moreover, we wish to tailor the developed operator in
specific contexts like versioning, transaction, and cloud. Finally, in the current setting,
labeling information is stored within the document. This has the effect of increasing
