以目標節(jié)點為導向的XML路徑查詢處理

1、以目標節(jié)點為導向的 X M L 路徑查詢處理王靜 1,孟小峰王宇:王珊1(中國科學院 計算技術研究所，北京100080)2(中國人民大學信息學院，北京100872)Target Node Aimed Path Expression Processing for XML DataWANG Jing1, MENG Xiao-Feng 2, WANG Yu 2+, WANG Shan 2'(Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100080, China)2 , (Informa

2、tion School, Renmin University of China, Beijing 100872, China)+ Corresponding author: Phn: +86-:Received 2003-12-25; Accepted 2004-06-10Wang J, Meng XF, WangY, Wang S. Target node aimed path expression processing for XML data. Journal of Software , 2005,16(5):827?837. DOI: jos160827Abstract : XML q

3、uery languages take complex path expressions as their core. To facilitate path expression processing, the processing strategy based on path decomposition and structural join operation needs to be investigated more deeply. In this paper, a target node aimed at path expression processing framework for

4、 XML data is proposed. This approach makes use ofthe extended basicoperations to reduce the number of join operations. In the procedure of path decomposition and query plan selection, target node in the query tree is utilized to avoid the transfer of the intermediate results. In addition to decompos

5、ition rules and strategies, a set of extended basic operations and implementation algorithms are proposed. Preliminary experiments indicate this approach has good performance. It provides path query processing with more choices.Key words : XML query processing; path expression; structural join; sele

6、ctive structural join; path index摘 要：XML查詢語言將復雜路徑表達式作為核心內容.為了加速路徑表達式處理，基于路徑分解和結構連接操作的處理策略需要更深入的研究.以目標節(jié)點為導向的XML路徑查詢處理框架被提了出來.該方法利用了擴展基本操作來減少連接操作的數目.在路徑分解和查詢計劃選擇的過程中，利用查詢樹中的目標節(jié)點來避免中間結果的傳遞.除了分解規(guī)則和策略以外，提出了一組擴展的基本操作和實現算法.初步的實驗結果顯示，該方法具有良好的性能.它為路徑查詢處理提供了更多的選擇.關鍵詞：XML查詢處理；路徑表達式；結構連接；選擇性結構連接；路徑索引?國家自然科學基金 )

