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

1、以目標(biāo)節(jié)點(diǎn)為導(dǎo)向的XML路徑查詢處理*Supported by the National Natural Science Foundation of China under Grant Nos.60073014, 60273018 (國家自然科學(xué)基金); the National High-Tech Research and Development Plan of China under Grant No.2002AA116030 (國家高技術(shù)研究發(fā)展計劃(863); the Key Project of Ministry of Education of China under Grant N

2、o.03044 (國家教育部科學(xué)技術(shù)重點(diǎn)項目); the Excellent Young Teachers Program of Ministry of Education of China (教育部優(yōu)秀青年教師資助計劃)作者簡介: 王靜(1975),女,山西襄垣人,博士,主要研究領(lǐng)域為數(shù)據(jù)庫與知識庫,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ù)倉庫.王 靜1, 孟小峰2, 王 宇

3、2+, 王 珊21(中國科學(xué)院 計算技術(shù)研究所,北京 100080)2(中國人民大學(xué) 信息學(xué)院,北京 100872)Target Node Aimed Path Expression Processing for XML DataWANG Jing1, MENG Xiao-Feng2, WANG Yu2+, WANG Shan21(Institute of Computing Technology, The Chinese Academy of Sciences, Beijing 100080, China)2(Information School, Renmin University of

4、China, Beijing 100872, China)+ Corresponding author: Phn: +86-10-62515575, Fax: 86-10-62519453, E-mail: sandpiperwyReceived 2003-12-25; Accepted 2004-06-10Wang J, Meng XF, Wang Y, Wang S. Target node aimed path expression processing for XML data. Journal of Software, 2005,16(5):827-837. DOI: 10.1360

5、/jos160827Abstract:XML query 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

6、processing framework for XML data is proposed. This approach makes use of the extended basic operations 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 result

7、s. In addition to decomposition 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 expressio

8、n; structural join; selective structural join; path index摘 要:XML查詢語言將復(fù)雜路徑表達(dá)式作為核心內(nèi)容.為了加速路徑表達(dá)式處理,基于路徑分解和結(jié)構(gòu)連接操作的處理策略需要更深入的研究.以目標(biāo)節(jié)點(diǎn)為導(dǎo)向的XML路徑查詢處理框架被提了出來.該方法利用了擴(kuò)展基本操作來減少連接操作的數(shù)目.在路徑分解和查詢計劃選擇的過程中,利用查詢樹中的目標(biāo)節(jié)點(diǎn)來避免中間結(jié)果的傳遞.除了分解規(guī)則和策略以外,提出了一組擴(kuò)展的基本操作和實現(xiàn)算法.初步的實驗結(jié)果顯示,該方法具有良好的性能.它為路徑查詢處理提供了更多的選擇.關(guān)鍵詞:XML查詢處理;路徑表達(dá)式;結(jié)構(gòu)連接

9、;選擇性結(jié)構(gòu)連接;路徑索引中圖法分類號:TP311文獻(xiàn)標(biāo)識碼: A隨著XML1標(biāo)準(zhǔn)被廣泛接收和采用,XML數(shù)據(jù)的管理和查詢問題也引起了人們的重視,成為研究的熱點(diǎn).盡管XML可以描述非常復(fù)雜的結(jié)構(gòu),其本質(zhì)仍然是樹狀的數(shù)據(jù).針對XML的查詢,學(xué)者們已經(jīng)提出了多種XML查詢語言,例如XPath2,XQuery3等,這些查詢語言都將路徑表達(dá)式作為核心內(nèi)容.針對路徑查詢的處理問題,人們已經(jīng)進(jìn)行了大量的研究工作.在樹狀的XML數(shù)據(jù)中匹配路徑查詢的基本方式是對數(shù)據(jù)進(jìn)行導(dǎo)航式的遍歷,文獻(xiàn)4,5對這種方式進(jìn)行了探討,它簡單、直接,但執(zhí)行效率不能得到保證,尤其是在大數(shù)據(jù)量的情況下.導(dǎo)航式遍歷方法的低效性促使了類似

