以目标节点为导向的XML路径查询处理

Vol.16,No.5©2005JournalofSoftware软件学报1000-9825/2005/16(05)0827以目标节点为导向的XML路径查询处理王静1,孟小峰2,王宇2+,王珊21(中国科学院计算技术研究所,北京100080)2(中国人民大学信息学院,北京100872)TargetNodeAimedPathExpressionProcessingforXMLDataWANGJing1,MENGXiao-Feng2,WANGYu2+,WANGShan21(InstituteofComputingTechnology,TheChineseAcademyofSciences,Beijing100080,China)2(InformationSchool,RenminUniversityofChina,Beijing100872,China)+Correspondingauthor:Phn:[phone],Fax:[phone],E-mail:[e-mail]2003-12-25;Accepted2004-06-10WangJ,MengXF,WangY,WangS.TargetnodeaimedpathexpressionprocessingforXMLdata.JournalofSoftware,2005,16(5):827837.DOI:10.1360/jos160827Abstract:XMLquerylanguagestakecomplexpathexpressionsastheircore.Tofacilitatepathexpressionprocessing,theprocessingstrategybasedonpathdecompositionandstructuraljoinoperationneedstobeinvestigatedmoredeeply.Inthispaper,atargetnodeaimedatpathexpressionprocessingframeworkforXMLdataisproposed.Thisapproachmakesuseoftheextendedbasicoperationstoreducethenumberofjoinoperations.Intheprocedureofpathdecompositionandqueryplanselection,targetnodeinthequerytreeisutilizedtoavoidthetransferoftheintermediateresults.Inadditiontodecompositionrulesandstrategies,asetofextendedbasicoperationsandimplementationalgorithmsareproposed.Preliminaryexperimentsindicatethisapproachhasgoodperformance.Itprovidespathqueryprocessingwithmorechoices.Keywords:XMLqueryprocessing;pathexpression;structuraljoin;selectivestructuraljoin;pathindex摘要:XML查询语言将复杂路径表达式作为核心内容.为了加速路径表达式处理,基于路径分解和结构连接操作的处理策略需要更深入的研究.以目标节点为导向的XML路径查询处理框架被提了出来.该方法利用了扩展基本操作来减少连接操作的数目.在路径分解和查询计划选择的过程中,利用查询树中的目标节点来避免中间结果的传递.除了分解规则和策略以外,提出了一组扩展的基本操作和实现算法.初步的实验结果显示,该方法具有良好的性能.它为路径查询处理提供了更多的选择.关键词:XML查询处理;路径表达式;结构连接;选择性结构连接;路径索引SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.60073014,60273018(国家自然科学基金);theNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2002AA116030(国家高技术研究发展计划(863));theKeyProjectofMinistryofEducationofChinaunderGrantNo.03044(国家教育部科学技术重点项目);theExcellentYoungTeachersProgramofMinistryofEducationofChina(教育部优秀青年教师资助计划)作者简介:王静(1975－),女,山西襄垣人,博士,主要研究领域为数据库与知识库,XML数据管理;孟小峰(1964—),男,博士,教授,博士生导师,主要研究领域为数据库与知识库,Web数据管理;王宇(1973—),女,博士生,主要研究领域为数据库与知识库,XML数据管理;王珊(1944—),女,教授,博士生导师,主要研究领域为数据库与知识库,数据仓库.828JournalofSoftware软件学报2005,16(5)中图法分类号:TP311文献标识码:A随着XML[1]标准被广泛接收和采用,XML数据的管理和查询问题也引起了人们的重视,成为研究的热点.尽管XML可以描述非常复杂的结构,其本质仍然是树状的数据.针对XML的查询,学者们已经提出了多种XML查询语言,例如XPath[2],XQuery[3]等,这些查询语言都将路径表达式作为核心内容.针对路径查询的处理问题,人们已经进行了大量的研究工作.在树状的XML数据中匹配路径查询的基本方式是对数据进行导航式的遍历,文献[4,5]对这种方式进行了探讨,它简单、直接,但执行效率不能得到保证,尤其是在大数据量的情况下.导航式遍历方法的低效性促使了类似于关系数据库中“一次一集合”的路径查询计算策略的出现.目前被广泛接受的分解连接查询执行策略的基本思路是,首先定位路径查询树中每个节点的候选元素节点集合,然后通过结构连接操作组合这些中间结果来生成最后的结果.采用这种策略会产生大量的结构连接操作.目前,这方面的工作主要集中在高效的结构连接算法上[69],而对路径查询的整体处理框架的研究较少.文献[7]提出了对正则路径表达式的分解计算方法,但只针对没有分支的路径查询,而且大量的结构连接操作是该方法不可避免的.文献[10]从信息过滤的角度研究了如何对路径查询进行分解,建立对路径查询的索引,考虑的问题不同.在基本操作的基础上,设计合理的路径分解和计算框架是一个需要进一步研究的问题.针对这个问题,结合在NativeXML数据管理系统Orient-X中的实际考虑,本文提出了一个以目标节点为导向的路径查询处理框架.该方法充分利用基本操作的支持,增大了基本查询片段的粒度,从而减少了结构连接的数目.本文第1节给出一些基本的概念.第2节描述路径查询的分解方法.第3节针对分解后的路径查询,探讨查询计划的生成.第4节描述查询中用到的扩展基本操作以及操作的具体实现.第5节分析实验结果.第6节对相关工作进行概述.第7节对全文工作进行总结,并展望未来的工作.1基本概念在本节,我们首先给出一些基本概念的定义,这些概念在后面的描述中会用到.XML数据的路径查询可以描述为一棵查询树,其形式化的描述如下:定义1.针对XML数据的路径查询可以表示为一棵查询树Q=(V,E,Root,predicate),V是树中节点的集合,Root是查询树的根.E是树中节点之间边的集合,边分为两种,分别表示父子包含关系和祖先后代包含关系.除了根节点之外,函数predicate赋给查询树中的每个节点一个谓词条件,该条件针对元素的名字、属性值及文本值等.这个查询树所表示的路径表达式是XPath[2]的子集.在下面的章节中,为了简单起见,查询的定义简化为Q=(VQ,EQ),VQ表示节点,EQ表示节点间的边.在实际的查询树中,往往只有一个节点在数据中的映射节点是查询需要的输出结果,其余节点之间的边只是对该节点的条件约束.基于这样的考虑,我们给出如下的一些定义.定义2.XML查询树中存在一个节点n,它在数据中的映射是查询的最终输出结果,该节点称为查询的目标节点.定义3.在XML查询树Q中,从根节点到目标节点之间的路径称为查询的主路径.定义4.在XML查询树Q中,孩子节点数目大于1的节点(即出现路径分叉的节点)称为分支节点.定义5.在XML查询树Q中,如果节点上除了针对元素名的谓词条件外,还定义了针对元素值或元素属性值的谓词条件,这样的节点称为值谓词节点.考虑图1中给出的查询树例子,它试图找到研究领域包括数据库的教授在会议上所发表的论文.节点F是查询的目标节点,从节点A到F的路径是查询的主路径,节点C是分支节点,而节点E上带有针对元素文本值的谓词条件,是值谓词节点.A.ElementName=“department”B.ElementName=“researchgroup”C.ElementName=“professor”D.ElementName=“interests”E.ElementName=“area”andE.TextValue=“DB”F.ElementName=“paper”*ABCDEFG*王静等:以目标节点为导向的XML路径查询处理829Fig.1Anexampleofquerytree图1查询树例子2路径查询的分解计算根据实际的查询需求以及底层访问方法的支持,我们提出了自己的查询计算框架.我们所研究的查询处理框架基于如下的两个前提:(1)查询树的目标节点是查询的输出结果.在查询树中,只有目标节点在数据中的映射节点是查询的输出结果,整个查询树的计算是以目标节点为导向的.(2)路径索引的支持.充分利用路径索引,尽量避免不必要的结构连接操作,从而减少计算代价,这是我们的一个指导思想.2.1查询分解状态为了描述查询分解,首先给出两个定义:定义6.给定一个路径查询Q=(VQ,EQ),一个查询片段N是满足如下条件的VQ中节点的集合:(1)QVN;(2)Nvu,,如果存在一个节点w位于从u到v的路径上,则.Nw定义7.给定一个路径查询Q=(VQ,EQ),从Q中导出的一个查询分解状态是一棵树D=(VD,ED),VD中的每个节点n对应于Q的一个查询片段N.D满足如下的条件:(1)MNVmnD,,;(2)NVDVnQ;(3)QDEE;(4)DDEvuNvuVn),(,,,.查询片段是可以借助索引等方式的支持进行快速计算的基本单位,各个查询片段之间通过结构连接操作来组合其执行的中间结果.对一个路径查询而言,根据查询片段划分的不同,可能的查询分解状态有很多.具体的查询片段的划分与底层的访问支持方式有着密切的关系.2.2简单路径分解查询片段的确定是查询分解的关键.通过考虑查询的实际情况和已有的访问方法,我们采用如下的一些启发式规则来确定查询片段.规则1.利用结构连接来处理不确定路径.当查询树Q中出现了表示祖先-后代关系的边时,则两端节点之间可能的路径是任意的,例如图1中节点A和B之间带“*”的边.这种不确定的路径的匹配无论是在数据中,还是在路径索引中都是代价很大的.利用结构连接来直接判断候选节点之间的祖先-后代关系是解决不确定路径匹配的较好方法.基于这样的认识,分解产生的查询片段中不应当包含表示祖先-后代关系的边,该类边只能出现在查询片段之间.规则2.查询片段不支持分支节点.我们的基本访问方法不能直接支持带有分支节点的路径查询,所以分支节点不能作为查询片段所对应路径的中间节点.规则3.值谓词节点作为查询片段的末端节点.830JournalofSoftware软件学报2005,16(5