7、；the National High-Tech Research and Development Plan of China under Grant (國家高技術研究發(fā)展計劃(863); the Key Project of Ministry of Education of China under Grant (國家教育部科學技術重點項目 );theExcellent Young Teachers Program of Ministry of Education of China (教育部優(yōu)秀青年教師資助計劃 )作者簡介：王靜(1975 -),女，山西襄垣人，博士，主要研究領域為數據庫與知識庫

8、,XML數據管理；孟小峰(1964 -),男，博士,教授，博士生導師，主要研究領域為數據庫與知識庫，Web數據管理；王宇(1973 -),女，博士生，主要研究領域為數據庫與知識庫,XML數據管理；王珊(1944 -),女，教授，博士生導師，主要研究領域為數據庫與知識庫，數據倉庫.中圖法分類號：TP311文獻標識碼：A隨著XME標準被廣泛接收和采用,XML數據的管理和查詢問題也引起了人們的重視，成為研究的熱點.盡管XML可以描述非常復雜的結構，其本質仍然是樹狀的數據.針又XML的查詢，學者們已經提出了多種XML查詢語言，例如XPath2 ,XQuery 3等，這些查詢語言都將路徑表達式作為核心內

9、容.針對路徑查詢的處理問題 ，人們已經進行了大量的研究工作.在樹的XML數據中匹配路徑查詢的基本方式是對數據進行導航式的遍歷，文獻4,5對這種方式進行了探討，它簡單、直接，但執(zhí)行效率不能得到保證，尤其是在大數據量的情況下.導航式遍歷方法的低效性促使了類似于關系數據庫中“一次一集合”的路徑查詢計算策略的出現.目前被廣泛接受的分解連接查詢執(zhí)行策略的基本思路是，首先定位路徑查詢樹中每個節(jié)點的候選元素節(jié)點集合，然后通過結構連接操作組合這些中間結果來生成最后的結果.采用這種策略會產生大量的結構連接操作.目前，這方面的工作主要集中在高效的結構連接算法上6?9,而對路徑查詢的整體處理框架的研究較少.文獻7提

10、出了對正則路徑表達式的分解計算方法，但只針對沒有分支的路徑查詢，而且大量的結構連接操作是該方法不可避免的.文獻10從信息過濾的角度研究了如何對路徑查詢進行分解，建立對路徑查詢的索引，考慮的問題不同.在基本操作的基礎上，設計合理的路徑分解和計算框架是一個需要進一步研究的問題針對這個問題，結合在Native XML數據管理系統(tǒng) Orient-X 中的實際考慮，本文提出了一個以目標節(jié)點為 導向的路徑查詢處理框架.該方法充分利用基本操作的支持，增大了基本查詢片段的粒度，從而減少了結構連接的數目.本文第1節(jié)給出一些基本的概念.第2節(jié)描述路徑查詢的分解方法 .第3節(jié)針對分解后的路徑查詢 ，探討查 詢計劃的

11、生成.第4節(jié)描述查詢中用到的擴展基本操作以及操作的具體實現.第5節(jié)分析實驗結果.第6節(jié)對相關工作進行概述.第7節(jié)對全文工作進行總結，并展望未來的工作.1基本概念在本節(jié)，我們首先給出一些基本概念的定義，這些概念在后面的描述中會用到.XML數據的路徑查詢可以描述為一棵查詢樹，其形式化的描述如下：定義1.針又XML數據的路徑查詢可以表示為一棵查詢樹Q=(V, E Root, predicate ), V是樹中節(jié)點的集合，Root是查詢樹的根.E是樹中節(jié)點之間邊的集合，邊分為兩種，分別表示父子包含關系和祖先后代包含關系.除了根節(jié)點之外，函數predicate賦給查詢樹中的每個節(jié)點一個謂詞條件，該條件針

12、對元素的名字、屬性值及文本值等.這個查詢樹所表示的路徑表達式是XPath2的子集.在下面的章節(jié)中，為了簡單起見，查詢的定義簡化為Q= ( VQ, Eq), Vq表示節(jié)點，Eq表示節(jié)點間的邊 .在實際的查詢樹中，往往只有一個節(jié)點在數據中的映射節(jié)點是查詢需要的輸出結果，其余節(jié)點之間的邊只是對該節(jié)點的條件約束.基于這樣的考慮，我們給出如下的一些定義.定義查詢樹中存在一個節(jié)點n,它在數據中的映射是查詢的最終輸出結果，該節(jié)點稱為查詢的目標節(jié)點.定義3.在XML查詢樹Q中，從根節(jié)點到目標節(jié)點之間的路徑稱為查詢的主路徑定義4.在XML查詢樹Q中，孩子節(jié)點數目大于 1的節(jié)點(即出現路徑分叉的節(jié)點)稱為分支節(jié)點

13、.定義5.在XML查詢樹Q中，如果節(jié)點上除了針對元素名的謂詞條件外，還定義了針對元素值或元素屬性值的謂t條件，這樣的節(jié)點稱為值謂詞節(jié)點.考慮圖1中給出的查詢樹例子，它試圖找到研究領域包括數據庫的教授在會議上所發(fā)表的論文.節(jié)點F是 查詢的目標節(jié)點，從節(jié)點A到F的路徑是查詢的主路徑，節(jié)點C是分支節(jié)點，而節(jié)點E上帶有針對元素文本值的謂詞條件，是值謂詞節(jié)點interestsresearchgroupprofessorpaper ”area " and =department ”conference ”Predicate“DBEet nodeFork node="supporter2

14、 路徑查詢的分解計算根據實際的查詢需求以及底層訪問方法的支持，我們提出了自己的查詢計算框架.我們所研究的查詢處理框架基于如下的兩個前提：(1)查詢樹的目標節(jié)點是查詢的輸出結果.在查詢樹中，只有目標節(jié)點在數據中的映射節(jié)點是查詢的輸出結果 ，整個查詢樹的計算是以目標節(jié)點為導向的.(2)路徑索引的支持.充分利用路徑索引，盡量避免不必要的結構連接操作，從而減少計算代價，這是我們的一個指導思想.2.1 查詢分解狀態(tài)為了描述查詢分解，首先給出兩個定義：定義6.給定一個路徑查詢Q=( VQ a), 一個查詢片段N是滿足如下條件的Vq中節(jié)點的集合：(1) NVq ；(2) u, v N ,如果存在一個節(jié)點w位

15、于從u到v的路徑上，則w N.定義7.給定一個路徑查詢Q=( V, Eq),從Q中導出的一個查詢分解狀態(tài)是一棵樹D=(W E),弘中的每個節(jié)點n對應于Q的一個查詢片段滿足如下的條件：(1) n,m Vd,N M ;(2) VqN ；n Vd EdEq； n Vd, u ,v N, (u,v) Ed .查詢片段是可以借助索引等方式的支持進行快速計算的基本單位，各個查詢片段之間通過結構連接操作來組合其執(zhí)行的中間結果.對一個路徑查詢而言，根據查詢片段劃分的不同，可能的查詢分解狀態(tài)有很多.具體的查詢片段的劃分與底層的訪問支持方式有著密切的關系2.2簡單路徑分解查詢片段的確定是查詢分解的關鍵.通過考慮查

16、詢的實際情況和已有的訪問方法，我們采用如下的一些啟發(fā)式規(guī)則來確定查詢片段.規(guī)則1.利用結構連接來處理不確定路徑.當查詢樹Q中出現了表示祖先-后代關系的邊時，則兩端節(jié)點之間可能的路徑是任意的，例如圖1中節(jié)點A和B之間帶“ *”的邊.這種不確定的路徑的匹配無論是在數據中，還是在路徑索引中都是代價很大的.利用結構連接來直接判斷候選節(jié)點之間的祖先-后代關系是解決不確定路徑匹配的較好方法.基于這樣的認識，分解產生的查詢片段中不應當包含表示祖先-后代關系的邊，該類邊只能出現在查詢片段之間.規(guī)則2.查詢片段不支持分支節(jié)點.我們的基本訪問方法不能直接支持帶有分支節(jié)點的路徑查詢，所以分支節(jié)點不能作為查詢片段所對

17、應路徑的中間節(jié)點.規(guī)則3.值謂詞節(jié)點作為查詢片段的末端節(jié)點.為了方便結合路徑索引和值索引來計算值謂詞條件，我們規(guī)定值謂詞節(jié)點只作為查詢片段的末端節(jié)點.多個值謂詞節(jié)點之間的關系通過結構連接來實現根據如上的3條啟發(fā)式規(guī)則，我們可以給出一個特定的查詢分解狀態(tài)定義8.給定一棵查詢樹Q=(VQ,Eq),如果Q中的一條路徑p=?w,v2,，vn?滿足如下的條件，則p是Q的一條簡單路徑：(1)對 i 1,.,n,M Vq , vi 是 vi+1 的父親節(jié)點；(2)路徑中相鄰兩個節(jié)點之間的邊(w, vi+1)不表示祖先-后代關系；(3)如果存在vi是Q中的分支節(jié)點或值謂詞節(jié)點，則i =n.從定義8可以看出，查

18、詢樹中的簡單路徑不包括祖先-后代結木關系，分支節(jié)點和值謂詞節(jié)點只能出現在路徑末端的路徑，它的計算可以直接通過路徑索引的查詢來完成定義9.給定一棵查詢樹CHVQ a),如果一個路徑集合P=p|p是查詢樹Q中出現的路徑滿足條件：(1) p是Q中的簡單路徑；(2)查詢樹Q中的每個節(jié)點至少包含在一條路徑中，則P是Q的一個簡單路徑分解.如果P還滿足第3個條件：(3) P的每條路徑p都是最長的，即Q中不存在另一個更長的簡單路徑包含p,則P是Q的一個最小簡單路 徑分解.,而且最小簡單路可以看出，最小簡單路徑分解是查詢樹的所有簡單路徑分解中包含簡單路徑數目最少的徑分解是唯一的.圖2(a)和圖2(b)給出了兩個

