Efficient structural joins on XML documents based on EXN-Tree encoding
基于EXN-Tree编码的XML结构连接算法研究

A new encoding model: EXN-Tree encoding was proposed in this paper. At first, concept of EXN-Tree was introduced, and then the nodes of XML document tree were mapped to nodes of EXN-Tree. Finally, node data structure of XML document tree was established according to the node encoding of EXN-Tree. On the basis of EXN-Tree encoding, a series of algorithms were put forward which can deal with the nodes without sorting and indexes and the nodes with sorting and indexes. These algorithms can solve the structural join of XML in the two cases. In the case of the nodes without sorting or indexes, the algorithm simply modified from VPJ algorithm was applied to the new encoding, and better CPU capability was demonstrated. In the case of the nodes with sorting or indexes, the procedure of the algorithm was described in detail, and its I/O complexity was analyzed. The results show that this algorithm has good performance and is superior to the current one in terms of I/O complexity.