10、于關(guān)系數(shù)據(jù)庫中“一次一集合”的路徑查詢計算策略的出現(xiàn).目前被廣泛接受的分解連接查詢執(zhí)行策略的基本思路是,首先定位路徑查詢樹中每個節(jié)點(diǎn)的候選元素節(jié)點(diǎn)集合,然后通過結(jié)構(gòu)連接操作組合這些中間結(jié)果來生成最后的結(jié)果.采用這種策略會產(chǎn)生大量的結(jié)構(gòu)連接操作.目前,這方面的工作主要集中在高效的結(jié)構(gòu)連接算法上6-9,而對路徑查詢的整體處理框架的研究較少.文獻(xiàn)7提出了對正則路徑表達(dá)式的分解計算方法,但只針對沒有分支的路徑查詢,而且大量的結(jié)構(gòu)連接操作是該方法不可避免的.文獻(xiàn)10從信息過濾的角度研究了如何對路徑查詢進(jìn)行分解,建立對路徑查詢的索引,考慮的問題不同.在基本操作的基礎(chǔ)上,設(shè)計合理的路徑分解和計算框架是一個需

11、要進(jìn)一步研究的問題.針對這個問題,結(jié)合在Native XML數(shù)據(jù)管理系統(tǒng)Orient-X中的實際考慮,本文提出了一個以目標(biāo)節(jié)點(diǎn)為導(dǎo)向的路徑查詢處理框架.該方法充分利用基本操作的支持,增大了基本查詢片段的粒度,從而減少了結(jié)構(gòu)連接的數(shù)目.本文第1節(jié)給出一些基本的概念.第2節(jié)描述路徑查詢的分解方法.第3節(jié)針對分解后的路徑查詢,探討查詢計劃的生成.第4節(jié)描述查詢中用到的擴(kuò)展基本操作以及操作的具體實現(xiàn).第5節(jié)分析實驗結(jié)果.第6節(jié)對相關(guān)工作進(jìn)行概述.第7節(jié)對全文工作進(jìn)行總結(jié),并展望未來的工作.1 基本概念在本節(jié),我們首先給出一些基本概念的定義,這些概念在后面的描述中會用到.XML數(shù)據(jù)的路徑查詢可以描述為一

12、棵查詢樹,其形式化的描述如下:定義1. 針對XML數(shù)據(jù)的路徑查詢可以表示為一棵查詢樹Q=(V,E,Root,predicate),V是樹中節(jié)點(diǎn)的集合,Root是查詢樹的根.E是樹中節(jié)點(diǎn)之間邊的集合,邊分為兩種,分別表示父子包含關(guān)系和祖先后代包含關(guān)系.除了根節(jié)點(diǎn)之外,函數(shù)predicate賦給查詢樹中的每個節(jié)點(diǎn)一個謂詞條件,該條件針對元素的名字、屬性值及文本值等.這個查詢樹所表示的路徑表達(dá)式是XPath2的子集.在下面的章節(jié)中,為了簡單起見,查詢的定義簡化為Q= (VQ,EQ),VQ表示節(jié)點(diǎn),EQ表示節(jié)點(diǎn)間的邊.在實際的查詢樹中,往往只有一個節(jié)點(diǎn)在數(shù)據(jù)中的映射節(jié)點(diǎn)是查詢需要的輸出結(jié)果,其余節(jié)點(diǎn)之

13、間的邊只是對該節(jié)點(diǎn)的條件約束.基于這樣的考慮,我們給出如下的一些定義.定義2. XML查詢樹中存在一個節(jié)點(diǎn)n,它在數(shù)據(jù)中的映射是查詢的最終輸出結(jié)果,該節(jié)點(diǎn)稱為查詢的目標(biāo)節(jié)點(diǎn).定義3. 在XML查詢樹Q中,從根節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間的路徑稱為查詢的主路徑.定義4. 在XML查詢樹Q中,孩子節(jié)點(diǎn)數(shù)目大于1的節(jié)點(diǎn)(即出現(xiàn)路徑分叉的節(jié)點(diǎn))稱為分支節(jié)點(diǎn).定義5. 在XML查詢樹Q中,如果節(jié)點(diǎn)上除了針對元素名的謂詞條件外,還定義了針對元素值或元素屬性值的謂詞條件,這樣的節(jié)點(diǎn)稱為值謂詞節(jié)點(diǎn).考慮圖1中給出的查詢樹例子,它試圖找到研究領(lǐng)域包括數(shù)據(jù)庫的教授在會議上所發(fā)表的論文.節(jié)點(diǎn)F是查詢的目標(biāo)節(jié)點(diǎn),從節(jié)點(diǎn)A到F的

14、路徑是查詢的主路徑,節(jié)點(diǎn)C是分支節(jié)點(diǎn),而節(jié)點(diǎn)E上帶有針對元素文本值的謂詞條件,是值謂詞節(jié)點(diǎn).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.ElementName=“supporter”*ABCDEFGH*Target nodeF

