以目标节点为导向的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(中国人民大学 信息学院,北京 100872)Targget Nodde AAimeed PPathh Exxpreessiion Proocesssinng ffor XMLL DaataWANGG Jiing11, MMENGG Xiiao-Fenng2, WWANGG Yuu2+, WWANGG Shhan221(Innstiitutte oof CCompputiing Tecchnoologgy, TheeChiinesse AAcaddemyy off Sccienncess, BBeijjingg 1000088

4、0, Chiina)2(Innforrmattionn Scchoool, Rennminn Unniveersiity of Chiina, Beeijiing 10008722, CChinna)+ Coorreespoondiing autthorr: PPhn:+86-10-6255155575, Faax: 866-100-62251994533, EE-maail: saandppipeerwyyyaahooo.coom.ccnReceeiveed 220033-122-255; Acceepteed 220044-066-100Wangg J, Meeng XF, Waang Y

5、, Wanng SS. TTargget nodee aimeed ppathh exprresssionn proccesssingg foor XXML dataa.Jouurnaal oof SSofttwarre, 20005,16(5):82278337. DOII: 110.113600/joos16608227Absttracct:XMLL quueryy laanguuagees ttakee coompllex patth eexprresssionns aas ttheiir ccoree. TTo ffaciilittatee paath exppresssioon pp

6、roccesssingg, 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 prropoosedd. TT

7、hiss 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 thhe iinte

