Updating the Pre/Post Plane in MonetDB/XQuery

We outline an efficient ACID-compliant mechanism for structural inserts and deletes in relational XML document storage that uses a region based pre/size/level encoding (equivalent to the pre/post encoding). Updates to such node-numbering schemes are considered prohibitive (i.e. physical cost linear to document size), because structural updates cause shifts in all pre-numbers after the update point, and require updates of the size of all ancestors, such that the root of the tree becomes a locking bottleneck. We show how such locking can be avoided by updating the size of ancestors using delta-increments, which are transaction-commutative operations. We also reduce the physical cost to the minimum (i.e. linear to update volume) by carefully exploiting the virtual column feature of MonetDB to store pre numbers (virtual columns are never materialized, and thus need not be updated). In our evaluation, we show the overhead of the update-feature in MonetDB/XQuery in terms of added XMark evaluation cost to stay within an acceptable limit (<30% on average).