19、可能的簡單路徑分解例子，圖中虛線包圍的區(qū)域是一個簡單路徑的范圍.圖2(b)所給出的是最小簡單路徑分解，其中的每個簡單路徑都不可能被更長的簡單路徑所包含.依據最小簡單路彳5分解的概念，我們可以得到相應的查詢分解狀態(tài).給定一棵查詢樹Q及其最小簡單路徑分解P, P中的每條簡單路徑對應于一個查詢片段，查詢片段之間的邊則由它們所包含的查詢節(jié)點之間的邊來決定.圖2(c)給出了根據圖2(b)中的最小簡單路徑分解得到的查詢分解狀態(tài)BA .,Path decomposition, of query tree f司路徑分解卞 g據最小簡單計劃E.蔓3.1F勺善詢弁戈帕涉查詢片段的截!個復雜的優(yōu)化 e 可題.HBC

20、,需要經過進一步的轉比才能的/,我禰施券劍南探討，只對其唯芙健聞題加雨HH在我彳門的.a夕分解狀態(tài)中、-'，每個查詢片段被看成是“4的，可以通過直接的訪問方法得到中嬲吉果.我們 對查詢片段的具體狀態(tài)給出明確的描述，為其確定具體操作符的選擇.每個查詢片段的狀態(tài)描述包括(LabelPath, Output,Operator), 其中LabelPath是查詢片段對應的簡單路徑,Output是查詢片段所需輸出的結果所包括的查詢節(jié)點，而Operator則是根據前兩者為該查詢片段所選擇的具體操作符查詢片段輸出的結果作為中間結果將會與結構相關的其他中間結果進行結構連接結果應當保留將用于進一步連接的元

