Storing and Querying Large XML Instances
Christian Grün · 2010
After its introduction in 1998, XML has quickly emerged as the de facto exchange format for textual data. Only ten years later, the amount of information that is being processed day by day, locally and globally, has virtually exploded, and no end is in sight. Correspondingly, many XML documents and collections have become much too large for being retrieved in their raw form – and this is where database technology gets into the game. This thesis describes the design of a full-fledged XML storage and query architecture, which represents the core of the Open Source database system BASEX. In contrast to numerous other works on XML processing, which either focus on theoretical aspects or practical implementation details, we have tried to bring the two worlds together: well-established and novel concepts from database technology and compiler construction are consolidated to a powerful and extensible software architecture that is supposed to both withstand the demands of complex real-life applications and comply with all the intricacies of the W3C Recommendations. In the Storage chapter, existing tree encodings are explored, which allow XML documents to be mapped to a database. The Pre/Dist/Size triple is chosen as the most suitable encoding and further optimized by merging all XML node properties into a single tuple, compactifying redundant information, and inlining attributes and numeric values. The address ranges of numerous large-scale and real-life XML instances are analyzed to find an optimal tradeoff between maximum document and minimum database size. The process of building a database is described in detail, including the import of tree data other than XML and the creation of main memory database instances. As one of the distinguishing features, the resulting storage is enriched by light-weight structural, value and full-text indexes, which speed up query processing by orders of magnitudes. The Querying chapter is introduced with a survey on state of the art XML query languages. We give some insight into the design of an XQuery processor and then focus on the optimization of queries. Beside classical concepts, such as constant folding or static typing, many optimizations are specific to XML: location paths are rewritten to access less XML nodes, and FLWOR expressions are reorganized to reduce the algorithmic com-