基于扩展前缀编码的左孩子右兄弟结构连接算法  

Left child and right sibling structural join algorithm based on extended prefix-coding

作　　者：文思[1] 文贵华[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510000

出　　处：《计算机工程与设计》2010年第10期2312-2315,2319,共5页Computer Engineering and Design

摘　　要：为了更加有效实现XML文档的结构查询,加强结构连接操作的效率,提出一种新结构连接算法。该算法采用扩展的前缀编码方案,在编码中增加了type、index等字段以利于定位树中结点在祖先结点列表或者后裔结点列表中的位置。该算法通过将XML文档树转换成左孩子右兄弟树,并定位树中一个祖先元素的起始点下标和终结点下标来找到该祖先元素的后裔结点列表。算法时间复杂度分析表明了该算法比现有算法的性能更好。To implement structural query of XML document more effectively,improve the efficiency of structural join a new structural join algorithm that adopts the extended prefix-code scheme by adding two fields of type and index to locate the nodes of tree in the ancestor list and descendant list is proposed.Subsequently,this algorithm translates the XML document tree into left child and right sibling tree,and then locates the descendant list for the ancestor element by its index of start point and index of end point.Time complexity analysis of the proposed algorithms indicated the algorithm has better performance than existing structural join algorithms.

关 键 词：左孩子右兄弟树 结构查询 结构连接算法 前缀编码 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]