Advanced Storage Structures for Native XML Databases
Dimităr Popov · KOPS (University of Konstanz) · 2012
The XQuery Update Facility has turned native XML databases from static document-oriented database systems to general purpose transactional systems. Consequently, data structures allowing both fast read and write operations have become a necessity. This thesis presents several such structures and focuses on the challenges that emerge by their application in a native XML database. A new algorithm is described, which serves to determine the position of an XML node using its unique identifier. Its formal description is further used as the basis of a proof of the algorithm’s correctness. Another central topic is the efficient storage and modification of records with variable length. Their handling in the context of XML databases is discussed in detail as well as optimizations, which improve the performance. Furthermore, mechanisms for updating different kinds of index structures are proposed along with maintaining index statistics.