??? XFilter首次利用基于有限狀態(tài)自動(dòng)機(jī)FSM(Finite State Machine)的方法來過濾XML文檔，它對(duì)每一個(gè)路徑查詢使用一個(gè)單獨(dú)的FSM,，并在文檔處理的過程中,，同時(shí)運(yùn)行所有的FSM。YFilter在XFilter的基礎(chǔ)上進(jìn)行了改進(jìn),，它將所有的XPath查詢合并成一個(gè)單獨(dú)的非確定有限自動(dòng)機(jī)NFA(Non-deterministic Finite Automaton)[6],，并共享所有查詢的公共前綴，YFilter主要考慮了謂詞中的AND謂詞查詢，采用后置處理的方式,，這種方式產(chǎn)生大量中間結(jié)果影響系統(tǒng)性能。
　　XEBT(XPath Evaluation Based on Tree automata)[7]利用樹自動(dòng)機(jī)技術(shù)作為查詢處理器,，它基于表達(dá)能力豐富的樹自動(dòng)機(jī),，無須附加中間狀態(tài)或保存中間結(jié)果，就能處理支持{[]}操作符的XPath,，所以能較高效地處理XPath查詢,。在優(yōu)化策略上，主要包括基于DTD的XPath查詢自動(dòng)機(jī)的構(gòu)造,、在空間代價(jià)有限增加的情況下采用局部確定化減少并發(fā)執(zhí)行的狀態(tài),、采用自上而下和自下而上相結(jié)合的查詢處理策略等。
　　其他處理XML流的方法主要有基于索引（Index-Filter）的方法[2],、基于Bloom Filter[3]的方法以及FiST[5]方法,。Index-Filter[2]采用基于索引的技術(shù)處理XML流數(shù)據(jù)，利用XML文檔流的文檔標(biāo)記動(dòng)態(tài)地建立XML文檔的索引,，從而避免處理一部分文檔,。在Index-Filter的方法中，建立索引要花費(fèi)一定的時(shí)間,，而且不能單遍處理XML文檔,。基于Bloom Filter的XML包過濾器具一種近似查詢方法,，利用Bloom Filter方法,，將XPath表達(dá)式作為字符串，將XPath與XML包之間的匹配轉(zhuǎn)換為字符串之間的匹配,，從而提高查詢性能,，但它只是用來處理簡單的XPath表達(dá)式且有一定的失誤率。FiST方法針對(duì)Twig Pattern提出的一種有別于YFilter的方法,，將一組Twig Pattern轉(zhuǎn)換為prufer序列,，并對(duì)一組Twig Pattern與XML流數(shù)據(jù)進(jìn)行整體性匹配。
2 GBRender模型
2.1 GBRender相關(guān)定義
　　當(dāng)XML以流的形式進(jìn)行處理時(shí),，在邏輯上實(shí)際是以先序遍歷的形式對(duì)XML樹中的結(jié)點(diǎn)進(jìn)行訪問,，通常采用基于事件的SAX模型來進(jìn)行解析。這樣,，在對(duì)XML結(jié)構(gòu)未知的情況下,，可以根據(jù)接收的元素信息來分析其結(jié)構(gòu)，并根據(jù)得到的結(jié)構(gòu)信息為后續(xù)服務(wù),。
??? 為了用來更好地描述GBRender查詢模型,，下面介紹幾個(gè)定義：
??? 定義1(組)：XML的任何一個(gè)元素都有一個(gè)從根開始的標(biāo)簽路徑，但很多元素都會(huì)有相同標(biāo)簽路徑，即1個(gè)標(biāo)簽路徑可以表示1組對(duì)應(yīng)的元素,。這里把XML文檔中每一個(gè)不同的標(biāo)簽路徑稱為組,。如圖2所示，root/person/name即為一個(gè)組,。

??? 定義2(組樹)：組樹是在處理XML數(shù)據(jù)流過程中,，記錄組、組之間關(guān)系的樹形結(jié)構(gòu),。其組織結(jié)構(gòu)如圖3所示,。組樹中，各組有指向其子組的鏈接,，每個(gè)組有指向父組的鏈接,，同時(shí)，同一層的組串接起來以便于處理時(shí)的需要,。
　　定義3(終結(jié)元素)：XPath表達(dá)式對(duì)應(yīng)的最后一個(gè)路徑元素,，稱為終結(jié)元素，它表示XPath請(qǐng)求所需的結(jié)果,。如//A/B//C,，C即終結(jié)元素。
　　定義4(著色)：尋找每一個(gè)組的標(biāo)簽路徑處于XPath表達(dá)式中的哪個(gè)位置,，即當(dāng)前XML元素的路徑與XPath路徑的關(guān)系并標(biāo)記該組,，這個(gè)過程稱為著色過程。例如,，組root/person/name對(duì)應(yīng)XPath表達(dá)式//name的終結(jié)元素name,，則可以標(biāo)記該組為該XPath的終結(jié)組。
2.2 GBRender結(jié)構(gòu)模型
　　目前的XML數(shù)據(jù)流XPath查詢處理,，基本結(jié)構(gòu)模型如圖4所示,，以XML數(shù)據(jù)流作為XPath分析器的輸入，分析器可能有多個(gè),，也可能合并為1個(gè),。對(duì)XPath查詢包含的索引信息有2種：一是傳輸之前的索引信息；二是接收端進(jìn)行處理形成的索引信息,。

