一种高效处理不完全结构约束的Twig查询方法  

作　　者：周军锋[1,2] 孟小峰[1] WANG Ling Tok 

机构地区：[1]中国人民大学信息学院,北京100872 [2]燕山大学计算机科学与技术系,秦皇岛066004 [3]新加坡国立大学计算学院,新加坡117590

出　　处：《中国科学（F辑:信息科学）》2009年第10期1034-1049,共16页

基　　金：国家自然科学基金(批准号:60833005);国家高技术研究发展计划(批准号:2007AA01Z155,2009AA011904);国家重点基础研究发展计划(批准号:2003CB317000)资助项目

摘　　要：越来越多的网络数据都以XML格式表示和存储,开发高效的查询处理算法以便从带有层次结构的XML文档中提取满足条件的数据是一个必须解决的问题.从XML文档中提取信息时,通常使用已有XML查询语言的核心组件—Twig查询—来表达查询语义.Twig查询的一个固有特点是其中的查询节点之间具有特定的先序关系,正是这一特点使其在很多情况下变得难以使用,从而不得不通过放宽Twig查询的约束条件来表达更灵活的语义.文中主要解决"不完全结构约束的查询(PSTP查询)"的处理问题.提出一种扩展的XPath语法,通过引入Samepath轴,可以以一种简单有效的方式表达灵活的查询语义;提出一种基于扩展XPath语法的查询处理算法pTwigStack,可以高效处理PSTP查询,从而避免分别处理PSTP查询对应的每个Twig查询所导致的性能下降问题;提出两种基于DTD schema的优化方法,用以改进pTwigStack算法的处理性能.不同数据集上的实验结果表明,pTwigStack算法在处理PSTP查询时,综合性能明显优于已有方法.

关 键 词：XML数据库 查询处理 不完全指定结构的Twig模式 整体Twig连接 XPATH 

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