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

1、以目標(biāo)節(jié)點為導(dǎo)向的 X M L 路徑查詢處理王靜 1,孟小峰王宇:王珊1(中國科學(xué)院 計算技術(shù)研究所，北京100080)2(中國人民大學(xué)信息學(xué)院，北京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查詢語言將復(fù)雜路徑表達(dá)式作為核心內(nèi)容.為了加速路徑表達(dá)式處理，基于路徑分解和結(jié)構(gòu)連接操作的處理策略需要更深入的研究.以目標(biāo)節(jié)點為導(dǎo)向的XML路徑查詢處理框架被提了出來.該方法利用了擴(kuò)展基本操作來減少連接操作的數(shù)目.在路徑分解和查詢計劃選擇的過程中，利用查詢樹中的目標(biāo)節(jié)點來避免中間結(jié)果的傳遞.除了分解規(guī)則和策略以外，提出了一組擴(kuò)展的基本操作和實現(xiàn)算法.初步的實驗結(jié)果顯示，該方法具有良好的性能.它為路徑查詢處理提供了更多的選擇.關(guān)鍵詞：XML查詢處理；路徑表達(dá)式；結(jié)構(gòu)連接；選擇性結(jié)構(gòu)連接；路徑索引?國家自然科學(xué)基金 )

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

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

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

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

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

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

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

14、 路徑查詢的分解計算根據(jù)實際的查詢需求以及底層訪問方法的支持，我們提出了自己的查詢計算框架.我們所研究的查詢處理框架基于如下的兩個前提：(1)查詢樹的目標(biāo)節(jié)點是查詢的輸出結(jié)果.在查詢樹中，只有目標(biāo)節(jié)點在數(shù)據(jù)中的映射節(jié)點是查詢的輸出結(jié)果 ，整個查詢樹的計算是以目標(biāo)節(jié)點為導(dǎo)向的.(2)路徑索引的支持.充分利用路徑索引，盡量避免不必要的結(jié)構(gòu)連接操作，從而減少計算代價，這是我們的一個指導(dǎo)思想.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中導(dǎo)出的一個查詢分解狀態(tài)是一棵樹D=(W E),弘中的每個節(jié)點n對應(yīng)于Q的一個查詢片段滿足如下的條件：(1) n,m Vd,N M ;(2) VqN ；n Vd EdEq； n Vd, u ,v N, (u,v) Ed .查詢片段是可以借助索引等方式的支持進(jìn)行快速計算的基本單位，各個查詢片段之間通過結(jié)構(gòu)連接操作來組合其執(zhí)行的中間結(jié)果.對一個路徑查詢而言，根據(jù)查詢片段劃分的不同，可能的查詢分解狀態(tài)有很多.具體的查詢片段的劃分與底層的訪問支持方式有著密切的關(guān)系2.2簡單路徑分解查詢片段的確定是查詢分解的關(guān)鍵.通過考慮查

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

17、應(yīng)路徑的中間節(jié)點.規(guī)則3.值謂詞節(jié)點作為查詢片段的末端節(jié)點.為了方便結(jié)合路徑索引和值索引來計算值謂詞條件，我們規(guī)定值謂詞節(jié)點只作為查詢片段的末端節(jié)點.多個值謂詞節(jié)點之間的關(guān)系通過結(jié)構(gòu)連接來實現(xiàn)根據(jù)如上的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)不表示祖先-后代關(guān)系；(3)如果存在vi是Q中的分支節(jié)點或值謂詞節(jié)點，則i =n.從定義8可以看出，查

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

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

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

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

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

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

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

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

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

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

28、rtitionin g join,出結(jié)果限定把 人£的SRPJdAnc和輸出結(jié)果限定通-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旌!弦嘴，產(chǎn)生結(jié)果-Anc algorithm嘲g字分方法與RPJ相同.當(dāng)

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

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

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

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

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

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 人工數(shù)據(jù)集的查詢描述們實現(xiàn)了 Query 擇性排序合并 Q1表1人工數(shù)據(jù)集的描述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),每類算法包括結(jié)果限定在祖先和后代的兩個算法.STF算法是對Stack-Tree類的算法進(jìn)行了改寫，使其只輸出指定的結(jié)果.ST算法是

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

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

38、的特征.從圖中可以看出，選擇性結(jié)構(gòu)連接算法 SRPJ在各個查詢.除Q4的優(yōu)勢不明顯以外，其他3個查詢上SRPJ都大大優(yōu)于RPJ.這個特征也與排序合并類算法的表現(xiàn)相一致80s 705.2.1復(fù)m睿曲t 50表2中n勺405_SSMJ ,STF -ST和Q6是兩個較3先節(jié)點和后代節(jié)題實現(xiàn)了這兩個查J復(fù)雜的查詢，每， .SSMJ,STF)40s 35 m 30 t 25 卜查詢包含0r麗彳 和SRpJj同比, SSMJ 亙STF ST連接.我們用五類算法分別基于結(jié)果為祖Stack-Tree(RPJj0算法完成連接劃分類算法的實驗結(jié)果最后對完全連接結(jié)果進(jìn)行一次援影節(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黝內(nèi)嘀的祖先節(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常合并類算法的結(jié)果的查詢結(jié)果350我2502001501世步氈實驗.：解處理策略的可行座partitio表4戈ning algorism.300250 口 SRPJ. RPJof queries usingJ分類算法的查200后果Ancestor (s)SRPJPath-R500500Descendants (s)SRPJrPath-R劃的性能證所提出聲匿詢價雞僉采用Q4<Mark數(shù)據(jù)集，選擇了大/Teresu1t 0fM>印0跖利ng0M的文檔.表5給出了實驗中所用Theort甲partQion徹一個不帶分支的路徑algorithmsby an

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

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

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

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

45、在 Native XML據(jù)管理系統(tǒng)中查詢計算的環(huán)境下進(jìn)行的.在路徑查詢的研究領(lǐng)域中，仍然有許多問題有待于進(jìn)一步的探討，如基于代價的查詢優(yōu)化、更多的基本操作（如多路結(jié)構(gòu)連接等）、新的訪問方法 等.未來我們將在路徑查詢的基礎(chǔ)上 ，對XQuery的查詢處理進(jìn)行進(jìn)一步的研究 .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