Dynamic labeling scheme for XML updates

Nowadays several labeling schemes are proposed to facilitate XML query processing, in which structural relationships among nodes could be quickly determined without accessing original XML documents. However, previous node indexing often encounters some troublesome problems when updates take place, such as a large amount of labels requiring re-labeling, huge space requirements for the updated labels, and inefficient determination of structural relationships. In this paper, we propose a novel labeling scheme that not only completely avoids re-labeling but also improves the performance of determining the structural relationships when XML documents are frequently updated at arbitrary positions. The fundamental difference between our scheme and previous ones is that, the gain in update performance of our labeling scheme does not come at the expense of the label size and the query performance. In particular, instead of completely assigning new labels for inserted nodes, the deleted labels are reused in our labeling scheme for encoding newly inserted nodes, which could effectively lower the label size. Moreover, we formally analyze the effectiveness of our proposed labeling scheme. Finally, we complement our analysis with experimental results on a range of real XML data.