L-Tree: A Dynamic Labeling Structure for Ordered XML Data

Download Now Free registration required

Executive Summary

With the ever growing use of XML as a data representation format, an increasing need can be seen for robust, high performance XML database systems. While most of the work focuses on efficient XML query processing, XML databases also need to support efficient updates. To speed up query processing, various labeling schemes have been proposed. However, the vast majority of these schemes have poor update performance. This paper introduces a dynamic labeling structure for XML data: L-Tree and its order-preserving labeling scheme with O(log n) amortized update cost and O(log n) bits per label. L-Tree has good performance on updates without compromising the performance of query processing. The paper presents the update algorithm for L-Tree and analyzes its complexity.

  • Format: PDF
  • Size: 140.5 KB