確定自動機上的XML數(shù)據(jù)過濾算法改進

印桂生，沈潔，謝曉芹

(哈爾濱工程大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

可擴展標記語言 (extensible markup language，XML)自1998年出現(xiàn)以來，目前已經(jīng)成為國際互聯(lián)網(wǎng)數(shù)據(jù)交換的標準格式，對XML數(shù)據(jù)流的過濾檢索也是當(dāng)前的研究熱點.近年來，在XML過濾技術(shù)領(lǐng)域，運用有限自動機來對XML數(shù)據(jù)流進行過濾已有了一些研究［1-5］，并取得了一些成果.已有的研究主要分為兩大類:第1類是基于非確定有限自動機(nondeterministic finite automaton，NFA)，其主要的思想是定義了XPath與NFA的相互轉(zhuǎn)換，優(yōu)點是構(gòu)造簡單，空間開銷較小，這種技術(shù)的典型代表是XFilter和 YFilter系統(tǒng);第2類是基于確定有限自動機(deterministic finite automaton，DFA)，它定義了XPath與DFA的相互轉(zhuǎn)換，優(yōu)點是狀態(tài)轉(zhuǎn)移目標明確，執(zhí)行效率較NFA有明顯的提高，其典型代表是Lazy DFA.

本文研究XML數(shù)據(jù)過濾過程中存在的緩存失效，緩存失效的發(fā)生會導(dǎo)致過濾的效率降低，因此研究基于確定有限自動機的XML數(shù)據(jù)過濾過程中如何減少緩存失效對于改進過濾的性能具有重要意義.本文的主要工作就是在DFA過濾機制研究的基礎(chǔ)上加入緩存失效控制機制，最大限度地提高過濾的時間性能和空間使用性.

1 Lazy DFA基本思想

Lazy DFA的基本思想［5］是所有的查詢表達式被轉(zhuǎn)換到單一的DFA中，其步驟是:

1)將所有的查詢轉(zhuǎn)換為一個單一的NFA.

2)根據(jù)NFA再轉(zhuǎn)換為相應(yīng)的DFA.為了記錄DFA狀態(tài)轉(zhuǎn)移的觸發(fā)條件，每個DFA狀態(tài)都維護一個狀態(tài)轉(zhuǎn)移哈希表.

3)需要記錄在該DFA狀態(tài)下，有哪些查詢表達式是和當(dāng)前過濾的XML文檔相匹配的，用于在過濾過程中進行結(jié)果收集.

對于已經(jīng)構(gòu)造好的DFA，用于過濾XML文檔時效率是非常高的.在利用DFA過濾的過程中，僅需要維護一個運行棧和一個指向當(dāng)前DFA狀態(tài)的指針即可，其中運行棧中存放的是從初始狀態(tài)到當(dāng)前DFA狀態(tài)之間DFA狀態(tài)轉(zhuǎn)移過程中的所有中間狀態(tài).當(dāng)遇到一個元素開始事件時，過濾引擎就會根據(jù)當(dāng)前過濾的元素節(jié)點的名字，查找當(dāng)前DFA狀態(tài)中的狀態(tài)轉(zhuǎn)移哈希表，得到目標狀態(tài).然后將當(dāng)前的DFA狀態(tài)壓入運行棧中，并把目標狀態(tài)置為當(dāng)前DFA狀態(tài)，最后根據(jù)需要進行結(jié)果收集.而在遇到一個元素結(jié)束事件時，僅需要將處于運行棧的棧頂?shù)腄FA狀態(tài)彈出，并重新置為當(dāng)前的DFA狀態(tài)即可.可見利用DFA進行XML文檔的過濾，每次狀態(tài)轉(zhuǎn)移操作的代價和NFA相比是很小的，因此過濾效率非常高.

然而一般情況下，直接利用DFA進行XML文檔的過濾是不現(xiàn)實的.因為在查詢表達式集合很大的時候，直接轉(zhuǎn)換成DFA時所產(chǎn)生DFA狀態(tài)的數(shù)量呈指數(shù)級增長，因此很可能非常巨大，以至于無法將整個DFA都存放在內(nèi)存中.對于單機XML查詢，必須考慮緩存的查詢問題，只有解決了海量數(shù)據(jù)的查詢才能使得XML數(shù)據(jù)流的應(yīng)用更加廣泛.

