Home > Explore Content > All Issues > Article View
A Prime Number Labeling Based on Tree Decomposition for Dynamic XML Data Management
Journal of The Korea Society of Computer and Information
Abbr :
JKSCI
2011, 16(4), pp.171-179
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
2011, 16(4), pp.171-179
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
-
As demand for efficiency in handling dynamic XML data grows, new dynamic XML labeling schemes have been researched. The key idea of the dynamic XML labeling scheme is to find ancestor-descendent-sibling relationships and to minimize memory space to store total label, response time and range of relabeling incurred by update operations. The prime number labeling scheme is a representative scheme which supports dynamic XML documents. It determines the ancestor-descendant relationships between two elements by a simple divisibility test of labels. When a new element is inserted into the XML data using this scheme, it does not change the label values of existing nodes. However, since each prime number must be used exclusively, labels can become significantly large. Therefore, in this paper, we introduce a novel technique to effectively reduce the problem of label overflow. The suggested idea is based on tree decomposition. When label overflow occurs, the full tree is divided into several sub-trees, and nodes in each sub-tree are separately labeled. Through experiments, we show the effectiveness of our scheme.
96 Viewed
Print this page
Download PDF