Research On Region Numbering Scheme Based XML Structural Join Algorithm

Because XML has its own characters that are different from the traditional data form, the traditional database technology cannot work efficiently. Therefore, it is necessary to research new technologies for XML data according to its special characters. And as one of the most important issues for XML data processing, query technologies have become the focus. In order to solve the key technology problems in XML path expression processing and provide feasible approaches for the large scale XML query application, this paper focus on the two important technologies in query processing which are element numbering scheme and structural join algorithm.Firstly, according to the question that most of the present numbering schemes have poor updating performance, a new dynamic region-based numbering scheme DNS is proposed in this paper. The scheme uses real numbers instead of integers to represent the region. Therefore it can utilize the gap between consecutive nodes to encode the new node or subtree, which can support updates efficiently. And a dynamic redistribution algorithm is proposed which can adjust the codes of some nodes in some parts of the document tree according to the condition of updates. Consequently, it improves the performance of updates more efficiently.Secondly, according to the question of the efficient implementation of structural join, based on the region numbering scheme, one partition_based structural join algorithm PBJ is proposed in this paper. The algorithm utilizes the stack to avoid replication and improves the I/O performance by partitioning the input data set according to the number of buffers instead of the size of available memory. Moreover, a structure named Inverse Tree is proposed according to the question of efficiency of structural join in memory. By establishing the structurefor the input set in memory, it can perform the structural join more efficiently.Finally,the paper conducts some performance tests based on the Native XML data management system Orient-X. The test results show that the dynamic numbering scheme DNS and the structural join algorithm PBJ have the good performance.