解決的方法是在實際過濾的時候，采取根據(jù)需要計算并展開DFA狀態(tài)的方法，可減少許多無用的DFA狀態(tài)的展開，從而避免了DFA狀態(tài)的爆炸式增長，只是對于新展開的DFA狀態(tài)需要保留其相應(yīng)的計算得到的NFA狀態(tài)集，稱為NFA Table.

一般而言，在緩存的存取過程中定位技術(shù)(例如:狀態(tài)重用)是減少緩存失效的根本所在.此外，一般順序存取比隨意存取更加有序，基于以上這2點，在緩存敏感性自動機技術(shù)的基礎(chǔ)上，提出一種改進的技術(shù)稱之為頻繁訪問(frequent access，F(xiàn)A)技術(shù).

2 DFA-TA過濾系統(tǒng)

2.1 XML過濾系統(tǒng)結(jié)構(gòu)

本文采用的XML過濾系統(tǒng)結(jié)構(gòu)如圖1所示.這個系統(tǒng)主要的部分包括一個用來解析用戶查詢的XPath解析器，一個用解析文檔的基于事件的SAX解析器［7］，一個用于過濾文檔的基于自動機的過濾機制.在這個過濾機制中的自動機可以是XPath-DFA或者是下文的DFA-FA自動機.

圖1 XML數(shù)據(jù)的過濾過程Fig.1 Filtering process of XML data

基于XPath查詢首先說明XPath-DFA的過濾過程.它是由來自于SAX解析器的事件驅(qū)動.事件有以下4種類型:start-of-document、end-of-document、start-of-element、end-of-element.一個 start-of-document引發(fā)一個新的過濾周期;end-of-document標志著一個round的結(jié)束;而在一個過濾周期中，當(dāng)一個start-of-element事件到達時，就引發(fā)了自動機上的一次狀態(tài)轉(zhuǎn)移;當(dāng)一個end-of-element事件發(fā)生時自動機返回到上一個狀態(tài).可以建立一個運行時間棧來表示當(dāng)前和先前訪問過的狀態(tài).通過一個end-ofdocument事件，系統(tǒng)檢查是否已經(jīng)到達了任何的可接受狀態(tài)，若有則將這個文檔發(fā)送給滿足XPath查詢要求的用戶.