　　GBRender查詢模型如圖5所示,，采用基于著色的方式來處理查詢，當(dāng)某個(gè)組首次出現(xiàn)時(shí),，通過著色器對(duì)其與XPath的關(guān)系進(jìn)行著色,。著色之后，再次遇到該組時(shí)不再依賴于XPath而只依賴其記錄的組著色信息,，尤其在單枝查詢的情況下,，可以直接對(duì)查詢進(jìn)行回應(yīng),。在GBRender模型中，組著色的過程,，實(shí)際上相當(dāng)于XPath確定化的過程,。例如，對(duì)于圖2的文檔進(jìn)行//name查詢,，當(dāng)首次出現(xiàn)name時(shí),，其組標(biāo)簽路徑為root/person/name，即是對(duì)//祖孫關(guān)系在此文檔上進(jìn)行的確認(rèn)化,，而且當(dāng)name出現(xiàn)在另一組時(shí)，會(huì)再一次進(jìn)行確認(rèn)化且不會(huì)相互影響,。而常采用的DTD優(yōu)化策略通常也是完成確認(rèn)化的工作,，當(dāng)遇到2個(gè)不同組均存在name標(biāo)簽時(shí)，//就需要特殊處理了,。

??? 為了同時(shí)響應(yīng)多個(gè)XPath查詢,，本文引入了著色序列的定義。
　　定義5(著色序列)：根據(jù)XPath請(qǐng)求序列,，對(duì)同一組生成對(duì)應(yīng)的著色信息序列,，此序列即稱為著色序列。因?yàn)椴煌腦Path有不同的著色信息,，因此也稱XPath著色序列,。
??? 每組均有著色序列，其組樹中組的結(jié)構(gòu)如圖6所示,。

2.3 GBRender處理模型
??? 基于組樹的動(dòng)態(tài)建立與組著色機(jī)制,，GBRender的任意組，僅當(dāng)首次出現(xiàn)時(shí)進(jìn)行XPath著色處理,，之后則根據(jù)著色情況進(jìn)行處理,。
　　GBRender的查詢處理，其數(shù)據(jù)輸入是XML的SAX解析事件流,，包括startDocument,、endDocument、startElement,、endElement和Text事件,，這里只給出GBRender處理模型在每一類事件的響應(yīng)動(dòng)作，而不討論數(shù)據(jù)緩存處理,。
　　startDocument： initiate the GroupTree GT and context?? //初始化組樹GT
　　StartElement(element)?? 　　　　　// element為新接收元素
　　If(not existsGroup(element))InsertGroupAndDrawXpathColor(element),；??

