Dynamic Containment Based Binary String Labeling Approach For XML Tree

Abstract

The labeling scheme is used to label the nodes of an XML tree. Based on the labeling scheme, XML queries can be processed without accessing the original XML document. One more important point for the labeling scheme is to process updates when nodes are inserted into or deleted from the XML tree. In this paper, we propose a node labeling scheme that solves the weak points of the prefix, prime, interval and containment based schemes by supporting efficient insert processing. The weak points of previous schemes are re-labeling when subtree or node insert to XML tree, a large number of nodes that need to be relabeled in the case of an insertion of XML data, and inefficient processing of structural joins. To address this weak point, dynamic containment based binary string labeling approach for XML tree is proposed in this paper. This scheme uses containment based binary string for label dynamic XML tree and concatenation of binary string and character sequences for label insertion XML subtree.