15、ork nodeFig.1 An example of query tree圖1 查詢樹例子2 路徑查詢的分解計算根據(jù)實際的查詢需求以及底層訪問方法的支持,我們提出了自己的查詢計算框架.我們所研究的查詢處理框架基于如下的兩個前提:(1) 查詢樹的目標(biāo)節(jié)點(diǎn)是查詢的輸出結(jié)果.在查詢樹中,只有目標(biāo)節(jié)點(diǎn)在數(shù)據(jù)中的映射節(jié)點(diǎn)是查詢的輸出結(jié)果,整個查詢樹的計算是以目標(biāo)節(jié)點(diǎn)為導(dǎo)向的.(2) 路徑索引的支持.充分利用路徑索引,盡量避免不必要的結(jié)構(gòu)連接操作,從而減少計算代價,這是我們的一個指導(dǎo)思想.2.1 查詢分解狀態(tài)為了描述查詢分解,首先給出兩個定義: 定義6. 給定一個路徑查詢Q=(VQ,EQ),一個查詢片段

16、N是滿足如下條件的VQ中節(jié)點(diǎn)的集合:(1) ;(2) ,如果存在一個節(jié)點(diǎn)w位于從u到v的路徑上,則定義7. 給定一個路徑查詢Q=(VQ,EQ),從Q中導(dǎo)出的一個查詢分解狀態(tài)是一棵樹D=(VD,ED),VD中的每個節(jié)點(diǎn)n對應(yīng)于Q的一個查詢片段N.D滿足如下的條件:(1) ;(2) ;(3) ;(4) .查詢片段是可以借助索引等方式的支持進(jìn)行快速計算的基本單位,各個查詢片段之間通過結(jié)構(gòu)連接操作來組合其執(zhí)行的中間結(jié)果.對一個路徑查詢而言,根據(jù)查詢片段劃分的不同,可能的查詢分解狀態(tài)有很多.具體的查詢片段的劃分與底層的訪問支持方式有著密切的關(guān)系.2.2 簡單路徑分解查詢片段的確定是查詢分解的關(guān)鍵.通過考

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

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

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

20、給出了兩個可能的簡單路徑分解例子,圖中虛線包圍的區(qū)域是一個簡單路徑的范圍.圖2(b)所給出的是最小簡單路徑分解,其中的每個簡單路徑都不可能被更長的簡單路徑所包含.依據(jù)最小簡單路徑分解的概念,我們可以得到相應(yīng)的查詢分解狀態(tài).給定一棵查詢樹Q及其最小簡單路徑分解P,P中的每條簡單路徑對應(yīng)于一個查詢片段,查詢片段之間的邊則由它們所包含的查詢節(jié)點(diǎn)之間的邊來決定.圖2(c)給出了根據(jù)圖2(b)中的最小簡單路徑分解得到的查詢分解狀態(tài).*ABCDEFGH*(a) GD*ABCEFH*(b) AFGHBCDE(c) *Fig.2 Path decomposition of query tree圖2 查詢樹的路

21、徑分解3 查詢計劃的選擇根據(jù)最小簡單路徑分解所得到的查詢分解狀態(tài)是查詢執(zhí)行的基礎(chǔ),需要經(jīng)過進(jìn)一步的轉(zhuǎn)化才能成為查詢計劃.具體的查詢計劃的確定是一個復(fù)雜的優(yōu)化問題,我們不作詳細(xì)的探討,只對其中的關(guān)鍵問題加以說明.3.1 查詢片段的狀態(tài)確定在我們的查詢分解狀態(tài)中,每個查詢片段被看成是原子的,可以通過直接的訪問方法得到中間結(jié)果.我們對查詢片段的具體狀態(tài)給出明確的描述,為其確定具體操作符的選擇.每個查詢片段的狀態(tài)描述包括(LabelPath, Output,Operator),其中LabelPath是查詢片段對應(yīng)的簡單路徑,Output是查詢片段所需輸出的結(jié)果所包括的查詢節(jié)點(diǎn),而Operator則是根