　　　　　　　　　　　　　　?? 　　　//如果不存在該組，則生成該組并進(jìn)行著色產(chǎn)生著色序列
　　setCurrentElement(element),；　　 //置element為當(dāng)前元素
??? Text (value)??? 　　　　　　　　　// 當(dāng)前元素的值
?????? Add value into currentElement.currentValue,；
　　　　　　　　　　　　　　　　　　　?// 增加到當(dāng)前元素值
　　? EndElement(element)??
?????? ProcessXPathColor(element)；?? // 根據(jù)當(dāng)前元素的著色序列信息進(jìn)行處理
?????? setCurrentElement(element.parentGroup)； //
??? EndDocument?
?????? cleanUp( ),；???? 　　　　　　　// 處理全部結(jié)束,，清理
2.4 GBRender查詢模型的主要特征
　　? GBRender查詢模型處理的操作方向與目前主要的查詢處理不同，分析器并不是與XPath綁定,，而是綁定到XML文檔結(jié)構(gòu)上,，它對(duì)XPath只在組首次出現(xiàn)時(shí)進(jìn)行著色的處理，之后則根據(jù)著色情況來進(jìn)行處理,。這種模型具有較強(qiáng)的靈活性,，主要特點(diǎn)如下：
??? (1)對(duì)XML文檔結(jié)構(gòu)無需任何考慮。因?yàn)橐越邮盏牧鲾?shù)據(jù)為依據(jù)來動(dòng)態(tài)建立組樹,。根據(jù)XML流數(shù)據(jù)的順序性與元素之間關(guān)系的局部性,，組樹的訪問總是發(fā)生在相鄰元素之間，因此效率很高,。
??? (2)無需依賴XPath分析器,。一旦著色，相當(dāng)于就對(duì)該組進(jìn)行了確定化,。同時(shí),，對(duì)于簡單的XPath表達(dá)式在當(dāng)前組即可直接判定作出處理。
??? (3)可以方便地利用現(xiàn)有的其他XPath查詢處理機(jī)制,，如自動(dòng)機(jī)模型,。因?yàn)樵谀撤N程度上，著色類似確定化XPath,，當(dāng)處理復(fù)雜謂詞時(shí),，其著色信息處理可以方便地吸收自動(dòng)機(jī)模型的思想。
??? (4)非常容易擴(kuò)展XPath查詢數(shù)目,，著色序列長度的增加對(duì)效率影響很小,。
??? (5)方便進(jìn)行類似關(guān)鍵詞查詢的流數(shù)據(jù)處理。如不考慮數(shù)據(jù)來源的結(jié)構(gòu),，用戶只關(guān)心信息中的author或name的信息,。本文模型可以很容易且高效的去完成處理，僅需傳入//author,、//name的XPath表達(dá)式串,，就可以應(yīng)用于任意的XML流數(shù)據(jù)源。
3 GBRender的主要算法
　　以單枝查詢?yōu)槔喴榻BGBRender查詢模型中的著色算法與處理算法,。
　　在單一分枝的查詢中,，由于XPath表達(dá)式中僅有//與/關(guān)系，組標(biāo)簽對(duì)于XPath路徑中的元素只存在3種關(guān)系,，即無,、中間元素或終結(jié)元素,，而本文關(guān)心的正是那些終結(jié)元素且此處暫不需考慮緩存，為了便于描述,，用Color.Empty,、Color.Mid以及Color.End來表示2種著色狀態(tài)。
??? (1)單一分枝下的組著色算法：
??? GroupRendering(G,， XPaths)
??? 輸入：組G是當(dāng)前元素所在組,，表達(dá)式串XPaths是XPath表達(dá)式集合
??? {
??? 　　Foreach(xpath in XPaths)
??? 　　{
??? 　　? If(G.tagPath not satisfy part xpath)?? //未發(fā)現(xiàn)匹配，e.tagPath為標(biāo)簽路徑
??? 　　　　　? G.XPathColorList.add(Color.Empty),；
　　??? 　 If(G.tagPath satisfy part xpath)?? 　　//有匹配
　　　??????? If(G.tagPath is 終結(jié)元素)?? 　　　　//是終結(jié)元素
???????????? G.XPathColorList.add(Color.End),；
????????? else???? 　　　　　　　　　　　　　　　　//不是終結(jié)匹配但匹配中間元素
????????????? G.XPathColorList.add(Color.Mid)；
??? 　　}
??? }
??? (2)endElement時(shí)根據(jù)組著色情況對(duì)元素進(jìn)行處理的算法：
??? ProcessXPathColor (G)
??? 輸入：組G是當(dāng)前元素所在組
??? {
???? 　　Foreach(color in G.XPathColorList)
???? 　　{? //單枝查詢情況下只需要對(duì)Color.End元素進(jìn)行處理
　　??????? Costomeri ++,；? // XPath逐個(gè)對(duì)應(yīng)
　　??????? If(color is Color.End)
　　??????? {
　　?????????? ToCustomer(Customeri,，G.currentElement.Value)； // 輸出結(jié)果
　　??????? }
　　??? }
??? }
4 實(shí)驗(yàn)
　　本文實(shí)現(xiàn)了GBRender查詢模型并應(yīng)用在單枝查詢上,，軟件環(huán)境是Windows xp+eclipse3.3+jdk1.5。硬件環(huán)境是：聯(lián)想旭日410M筆記本電腦,，配置為：CPU雙核T2080,，內(nèi)存1 GB，硬盤120 GB,。
??? 在實(shí)驗(yàn)中,，綜合了文檔大小與查詢數(shù)目的多少并與YFilter和Index-Filter作比較，結(jié)果發(fā)現(xiàn),，當(dāng)文檔相對(duì)較大時(shí)查詢數(shù)量無論多少,，GBRender都顯得非常有效；當(dāng)文檔相對(duì)較小而查詢數(shù)量較大時(shí),，GBRender與YFilter較為有效,。實(shí)驗(yàn)結(jié)果如圖7所示。