舉例說明XPath-DFA的過濾過程，對于給定的一個XML文檔:＜A＞＜B＞＜C＞＜/C＞＜/B＞＜/A＞，若干XPath查詢?nèi)缦聁1=A/B/C;q2=/B/ A;q3=/A/*;q4=/A/B中，通過建立 XPath-DFA，如圖2(a).將查詢的結(jié)果與可接受的狀態(tài)相關(guān)聯(lián)，當(dāng)?shù)竭_一個可接受的狀態(tài)的時候，則與其狀態(tài)相關(guān)聯(lián)的查詢要求就滿足了，如圖2(b).

圖2 查詢的自動機表示Fig.2 Automata expression for querying

在構(gòu)造完緩沖自動機之后，就可以在緩沖自動機中利用一個運行時間棧來執(zhí)行過濾.

2.2 頻繁訪問區(qū)的定義

頻繁訪問區(qū)是存儲那些過濾中狀態(tài)轉(zhuǎn)移頻繁的節(jié)點的鄰近區(qū)域.如與文檔的根節(jié)點元素相關(guān)的狀態(tài)轉(zhuǎn)移被存取的次數(shù)一般要多于其他節(jié)點.通過將這些頻繁的狀態(tài)轉(zhuǎn)移集中到一個特殊的區(qū)域中，緩存失效中的強制性失效和容量失效的數(shù)量會大大減少.然后給頻繁訪問區(qū)的大小設(shè)置一個限制，從而進一步減少容量失效.

2.3 頻繁訪問區(qū)的舉例

首先給出一個不帶頻繁訪問區(qū)的自動機，并用矩陣的方法來表示這個自動機:行索引當(dāng)前的狀態(tài)，列索引符號(如XML元素名，或者XML卷標)，每個矩陣單元都標注了從當(dāng)前狀態(tài)通過某個符號指向的下一個狀態(tài).為矩陣中的每個單元增加一個計數(shù)器用以記錄相關(guān)狀態(tài)轉(zhuǎn)移的頻率次數(shù).圖3所示的是這樣的一個自動機的片段，自動機中每個單元都形如＜Next State，Counter＞，其中Next State表示自動機的下一狀態(tài)，Counter代表計數(shù)器.

圖3 舉例說明頻繁訪問區(qū)自動機Fig.3 Example of an automaton with FA

為了構(gòu)造一個頻繁訪問自動機首先需要確定頻繁訪問區(qū)里的節(jié)點.設(shè)置一個關(guān)于頻繁訪問節(jié)點的閾值為存取頻率為10.通過對矩陣的逐行掃描確定頻繁訪問節(jié)點(frequent access node，F(xiàn)AN)，并記錄每一行中的FANbase(最左邊的FAN單元)以及FANtail(最右邊的FAN單元).為了保留矩陣快速轉(zhuǎn)換的優(yōu)點，可以標志在FANbase和FANtail之間的所有單元為FAN，并將這個片段成為緊致行.由此也改進了構(gòu)造的速度，如圖3中的原自動機用陰影標識出了所有的熱點，在第2行第B列的＜8，0＞單元，雖然它的存取頻率小于10，但因為緊致行的定義所以也被標注成了陰影單元.

圖3中所示的FA就是由帶有FAN的自動機所構(gòu)造出來的.由圖3可知FA是一種從檢索0開始的排列結(jié)構(gòu).排列中的每個元素都由一個4項組成的元組構(gòu)成，＜offset，base，tail，miss＞，所有的值都被初始化為－1.FA排列元素中的base和tail是對應(yīng)的緊致行(對應(yīng)于原自動機中)的起始位置和終止位置.base和tail中的值分別是緊致行中的最小符號和最大符號.

對于原自動機中的每一個緊致行，(tail－base+1)個排列元素將被添加到FA區(qū)域中.offset的值將在FA構(gòu)造的過程中被設(shè)置，其作用在于在過濾中引導(dǎo)當(dāng)前的索引前往offset排列元素.給定FA中的當(dāng)前索引cur，以及當(dāng)前符號tag，如果base≠－1且base≤tag≤tail，那么下一個要訪問的排列元素就是FA中索引號為(cur+offset+tag－base)的元素，否則，miss區(qū)域就指向原自動機中的該狀態(tài)以此來解決FA部分的排列元素失效.

如果一個轉(zhuǎn)換能在頻繁訪問區(qū)中結(jié)束(即所謂的一個頻繁訪問區(qū)擊中)，這個緩沖將不必涉及到原自動機.當(dāng)這個緩沖在頻繁訪問區(qū)中失效時，原自動機就需要被訪問了.在訪問原自動機之前，我們保存當(dāng)前棧的內(nèi)容，包括棧的大小和運行時間棧的頂部內(nèi)容形如(msize，mtop).然后將運行時間棧頂內(nèi)容置換成原自動機頻繁訪問區(qū)中節(jié)點中失效區(qū)域的TOP排列元素.原自動機中的轉(zhuǎn)換將一直持續(xù)到棧的大小重新變?yōu)閙size，此時將棧頂置換成mtop，并假設(shè)是在頻繁訪問區(qū)中發(fā)生的轉(zhuǎn)換.整個文檔都過濾完成后，與接受狀態(tài)相關(guān)聯(lián)的查詢就是滿足條件的查詢.

圖3中的箭頭所示的為利用頻繁訪問區(qū)的XML文檔的過濾過程，＜A＞＜B＞＜C＞＜/C＞＜/B＞＜B＞＜/B＞ ＜/A＞.實線箭頭代表在熱緩沖之間的轉(zhuǎn)換，虛線箭頭將轉(zhuǎn)換改道至原自動機中.過濾的過程從熱緩沖中的0索引(cur=0)開始.當(dāng)標簽＜A＞到來時，通過(cur+offset+tag－base)計算出下一個索引號，例如當(dāng)tag=A，offset=1，base= A(在0元素中)，下一個索引號即為1.后繼的事件＜B＞也通過類似的方法處理，當(dāng)處理第3個事件＜C＞時，出現(xiàn)了一個熱緩沖失效，于是轉(zhuǎn)換就必須轉(zhuǎn)向原自動機中.當(dāng)處理完第4個事件＜/C＞以后，運行時間?；謴?fù)并且轉(zhuǎn)換重新回到熱緩沖區(qū)域.

2.4 頻繁訪問區(qū)的構(gòu)造算法

為了構(gòu)造頻繁訪問區(qū)緩存駐留并盡可能的減少失效率，對頻繁訪問區(qū)的構(gòu)造增加2項限制:

1)頻繁訪問區(qū)的大小必須小于緩存容量C.如果頻繁訪問區(qū)的大小接近于或者大于C，訪問的范圍過大使得過濾查詢的效率低下，但是如果太小的話又會加劇失效的產(chǎn)生.因此在我們的執(zhí)行過程中一般將頻繁訪問區(qū)的大小設(shè)置為L2緩存大小的一半.

2)頻繁訪問區(qū)中節(jié)點的選擇一般是在考慮在存取頻率上選擇一個閾值.

基于以上2點限制條件的考慮，算法1給出一種自頂向下的方式構(gòu)造頻繁訪問區(qū)，利用一個隊列wquence來存儲自動機的等待狀態(tài)M(自動機的等待狀態(tài)是指從該狀態(tài)開始的一些狀態(tài)轉(zhuǎn)移就進入到頻繁訪問區(qū)中).該算法中還使用了另外一個隊列pqueue來存儲頻繁訪問區(qū)中的節(jié)點加入頻繁訪問區(qū)時的索引位置.

算法1 構(gòu)造頻繁訪問區(qū)

輸入:帶計數(shù)器的自動機M，頻繁訪問區(qū)的大小限制為sizeLimit閾值t

頻繁訪問區(qū)的構(gòu)造在線和離線狀態(tài)都可以，在其自適應(yīng)性和開銷中尋求權(quán)衡.在線方式可以很好的適應(yīng)局部模式，但是會產(chǎn)生運行時間開銷的問題，可以為每次轉(zhuǎn)換增加一個計數(shù)器來增加自動機的容量.因此一般都采用離線的方式來構(gòu)造頻繁訪問區(qū).

2.5 頻繁訪問區(qū)節(jié)點的閾值確定

給定一個工作負載(系列文檔)，通過使用speedup定義頻繁訪問區(qū)的有效性，speedup是過濾中不帶頻繁訪問區(qū)的緩存失效值T過濾中帶頻繁訪問區(qū)的緩存失效值B的比率:

T的值可以通過緩存失效的模型進行評估，B的值由下面的公式評估:

式中:hbsize是依據(jù)緩存行的數(shù)量決定的頻繁訪問區(qū)的大小，tc為該工作負載中發(fā)生的狀態(tài)轉(zhuǎn)移的總數(shù)，mbuf是頻繁訪問區(qū)中存取失效的不命中率(而非cache的不命中率)，r仍然為沖突失效和強制性失效的比率，F(xiàn)為原始自動機中的狀態(tài)轉(zhuǎn)移的記錄.該等式分2部分評估了利用頻繁訪問區(qū)技術(shù)中的緩存失效:第1部分為hbsize，包括頻繁訪問區(qū)中的狀態(tài)轉(zhuǎn)移時發(fā)生的緩存強制性失效.由于頻繁訪問區(qū)是連續(xù)不間斷的并且其大小遠小于緩存大小，可忽略頻繁訪問區(qū)擊中時的容量和沖突失效.第2部分為tcmbuf(1+r)F，這部分是當(dāng)發(fā)生熱緩沖失效時的強制性和沖突失效.mbuf=1－h(huán)buf，這里bbuf為頻繁訪問區(qū)中節(jié)點的計數(shù)器值總和與tc的比值，在這部分忽略頻繁訪問區(qū)的失效轉(zhuǎn)移時的容量緩存失效.

對于給定的一個閾值t，可以利用一個跟算法2類似的算法得到 hbsize和 mbuf值，然后利用式(1)、(2)計算出speedup值.如果speedup＞1，則此頻繁訪問區(qū)可以將緩存性能提高speedup標度，反之，過濾的過程就回到原自動機中而不使用頻繁訪問區(qū).

最后，給出一個簡單的迭代算法來確定最終的閾值t來得到最大的speedup值.定義t為［x，y］范圍內(nèi)的一個整數(shù)，其中x為最小的計數(shù)器值(如果最小值是0，則設(shè)定x=1)，y為最大的計數(shù)器值.從x到y(tǒng)逐漸改變t值并計算取(y－x+1)個整數(shù)時speedup值，得到最大speedup值的t值就是閾值.

3 算法性能分析

3.1 實驗環(huán)境

為了驗證DFA-FA算法的有效性，建立了基于頻繁訪問區(qū)的XPath查詢過濾優(yōu)化的測試環(huán)境，本實驗中的硬件環(huán)境為IBM X61計算機，操作系統(tǒng)是Windows XP，CUP為Intel T7100，主頻為1.8 GHz，內(nèi)存為2 GB.L1緩存為32 kB(16 K結(jié)構(gòu)，16 K數(shù)據(jù))，L2緩存為512 KB.cache行大小為64 Byte.過濾系統(tǒng)用C++并通過g++3.2.2－5編譯.過濾實驗全部采用內(nèi)存駐留技術(shù)并保證內(nèi)存的使用率不超過80%.

3.2 實驗測試數(shù)據(jù)

實驗中使用的數(shù)據(jù)集合如下:1)NASA提供的天文學(xué)方面的XML數(shù)據(jù)［6］(簡單的XML數(shù)據(jù)); 2)NAA提供的分類的廣告方面的XML數(shù)據(jù)［7］(普通的復(fù)雜程度);3)TreeBank的語言學(xué)方面的XML數(shù)據(jù)(比較復(fù)雜的XML數(shù)據(jù)).其中NASA和Tree-Bank的XML數(shù)據(jù)為真實數(shù)據(jù)，而NAA的數(shù)據(jù)是由IBM XML數(shù)據(jù)生成器產(chǎn)生的合成數(shù)據(jù)［2］.表1描述的就是這些數(shù)據(jù)的特征，其中第1項顯示的是數(shù)據(jù)的最大元素深度，NASA數(shù)據(jù)相對較淺，NAA和TreeBank數(shù)據(jù)較深;第2項表示的是其中DTD和XML的嵌套數(shù)量.DTD的嵌套表示DTD中定義的遞歸的元素數(shù)量，XML的嵌套表示的是在XML數(shù)據(jù)中有多少個遞歸模式的表示.注意到NASA數(shù)據(jù)的DTD中僅有一個遞歸元素以及18個遞歸模式，MAA XML數(shù)據(jù)有中等數(shù)量的遞歸模式，而TreeBank XML數(shù)據(jù)中有大量的遞歸模式;最后一項是顯示的是在DTD中元素的數(shù)量和XML數(shù)據(jù)的起始標簽.

表1 XML數(shù)據(jù)流特征Table 1 The feature of XML data in experiment

3.3 實驗結(jié)果數(shù)據(jù)

由于支持不同特性的XPath中的執(zhí)行性能不同，在本文的XPath測試集合產(chǎn)生過程中，假定產(chǎn)生100000XPath查詢表達式，分別在NASA，NAA，Tree-Bank數(shù)據(jù)集中抽取大小分別為5、10、15、20和25 MB的數(shù)據(jù)包作為測試用例，利用本文的算法優(yōu)化了Lazy DFA的過濾過程，著重從過濾的執(zhí)行時間和內(nèi)存使用情況分析比較Yfilter(NFA)，Lazy DFA以及DFA-FA的執(zhí)行情況，得到的關(guān)于執(zhí)行時間的實驗數(shù)據(jù)如圖4所示.

圖4 數(shù)據(jù)過濾Fig.4 Data filtering data

圖4的實驗數(shù)據(jù)證明本文提出的DFA-FA過濾系統(tǒng)，能夠有效的提高XPath執(zhí)行器的執(zhí)行效率.并且隨著測試數(shù)據(jù)復(fù)雜程度的增加(從NASA，NAA到TreeBank數(shù)據(jù)包的最大深度、嵌套層次和元素的數(shù)量都是遞增的)，執(zhí)行的的XPath過濾性能的優(yōu)越性越強.具體而言，對于簡單的NASA數(shù)據(jù)，在數(shù)據(jù)集小于10 MB時，DFA-FA系統(tǒng)的過濾性能甚至略低于YFilter系統(tǒng)和LazyDFA系統(tǒng)，因為對于簡單數(shù)據(jù)所需過濾時間較少，而采集頻繁訪問區(qū)中的節(jié)點需要花費更多的時間.而對于中等復(fù)雜的NAA數(shù)據(jù)，DFA-FA系統(tǒng)所需的平均過濾時間是YFilter系統(tǒng)的80.2%，是LazyDFA系統(tǒng)的75%.對于最復(fù)雜的TreeBank數(shù)據(jù)，DFA-FA系統(tǒng)所需的平均過濾時間是 YFilter系統(tǒng)的 52.6%，是 LazyDFA系統(tǒng)的64.5%.因此，隨著測試數(shù)據(jù)復(fù)雜程度的增加，當(dāng)數(shù)據(jù)中包含越來越多元素和嵌套層次的時候，優(yōu)化后的過濾效率提高的更加明顯，該系統(tǒng)具有更好的實用性.

圖5 內(nèi)存使用情況Fig.5 The Usage of Memory

圖5表示的是執(zhí)行過程中內(nèi)存的利用情況.對于簡單的NASA數(shù)據(jù)內(nèi)存的使用率都很低.但是當(dāng)測試數(shù)據(jù)的復(fù)雜度不斷增加，YFilter系統(tǒng)對于內(nèi)存的需求成指數(shù)級增長，分別增長300%和1 600%，LazyDFA系統(tǒng)的增長分別是 200%和 600%，而DFA-FA系統(tǒng)內(nèi)存的使用增長僅為100%和200%，遠遠小于前2種系統(tǒng)對內(nèi)存的要求.

4 結(jié)束語

對多組測試數(shù)據(jù)集的實驗結(jié)果可以證明本文提出的DFA-FA過濾系統(tǒng)，能夠有效的提高XPath執(zhí)行器的執(zhí)行效率.隨著測試數(shù)據(jù)復(fù)雜程度的增加，3組測試數(shù)據(jù)集NASA、NAA和TreeBank中涉及的數(shù)據(jù)包的最大深度、嵌套層次和元素的數(shù)量都是遞增的，執(zhí)行的的XPath過濾性能的優(yōu)越性越強.并且DFA-FA系統(tǒng)內(nèi)存的使用增長率很低，遠小于前2種系統(tǒng)對內(nèi)存的要求.

［1］ALTINEL M，F(xiàn)RANKLIN M J.Efficient filtering of XML documents for selective dissemination of information［J］.VLDB，2000，11(4):53-64.

［2］CHAN C Y，F(xiàn)EIBER P，GAROFALAKIS M，RASTOGI R.Efficient filtering of XML documents with XPath expressions［J］.VLDB，2002，11(4):354-379.

［3］DIAO Y，ALTINEL M，F(xiàn)RANKLIN M J，ZHANG H，F(xiàn)ISCHER P.Path sharing and predicate evaluation for highperformance xml filtering［J］.TODS，2003，10:467-516.

［4］DIAO Y，F(xiàn)ISCHER P，F(xiàn)RANKLIN M J.Yfilter:Efficient and scalable filtering of XML documents［J］.ICDE，2002: 341-342.

［5］GREEN T J，MIKLAU G，ONIZUKA M.Processing XML streams with deterministic automata［J］.ICDT，2002:1-48.

［6］NASA＇s Astronomical Aata Center.ADC XML resource page［EB/OL］.［2009-06-05］.http://xml.gsfc.nasa.gov/.

［7］NAA classified advertising standards task force［EB/OL］.［2009-06-04］.http://www.naa.org/TECHNOLOGY/ CLASSTDTF.

［8］徐德智，吳敏.XML自動機的構(gòu)造及實用化研究［J］.計算機學(xué)報，2008，26(4):471-476.

XU Dezhi，WU Min.Research on XML automaton build and implementation［J］.Chinese Journal of Computers，2008，26(4):471-476.

［9］高軍，楊冬青，唐世渭，王騰蛟.基于樹自動機的XPath在XML數(shù)據(jù)流上的高效執(zhí)行［J］.軟件學(xué)報，2005，16 (20):223-232.

GAO Jun，YANG Dongqing，TANG Shiwei.Tree automata based efficient XPath evaluation over XML data stream［J］.Journal of Software，2005，16(20):223-232.

［10］WEI Mingzhu，RUNDENSTEINER E A，MURALIA Mani，LI Ming.Processing recursive XQuery over XML streams:the raindrop approach［J］.Data＆Knowledge Engineering，2008(65):243-265.

［11］MARTENS W，NIEHREN.Minimizing tree automata for unranked trees［J］.DBPL，2005:232-246.

［12］孟小峰，王宇，王小鋒.XML查詢優(yōu)化研究［J］.軟件學(xué)報，2006，10(10):2069-2086.

MENG Xiaofeng，WANG Yu，WANG Xiaofeng.Research on XML query optimization［J］.Journal of Software，2006，10(10):2069-2086.