Efficient querying and updating of XML data: the Rainforest data structure
Lourens E. Veen · 2007
With the advent of the World Wide Web and the increase in information sharing it has brought, information interchange formats based on XML have become more and more important, and the need has arisen to store and process semistructured data. Prior work has mainly focused on developing XML extensions for relational database systems, with a focus on querying. This research takes a different tack, focusing on native XML databases and updates. In this report, I describe a novel data structure for native XML databases called the Rainforest. I show that an optimal renumbering-free encoding of an XML tree can not exist, and instead present a design for a nonoptimal, but under random insertion efficient encoding. A (to my knowledge) novel variant of the B-tree called the compressed B-tree is introduced, which supports random updates and can store XML elements that are encoded according to this encoding. The Rainforest itself is introduced as a forest of these compressed B-trees, with XML elements of the same type stored together in a single tree. The Rainforest also contains a Liana, which is a doubly linked list linking all elements together in document order for easy traversal. Finally, a query algorithm very much like the Holistic Twig Join is introduced for evaluating ancestor-descendant twig pattern queries on the Rainforest. I complement this theoretical work with experimental results showing various properties of the encoding scheme, the compressed B-trees and the effect of the Liana on performance.