22、據(jù)前兩者為該查詢片段所選擇的具體操作符.查詢片段輸出的結(jié)果作為中間結(jié)果將會與結(jié)構(gòu)相關(guān)的其他中間結(jié)果進(jìn)行結(jié)構(gòu)連接,所以查詢片段的輸出結(jié)果應(yīng)當(dāng)保留將用于進(jìn)一步連接的元素節(jié)點(diǎn)信息,或者是查詢最后輸出結(jié)果的內(nèi)容.查詢片段輸出的確定是根據(jù)查詢片段在查詢分解狀態(tài)樹中的邊,按照如下的規(guī)則來進(jìn)行.給定一個路徑查詢Q=(VQ,EQ),從Q中根據(jù)最小簡單路徑分解得到的查詢分解狀態(tài)D=(VD,ED),D中任意一個查詢片段N的輸出結(jié)果由所有滿足如下條件的查詢節(jié)點(diǎn)u所對應(yīng)的元素組成:(1) ;(2) ;或者(3) u是Q的目標(biāo)節(jié)點(diǎn).一旦確定了輸出結(jié)果,對每個查詢片段就可以根據(jù)其對應(yīng)的簡單路徑的情況指定相應(yīng)的基本操作.3

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

24、有限的,只與分支節(jié)點(diǎn)的不同連接順序選擇有關(guān).圖3描述了一個查詢分解狀態(tài)可能有的查詢計劃.圖3(a)是將目標(biāo)查詢片段作為根節(jié)點(diǎn)的查詢分解狀態(tài)樹,FGH對應(yīng)的是目標(biāo)查詢片段.它對應(yīng)的兩個可能的查詢計劃如圖3(b)和圖3(c)所示.OBOC OBOC OA AFGHBCDEOD OC OF OF OF OBOC OBOC AFGHBCDEOF OD OA OC (b) *AFGHBCDE(a) (c) Fig.3 Selection of query plan圖3 查詢計劃的選擇4 擴(kuò)展的基本操作在基于最小簡單路徑分解的計算框架中,由于以目標(biāo)節(jié)點(diǎn)為導(dǎo)向和簡單路徑原子化的前提存在,原有的基本操作不能滿

25、足需求,需要引入新的操作.4.1 擴(kuò)展的索引查詢操作在我們基于簡單路徑的分解框架中,查詢片段對應(yīng)的簡單路徑是一個原子操作,需要路徑索引的支持,直接得到滿足簡單路徑關(guān)系的結(jié)果,從而避免多個二元結(jié)構(gòu)連接操作.根據(jù)簡單路徑的定義,為了有效地支持其查詢,需要擴(kuò)展的索引查詢操作包括:(1) SimplePath:對給定的簡單標(biāo)記路徑L1/L2/Ln,返回滿足路徑約束條件的指定結(jié)果,包括:L1對應(yīng)的元素節(jié)點(diǎn)集合,Ln對應(yīng)的元素節(jié)點(diǎn)集合,或者(L1,Ln)對應(yīng)的元素節(jié)點(diǎn)對集合.(2) PathWithPredicate:對給定的標(biāo)記路徑L1/L2/Ln值謂詞條件,返回滿足路徑約束條件和值謂詞條件的指定結(jié)果,

26、包括:L1對應(yīng)的元素節(jié)點(diǎn)集合,Ln對應(yīng)的滿足值謂詞條件的元素節(jié)點(diǎn)集合,或者(L1,Ln)對應(yīng)的元素節(jié)點(diǎn)對集合.文獻(xiàn)11中詳細(xì)論述了利用SUPEX索引實現(xiàn)上述操作的方法.4.2 選擇性結(jié)構(gòu)連接操作結(jié)構(gòu)連接是XML查詢處理中的核心操作,目前所考慮的結(jié)構(gòu)連接操作是一種完全結(jié)構(gòu)連接操作,即結(jié)構(gòu)連接所輸出的結(jié)果是參加連接的兩個輸入集合中滿足條件的元組的合并.在我們的計算框架中,查詢樹的計算是以目標(biāo)節(jié)點(diǎn)為導(dǎo)向的,而不必給出全連接的結(jié)果.選擇性結(jié)構(gòu)連接操作只輸出需要保留的部分作為結(jié)果,對無用查詢結(jié)果的剔除可以盡早進(jìn)行,其定義如下:定義10. 給定兩個輸入集合A=(a1,a2,am)和D=(d1,d2,dn)

27、,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 選擇性結(jié)構(gòu)連接算法實現(xiàn)本節(jié)給出了兩類選擇性結(jié)構(gòu)連接算法:排序合并和基于區(qū)域劃分.4.3.1 選擇性排序合并結(jié)構(gòu)連接算法dn+1a2and1d2d2nd2n-1dn(a) XML tree(a) XML樹a2a1and1d2d2nd2n-1dndn+1(b) Sort merge join by ancestor nodes(b) 按祖