21、素節(jié)點信息,或者是查詢最后輸出結果的內容,所以查詢片段的輸出 .查詢片段輸出的確定是根據查詢片段在查詢分解狀態(tài)樹中的邊，按照如下的規(guī)則來進行.給定一個路徑查詢Q=( VQ, Eq),從Q中根據最小簡單路徑分解得到的查詢分解狀態(tài)D=(VD, Ed), D中任意一個查詢片段(2)N的輸出結果由所有滿足如下條件的查詢節(jié)點 u N ;v Vq,v N,(u,v) Eq ;或者u是Q的目標節(jié)點.u所對應的元素組成一旦確定了輸出結果，對每個查詢片段就可以根據其對應的簡單路徑的情況指定相應的基本操作3.2結構連接順序的選擇在以路徑查詢的目標節(jié)點為查詢結果的前提下,如果每個結構連接操作只產生下一步操作所需的數

22、據作為結果，可以大大減小中間結果的規(guī)模，避免不必要的中間結果傳遞.基于這樣的觀察，我們以目標節(jié)點作為導向，只考慮滿足這種特性的查詢計劃.,選擇最優(yōu)的計劃.然后考慮 ,其根節(jié)點是子樹的目標節(jié)點我們采用如下的啟發(fā)式方法來選擇查詢計劃：將目標節(jié)點所屬的查詢片段作為根節(jié)點，從而將查詢狀態(tài)樹 劃分為若干個子樹.對每個子樹分別考慮以子樹的根節(jié)點為輸出結果的查詢計劃各個子樹與根節(jié)點的可能連接計劃.目標節(jié)點的每個子樹形成了一個查詢子樹 為每個子樹選擇查詢計劃是一個遞歸的過程 這樣產生的查詢計劃的數目是相當有限的 ，只與分支節(jié)點的不同連接順序選擇有關 .圖3描述了一個查詢 分解狀態(tài)可能有的查詢計劃 .圖3(a)

23、是將目標查詢片段作為根節(jié)點的查詢分解狀態(tài)樹 ，FGH寸應的是目標查詢 片段.它對應的兩個可能的查詢計劃如圖 3(b)和圖3(c)所示.QSelection of queryplanBCQCCDE圖3查詢計劃的選擇4 擴展的基本操作在基于最小簡單路徑分解的計算框架中，由于以目標節(jié)點為導向和簡單路徑原子化的前提存在，原有的基本操作不能滿足需求，需要引入新的操作.4.1 擴展的索引查詢操作在我們基于簡單路徑的分解框架中，查詢片段對應的簡單路徑是一個原子操作，需要路徑索引的支持，直接得到滿足簡單路徑關系的結果，從而避免多個二元結構連接操作.根據簡單路徑的定義，為了有效地支持其查詢，需要擴展的索引查詢操

24、作包括:(1) SimplePath:對給定的簡單標記路徑L1/L2/，7Ln,返回滿足路徑約束條件的指定結果，包括：Li對應的元素節(jié)點集合，Ln對應的元素節(jié)點集合，或者(Li,Ln)對應的元素節(jié)點對集合.PathWithPredicate:對給定的標記路徑L1/L2/-7Ln值謂詞條件,返回滿足路徑約束條件和值謂詞條件的指定結果，包括：Li對應的元素節(jié)點集合，Ln對應的滿足值謂詞條件的元素節(jié)點集合，或者(Li, Ln)對應的元素節(jié)點對集合.文獻11中詳細論述了利用SUPEXt引實現上述操作的方法.4.2 選擇性結構連接操作結構連接是XML查詢處理中的核心操作，目前所考慮的結構連接操作是一種完

