確定自動機上的XML數據過濾算法改進

印桂生，沈潔，謝曉芹

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

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

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

1 Lazy DFA基本思想

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

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

2)根據NFA再轉換為相應的DFA.為了記錄DFA狀態轉移的觸發條件，每個DFA狀態都維護一個狀態轉移哈希表.

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

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

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

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

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

2 DFA-TA過濾系統

2.1 XML過濾系統結構

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

圖1 XML數據的過濾過程Fig.1 Filtering process of XML data

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

舉例說明XPath-DFA的過濾過程，對于給定的一個XML文檔:＜A＞＜B＞＜C＞＜/C＞＜/B＞＜/A＞，若干XPath查詢如下q1=A/B/C;q2=/B/ A;q3=/A/*;q4=/A/B中，通過建立 XPath-DFA，如圖2(a).將查詢的結果與可接受的狀態相關聯，當到達一個可接受的狀態的時候，則與其狀態相關聯的查詢要求就滿足了，如圖2(b).

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

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

2.2 頻繁訪問區的定義

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

2.3 頻繁訪問區的舉例

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

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

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

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

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

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

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

2.4 頻繁訪問區的構造算法

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

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

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

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

算法1 構造頻繁訪問區

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

頻繁訪問區的構造在線和離線狀態都可以，在其自適應性和開銷中尋求權衡.在線方式可以很好的適應局部模式，但是會產生運行時間開銷的問題，可以為每次轉換增加一個計數器來增加自動機的容量.因此一般都采用離線的方式來構造頻繁訪問區.

2.5 頻繁訪問區節點的閾值確定

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

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

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

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

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

3 算法性能分析

3.1 實驗環境

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

3.2 實驗測試數據

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

表1 XML數據流特征Table 1 The feature of XML data in experiment

3.3 實驗結果數據

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

圖4 數據過濾Fig.4 Data filtering data

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

圖5 內存使用情況Fig.5 The Usage of Memory

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

4 結束語

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

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

［2］CHAN C Y，FEIBER 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，FRANKLIN M J，ZHANG H，FISCHER P.Path sharing and predicate evaluation for highperformance xml filtering［J］.TODS，2003，10:467-516.

［4］DIAO Y，FISCHER P，FRANKLIN 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自動機的構造及實用化研究［J］.計算機學報，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數據流上的高效執行［J］.軟件學報，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查詢優化研究［J］.軟件學報，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.