28、先節(jié)點(diǎn)排序合并結(jié)構(gòu)連接(c) SSMJ-Anc(c) SSMJ-Anca2a1and1d2dndn+1Fig.4 A case for SSMJ-Anc algorithm圖4 SSMJ-Anc算法的例子a1根據(jù)輸出結(jié)果是A或D中的元素,選擇性排序合并結(jié)構(gòu)連接(selective sort merge join,簡稱SSMJ)算法有兩個:SSMJ-Anc和SSMJ-Des.它們利用了只輸出一個輸入集合中元素的特點(diǎn),避免了對某些元素的處理,從而避免了完全結(jié)構(gòu)連接的排序合并算法可能產(chǎn)生的對輸入集合的多遍掃描.這兩個算法在最壞情況下對兩個輸入集合各掃描一遍.圖4和圖5分別給出了完全結(jié)構(gòu)連接的按祖先和

29、后代排序合并算法的最壞情況,以及SSMJ-Anc和SSMJ-Des在這兩種情況下的效率.在圖4(a)所描述的數(shù)據(jù)分布情況下,圖4(b)描述了按祖先排序合并算法進(jìn)行完全結(jié)構(gòu)連接的對D的多遍掃描,而圖4(c)中的SSMJ-Anc算法只需從d1到dn的掃描比較.圖5中的情況也相類似.需要指出的是,SSMJ-Anc和SSMJ-Des只適用于祖先-后代關(guān)系的計算.d2n-1d2na0a1ana2d1d2d3dna3a0a2ana1d1dnd2(a) XML tree(a) XML樹(b) Sort merge join by descendant nodes(b) 按后代節(jié)點(diǎn)排序合并結(jié)構(gòu)連接(c) SS

30、MJ-Des(c) SSMJ-Desa1ana2d1d2d3dna3Fig.5 A case for SSMJ-Des algorithm圖5 SSMJ-Des算法的例子a04.3.2 基于區(qū)域劃分的選擇性結(jié)構(gòu)連接算法針對輸入數(shù)據(jù)集合無序的情況,我們已經(jīng)提出了基于區(qū)域劃分的結(jié)構(gòu)連接算法(range partitioning join,簡稱RPJ)12,實現(xiàn)了完全結(jié)構(gòu)連接操作.在RPJ算法的基礎(chǔ)上,針對選擇性結(jié)構(gòu)連接操作,我們提出了基于區(qū)域劃分的選擇性結(jié)構(gòu)連接算法(selective range partitioning join,簡稱SRPJ).該類算法包括兩個:輸出結(jié)果限定在A上的SRPJ-

31、Anc和輸出結(jié)果限定在D上的SRPJ-Des. SRPJ-Anc算法SRPJ-Anc充分利用元素編碼的特點(diǎn),盡早地對A中節(jié)點(diǎn)進(jìn)行判斷,產(chǎn)生結(jié)果.算法分為3個階段:(1) 子集合劃分階段.首先對后代節(jié)點(diǎn)集合D進(jìn)行劃分,所采用的劃分方法與RPJ相同.當(dāng)對祖先節(jié)點(diǎn)集合A進(jìn)行劃分時,可以利用祖先節(jié)點(diǎn)的特點(diǎn)來產(chǎn)生部分結(jié)果.如果A中的節(jié)點(diǎn)a的區(qū)域編碼完全覆蓋了一個子區(qū)間Ri,只要Ri對應(yīng)的子集合Di中的元素節(jié)點(diǎn)數(shù)目不為0,Di中所有的節(jié)點(diǎn)都是a的后代節(jié)點(diǎn).利用這個特點(diǎn),我們在對A中的節(jié)點(diǎn)進(jìn)行劃分時就可以判斷一些節(jié)點(diǎn)是否有后代節(jié)點(diǎn),具體的判斷規(guī)則為:假設(shè)A中的一個節(jié)點(diǎn)a的區(qū)域編碼完全覆蓋了n個

