印桂生，沈潔，謝曉芹

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

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

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

1 Lazy DFA基本思想

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

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

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

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

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

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

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

一般而言，在緩存的存取過程中定位技術(shù)(例如:狀態(tài)重用)是減少緩存失效的根本所在.此外，一般順序存取比隨意存取更加有序，基于以上這2點(diǎn)，在緩存敏感性自動(dòng)機(jī)技術(shù)的基礎(chǔ)上，提出一種改進(jìn)的技術(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所示.這個(gè)系統(tǒng)主要的部分包括一個(gè)用來解析用戶查詢的XPath解析器，一個(gè)用解析文檔的基于事件的SAX解析器［7］，一個(gè)用于過濾文檔的基于自動(dòng)機(jī)的過濾機(jī)制.在這個(gè)過濾機(jī)制中的自動(dòng)機(jī)可以是XPath-DFA或者是下文的DFA-FA自動(dòng)機(jī).

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

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

舉例說明XPath-DFA的過濾過程，對(duì)于給定的一個(gè)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ù)竭_(dá)一個(gè)可接受的狀態(tài)的時(shí)候，則與其狀態(tài)相關(guān)聯(lián)的查詢要求就滿足了，如圖2(b).

圖2 查詢的自動(dòng)機(jī)表示Fig.2 Automata expression for querying

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

T的值可以通過緩存失效的模型進(jìn)行評(píng)估，B的值由下面的公式評(píng)估:

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

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

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

3 算法性能分析

3.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證DFA-FA算法的有效性，建立了基于頻繁訪問區(qū)的XPath查詢過濾優(yōu)化的測(cè)試環(huán)境，本實(shí)驗(yàn)中的硬件環(huán)境為IBM X61計(jì)算機(jī)，操作系統(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編譯.過濾實(shí)驗(yàn)全部采用內(nèi)存駐留技術(shù)并保證內(nèi)存的使用率不超過80%.

3.2 實(shí)驗(yàn)測(cè)試數(shù)據(jù)

實(shí)驗(yàn)中使用的數(shù)據(jù)集合如下:1)NASA提供的天文學(xué)方面的XML數(shù)據(jù)［6］(簡(jiǎn)單的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í)數(shù)據(jù)，而NAA的數(shù)據(jù)是由IBM XML數(shù)據(jù)生成器產(chǎn)生的合成數(shù)據(jù)［2］.表1描述的就是這些數(shù)據(jù)的特征，其中第1項(xiàng)顯示的是數(shù)據(jù)的最大元素深度，NASA數(shù)據(jù)相對(duì)較淺，NAA和TreeBank數(shù)據(jù)較深;第2項(xiàng)表示的是其中DTD和XML的嵌套數(shù)量.DTD的嵌套表示DTD中定義的遞歸的元素?cái)?shù)量，XML的嵌套表示的是在XML數(shù)據(jù)中有多少個(gè)遞歸模式的表示.注意到NASA數(shù)據(jù)的DTD中僅有一個(gè)遞歸元素以及18個(gè)遞歸模式，MAA XML數(shù)據(jù)有中等數(shù)量的遞歸模式，而TreeBank XML數(shù)據(jù)中有大量的遞歸模式;最后一項(xiàng)是顯示的是在DTD中元素的數(shù)量和XML數(shù)據(jù)的起始標(biāo)簽.

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

3.3 實(shí)驗(yàn)結(jié)果數(shù)據(jù)

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

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

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

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

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

4 結(jié)束語

對(duì)多組測(cè)試數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可以證明本文提出的DFA-FA過濾系統(tǒng)，能夠有效的提高XPath執(zhí)行器的執(zhí)行效率.隨著測(cè)試數(shù)據(jù)復(fù)雜程度的增加，3組測(cè)試數(shù)據(jù)集NASA、NAA和TreeBank中涉及的數(shù)據(jù)包的最大深度、嵌套層次和元素的數(shù)量都是遞增的，執(zhí)行的的XPath過濾性能的優(yōu)越性越強(qiáng).并且DFA-FA系統(tǒng)內(nèi)存的使用增長(zhǎng)率很低，遠(yuǎn)小于前2種系統(tǒng)對(duì)內(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自動(dòng)機(jī)的構(gòu)造及實(shí)用化研究［J］.計(jì)算機(jī)學(xué)報(bào)，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］高軍，楊冬青，唐世渭，王騰蛟.基于樹自動(dòng)機(jī)的XPath在XML數(shù)據(jù)流上的高效執(zhí)行［J］.軟件學(xué)報(bào)，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é)報(bào)，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.