8、ermeediaate 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 queery

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、(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树a2a1and1d2d2nd2n1dndn+1(b) Sor

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

35、完全全结构连连接的排排序合并并算法可可能产生生的对输输入集合合的多遍遍扫描.这两个个算法在在最坏情情况下对对两个输输入集合合各扫描描一遍.图4和和图5分分别给出出了完全全结构连连接的按按祖先和和后代排排序合并并算法的的最坏情情况,以以及SSSMJ-Ancc和SSSMJ-Dess在这两两种情况况下的效效率.在在图4(a)所所描述的的数据分分布情况况下,图图4(bb)描述述了按祖祖先排序序合并算算法进行行完全结结构连接接的对DD的多遍遍扫描,而图44(c)中的SSSMJJ-Annc算法法只需从从d1到dn的扫描描比较.图5中中的情况况也相类类似.需需要指出出的是,SSMMJ-AAnc和和SSMMJ

36、-DDes只只适用于于祖先-后代关关系的计计算.d2n1d2na0a1ana2d1d2d3dna3a0a2ana1d1dnd2(a) XML tree(a) XML树(b) Sort merge join by descendant nodes(b) 按后代节点排序合并结构连接(c) SSMJ-Des(c) SSMJ-Desa1ana2d1d2d3dna3Fig.5 A case for SSMJ-Des algorithm图5 SSMJ-Des算法的例子a0基于区域域划分的的选择性性结构连连接算法法针对输入入数据集集合无序序的情况况,我们们已经提提出了基基于区域域划分的的结构连连接算法法(r

37、aangee paartiitiooninng jjoinn,简称称RPJJ)112,实现了了完全结结构连接接操作.在RPPJ算法法的基础础上,针针对选择择性结构构连接操操作,我我们提出出了基于于区域划划分的选选择性结结构连接接算法(sellecttivee raangee paartiitiooninng jjoinn,简称称SRPPJ).该类算算法包括括两个:输出结结果限定定在A上的SSRPJJ-Annc和输输出结果果限定在在D上的SSRPJJ-Dees.SRPJJ-Annc算法法SRPJJ-Annc充分分利用元元素编码码的特点点,尽早早地对AA中节点点进行判判断,产产生结果果.算法法分为

38、33个阶段段:(1) 子集合合划分阶阶段.首首先对后后代节点点集合DD进行划划分,所所采用的的划分方方法与RRPJ相相同.当当对祖先先节点集集合A进行划划分时,可以利利用祖先先节点的的特点来来产生部部分结果果.如果果A中的节节点a的区域域编码完完全覆盖盖了一个个子区间间Ri,只要要Ri对应的的子集合合Di中的元元素节点点数目不不为0,Di中所有有的节点点都是aa的后代代节点.利用这这个特点点,我们们在对AA中的节节点进行行划分时时就可以以判断一一些节点点是否有有后代节节点,具具体的判判断规则则为:假假设A中的一一个节点点a的区域域编码完完全覆盖盖了n个子区区间,如如果这些些子区间间所对应应的D

39、的子集集合中至至少存在在一个不不为空,那么在在D中一定定存在aa的后代代节点,即a应当作作为结果果输出.对于确确定为输输出结果果的A中节点点,就不不再划分分到子集集合中进进行处理理;对于于那些不不能确定定为结果果的A中节点点,只需需将其划划分到与与区域编编码部分分相交的的子区间间所对应应的子集集合中,这样的的子集合合的最大大数目为为2.(2) 连接阶阶段.对对于那些些在子集集合划分分阶段不不能确定定的A中的节节点,需需要实际际的连接接来进行行检查.对每一一对子集集合Ai和Di,分别别进行连连接.由由于A中的一一个节点点可能被被划分到到两个子子集合中中,所以以它可能能在结果果中出现现两次,即连接

40、接阶段产产生的结结果集中中可能出出现重复复元素.(3) 去重阶阶段.子子集合划划分和连连接阶段段已经产产生了所所有的输输出结果果,但连连接阶段段所产生生的结果果中可能能会出现现重复值值.该阶阶段的主主要任务务是合并并各个子子集合对对的连接接结果,去掉重重复值.SRPJJ-Dees算法法SRPJJ-Dees的基基本思想想与SRRPJ-Ancc类似,不同的的是考虑虑的目标标是集合合D.算法法分为两两个阶段段:(1) 子集合合划分阶阶段.首首先对祖祖先节点点集合AA进行划划分,所所采用的的划分方方法与RRPJ相相同,不不同的是是对每个个子集合合Ai额外记记录该子子集合中中区域编编码完全全覆盖其其对应

41、子子区间的的节点个个数Vi.如果果A中节点点a的区域域编码完完全覆盖盖了一个个子区间间Ri,则Di中所有有的节点点都是aa的后代代节点.利用这这个特点点,在对对后代节节点集合合D进行划划分时可可以判断断一些节节点是否否有祖先先节点,判断规规则为:假设DD中的一一个节点点d应当划划分到DDi,如果果对应的的Ai的Vi值不为为0,则则Ai中一定定存在dd的祖先先节点,即d应当作作为结果果输出.对于确确定为输输出结果果的D中节点点,就不不再划分分到子集集合中进进行处理理;对于于那些不不能确定定为结果果的D中节点点,仍按按照RPPJ算法法中的划划分方法法划分到到子集合合中,进进行进一一步的处处理.(2

42、) 连接阶阶段.对对于在子子集合划划分阶段段没有确确定的DD中节点点,连接接阶段进进行进一一步的处处理.根根据装入入内存的的子集合合的不同同,可以以采用相相应的连连接算法法.由于于D中每个个元素最最多只被被划分到到一个子子集合中中,所以以连接阶阶段产生生的结果果中没有有重复.两个阶阶段产生生的结果果可以直直接合并并生成最最后的输输出结果果.实验结果果和分析析为了对本本文中所所提出方方法的有有效性进进行验证证,我们们进行了了初步的的实验.本节对对实验的的结果进进行了描描述和分析.实验设置置我们的实实验在NNatiive XMLL数据管管理系统统Oriientt-X的的基础上上进行,所有的的算法都

43、都用C+编程程语言来来实现.所有的的实验在在一台DDuroon 11.0GGHz,2566M RRAM,40GG硬盘的的PC上上运行,底层操操作系统统是Wiindoows XP.我们选择择执行时时间为评评价指标标.这里里所给出出的执行行时间都都是运行行实验多多次,去去掉最高高和最低低值后得得到的平平均执行行时间.选择性结结构连接接的有效效性选择性结结构连接接操作在在我们的的路径查查询框架架中具有有重要的的作用,本节我我们结合合所提出出的多种种实现算算法对其其进行性性能上的的分析.我们采用用IBMM XMML GGeneerattor生生成了大大小为1113MM的实验验文档,所用的的DTDD如图

44、66所示,其中各各个元素素的个数数在表11中给出出.我们们采用了了表2所所示的66个查询询,它们们可以分分为两类类:Q11到Q44是简单单结构关关系查询询;Q55和Q66是复杂杂查询,用来反反映包含含多个连连接操作作的查询询的执行行情况.除了人人工生成成的数据据集以外外,我们们也在真真实的数数据集DDBLPP和XMMarkk上进行行了实验验,实验验结果类类似.!ELEMENT manager (name, (manager | department | employee)+)!ELEMENT department (name, email?, employee+, department*)!E

45、LEMENT employee (name+, email?)!ELEMENT name (#PCDATA)!ELEMENT email (#PCDATA)Fig.6 TThe DTDD off syynthhetiic ddataa seet图6 人工数数据集的的DTDDTablle 11 Deescrripttionn off syynthhetiic ddataa seet表1 人工数数据集的的描述ElemmenttNumbberManaagerr38Depaartmmentt2864459Emplloyeee5436685Namee111113900Emaiil599446Tablle

46、 22 DDesccripptioon oof qquerriess off syynthhetiic ddataa seet表2 人工数数据集的的查询描描述QuerryPathh exxpreessiionResuult (Anncesstorr)Resuult (Deesceendaant)Q1manaagerr/eemplloyeee38543 6855Q2depaartmmentt/eemplloyeee286 4599543 6311Q3depaartmmentt/eemaiil34 222359 9929Q4emplloyeee/emaail31 339131 3391Q5depa

47、artmmentt/eemplloyeee/emaail10 447731 3374Q6manaagerr/ddepaartmmentt/eemaiil1459 9929简单结构构关系查查询这里我们们用表22中的44个简单单结构关关系查询询Q1到到Q4来来比较不不同的选选择性结结构连接接实现算算法的性性能.我我们实现现了5类类算法:选择性性排序合合并连接接(SSSMJ),Sttackk-Trree-Fillterr(STTF),Staack-Treee(SST),选择性性区域划划分连接接(SRRPJ)和区域域划分连连接(RRPJ),每类类算法包包括结果果限定在在祖先和和后代的的两个算算法.SS

48、TF算算法是对对Staack-Treee类的的算法进进行了改改写,使使其只输输出指定定的结果果.STT算法是是在Sttackk-Trree类类的算法法后附加加了一个个投影到到指定输输出的过过程,RRPJ也也是类似似.我们们将这55种算法法分为两两类进行行比较:基于排排序合并并和基于于划分,这是因因为我们们在计算算基于排排序合并并算法的的执行时时间时没没有考虑虑排序的的时间,在这种种情况下下,基于于排序合合并的算算法效率率明显高高于基于于划分的的算法.此外,实验的的目的是是想反映映选择性性结构连连接算法法与其对对应的完完全结构构连接算算法加投投影的性性能比较较.图7和图图8描述述了排序序合并类类

49、算法的的性能,分别比比较了输输出结果果限定在在祖先节节点和后后代节点点上的算算法.从从图7中中可以看看出,选选择性结结构连接接算法SSSMJJ和STTF的性性能在各各个查询询上均优优于STT,这说说明选择择性结构构连接算算法的实实现策略略在性能能上优于于完全结结构连接接加投影影的实现现策略.对查询询Q1,Q2和和Q3,两种策策略的执执行时间间相差较较大,而而Q4的的执行时时间则比比较接近近,这是是由于前前3个查查询所涉涉及的祖祖先节点点元素mmanaagerr和deeparrtmeent是是递归定定义的,而Q44中的eemplloyeee则没没有递归归定义.当祖先先元素存存在递归归定义时时,选

50、择择性结构构连接算算法由于于可以避避免对嵌嵌套节点点的多次次处理,所以较较大程度度地提高高了执行行效率.此外,SSMMJ和SSTF在在各个查查询上的的执行时时间都比比较接近近,SSSMJ略略优于SSTF,这是由由于两种种算法本本质上是是相同的的,而SSTF在在内存中中的栈和和链表处处理稍复复杂一些些.图88所描述述的性能能比较表表现了与与图7类类似的特特征.图9和图图10描描述了基基于划分分的算法法的性能能比较.从图中中可以看看出,选选择性结结构连接接算法SSRPJJ在各个个查询上上都优于于基于区区域划分分的完全全结构连连接加投投影的方方法.除除Q4的的优势不不明显以以外,其其他3个个查询上上

51、SRPPJ都大大大优于于RPJJ.这个个特征也也与排序序合并类类算法的的表现相相一致.Execution time (s)01020304050607080Q1Q2Q3Q4STSTFSSMJExecution time (s)0510152025303540Q1Q2Q3Q4STSTFSSMJFig.7 The result of sort merge algorithmsby ancestor图7 输出祖先节点的排序合并类算法的结果Fig.8 The result of sort merge algorithmsby descendant图8 输出后代节点的排序合并类算法的结果Executio

52、n time (s)050100150200250300350Q1Q2Q3Q4RPJSRPJExecution time (s)050100150200250300350400Q1Q2Q3Q4RPJSRPJFig.9 The result of partitioning algorithmsby ancestor图9 输出祖先节点的划分类算法的结果Fig.10 The result of partitioning algorithmsby descendant图10 输出后代节点的划分类算法的结果复杂查询询表2中的的Q5和和Q6是是两个较较为复杂杂的查询询,每个个查询包包含了两两个连接接.我们

53、们用五类类算法分分别基于于结果为为祖先节节点和后后代节点点实现了了这两个个查询.SSMMJ,SSTF和和SRPPJ同上上节所述述,而PPathh-S(Patth-RR)则表表示先采采用Sttackk-Trree(RPJJ)算法法完成连连接,最最后对完完全连接接结果进进行一次次投影.表3和和表4分分别给出出了排序序合并类类算法和和划分类类算法的的实验结结果.从从表3中中可以看看出,SSSMJJ和STTF执行行时间相相近,都都大大优优于Paath-S.而而表4则则反映了了SRPPJ与PPathh-R相相比所取取得的性性能优势势.Tablle3Thee reesullt oof qquerriess

54、 ussingg soort merrge alggoriithmms表3 排序合合并类算算法的查查询结果果QuerryAnceestoor (s)Desccenddantt (ss)SSMJJSTFPathh-SSSMJJSTFPathh-SQ53.12.9444.8337.6888.19935.778Q61.0881.2999.1113.0773.4338.633Tablle 44 TThe ressultt off quueriies usiing parrtittionningg allgorrithhms表4 划分类类算法的的查询结结果QuerryAnceestoor (s)Desc

55、cenddantts (s)SRPJJPathh-RSRPJJPathh-RQ512.22221.66330.113122.81Q66.66625.9928.36645查询执行行计划的的性能我们用初初步的实实验来验验证所提提出的查查询分解解处理策策略的可可行性.实验采采用XMMarkk数据集集,选择择了大小小分别为为1M,10MM和200M的文文档.表表5给出出了实验验中所用用的查询询例子QQP1和和QP22.QPP1是一一个不带带分支的的路径查查询,存存在不确确定路径径.而QQP2则则带有分分支路径径,是一一个树状状的路径径查询.对QPP1和QQP2,我们分分别采用用了两个个不同的的执行计计

56、划来实实现.连连接计划划通过单单步的结结构连接接操作来来完成查查询,连连接顺序序采用逐逐步向目目标节点点靠拢的的顺序.分解计计划是采采用本章章所提出出的分解解策略所所产生的的执行计计划.两两个查询询例子的的执行结结果分别别见表66和表77.从表表6可以以看到,除了数数据为11M的情情况以外外,QPP1的分分解计划划的执行行时间大大大小于于连接计计划.对对QP22来说,这种执执行时间间的差距距更为明明显.虽然这里里的连接接计划并并不是通通过优化化而选出出的最优优计划,但从实实验结果果仍然可可以看出出,基于于分解策策略的执执行计划划具有一一定的优优势,可可以成为为一种优优先考虑虑的选择择.Tabl

57、le 55 DDesccripptioon oof ppathh quueriies表5 路径查查询描述述QuerryPathh exxpreessiionQP1/sitte/opeen_aaucttionn/biiddeer/iincrreasseQP2/sitte/oopenn_auuctiionss/oppen_aucctioonaannootattionn/deescrripttionn/teext/biddderr/naameTablle 66 TThe exeecuttionn tiime of QP11(mss)表6 QP11的执行行时间(ms)Dataasett (MM)Joi

58、nn pllanDecoompoosittionn pllan115.333110114.3331.33320328151Tablle7Thee exxecuutioon ttimee off QPP2(mms)表7 QP22的执行行时间(ms)Dataasett (MM)Joinn pllanDecoompoosittionn pllan115.66715.6671010483.33320250.33161.67相关工作作路径查询询的处理理方面已已经有大大量的研研究工作作.继承承了半结结构化数数据领域域的研究究,文献献7,8对对导航式式遍历的的路径查查询匹配配方法进进行了研研究.导导航式遍遍

59、历方法法简单、直接,但执行行效率不不能得到到保证,尤其是是在大数数据量的的情况下.“一次一一集合”的路径径查询计计算策略略目前被被广泛接接受,基基于该策策略的研研究工作作包括多多个方面面,结构构连接算算法的研研究是其其中的重重点.目目前已有有的工作作大体上上可以分分为两类类:基于于排序合合并的算算法668和基基于划分分的方法法9.排序序合并类类的算法法依赖于于一定的的前提条条件:数数据集合合是有序序的,或或者集合合上存在在索引.当条件件不成立立时,算算法的效效率会大大大降低低.文献献9中的划划分方法法虽然不不要求输输入数据据集合有有序或存存在索引引,但只只适用于于其提出出的PBBiTrree编

60、编码,应应用范围围非常有有限.在在结构连连接操作作的基础础上,对对路径查查询的整整体处理理框架的的研究目目前还比比较少.文献7提提出了对对正则路路径表达达式的分分解计算算方法,但只针针对没有有分支的的路径查查询,而而大量的的结构连连接操作作在该方方法是不不可避免免的.文文献110从从信息过过滤的角角度研究究了如何何对路径径查询进进行分解解,建立立对路径径查询的的索引,从而实实现对XXML文文档的高高效过滤滤.此外外,文献献133,144对结结构连接接的结果果估计问问题进行行了研究究,文献献155则针针对结构构连接的的顺序选选择问题题提出了了多种优优化算法法.除了基于于结构连连接的策策略以外外,