32、子區(qū)間,如果這些子區(qū)間所對應(yīng)的D的子集合中至少存在一個不為空,那么在D中一定存在a的后代節(jié)點(diǎn),即a應(yīng)當(dāng)作為結(jié)果輸出.對于確定為輸出結(jié)果的A中節(jié)點(diǎn),就不再劃分到子集合中進(jìn)行處理;對于那些不能確定為結(jié)果的A中節(jié)點(diǎn),只需將其劃分到與區(qū)域編碼部分相交的子區(qū)間所對應(yīng)的子集合中,這樣的子集合的最大數(shù)目為2.(2) 連接階段.對于那些在子集合劃分階段不能確定的A中的節(jié)點(diǎn),需要實際的連接來進(jìn)行檢查.對每一對子集合Ai和Di,分別進(jìn)行連接.由于A中的一個節(jié)點(diǎn)可能被劃分到兩個子集合中,所以它可能在結(jié)果中出現(xiàn)兩次,即連接階段產(chǎn)生的結(jié)果集中可能出現(xiàn)重復(fù)元素.(3) 去重階段.子集合劃分和連接階段已經(jīng)產(chǎn)生了所有的輸出結(jié)

33、果,但連接階段所產(chǎn)生的結(jié)果中可能會出現(xiàn)重復(fù)值.該階段的主要任務(wù)是合并各個子集合對的連接結(jié)果,去掉重復(fù)值. SRPJ-Des算法SRPJ-Des的基本思想與SRPJ-Anc類似,不同的是考慮的目標(biāo)是集合D.算法分為兩個階段:(1) 子集合劃分階段.首先對祖先節(jié)點(diǎn)集合A進(jìn)行劃分,所采用的劃分方法與RPJ相同,不同的是對每個子集合Ai額外記錄該子集合中區(qū)域編碼完全覆蓋其對應(yīng)子區(qū)間的節(jié)點(diǎn)個數(shù)Vi.如果A中節(jié)點(diǎn)a的區(qū)域編碼完全覆蓋了一個子區(qū)間Ri,則Di中所有的節(jié)點(diǎn)都是a的后代節(jié)點(diǎn).利用這個特點(diǎn),在對后代節(jié)點(diǎn)集合D進(jìn)行劃分時可以判斷一些節(jié)點(diǎn)是否有祖先節(jié)點(diǎn),判斷規(guī)則為:假設(shè)D中的一個節(jié)點(diǎn)d應(yīng)

34、當(dāng)劃分到Di,如果對應(yīng)的Ai的Vi值不為0,則Ai中一定存在d的祖先節(jié)點(diǎn),即d應(yīng)當(dāng)作為結(jié)果輸出.對于確定為輸出結(jié)果的D中節(jié)點(diǎn),就不再劃分到子集合中進(jìn)行處理;對于那些不能確定為結(jié)果的D中節(jié)點(diǎn),仍按照RPJ算法中的劃分方法劃分到子集合中,進(jìn)行進(jìn)一步的處理.(2) 連接階段.對于在子集合劃分階段沒有確定的D中節(jié)點(diǎn),連接階段進(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é)

35、對實驗的結(jié)果進(jìn)行了描述和分析.5.1 實驗設(shè)置我們的實驗在Native XML數(shù)據(jù)管理系統(tǒng)Orient-X的基礎(chǔ)上進(jìn)行,所有的算法都用C+編程語言來實現(xiàn).所有的實驗在一臺Duron 1.0GHz,256M RAM,40G硬盤的PC上運(yùn)行,底層操作系統(tǒng)是Windows XP.我們選擇執(zhí)行時間為評價指標(biāo).這里所給出的執(zhí)行時間都是運(yùn)行實驗多次,去掉最高和最低值后得到的平均執(zhí)行時間.5.2 選擇性結(jié)構(gòu)連接的有效性選擇性結(jié)構(gòu)連接操作在我們的路徑查詢框架中具有重要的作用,本節(jié)我們結(jié)合所提出的多種實現(xiàn)算法對其進(jìn)行性能上的分析.我們采用IBM XML Generator生成了大小為113M的實驗文檔,所用的D

36、TD如圖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é)果類似.á!ELEMENT manager (name, (manager | department | employee)+)ñá!ELEMENT department (name, email?, employee+, department*)ñá!ELEMENT em

