基于区域划分的XML结构连接

作     者：王静 孟小峰 王珊 

作者机构：中国科学院计算技术研究所北京100080 中国人民大学信息学院北京100872 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2004年第15卷第5期

页      面：720-729页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金60073014 60273018 国家高技术研究发展计划(863)2002AA116030 国家教育部科学技术重点项目03044 国家教育部优秀青年教师资助计划 

主　　题：XML查询处理 路径表达式 编码方法 结构连接 

摘      要：结构连接是XML查询处理的核心操作,受到了研究界的关注.高效的算法是高效查询处理的关键.目前已经提出了许多结构连接的算法,它们中的大多数都基于如下的前提条件之一:输入元素集合存在索引或者有序.当这些条件不成立时,由于对输入数据临时排序或建索引的代价,这些算法的性能会大大下降.基于这样的观察,提出了一种基于区域划分的结构连接算法.该算法基于任务分解的思想,利用区域编码的特点对输入集合进行划分.给出了详细的算法设计,并对算法的I/O复杂性进行了分析.大量的实验结果显示,该算法具有良好的性能,在输入数据无序或没有索引的情况下优于现有的排序合并算法,可以为查询计划提供更多的选择.