A New Labeling Scheme without Re-labeling Using Circular Concepts for Dynamic XML Data

XML has become the new standard for storing and exchanging data in the Internet. As demand for efficiency in handling XML document grows, labeling scheme has become an important topic in data storage. Recent works on labeling schemes emphasize the dynamic XML environments where frequent updates to XML documents are expected. In these researches, an insertion of a new node into the XML document triggers re-labeling of pre-existing nodes. In this paper, we introduce a new labeling scheme, circle labeling scheme. In this paper, XML documents are represented in a circular form, and we propose three concepts for noble labeling scheme. The notion of Radius is applied to support inclusion of new nodes at arbitrary positions in the tree. This eliminates the need for re-labeling existing nodes and prevents the label length from growing, and mitigates conflict with existing labels. Efficient storage of labels is supported by the use of concepts rotation number and root circle/extension circle. The proposed scheme is tested against three other labeling schemes to show its efficiency.