25、全結構連接操作，即結構連接所輸出的結果是參加連接的兩個輸入集合中滿足條件的元組的合并.在我們的計算框架中，查詢樹的計算是以目標節(jié)點為導向的，而不必給出全連接的結果 .選擇性結構連接操作只輸出需要保留的部分作為結果，對無用查詢結果的剔除可以盡早進行，其定義如下：定義10.給定兩個輸入集合A=(a, a?,，am)和D=(d1, d2,，dn),A和D分別是m維和n維元組的集合，對指定的潛在祖先ai,潛在后代dj以及輸出結果定義，選擇性結構連接操作產生的結果集合為 ( X1, x2,，xp)|ai是dj的祖先；xk?a1,，am或者xk?d1,，dn,且xk在輸出結果定義中,k=1,，p.4.3

26、選擇性結構連接算法實現本節(jié)給出了兩類選擇性結構連接算法：排序合并和基于區(qū)域劃分4.3.1 選擇性排序合并結構連接算法根據輸出結果是 A或D中的元素，選擇性排序合并結構連接(selective sort merge join, 簡稱SSMJ)算法有兩個:SSMJ-Anc和SSMJ-Des.它們利用了只輸出一個輸入集合中元素的特點，避免了對某些元素的處理，從而避免了完全結構連接的排序合并算法可能產生的對輸入集合的多遍掃描.這兩個算法在最壞情況下對兩,以及個輸入集合各掃描一遍.圖4和圖5分別給出了完全結構連接的按祖先和后代排序合并算法的最壞情況SSMJ-Anc和SSMJ-Des在這兩種情況下的效率

