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

1、以目标节点为导向的XML路径查询处理Supported by the National Natural Science Foundation of China under Grant Nos.60073014, 60273018 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2002AA116030 (国家高技术研究发展计划(863); the Key Project of Ministry of Education of China under Grant No

2、.03044 (国家教育部科学技术重点项目); the Excellent Young Teachers Program of Ministry of Education of China (教育部优秀青年教师资助计划)作者简介: 王静(1975),女,山西襄垣人,博士,主要研究领域为数据库与知识库,XML数据管理;孟小峰(1964),男,博士,教授,博士生导师,主要研究领域为数据库与知识库,Web数据管理;王宇(1973),女,博士生,主要研究领域为数据库与知识库,XML数据管理;王珊(1944),女,教授,博士生导师,主要研究领域为数据库与知识库,数据仓库.王 静1, 孟小峰2, 王 宇2

3、+, 王 珊21(中国科学院 计算技术研究所,北京 100080)2(中国人人民大学学 信息息学院,北京 10008772)Targeet NNodee Aiimedd Paath Exppresssioon PProccesssingg foor XXML DattaWANG Jinng1, MMENGG Xiiao-Fenng2, WWANGG Yuu2+, WWANGG Shhan221(Insstittutee off Coompuutinng TTechhnollogyy, TThe Chiinesse AAcaddemyy off Sccienncess, BBeijjingg 1

4、0000880, Chiina)2(Infformmatiion Schhooll, RRenmmin Uniiverrsitty oof CChinna, Beiijinng 11008872, Chhinaa)+ Corrressponndinng aauthhor: Phhn: +86-10-6255155575, Faax: 866-100-62251994533, EE-maail: saandppipeerwyyyaahooo.coom.ccnReceiivedd 20003-12-25; Acceepteed 220044-066-100Wang J, Menng XXF, Wa

5、nng YY, WWangg S. Taargeet nnodee aimeed ppathh exprresssionn proccesssingg foor XXML dataa. Jouurnaal oof SSofttwarre, 20005,16(5):82278337. DOII: 110.113600/joos16608227Abstrractt:XMLL quueryy laanguuagees ttakee coompllex patth eexprresssionns aas ttheiir ccoree. TTo ffaciilittatee paath exppress

6、sioon pproccesssingg, tthe proocesssinng sstraateggy bbaseed oon ppathh deecommpossitiion andd sttruccturral joiin ooperratiion neeeds too bee innvesstiggateed mmoree deeeplly. In thiis ppapeer, a ttargget nodde aaimeed aat ppathh exxpreessiion proocesssinng fframmewoork forr XMML ddataa iss prropoo

7、sedd. TThiss appprooachh maakess usse oof tthe exttendded bassic opeerattionns tto rreduuce thee nuumbeer oof jjoinn opperaatioons. Inn thhe pprocceduure of patth ddecoompoosittionn annd qquerry pplann seelecctioon, tarrgett noode in thee quueryy trree is utiilizzed to avooid thee trranssferr off th

8、he iinteermeediaate ressultts. In addditiion to deccompposiitioon rrulees aand strrateegiees, a sset of exttendded bassic opeerattionns aand impplemmenttatiion alggoriithmms aare proopossed. Prreliiminnaryy exxperrimeentss inndiccatee thhis appproaach hass goood perrforrmannce. Itt prroviidess paath

9、 queery proocesssinng wwithh moore chooicees.Key wwordds:XMLL quueryy prroceessiing; paath exppresssioon; strructturaal jjoinn; sseleectiive strructturaal jjoinn; ppathh inndexx摘 要:XMLL查询语语言将复复杂路径径表达式式作为核核心内容容.为了了加速路路径表达达式处理理,基于于路径分分解和结结构连接接操作的的处理策策略需要要更深入入的研究究.以目目标节点点为导向向的XMML路径径查询处处理框架架被提了了出来.该方法法

10、利用了了扩展基基本操作作来减少少连接操操作的数数目.在在路径分分解和查查询计划划选择的的过程中中,利用用查询树树中的目目标节点点来避免免中间结结果的传传递.除除了分解解规则和和策略以以外,提提出了一一组扩展展的基本本操作和和实现算算法.初初步的实实验结果果显示,该方法法具有良良好的性性能.它它为路径径查询处处理提供供了更多多的选择择.关键词:XMLL查询处处理;路路径表达达式;结结构连接接;选择择性结构构连接;路径索索引中图法分类类号:TP3311文文献标识识码: A随着XMLL1标准被被广泛接接收和采采用,XXML数数据的管管理和查查询问题题也引起起了人们们的重视视,成为为研究的的热点.尽管

11、XXML可可以描述述非常复复杂的结结构,其其本质仍仍然是树树状的数数据.针针对XMML的查查询,学学者们已已经提出出了多种种XMLL查询语语言,例例如XPPathh2,XQQuerry33等,这些查查询语言言都将路路径表达达式作为为核心内内容.针针对路径径查询的的处理问问题,人人们已经经进行了了大量的的研究工工作.在在树状的的XMLL数据中中匹配路路径查询询的基本本方式是是对数据据进行导导航式的的遍历,文献4,55对这这种方式式进行了了探讨,它简单单、直接接,但执执行效率率不能得得到保证证,尤其其是在大大数据量量的情况况下.导导航式遍遍历方法法的低效效性促使使了类似似于关系系数据库库中“一次一

12、一集合”的路径径查询计计算策略略的出现现.目前前被广泛泛接受的的分解连连接查询询执行策策略的基基本思路路是,首首先定位位路径查查询树中中每个节节点的候候选元素素节点集集合,然然后通过过结构连连接操作作组合这这些中间间结果来来生成最最后的结结果.采采用这种种策略会会产生大大量的结结构连接接操作.目前,这方面面的工作作主要集集中在高高效的结结构连接接算法上上69,而对对路径查查询的整整体处理理框架的的研究较较少.文文献77提出出了对正正则路径径表达式式的分解解计算方方法,但但只针对对没有分分支的路路径查询询,而且且大量的的结构连连接操作作是该方方法不可可避免的的.文献献100从信信息过滤滤的角度度

13、研究了了如何对对路径查查询进行行分解,建立对对路径查查询的索索引,考考虑的问问题不同同.在基基本操作作的基础础上,设设计合理理的路径径分解和和计算框框架是一一个需要要进一步步研究的的问题.针对这个问问题,结结合在NNatiive XMLL数据管管理系统统Oriientt-X中中的实际际考虑,本文提提出了一一个以目目标节点点为导向向的路径径查询处处理框架架.该方方法充分分利用基基本操作作的支持持,增大大了基本本查询片片段的粒粒度,从从而减少少了结构构连接的的数目.本文第1节节给出一一些基本本的概念念.第22节描述述路径查查询的分分解方法法.第33节针对对分解后后的路径径查询,探讨查查询计划划的生

14、成成.第44节描述述查询中中用到的的扩展基基本操作作以及操操作的具具体实现现.第55节分析析实验结结果.第第6节对对相关工工作进行行概述.第7节节对全文文工作进进行总结结,并展展望未来来的工作作.基本概念在本节,我我们首先先给出一一些基本本概念的的定义,这些概概念在后后面的描描述中会会用到.XML数据据的路径径查询可可以描述述为一棵棵查询树树,其形形式化的的描述如如下:定义1. 针对XXML数数据的路路径查询询可以表表示为一一棵查询询树Q=(V,E,Rooot,preediccatee),V是树中中节点的的集合,Rooot是查查询树的的根.EE是树中中节点之之间边的的集合,边分为为两种,分别表

15、表示父子子包含关关系和祖祖先后代代包含关关系.除除了根节节点之外外,函数数preediccatee赋给查查询树中中的每个个节点一一个谓词词条件,该条件件针对元元素的名名字、属属性值及及文本值值等.这个查询树树所表示示的路径径表达式式是XPPathh2的子集集.在下下面的章章节中,为了简简单起见见,查询询的定义义简化为为Q= (VQ,EQ),VQ表示节节点,EEQ表示节节点间的的边.在实际的查查询树中中,往往往只有一一个节点点在数据据中的映映射节点点是查询询需要的的输出结结果,其其余节点点之间的的边只是是对该节节点的条条件约束束.基于于这样的的考虑,我们给给出如下下的一些些定义.定义2. XMM

16、L查询询树中存存在一个个节点nn,它在在数据中中的映射射是查询询的最终终输出结结果,该该节点称称为查询询的目标标节点.定义3. 在XMML查询询树Q中,从从根节点点到目标标节点之之间的路路径称为为查询的的主路径径.定义4. 在XMML查询询树Q中,孩孩子节点点数目大大于1的的节点(即出现现路径分分叉的节节点)称称为分支支节点.定义5. 在XMML查询询树Q中,如如果节点点上除了了针对元元素名的的谓词条条件外,还定义义了针对对元素值值或元素素属性值值的谓词词条件,这样的的节点称称为值谓谓词节点点.考虑图1中中给出的的查询树树例子,它试图图找到研研究领域域包括数数据库的的教授在在会议上上所发表表的

17、论文文.节点点F是查询询的目标标节点,从节点点A到F的路径径是查询询的主路路径,节节点C是分支支节点,而节点点E上带有有针对元元素文本本值的谓谓词条件件,是值值谓词节节点.Predicate nodePredicate nodeA.ElementName=“department”B.ElementName=“researchgroup”C.ElementName=“professor”D.ElementName=“interests”E.ElementName=“area” and E.TextValue=“DB”F.ElementName=“paper”G.ElementName=“conf

18、erence”H.ElementName=“supporter”*ABCDEFGH*Target nodeFork nodeFig.11 An exaamplle oof qquerry ttreee图1 查查询树例例子路径查询的的分解计计算根据实际的的查询需需求以及及底层访访问方法法的支持持,我们们提出了了自己的的查询计计算框架架.我们们所研究究的查询询处理框框架基于于如下的的两个前前提:(1) 查询树树的目标标节点是是查询的的输出结结果.在在查询树树中,只只有目标标节点在在数据中中的映射射节点是是查询的的输出结结果,整整个查询询树的计计算是以以目标节节点为导导向的.(2) 路径径索引的的支

19、持.充分利利用路径径索引,尽量避避免不必必要的结结构连接接操作,从而减减少计算算代价,这是我我们的一一个指导导思想.查询分解状状态为了描述查查询分解解,首先先给出两两个定义义: 定义6. 给定一一个路径径查询QQ=(VQ,EQ),一一个查询询片段NN是满足足如下条条件的VVQ中节点点的集合合:(1) ;(2) ,如果存存在一个个节点ww位于从从u到v的路径径上,则则定义7. 给定一一个路径径查询QQ=(VQ,EQ),从从Q中导出出的一个个查询分分解状态态是一棵棵树D=(VD,ED),VD中的每每个节点点n对应于于Q的一个个查询片片段N.D满足如如下的条条件:(1) ;(2) ;(3) ;(4)

20、 .查询片段是是可以借借助索引引等方式式的支持持进行快快速计算算的基本本单位,各个查查询片段段之间通通过结构构连接操操作来组组合其执执行的中中间结果果.对一一个路径径查询而而言,根根据查询询片段划划分的不不同,可可能的查查询分解解状态有有很多.具体的的查询片片段的划划分与底底层的访访问支持持方式有有着密切切的关系系.简单路径分分解查询片段的的确定是是查询分分解的关关键.通通过考虑虑查询的的实际情情况和已已有的访访问方法法,我们们采用如如下的一一些启发发式规则则来确定定查询片片段.规则1. 利用结结构连接接来处理理不确定定路径.当查询树QQ中出现现了表示示祖先-后代关关系的边边时,则则两端节节点

21、之间间可能的的路径是是任意的的,例如如图1中中节点AA和B之间带带“*”的边.这种不不确定的的路径的的匹配无无论是在在数据中中,还是是在路径径索引中中都是代代价很大大的.利利用结构构连接来来直接判判断候选选节点之之间的祖祖先-后后代关系系是解决决不确定定路径匹匹配的较较好方法法.基于于这样的的认识,分解产产生的查查询片段段中不应应当包含含表示祖祖先-后后代关系系的边,该类边边只能出出现在查查询片段段之间.规则2. 查询片片段不支支持分支支节点.我们的基本本访问方方法不能能直接支支持带有有分支节节点的路路径查询询,所以以分支节节点不能能作为查查询片段段所对应应路径的的中间节节点.规则3. 值谓词

22、词节点作作为查询询片段的的末端节节点.为了方便结结合路径径索引和和值索引引来计算算值谓词词条件,我们规规定值谓谓词节点点只作为为查询片片段的末末端节点点.多个个值谓词词节点之之间的关关系通过过结构连连接来实实现.根据如上的的3条启启发式规规则,我我们可以以给出一一个特定定的查询询分解状状态.定义8. 给定一一棵查询询树Q=(VQ,EQ),如如果Q中的一一条路径径p=v1,v2,vn满足如如下的条条件,则则p是Q的一条条简单路路径:(1) 对对,vi是vi+1的父父亲节点点;(2) 路路径中相相邻两个个节点之之间的边边(vi,vi+1)不不表示祖祖先-后后代关系系;(3) 如如果存在在vi是Q中

23、的分分支节点点或值谓谓词节点点,则ii=n.从定义8可可以看出出,查询询树中的的简单路路径不包包括祖先先-后代代结构关关系,分分支节点点和值谓谓词节点点只能出出现在路路径末端端的路径径,它的的计算可可以直接接通过路路径索引引的查询询来完成成.定义9. 给定一一棵查询询树Q=(VQ,EQ),如如果一个个路径集集合P=p|p是查询询树Q中出现现的路径径满足足条件:(1) p是Q中的简简单路径径;(2) 查查询树QQ中的每每个节点点至少包包含在一一条路径径中,则则P是Q的一个个简单路路径分解解.如果P还满满足第33个条件件:(3) PP的每条条路径pp都是最最长的,即Q中不存存在另一一个更长长的简单

24、单路径包包含p,则P是Q的一个个最小简简单路径径分解.可以看出,最小简简单路径径分解是是查询树树的所有有简单路路径分解解中包含含简单路路径数目目最少的的,而且且最小简简单路径径分解是是唯一的的.图22(a)和图22(b)给出了了两个可可能的简简单路径径分解例例子,图图中虚线线包围的的区域是是一个简简单路径径的范围围.图22(b)所给出出的是最最小简单单路径分分解,其其中的每每个简单单路径都都不可能能被更长长的简单单路径所所包含.依据最小简简单路径径分解的的概念,我们可可以得到到相应的的查询分分解状态态.给定定一棵查查询树QQ及其最最小简单单路径分分解P,P中的每每条简单单路径对对应于一一个查询

25、询片段,查询片片段之间间的边则则由它们们所包含含的查询询节点之之间的边边来决定定.图22(c)给出了了根据图图2(bb)中的的最小简简单路径径分解得得到的查查询分解解状态.*ABCDEFGH*(a) GD*ABCEFH*(b) AFGHBCDE(c) *Fig.22 Patth ddecoompoosittionn off quueryy trree图2 查查询树的的路径分分解查询计划的的选择根据最小简简单路径径分解所所得到的的查询分分解状态态是查询询执行的的基础,需要经经过进一一步的转转化才能能成为查查询计划划.具体体的查询询计划的的确定是是一个复复杂的优优化问题题,我们们不作详详细的探探讨

26、,只只对其中中的关键键问题加加以说明明.查询片段的的状态确确定在我们的查查询分解解状态中中,每个个查询片片段被看看成是原原子的,可以通通过直接接的访问问方法得得到中间间结果.我们对对查询片片段的具具体状态态给出明明确的描描述,为为其确定定具体操操作符的的选择.每个查查询片段段的状态态描述包包括(LLabeelPaath, Ouutpuut,Opeerattor),其中中LabbelPPathh是查询询片段对对应的简简单路径径,Ouutpuut是查查询片段段所需输输出的结结果所包包括的查查询节点点,而OOperratoor则是是根据前前两者为为该查询询片段所所选择的的具体操操作符.查询片段输输出

27、的结结果作为为中间结结果将会会与结构构相关的的其他中中间结果果进行结结构连接接,所以以查询片片段的输输出结果果应当保保留将用用于进一一步连接接的元素素节点信信息,或或者是查查询最后后输出结结果的内内容.查查询片段段输出的的确定是是根据查查询片段段在查询询分解状状态树中中的边,按照如如下的规规则来进进行.给定一个路路径查询询Q=(VQ,EQ),从从Q中根据据最小简简单路径径分解得得到的查查询分解解状态DD=(VD,ED),D中任意意一个查查询片段段N的输出出结果由由所有满满足如下下条件的的查询节节点u所对应应的元素素组成:(1) ;(2) ;或者(3) u是Q的目标标节点.一旦确定了了输出结结果

28、,对对每个查查询片段段就可以以根据其其对应的的简单路路径的情情况指定定相应的的基本操操作.结构连接顺顺序的选选择在以路径查查询的目目标节点点为查询询结果的的前提下下,如果果每个结结构连接接操作只只产生下下一步操操作所需需的数据据作为结结果,可可以大大大减小中中间结果果的规模模,避免免不必要要的中间间结果传传递.基基于这样样的观察察,我们们以目标标节点作作为导向向,只考考虑满足足这种特特性的查查询计划划.我们采用如如下的启启发式方方法来选选择查询询计划:将目标标节点所所属的查查询片段段作为根根节点,从而将将查询状状态树划划分为若若干个子子树.对对每个子子树分别别考虑以以子树的的根节点点为输出出结

29、果的的查询计计划,选选择最优优的计划划.然后后考虑各各个子树树与根节节点的可可能连接接计划.目标节节点的每每个子树树形成了了一个查查询子树树,其根根节点是是子树的的目标节节点.为为每个子子树选择择查询计计划是一一个递归归的过程程.这样产生的的查询计计划的数数目是相相当有限限的,只只与分支支节点的的不同连连接顺序序选择有有关.图图3描述述了一个个查询分分解状态态可能有有的查询询计划.图3(a)是是将目标标查询片片段作为为根节点点的查询询分解状状态树,FGHH对应的的是目标标查询片片段.它它对应的的两个可可能的查查询计划划如图33(b)和图33(c)所示.OOBOC OBOC OA AFGHBCD

30、EOD OC OF OF OF OBOC OBOC AFGHBCDEOF OD OA OC (b) *AFGHBCDE(a) (c) Fig.33 Sellecttionn off quueryy pllan图3 查查询计划划的选择择扩展的基本本操作在基于最小小简单路路径分解解的计算算框架中中,由于于以目标标节点为为导向和和简单路路径原子子化的前前提存在在,原有有的基本本操作不不能满足足需求,需要引引入新的的操作.扩展的索引引查询操操作在我们基于于简单路路径的分分解框架架中,查查询片段段对应的的简单路路径是一一个原子子操作,需要路路径索引引的支持持,直接接得到满满足简单单路径关关系的结结果,从

31、从而避免免多个二二元结构构连接操操作.根根据简单单路径的的定义,为了有有效地支支持其查查询,需需要扩展展的索引引查询操操作包括括:(11) SSimpplePPathh:对给给定的简简单标记记路径LL1/L2/Ln,返回回满足路路径约束束条件的的指定结结果,包包括:LL1对应的的元素节节点集合合,Ln对应的的元素节节点集合合,或者者(L1,Ln)对应应的元素素节点对对集合.(2) PPathhWitthPrrediicatte:对对给定的的标记路路径L1/L2/Ln值谓谓词条件件,返返回满足足路径约约束条件件和值谓谓词条件件的指定定结果,包括:L1对应的的元素节节点集合合,Ln对应的的满足值值

32、谓词条条件的元元素节点点集合,或者(L1,Ln)对应应的元素素节点对对集合.文献111中详详细论述述了利用用SUPPEX索索引实现现上述操操作的方方法.选择性结构构连接操操作结构连接是是XMLL查询处处理中的的核心操操作,目目前所考考虑的结结构连接接操作是是一种完完全结构构连接操操作,即即结构连连接所输输出的结结果是参参加连接接的两个个输入集集合中满满足条件件的元组组的合并并.在我我们的计计算框架架中,查查询树的的计算是是以目标标节点为为导向的的,而不不必给出出全连接接的结果果.选择择性结构构连接操操作只输输出需要要保留的的部分作作为结果果,对无无用查询询结果的的剔除可可以尽早早进行,其定义义

33、如下:定义10. 给定定两个输输入集合合A=(a1,a2,am)和和D=(d1,d2,dn),A和D分别是是m维和n维元组组的集合合,对指指定的潜潜在祖先先ai,潜在在后代ddj以及输输出结果果定义,选择性性结构连连接操作作产生的的结果集集合为(x1,x2,xp)|ai是dj的祖先先;xka1,am或者者xkd1,dn,且且xk在输出出结果定定义中,k=1,p.选择性结构构连接算算法实现现本节给出了了两类选选择性结结构连接接算法:排序合合并和基基于区域域划分.选择性排序序合并结结构连接接算法dn+1a2and1d2d2nd2n1dn(a) XML tree(a) XML树a2a1and1d2d

34、2nd2n1dndn+1(b) Sort merge join by ancestor nodes(b) 按祖先节点排序合并结构连接(c) SSMJ-Anc(c) SSMJ-Anca2a1and1d2dndn+1Fig.4 A case for SSMJ-Anc algorithm图4 SSMJ-Anc算法的例子a1根据输出结结果是AA或D中的元元素,选选择性排排序合并并结构连连接(sseleectiive sorrt mmergge jjoinn,简称称SSMMJ)算算法有两两个:SSSMJJ-Annc和SSSMJJ-Dees.它它们利用用了只输输出一个个输入集集合中元元素的特特点,避避免了

35、对对某些元元素的处处理,从从而避免免了完全全结构连连接的排排序合并并算法可可能产生生的对输输入集合合的多遍遍扫描.这两个个算法在在最坏情情况下对对两个输输入集合合各扫描描一遍.图4和和图5分分别给出出了完全全结构连连接的按按祖先和和后代排排序合并并算法的的最坏情情况,以以及SSSMJ-Ancc和SSSMJ-Dess在这两两种情况况下的效效率.在在图4(a)所所描述的的数据分分布情况况下,图图4(bb)描述述了按祖祖先排dn+1a2and1d2d2nd2n1dn(a) XML tree(a) XML树a2a1and1d2d2nd2n1dndn+1(b) Sort merge join by an

36、cestor nodes(b) 按祖先节点排序合并结构连接(c) SSMJ-Anc(c) SSMJ-Anca2a1and1d2dndn+1Fig.4 A case for SSMJ-Anc algorithm图4 SSMJ-Anc算法的例子a1d2d2n1d2naa0a1ana2d1d2d3dna3a0a2ana1d1dnd2(a) XML tree(a) XML树(b) Sort merge join by descendant nodes(b) 按后代节点排序合并结构连接(c) SSMJ-Des(c) SSMJ-Desa1ana2d1d2d3dna3Fig.5 A case for SSM

37、J-Des algorithm图5 SSMJ-Des算法的例子a0基于区域划划分的选选择性结结构连接接算法针对输入数数据集合合无序的的情况,我们已已经提出出了基于于区域划划分的结结构连接接算法(rannge parrtittionningg jooin,简称RRPJ)122,实实现了完完全结构构连接操操作.在在RPJJ算法的的基础上上,针对对选择性性结构连连接操作作,我们们提出了了基于区区域划分分的选择择性结构构连接算算法(sseleectiive rannge parrtittionningg jooin,简称SSRPJJ).该该类算法法包括两两个:输输出结果果限定在在A上的SSRPJJ-A

38、nnc和输输出结果果限定在在D上的SSRPJJ-Dees.SRPJ-Ancc算法SRPJ-Ancc充分利利用元素素编码的的特点,尽早地地对A中节点点进行判判断,产产生结果果.算法法分为33个阶段段:(1) 子子集合划划分阶段段.首先先对后代代节点集集合D进行划划分,所所采用的的划分方方法与RRPJ相相同.当当对祖先先节点集集合A进行划划分时,可以利利用祖先先节点的的特点来来产生部部分结果果.如果果A中的节节点a的区域域编码完完全覆盖盖了一个个子区间间Ri,只要要Ri对应的的子集合合Di中的元元素节点点数目不不为0,Di中所有有的节点点都是aa的后代代节点.利用这这个特点点,我们们在对AA中的节

39、节点进行行划分时时就可以以判断一一些节点点是否有有后代节节点,具具体的判判断规则则为:假假设A中的一一个节点点a的区域域编码完完全覆盖盖了n个子区区间,如如果这些些子区间间所对应应的D的子集集合中至至少存在在一个不不为空,那么在在D中一定定存在aa的后代代节点,即a应当作作为结果果输出.对于确确定为输输出结果果的A中节点点,就不不再划分分到子集集合中进进行处理理;对于于那些不不能确定定为结果果的A中节点点,只需需将其划划分到与与区域编编码部分分相交的的子区间间所对应应的子集集合中,这样的的子集合合的最大大数目为为2.(2) 连连接阶段段.对于于那些在在子集合合划分阶阶段不能能确定的的A中的节节

40、点,需需要实际际的连接接来进行行检查.对每一一对子集集合Ai和Di,分别别进行连连接.由由于A中的一一个节点点可能被被划分到到两个子子集合中中,所以以它可能能在结果果中出现现两次,即连接接阶段产产生的结结果集中中可能出出现重复复元素.(3) 去去重阶段段.子集集合划分分和连接接阶段已已经产生生了所有有的输出出结果,但连接接阶段所所产生的的结果中中可能会会出现重重复值.该阶段段的主要要任务是是合并各各个子集集合对的的连接结结果,去去掉重复复值.SRPJ-Dess算法SRPJ-Dess的基本本思想与与SRPPJ-AAnc类类似,不不同的是是考虑的的目标是是集合DD.算法法分为两两个阶段段:(1)

41、子子集合划划分阶段段.首先先对祖先先节点集集合A进行划划分,所所采用的的划分方方法与RRPJ相相同,不不同的是是对每个个子集合合Ai额外记记录该子子集合中中区域编编码完全全覆盖其其对应子子区间的的节点个个数Vi.如果果A中节点点a的区域域编码完完全覆盖盖了一个个子区间间Ri,则Di中所有有的节点点都是aa的后代代节点.利用这这个特点点,在对对后代节节点集合合D进行划划分时可可以判断断一些节节点是否否有祖先先节点,判断规规则为:假设DD中的一一个节点点d应当划划分到DDi,如果果对应的的Ai的Vi值不为为0,则则Ai中一定定存在dd的祖先先节点,即d应当作作为结果果输出.对于确确定为输输出结果果

42、的D中节点点,就不不再划分分到子集集合中进进行处理理;对于于那些不不能确定定为结果果的D中节点点,仍按按照RPPJ算法法中的划划分方法法划分到到子集合合中,进进行进一一步的处处理.(2) 连连接阶段段.对于于在子集集合划分分阶段没没有确定定的D中节点点,连接接阶段进进行进一一步的处处理.根根据装入入内存的的子集合合的不同同,可以以采用相相应的连连接算法法.由于于D中每个个元素最最多只被被划分到到一个子子集合中中,所以以连接阶阶段产生生的结果果中没有有重复.两个阶阶段产生生的结果果可以直直接合并并生成最最后的输输出结果果.实验结果和和分析为了对本文文中所提提出方法法的有效效性进行行验证,我们进进

43、行了初初步的实实验.本本节对实实验的结结果进行行了描述述和分析.实验设置我们的实验验在Naativve XXML数数据管理理系统OOrieent-X的基基础上进进行,所所有的算算法都用用C+编程语语言来实实现.所所有的实实验在一一台Duuronn 1.0GHHz,2256MM RAAM,440G硬硬盘的PPC上运运行,底底层操作作系统是是Winndowws XXP.我们选择执执行时间间为评价价指标.这里所所给出的的执行时时间都是是运行实实验多次次,去掉掉最高和和最低值值后得到到的平均均执行时时间.选择性结构构连接的的有效性性选择性结构构连接操操作在我我们的路路径查询询框架中中具有重重要的作作用

44、,本本节我们们结合所所提出的的多种实实现算法法对其进进行性能能上的分分析.我们采用IIBM XMLL Geenerratoor生成成了大小小为1113M的的实验文文档,所所用的DDTD如如图6所所示,其其中各个个元素的的个数在在表1中中给出.我们采采用了表表2所示示的6个个查询,它们可可以分为为两类:Q1到到Q4是是简单结结构关系系查询;Q5和和Q6是是复杂查查询,用用来反映映包含多多个连接接操作的的查询的的执行情情况.除除了人工工生成的的数据集集以外,我们也也在真实实的数据据集DBBLP和和XMaark上上进行了了实验,实验结结果类似似.!ELEMENT manager (name, (ma

45、nager | department | employee)+)!ELEMENT manager (name, (manager | department | employee)+)!ELEMENT department (name, email?, employee+, department*)!ELEMENT employee (name+, email?)!ELEMENT name (#PCDATA)!ELEMENT email (#PCDATA)Fig.66 Thee DTTD oof ssyntthettic datta sset图6 人人工数据据集的DDTDTablee 1 Dee

46、scrripttionn off syynthhetiic ddataa seet表1 人人工数据据集的描描述ElemeentNumbeerManagger38Deparrtmeent286 4459Emplooyeee543 6685Name1 1111 3900Emaill59 9446Tablee 2 Deescrripttionn off quueriies of synntheeticc daata sett表2 人人工数据据集的查查询描述述QueryyPath exppresssioonResullt (Anccesttor)Resullt (Desscenndannt)Q1man

47、agger/emmplooyeee38543 6685Q2deparrtmeent/emmplooyeee286 4459543 6631Q3deparrtmeent/emmaill34 222359 9229Q4emplooyeee/eemaiil31 399131 3991Q5deparrtmeent/emmplooyeee/eemaiil10 477731 3774Q6managger/deeparrtmeent/emmaill1459 9229简单结构关关系查询询这里我们用用表2中中的4个个简单结结构关系系查询QQ1到QQ4来比比较不同同的选择择性结构构连接实实现算法法的性能能.我们们

48、实现了了5类算算法:选选择性排排序合并并连接(SSMMJ),Staack-Treee-FFiltter(STFF),SStacck-TTreee(STT),选选择性区区域划分分连接(SRPPJ)和和区域划划分连接接(RPPJ),每类算算法包括括结果限限定在祖祖先和后后代的两两个算法法.STTF算法法是对SStacck-TTreee类的算算法进行行了改写写,使其其只输出出指定的的结果.ST算算法是在在Staack-Treee类的的算法后后附加了了一个投投影到指指定输出出的过程程,RPPJ也是是类似.我们将将这5种种算法分分为两类类进行比比较:基基于排序序合并和和基于划划分,这这是因为为我们在在计

49、算基基于排序序合并算算法的执执行时间间时没有有考虑排排序的时时间,在在这种情情况下,基于排排序合并并的算法法效率明明显高于于基于划划分的算算法.此此外,实实验的目目的是想想反映选选择性结结构连接接算法与与其对应应的完全全结构连连接算法法加投影影的性能能比较.图7和图88描述了了排序合合并类算算法的性性能,分分别比较较了输出出结果限限定在祖祖先节点点和后代代节点上上的算法法.从图图7中可可以看出出,选择择性结构构连接算算法SSSMJ和和STFF的性能能在各个个查询上上均优于于ST,这说明明选择性性结构连连接算法法的实现现策略在在性能上上优于完完全结构构连接加加投影的的实现策策略.对对查询QQ1,

50、QQ2和QQ3,两两种策略略的执行行时间相相差较大大,而QQ4的执执行时间间则比较较接近,这是由由于前33个查询询所涉及及的祖先先节点元元素maanagger和和depparttmennt是递递归定义义的,而而Q4中中的emmplooyeee则没有有递归定定义.当当祖先元元素存在在递归定定义时,选择性性结构连连接算法法由于可可以避免免对嵌套套节点的的多次处处理,所所以较大大程度地地提高了了执行效效率.此此外,SSSMJJ和STTF在各各个查询询上的执执行时间间都比较较接近,SSMMJ略优优于STTF,这这是由于于两种算算法本质质上是相相同的,而STTF在内内存中的的栈和链链表处理理稍复杂杂一些

51、.图8所所描述的的性能比比较表现现了与图图7类似似的特征征.图9和图110描述述了基于于划分的的算法的的性能比比较.从从图中可可以看出出,选择择性结构构连接算算法SRRPJ在在各个查查询上都都优于基基于区域域划分的的完全结结构连接接加投影影的方法法.除QQ4的优优势不明明显以外外,其他他3个查查询上SSRPJJ都大大大优于RRPJ.这个特特征也与与排序合合并类算算法的表表现相一一致.Execution time (s)Execution time (s)01020304050607080Q1Q2Q3Q4STSTFSSMJExecution time (s)0510152025303540Q1Q

52、2Q3Q4STSTFSSMJFig.7 The result of sort merge algorithmsby ancestor图7 输出祖先节点的排序合并类算法的结果Fig.8 The result of sort merge algorithmsby descendant图8 输出后代节点的排序合并类算法的结果Execution time (s)050100150200250300350Q1Q2Q3Q4RPJSRPJExecution time (s)050100150200250300350400Q1Q2Q3Q4RPJSRPJFig.9 The result of partition

53、ing algorithmsby ancestor图9 输出祖先节点的划分类算法的结果Fig.10 The result of partitioning algorithmsby descendant图10 输出后代节点的划分类算法的结果复杂查询表2中的QQ5和QQ6是两两个较为为复杂的的查询,每个查查询包含含了两个个连接.我们用用五类算算法分别别基于结结果为祖祖先节点点和后代代节点实实现了这这两个查查询.SSSMJJ,STTF和SSRPJJ同上节节所述,而Paath-S(PPathh-R)则表示示先采用用Staack-Treee(RRPJ)算法完完成连接接,最后后对完全全连接结结果进行行一次

54、投投影.表表3和表表4分别别给出了了排序合合并类算算法和划划分类算算法的实实验结果果.从表表3中可可以看出出,SSSMJ和和STFF执行时时间相近近,都大大大优于于Patth-SS.而表表4则反反映了SSRPJJ与Paath-R相比比所取得得的性能能优势.Tablee 3 Thee reesullt oof qquerriess ussingg soort merrge alggoriithmms表3 排排序合并并类算法法的查询询结果QueryyAncesstorr (ss)Desceendaant (s)SSMJSTFPath-SSSMJSTFPath-SQ53.12.944.837.688

55、.1935.788Q61.081.299.113.073.438.63Tablee 4 Thhe rresuult of queeriees uusinng pparttitiioniing alggoriithmms表4 划划分类算算法的查查询结果果QueryyAncesstorr (ss)Desceendaantss (ss)SRPJPath-RSRPJPath-RQ512.22221.63330.133122.881Q66.6625.9228.3645查询执行计计划的性性能我们用初步步的实验验来验证证所提出出的查询询分解处处理策略略的可行行性.实实验采用用XMaark数数据集,选择了了大

56、小分分别为11M,110M和和20MM的文档档.表55给出了了实验中中所用的的查询例例子QPP1和QQP2.QP11是一个个不带分分支的路路径查询询,存在在不确定定路径.而QPP2则带带有分支支路径,是一个个树状的的路径查查询.对对QP11和QPP2,我我们分别别采用了了两个不不同的执执行计划划来实现现.连接接计划通通过单步步的结构构连接操操作来完完成查询询,连接接顺序采采用逐步步向目标标节点靠靠拢的顺顺序.分分解计划划是采用用本章所所提出的的分解策策略所产产生的执执行计划划.两个个查询例例子的执执行结果果分别见见表6和和表7.从表66可以看看到,除除了数据据为1MM的情况况以外,QP11的分

57、解解计划的的执行时时间大大大小于连连接计划划.对QQP2来来说,这这种执行行时间的的差距更更为明显显.虽然这里的的连接计计划并不不是通过过优化而而选出的的最优计计划,但但从实验验结果仍仍然可以以看出,基于分分解策略略的执行行计划具具有一定定的优势势,可以以成为一一种优先先考虑的的选择.Tablee 5 Deescrripttionn off paath queeriees表5 路路径查询询描述QueryyPath exppresssioonQP1/sitee/oopenn_auuctiion/biddderr/inncreeaseeQP2/sitee/oppen_aucctioons/opee

58、n_aaucttionnannnottatiion/desscriiptiion/texxt/biddderr/naameTablee 6 Thhe eexeccutiion timme oof QQP1 (mss)表6 QQP1的的执行时时间(mms)Datasset (M)Join plaanDecommpossitiion plaan115.333110114.33331.33320328151Tablee 7 Thee exxecuutioon ttimee off QPP2 (mss)表7 QQP2的的执行时时间(mms)Datasset (M)Join plaanDecommpos

59、sitiion plaan115.67715.6771010483.33320250.333161.667相关工作路径查询的的处理方方面已经经有大量量的研究究工作.继承了了半结构构化数据据领域的的研究,文献7,88对导导航式遍遍历的路路径查询询匹配方方法进行行了研究究.导航航式遍历历方法简简单、直直接,但但执行效效率不能能得到保保证,尤尤其是在在大数据据量的情情况下.“一次一集集合”的路径径查询计计算策略略目前被被广泛接接受,基基于该策策略的研研究工作作包括多多个方面面,结构构连接算算法的研研究是其其中的重重点.目目前已有有的工作作大体上上可以分分为两类类:基于于排序合合并的算算法668和基基

60、于划分分的方法法9.排序序合并类类的算法法依赖于于一定的的前提条条件:数数据集合合是有序序的,或或者集合合上存在在索引.当条件件不成立立时,算算法的效效率会大大大降低低.文献献9中的划划分方法法虽然不不要求输输入数据据集合有有序或存存在索引引,但只只适用于于其提出出的PBBiTrree编编码,应应用范围围非常有有限.在在结构连连接操作作的基础础上,对对路径查查询的整整体处理理框架的的研究目目前还比比较少.文献7提提出了对对正则路路径表达达式的分分解计算算方法,但只针针对没有有分支的的路径查查询,而而大量的的结构连连接操作作在该方方法是不不可避免免的.文文献110从从信息过过滤的角角度研究究了如