German English

Insert-Friendly Hierarchical Numbering Schemes for XML


Google Scholar

publication iconBöhme, Timo; Mimaroglu, Selim; O'Neil, Elizabeth; O'Neil, Patrick; Rahm, Erhard
Insert-Friendly Hierarchical Numbering Schemes for XML
Techn. Report, Univ. of Leipzig


Numbering schemes for labeling XML nodes are the key design element to support generic XML storage and high-efficiency access in relational databases or other reliable stores. In this paper we present a class of hierarchical numbering schemes that combine two prior published schemes [2, 13] by authors of this paper. No schema is required for the data, and streaming access is supported. Our schemes support fast query processing and fast retrieval of document fragments while supporting insertion of new nodes, or sub-trees, at arbitrary positions within a document, without the need to relabel any old nodes. These insertion capabilities are not supported in other numbering schemes that have appeared in the literature. We also present a detailed quantitative
analysis to comparatively evaluate the effectiveness and performance of the new numbering schemes.