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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、全結(jié)構(gòu)連接操作，即結(jié)構(gòu)連接所輸出的結(jié)果是參加連接的兩個(gè)輸入集合中滿(mǎn)足條件的元組的合并.在我們的計(jì)算框架中，查詢(xún)樹(shù)的計(jì)算是以目標(biāo)節(jié)點(diǎn)為導(dǎo)向的，而不必給出全連接的結(jié)果 .選擇性結(jié)構(gòu)連接操作只輸出需要保留的部分作為結(jié)果，對(duì)無(wú)用查詢(xún)結(jié)果的剔除可以盡早進(jìn)行，其定義如下：定義10.給定兩個(gè)輸入集合A=(a, a?,，am)和D=(d1, d2,，dn),A和D分別是m維和n維元組的集合，對(duì)指定的潛在祖先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)連接算法實(shí)現(xiàn)本節(jié)給出了兩類(lèi)選擇性結(jié)構(gòu)連接算法：排序合并和基于區(qū)域劃分4.3.1 選擇性排序合并結(jié)構(gòu)連接算法根據(jù)輸出結(jié)果是 A或D中的元素，選擇性排序合并結(jié)構(gòu)連接(selective sort merge join, 簡(jiǎn)稱(chēng)SSMJ)算法有兩個(gè):SSMJ-Anc和SSMJ-Des.它們利用了只輸出一個(gè)輸入集合中元素的特點(diǎn)，避免了對(duì)某些元素的處理，從而避免了完全結(jié)構(gòu)連接的排序合并算法可能產(chǎn)生的對(duì)輸入集合的多遍掃描.這兩個(gè)算法在最壞情況下對(duì)兩,以及個(gè)輸入集合各掃描一遍.圖4和圖5分別給出了完全結(jié)構(gòu)連接的按祖先和后代排序合并算法的最壞情況SSMJ-Anc和SSMJ-Des在這兩種情況下的效率

27、.在圖4(a)所描述的數(shù)據(jù)分布情況下，圖4(b)描述了按祖先排序合并算法進(jìn)行完全結(jié)構(gòu)連接的對(duì)D的多遍掃描，而圖4(c)中的SSMJ-Anc算法只需從d1到dn的掃描比較.圖5-后代關(guān)系的計(jì)算.中的情況也相類(lèi)似.需要指出的是，SSMJ-Anc和SSMJ-Des只適用于祖先針對(duì)輸入數(shù)寸/Ia2d2n無(wú)序腳情況a1aod1d2d1%a1 .a2d一一d1join,簡(jiǎn)稱(chēng)RPJ)嗎* 施了完全結(jié)構(gòu)連接操作 于區(qū)域劃分的：算法d1dn,我們已葡此座處域劃分的結(jié)木連接算法.d2 r一 r A. . dn+1.針對(duì)選擇性結(jié)構(gòu)連接操作d2n?1于區(qū)域劃分的選擇陶承構(gòu)連盤(pán)卜法(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編碼的特點(diǎn)(典整A cas(1)子集合劃分階段.首先對(duì)后代節(jié)縹解SRPJ-Anc 耀 Xes量,.d2ao a1J / / (range partitioningdna2da3我們提出了基 a。.簡(jiǎn)稱(chēng)SRPJ).該類(lèi)算法包括兩個(gè)：輸dn(c博然MA晚s (cLSSMJiAncan旌!弦嘴，產(chǎn)生結(jié)果-Anc algorithm嘲g字分方法與RPJ相同.當(dāng)

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

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

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

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

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

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ù)集的查詢(xún)描述們實(shí)現(xiàn)了 Query 擇性排序合并 Q1表1人工數(shù)據(jù)集的描述Eleme

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

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

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

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

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

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

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

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

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

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

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