基于EXN-Tree编码的XML结构连接算法研究

Efficient structural joins on XML documents based on EXN-Tree encoding

提出了EXN-Tree的概念,将XML文档树的节点映射到EXN-Tree,依据EXN-Tree的节点编码生成XML文档树节点数据结构。基于此新型的节点编码结构,就无序无索引节点集和有序有索引节点集两种情况下的XML结构连接算法展开研究,提出了一系列的结构连接算法,解决了无序无索引节点集和有序有索引节点集两种情况下的XML结构连接。分析表明该算法的I/O复杂性优于已有算法,具有良好的性能。

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.