37、ployee (name+, email?)ñá!ELEMENT name (#PCDATA)ñá!ELEMENT email (#PCDATA)ñ Fig.6 The DTD of synthetic data set圖6 人工數(shù)據(jù)集的DTDTable 1 Description of synthetic data set表1 人工數(shù)據(jù)集的描述ElementNumberManager38Department286 459Employee543 685Name1 111 390Email59 946Table 2 Description of

38、queries of synthetic data set表2 人工數(shù)據(jù)集的查詢描述QueryPath expressionResult (Ancestor)Result (Descendant)Q1manager/employee38543 685Q2department/employee286 459543 631Q3department/email34 22359 929Q4employee/email31 39131 391Q5department/employee/email10 47731 374Q6manager/department/email1459 9295.2.1 簡單結(jié)

39、構(gòu)關(guān)系查詢這里我們用表2中的4個簡單結(jié)構(gòu)關(guān)系查詢Q1到Q4來比較不同的選擇性結(jié)構(gòu)連接實現(xiàn)算法的性能.我們實現(xiàn)了5類算法:選擇性排序合并連接(SSMJ),Stack-Tree-Filter(STF),Stack-Tree(ST),選擇性區(qū)域劃分連接(SRPJ)和區(qū)域劃分連接(RPJ),每類算法包括結(jié)果限定在祖先和后代的兩個算法.STF算法是對Stack-Tree類的算法進(jìn)行了改寫,使其只輸出指定的結(jié)果.ST算法是在Stack-Tree類的算法后附加了一個投影到指定輸出的過程,RPJ也是類似.我們將這5種算法分為兩類進(jìn)行比較:基于排序合并和基于劃分,這是因為我們在計算基于排序合并算法的執(zhí)行時間時沒

40、有考慮排序的時間,在這種情況下,基于排序合并的算法效率明顯高于基于劃分的算法.此外,實驗的目的是想反映選擇性結(jié)構(gòu)連接算法與其對應(yīng)的完全結(jié)構(gòu)連接算法加投影的性能比較.圖7和圖8描述了排序合并類算法的性能,分別比較了輸出結(jié)果限定在祖先節(jié)點(diǎn)和后代節(jié)點(diǎn)上的算法.從圖7中可以看出,選擇性結(jié)構(gòu)連接算法SSMJ和STF的性能在各個查詢上均優(yōu)于ST,這說明選擇性結(jié)構(gòu)連接算法的實現(xiàn)策略在性能上優(yōu)于完全結(jié)構(gòu)連接加投影的實現(xiàn)策略.對查詢Q1,Q2和Q3,兩種策略的執(zhí)行時間相差較大,而Q4的執(zhí)行時間則比較接近,這是由于前3個查詢所涉及的祖先節(jié)點(diǎn)元素manager和department是遞歸定義的,而Q4中的emplo

41、yee則沒有遞歸定義.當(dāng)祖先元素存在遞歸定義時,選擇性結(jié)構(gòu)連接算法由于可以避免對嵌套節(jié)點(diǎn)的多次處理,所以較大程度地提高了執(zhí)行效率.此外,SSMJ和STF在各個查詢上的執(zhí)行時間都比較接近,SSMJ略優(yōu)于STF,這是由于兩種算法本質(zhì)上是相同的,而STF在內(nèi)存中的棧和鏈表處理稍復(fù)雜一些.圖8所描述的性能比較表現(xiàn)了與圖7類似的特征.圖9和圖10描述了基于劃分的算法的性能比較.從圖中可以看出,選擇性結(jié)構(gòu)連接算法SRPJ在各個查詢上都優(yōu)于基于區(qū)域劃分的完全結(jié)構(gòu)連接加投影的方法.除Q4的優(yōu)勢不明顯以外,其他3個查詢上SRPJ都大大優(yōu)于RPJ.這個特征也與排序合并類算法的表現(xiàn)相一致.Execution tim

42、e (s)01020304050607080Q1Q2Q3Q4STSTFSSMJExecution time (s)0510152025303540Q1Q2Q3Q4STSTFSSMJFig.7 The result of sort merge algorithmsby ancestor圖7 輸出祖先節(jié)點(diǎn)的排序合并類算法的結(jié)果Fig.8 The result of sort merge algorithmsby descendant圖8 輸出后代節(jié)點(diǎn)的排序合并類算法的結(jié)果Execution time (s)050100150200250300350Q1Q2Q3Q4RPJSRPJExecution

43、time (s)050100150200250300350400Q1Q2Q3Q4RPJSRPJFig.9 The result of partitioning algorithmsby ancestor圖9 輸出祖先節(jié)點(diǎn)的劃分類算法的結(jié)果Fig.10 The result of partitioning algorithmsby descendant圖10 輸出后代節(jié)點(diǎn)的劃分類算法的結(jié)果5.2.2 復(fù)雜查詢表2中的Q5和Q6是兩個較為復(fù)雜的查詢,每個查詢包含了兩個連接.我們用五類算法分別基于結(jié)果為祖先節(jié)點(diǎn)和后代節(jié)點(diǎn)實現(xiàn)了這兩個查詢.SSMJ,STF和SRPJ同上節(jié)所述,而Path-S(Path

44、-R)則表示先采用Stack-Tree(RPJ)算法完成連接,最后對完全連接結(jié)果進(jìn)行一次投影.表3和表4分別給出了排序合并類算法和劃分類算法的實驗結(jié)果.從表3中可以看出,SSMJ和STF執(zhí)行時間相近,都大大優(yōu)于Path-S.而表4則反映了SRPJ與Path-R相比所取得的性能優(yōu)勢.Table 3 The result of queries using sort merge algorithms表3 排序合并類算法的查詢結(jié)果QueryAncestor (s)Descendant (s)SSMJSTFPath-SSSMJSTFPath-SQ53.12.944.837.688.1935.78Q61.

45、081.299.113.073.438.63Table 4 The result of queries using partitioning algorithms表4 劃分類算法的查詢結(jié)果QueryAncestor (s)Descendants (s)SRPJPath-RSRPJPath-RQ512.2221.6330.13122.81Q66.6625.928.36455.3 查詢執(zhí)行計劃的性能我們用初步的實驗來驗證所提出的查詢分解處理策略的可行性.實驗采用XMark數(shù)據(jù)集,選擇了大小分別為1M,10M和20M的文檔.表5給出了實驗中所用的查詢例子QP1和QP2.QP1是一個不帶分支的路徑查詢

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

47、n of path queries表5 路徑查詢描述QueryPath expressionQP1/site/open_auction/bidder/increaseQP2/site/open_auctions/open_auctionannotation/description/text/bidder/nameTable 6 The execution time of QP1 (ms)表6 QP1的執(zhí)行時間(ms)Dataset (M)Join planDecomposition plan115.33<110114.3331.3320328151Table 7 The executio

48、n time of QP2 (ms)表7 QP2的執(zhí)行時間(ms)Dataset (M)Join planDecomposition plan115.6715.671010483.3320250.33161.676 相關(guān)工作路徑查詢的處理方面已經(jīng)有大量的研究工作.繼承了半結(jié)構(gòu)化數(shù)據(jù)領(lǐng)域的研究,文獻(xiàn)7,8對導(dǎo)航式遍歷的路徑查詢匹配方法進(jìn)行了研究.導(dǎo)航式遍歷方法簡單、直接,但執(zhí)行效率不能得到保證,尤其是在大數(shù)據(jù)量的情況下.“一次一集合”的路徑查詢計算策略目前被廣泛接受,基于該策略的研究工作包括多個方面,結(jié)構(gòu)連接算法的研究是其中的重點(diǎn).目前已有的工作大體上可以分為兩類:基于排序合并的算法6-8和基于

49、劃分的方法9.排序合并類的算法依賴于一定的前提條件:數(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則針對

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

51、們的工作是在Native XML數(shù)據(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. Extensible markup language (XML) 1.0 (2nd Edition). W3C Recommendation, 2000. /TR/

52、2000/REC-xml-200010062 Clark J, DeROse S, eds. XML Path language (XPath) Version 1.0. W3C Recommendation, 1999. /TR/1999/ REC-xpath-199911163 Chamberlin D, Florescu D, Robie J, Simeon J, Stefanescu M, eds. XQuery: A query language for XML. W3C Working Draft, 2001. /TR

53、/2001/WD-xquery-20012154 Goldman R, McHugh J, Widom J. From semisturctured data to XML: Migrating the lore model and query language. In: Proc. of the 2nd Intl Workshop on the Web and Databases (WebDB99). 1999. http:/www-rocq.inria.fr/cluet/WEBDB/lore.ps5 McHugh J, Widom J. Query optimization for XML

54、. In: Atkinson MP, Orlowska ME, Valduriez P, Zdonik SB, Brodie ML, eds. Proc. of the 25th Intl Conf. on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 1999. 315-326.6 Zhang C, Naughton J, DeWitt D, Luo Q, Lohman G. On supporting containment queries in relational database managemen

55、t systems. In: Timos S, ed. Proc. of the 2001 ACM SIGMOD Intl Conf. on Management of Data. New York: ACM Press, 2001. 425-436.7 Li QZ, Moon B. Indexing and querying XML data for regular path expressions. In: Apers PMG, Atzeni P, Ceri S, Paraboschi S, Ramamohanarao K, Snodgrass RT, eds. Proc. of the 27th Intl Conf. on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 2