An Efficient Numbering Scheme for Dynamic XML Trees

It is an essential operation in XML queries to determine the structural relationship between two arbitrary nodes. The numbering scheme is designed to label the XML nodes so that the structural relationships between nodes can be easily determined by comparing their labels without accessing the original XML file. This paper presents a novel XML tree numbering scheme, called BFN, which takes advantage of the property of binary fractional numbers and can completelyavoid re-labeling any existing nodes when the XML update is performed in any case. Our experimental results show that BFN works much better than the existing dynamic numbering schemes considering either the static numbering or the XML data updates.