27、.在圖4(a)所描述的數據分布情況下，圖4(b)描述了按祖先排序合并算法進行完全結構連接的對D的多遍掃描，而圖4(c)中的SSMJ-Anc算法只需從d1到dn的掃描比較.圖5-后代關系的計算.中的情況也相類似.需要指出的是，SSMJ-Anc和SSMJ-Des只適用于祖先針對輸入數寸/Ia2d2n無序腳情況a1aod1d2d1%a1 .a2d一一d1join,簡稱RPJ)嗎* 施了完全結構連接操作 于區(qū)域劃分的：算法d1dn,我們已葡此座處域劃分的結木連接算法.d2 r一 r A. . dn+1.針對選擇性結構連接操作d2n?1于區(qū)域劃分的選擇陶承構連盤卜法(selective range pa

28、rtitionin g join,出結果限定把 人£的SRPJdAnc和輸出結果限定通-D:的-SRPJtDe；s.4.3.2.1SRPJ舜cXMWe(b)(bS0Vt merge 邸拈bybyn霹瓢e nodnts nodesLXHf編碼的特點(典整A cas(1)子集合劃分階段.首先對后代節(jié)縹解SRPJ-Anc 耀 Xes量,.d2ao a1J / / (range partitioningdna2da3我們提出了基 a。.簡稱SRPJ).該類算法包括兩個：輸dn(c博然MA晚s (cLSSMJiAncan旌!弦嘴，產生結果-Anc algorithm嘲g字分方法與RPJ相同.當

29、對祖先節(jié)點集合個階段：A進行劃分時，可以利用祖先節(jié)點的特點來產生部分結果.如果A中的節(jié)點a的區(qū)域編碼完全覆蓋了一個子區(qū)間R,只要R對應的子集合 D中的元素節(jié)點數目不為0, D中所有的節(jié)點都是a的后代節(jié)點.利用這個特點，我們在對A中的節(jié)點進行劃分時就可以判斷一些節(jié)點是否有后代節(jié)點，具體的判斷規(guī)則為：假設A中的一個節(jié)點a的區(qū)域編碼完全覆蓋了n個子區(qū)間，如果這些子區(qū)間所對應的D的子集合中至少存在一個不為空，那么在D中一定存在a的后代節(jié)點，即a應當作為結果輸出.對于確定為輸出結果的A中節(jié)點，就不再劃分到子集合中進行處理；對于那些不能確定為結果的A中節(jié)點，只需將其劃分到與區(qū)域編碼部分相交的子區(qū)間所對應的

30、子集合中，這樣的子集合的最大數目為2.(2)連接階段.對于那些在子集合劃分階段不能確定的A中的節(jié)點，需要實際的連接來進行檢查.對每一對子集合A和D,分別進行連接.由于A中的一個節(jié)點可能被劃分到兩個子集合中，所以它可能在結果中出現兩次，即連接階段產生的結果集中可能出現重復元素(3)去重階段.子集合劃分和連接階段已經產生了所有的輸出結果，但連接階段所產生的結果中可能會出現重復值.該階段的主要任務是合并各個子集合對的連接結果，去掉重復值.4.3.2.2 SRPJ-Des 算法SRPJ-Des的基本思想與 SRPJ-Anc類似，不同的是考慮的目標是集合D算法分為兩個階段：(1)子集合劃分階段.首先對祖

31、先節(jié)點集合A進行劃分，所采用的劃分方法與RPJ相同，不同的是對每個子集合A額外記錄該子集合中區(qū)域編碼完全覆蓋其對應子區(qū)間的節(jié)點個數V.如果A中節(jié)點a的區(qū)域編碼完全覆蓋了一個子區(qū)間R,則D中所有的節(jié)點都是a的后代節(jié)點.利用這個特點，在對后代節(jié)點集合D進行劃分時可以判斷一些節(jié)點是否有祖先節(jié)點，判斷規(guī)則為：假設D中的一個節(jié)點 d應當劃分到 D,如果對應的 A的V值不為0,則A中一定存在d的祖先節(jié)點，即d應當作為結果輸出.對于確定為輸出結果的D中節(jié)點，就不再劃分到子集合中進行處理；對于那些不能確定為結果的D中節(jié)點，仍按照RPJ算法中的劃分方法劃分到子集合中，進行進一步的處理.(2)連接階段.對于在子集

32、合劃分階段沒有確定的D中節(jié)點，連接階段進行進一步的處理.根據裝入內存的子集合的不同，可以采用相應的連接算法.由于D中每個元素最多只被劃分到一個子集合中，所以連接階段產生的結果中沒有重復.兩個階段產生的結果可以直接合并生成最后的輸出結果5實驗結果和分析為了對本文中所提出方法的有效性進行驗證，我們進行了初步的實驗.本節(jié)對實驗的結果進行了描述和分析.5.1 實驗設置我們的實驗在 Native XML數據管理系統(tǒng) Orient-X 的基礎上進行，所有的算法都用C+播程語言來實現.所有的實驗在一臺Duron ,256M RAM,40G 硬盤的PC上運行，底層操作系統(tǒng)是 Windows XP.我們選擇執(zhí)行

33、時間為評價指標.這里所給出的執(zhí)行時間都是運行實驗多次，去掉最高和最低值后得到的平均執(zhí)行時間.5.2 選擇性結構連接的有效性選擇性結構連接操作在我們的路徑查詢框架中具有重要的作用，本節(jié)我們結合所提出的多種實現算法對其進行性能上的分析.我們采用 舊M XMLGenerator生成了大小為113M的實驗文檔，所用的DTD如圖6所示，其中各個元素的個 數在表1中給出.我們采用了表2所示的6個查詢，它們可以分為兩類:Q1到Q4是簡單結構關系查詢；Q5和Q6 是復雜查詢，用來反映包含多個連接操作的查詢的執(zhí)行情況.除了人工生成的數據集以外，我們也在真實的數據集DBLP和XMark上進行了實驗，實驗結果類似.

34、?!ELEMENTmanager (name, (manager | department | employee)+)? ?!ELEMENTdThParEmTEt oKsym微 efemadata eetployee+, department*)? ?!ELEMENT emplo 蹲eQname+C eM?l?勺 DTD?!ELEMeNT namesPCIDATfsynthetic data set?!ELEMENT email (#PCDATA)?Table 2 Description ofset表2 人工數據集的查詢描述們實現了 Query 擇性排序合并 Q1表1人工數據集的描述Eleme

35、ntNumber queries of synthetic dataManager38Department286459Employee543685NameResllt11 390Result 5 類 算法：選Path expressiEma"(Ancest(59 946 (Descendant)連接manager(SSMJ),Stack-Tree-Filter(STF),Stack-Tree(ST),選擇性區(qū)域劃分連接(SRPJ)和區(qū)域劃分連接(RPJ),每類算法包括結果限定在祖先和后代的兩個算法.STF算法是對Stack-Tree類的算法進行了改寫，使其只輸出指定的結果.ST算法是

36、在Stack-Tree類的算法后附加了一個投影到指定輸出的過程，RPJ也是類似.我們將這5種算法分為兩類進行比較：基于排序合并和基于劃分，這是因為我們在計算基于排序合并算法的執(zhí)行時間時沒有 考慮排序的時間，在這種t#況下，基于排序合并的算法效率明顯高于基于劃分的算法.此外，實驗的目的是想反映選擇性結構連接算法與其對應的完全結構連接算法加投影的性能比較圖7和圖8描述了排序合并類算法的性能，分別比較了輸出結果限定在祖先節(jié)點和后代節(jié)點上的算法.從圖7中可以看出，選擇性結構連接算法SSMJ和STF的性能在各個查詢上均優(yōu)于ST,這說明選擇性結構連接算法的實現策略在性能上優(yōu)于完全結構連接加投影的實現策略.

37、對查詢Q1,Q2和Q3,兩種策略的執(zhí)行時間相差較大，而Q4的執(zhí)行時間則比較接近 ，這是由于前3個查詢所涉及的祖先節(jié)點元素manager和department是遞歸定義的，而Q4中的employee則沒有遞歸定義.當祖先元素存在遞歸定義時，選擇性結構連接算法由于可以避免對嵌套節(jié)點的多次處理 ，所以較大程度地提高了執(zhí)行效率.此外,SSMJ和STF在各個查詢上的執(zhí)行時間都比較接近,SSMJ略優(yōu)于STF,這是由于兩種算法本質上是相同的，而STF在內存中的棧和鏈表處理稍復雜一些.圖8圖9和圖10描述了基于劃分的算法的性能比較 上都優(yōu)于基于區(qū)域劃分的完全結構連接加投影的方法所描述的性能比較表現了與圖7類似

38、的特征.從圖中可以看出，選擇性結構連接算法 SRPJ在各個查詢.除Q4的優(yōu)勢不明顯以外，其他3個查詢上SRPJ都大大優(yōu)于RPJ.這個特征也與排序合并類算法的表現相一致80s 705.2.1復m睿曲t 50表2中n勺405_SSMJ ,STF -ST和Q6是兩個較3先節(jié)點和后代節(jié)題實現了這兩個查J復雜的查詢，每， .SSMJ,STF)40s 35 m 30 t 25 卜查詢包含0r麗彳 和SRpJj同比, SSMJ 亙STF ST連接.我們用五類算法分別基于結果為祖Stack-Tree(RPJj0算法完成連接劃分類算法的實驗結果最后對完全連接結果進行一次援影節(jié)所述，而Path-S(Path-R)

39、則表示先采用劃給出了排序合并類算法和Q1中可以癖出，用SMJ木口 STF執(zhí)行時間SRPJ與Path-R相比而菽得的在徐優(yōu)勢Q3Q4Q2Q3Q4The result of sort merge algorithmsTable 3 The result .by ancestormerge黝內嘀的祖先節(jié)點的堪篇并類算法鈿察里r (s)表3排序合并類算法Table，e m350 3The resulFRPJIRPJQ5Q65.3旬執(zhí)行計QuerySSMJ STF S廊圖8The result of sort merge algorithmsby descendantof queries using s

40、ort藤潸坪部端SSMJ STF所S常合并類算法的結果的查詢結果350我2502001501世步氈實驗.：解處理策略的可行座partitio表4戈ning algorism.300250 口 SRPJ. RPJof queries usingJ分類算法的查200后果Ancestor (s)SRPJPath-R500500Descendants (s)SRPJrPath-R劃的性能證所提出聲匿詢價雞僉采用Q4<Mark數據集，選擇了大/Teresu1t 0fM>印0跖利ng0M的文檔.表5給出了實驗中所用Theort甲partQion徹一個不帶分支的路徑algorithmsby an

41、cestor圖9輸出祖先節(jié)點的劃分類算法的結果algorithmsby descendant圖10輸出后代節(jié)點的劃分類算法的結果查詢，存在不確定路徑.而QP2則帶有分支路徑，是一個樹狀的路徑查詢.對QP1和QP2,我們分別采用了兩個不 同的執(zhí)行計劃來實現.連接計劃通過單步的結構連接操作來完成查詢，連接順序采用逐步向目標節(jié)點靠攏的順序.分解計劃是采用本章所提出的分解策略所產生的執(zhí)行計劃.兩個查詢例子的執(zhí)行結果分別見表6和表7.從表6可以看到，除了數據為1M的情況以外，QP1的分解計劃的執(zhí)行時間大大小于連接計劃.對QP2來說，這種執(zhí)行時間的差距更為明顯 .雖然這里的連接計劃并不是通過優(yōu)化而選出的最

42、優(yōu)計劃，但從實驗結果仍然可以看出，基于分解策略的執(zhí)行計劃具有一定的優(yōu)勢，可以成為一種優(yōu)先考慮的選擇.Table 5 Description of path queries表5路徑查詢描述承了半結構化數據領域的研究，文獻7,8對導航式遍歷的路徑查詢匹配方法進 行了研究.導航式遍歷方法 簡單、直接，但執(zhí)行效率不能得到保證，尤其是在大數據量的情 況下.QueryPath expression“一次QP1/site 集合”的路徑查詢計算策略 目前被廣泛接 受，基于該策略的研究工作包括多個方面，結構連接算法的研究是其中的重點.目前已有的工作大體上可以分為兩類：基于排序合并的算法6?8和基于劃分的方法 .

43、排序合并類的算法依賴于一定的前提條件：數據集合是有序的，或者集合上存在索引.當條件不成立時，算法的效率會大大降低.文獻9中的劃分方法雖然不要求輸入數據集合有序或存在索引，但只適用于其提出的PBiTree編碼，應用范圍非常有限.在結構連接操作的基礎上，對路徑查詢的整體處理框架的研究目前還比較少.文獻7提出了對正則路徑表達式的分解計算方法，但只針對沒有分支的路徑查詢，而大量的結構連接操作在該方法是不可避免的.文獻10從信息過濾的角度研究了如何對路徑查詢進行分解，建立對路徑查詢的索引，從而實現對XML文檔的高效過濾.止匕外，文獻13,14對結構連接的結果估計問題進行 了研究，文獻15則針對結 構連接

44、的順序選擇問題提出 了多種優(yōu)化算法.除了基于結構連接的策略以外，還有一些研究工作從其他角度出發(fā)對路徑查詢 處理進行了探討.文獻16針對路徑查詢的匹配，提出了新的整體樹狀連接算法 ，不會產生中間結果.采用這種策略處理路徑查詢的問題 在于將整個的執(zhí)行由連接算法控制，不能進行優(yōu)化和選擇.路徑查詢的計算是XML查詢處理中的關鍵問題，本文結合實際的系統(tǒng)，提出了路徑查詢的計算框架.首先給出了路徑查詢的一些相關定義，在此基礎上提出了對查詢樹的最小簡單路徑分解.針對由最小簡單路徑分解導出的查詢分解狀態(tài)，提出了一些擴展的操作符，包括選擇性結構連接操作和擴展的索引查詢操作，并分別給出了具體的實現方法.我們的工作是

45、在 Native XML據管理系統(tǒng)中查詢計算的環(huán)境下進行的.在路徑查詢的研究領域中，仍然有許多問題有待于進一步的探討，如基于代價的查詢優(yōu)化、更多的基本操作（如多路結構連接等）、新的訪問方法 等.未來我們將在路徑查詢的基礎上 ，對XQuery的查詢處理進行進一步的研究 .References :1 Bray T, Paoli J, Sperberg-McQueen CM, Maler E, eds. Extensiblemarkup language (XML) (2nd Edition). W3CRecommendation, 2000.2 Clark J, DeROse S, eds. XM

46、L Path language (XPath) Version . W3C Recommendation, 1999.3 Chamberlin D, Florescu D, Robie J, Simeon J, Stefanescu M, eds. XQuery: A query language for XML. W3C WorkingDraft, 2001.4 Goldman R, McHugh J, Widom J. From semisturctured data to XML: Migrating the lore model and query language. In: Proc

47、. of the 2nd Int ' l Workshop on the Web and Databases (WebDB 99).1999.5 McHugh J, Widom J. Query optimization for XML. In: Atkinson MP, Orlowska ME, Valduriez P, Zdonik SB, BrodieML, eds. Proc. of the 25th Int l Conf . on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 1999. 3

48、15?326.6 Zhang C, Naughton J, DeWitt D, Luo Q, Lohman G. On supporting containment queries in relational database management systems. In: Timos S, ed. Proc. of the 2001 ACM SIGMOD Int' l Conf. on Management of Data. New York: ACM Press,2001. 425?436.7 Li QZ, Moon B. Indexing and querying XML dat

49、a for regular path expressions. In: Apers PMG, Atzeni P, Ceri S, Paraboschi S, Ramamohanarao K, Snodgrass RT, eds. Proc. of the 27th Int l Conf . on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 2001. 361?370.8 AI-Khalifa S, Jagadish HV, Koudas N, Patel JM, Srivastava D, Wu YQ. S

50、tructural joins: A primitive for efficient XML query pattern matching. In: Agrawal R, Dittrich K, Ngu AHH, eds. Proc. of the 18th Int' l Conf. on DataEngineering. Los Alamitos: IEEE Press, 2002. 141?152.9 WangW, Jiang H, Lu H, Yu X. PBiTree coding and efficient processing of containment join. In: Dayal U, Ramamritham K, Vijayaraman TM, eds. Proc