MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane


Boncz, Peter and Flokstra, Jan and Grust, Torsten and Keulen, Maurice van and Manegold, Stefan and Mullender, Sjoerd and Rittinger, Jan and Teubner, Jens (2006) MonetDB/XQuery - Consistent & Efficient Updates on the Pre/Post Plane. In: 10th International Conference on Extending Database Technology, EDBT 2006, 26-31 March 2006, Munich, Germany (pp. pp. 1190-1193).

open access
Abstract:Relational XQuery processors aim at leveraging mature relational DBMS query processing technology to provide scalability and efficiency. To achieve this goal, various storage schemes have been proposed to encode the tree structure of XML documents in flat relational tables. Basically, two classes can be identified: (1) encodings using fixed-length surrogates, like the preorder ranks in the pre/post encoding [5] or the equivalent pre/size/level encoding [8], and (2) encodings using variable-length surrogates, like, e.g., ORDPATH [9] or P-PBiTree [12]. Recent research [1] showed a clear advantage of the former for efficient evaluation of XPath location steps, exploiting techniques like cheap node order tests, positional lookup, and node skipping in staircase join [7]. However, once updates are involved, variable-length surrogates are often considered the better choice, mainly as a straightforward implementation of structural XML updates using fixed-length surrogates faces two performance bottlenecks: (i) high physical cost (the preorder ranks of all nodes following the update position must be modified—on average 50% of the document), and (ii) low transaction concurrency (updating the size of all ancestor nodes causes lock contention on the document root).
Item Type:Conference or Workshop Item
Copyright:© 2006 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 238692