基于扩展Dewey编码的XML结构连接算法

摘要

To effectively realize querying XML document and reduce scanning cost of structural joins, inefficient structural join algorithms based on merging are analyzed. Making full use of structural properties of XML, extended Dewey coding is proposed which can quickly judge structural relations, and a improved Stack-Tree-Desc algorithm based on extended Dewey coding is given. Coding length is shorten and space cost is reduced by extended Dewey coding. Binary search is introduced into improved Stack-Tree-Desc algorithm to efficiently jump nodes which are not taken part in structural join. Scanned nodes of AList and DList are cut down and querying efficiency is increased accordingly. Theoretical analysis and experimental results show the accuracy and efficiency of the proposed coding scheme and structural join algorithm.%为有效实现XML文档查询,减少查询时结构连接的扫描代价,分析了基于归并思想的结构连接算法查询效率低的原因,充分利用XML数据的结构特点,提出了能够直接判断结点间结构关系的扩展Dewey编码,基于该编码的改进的Stack-Tree-Desc结构连接算法.应用扩展的Dewey编码,缩短了编码长度,降低了空间成本.改进的Stack-Tree-Desc算法引入二分查找快速跳过不需要参与连接的结点,减少了AList和DList列表中被扫描的结点数量,提高了查询效率.理论分析和实验结果表明了该编码方案以及结构连接算法的准确性和有效性.