黃 碩，樓樹(shù)美

(1. 華中師范大學(xué) 信息技術(shù)系，湖北 武漢430079；2. 信陽(yáng)職業(yè)技術(shù)學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，河南 信陽(yáng) 464000；3. 南京理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210094)

0 引言

在Web技術(shù)中，為了分享公共資源，人們需要用信息載體來(lái)傳遞信息.目前，主要的信息載體用的是超文本(hypertext)，但是超文本的缺點(diǎn)是只能依賴瀏覽器，不能被其他的應(yīng)用程序所利用，HTML具有局限性.針對(duì)HTML存在的問(wèn)題，產(chǎn)生了XML[1](eXtensible Markup Language).XML作為互聯(lián)網(wǎng)上共享數(shù)據(jù)的新標(biāo)準(zhǔn)是可擴(kuò)展的置標(biāo)語(yǔ)言，可與HTML兼容，應(yīng)用范圍不受限制，是半結(jié)構(gòu)化數(shù)據(jù)特殊的表現(xiàn)方式.XML以其較高的靈活性、擴(kuò)展性和格式很快占據(jù)了商業(yè)市場(chǎng).多數(shù)企業(yè)已經(jīng)采用XML進(jìn)行數(shù)據(jù)共享和交流.大部分XML中，路徑表達(dá)式都是重要的組成部分之一，所以對(duì)路徑表達(dá)式進(jìn)行優(yōu)化，提高性能非常有必要.本文中提到了補(bǔ)路徑和路徑縮短法兩種優(yōu)化路徑表達(dá)式的方法.而如何提高查詢XML數(shù)據(jù)的效率是現(xiàn)在的一個(gè)熱門(mén)話題.網(wǎng)絡(luò)上現(xiàn)在已經(jīng)有非常多的XML數(shù)據(jù)，提取這些數(shù)據(jù)，需要一個(gè)文檔查詢工具，本論文中提到了最常用的查詢語(yǔ)言——XQuery[2].過(guò)濾技術(shù)是在過(guò)程中將有害信息過(guò)濾掉，在面對(duì)數(shù)據(jù)量比較大，對(duì)處理速度的要求比較高的情況下，需要對(duì)傳統(tǒng)的過(guò)濾技術(shù)進(jìn)行改造，本文最后詳細(xì)闡述了XML過(guò)濾算法的實(shí)現(xiàn).

1 XML路徑表達(dá)式的優(yōu)化

中國(guó)人民大學(xué)孟小峰[3]教授將XML描述為表現(xiàn)半結(jié)構(gòu)化數(shù)據(jù)的形式.它有結(jié)構(gòu)不規(guī)則、不進(jìn)行類型約束、模式信息模糊等特點(diǎn).與傳統(tǒng)關(guān)系的結(jié)構(gòu)數(shù)據(jù)相比，半結(jié)構(gòu)化數(shù)據(jù)模式?jīng)]有明確定義，模式產(chǎn)生在數(shù)據(jù)后面，且它規(guī)模會(huì)不斷變化.由于半結(jié)構(gòu)化數(shù)據(jù)的特點(diǎn)，所以它的靈活性很大，能夠適應(yīng)網(wǎng)絡(luò)數(shù)據(jù)的復(fù)雜要求.

1.1 優(yōu)化目的

目前，正規(guī)路徑表達(dá)式被廣泛地應(yīng)用于包括XML在內(nèi)的許多半結(jié)構(gòu)化數(shù)據(jù)查詢語(yǔ)言中.首先，要對(duì)XML文檔進(jìn)行簡(jiǎn)化，簡(jiǎn)化成DTD，也就是擴(kuò)展正則表達(dá)式.對(duì)正則表達(dá)式DTD進(jìn)行優(yōu)化是XML路徑表達(dá)式優(yōu)化的重要問(wèn)題.下面，我們通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明正則表達(dá)式優(yōu)化的問(wèn)題.如圖1，需要查詢Q1:select×Where(college.persons.person.name)×.

圖1 XML文檔樹(shù)結(jié)構(gòu)Fig. 1 XML document tree structure

對(duì)于Q1,我們需要查詢出學(xué)院中所有工作人員的名字.如果文檔中沒(méi)有索引，對(duì)Q1進(jìn)行查詢要按照路徑“學(xué)院工作人員個(gè)人姓名”來(lái)對(duì)文檔中的每個(gè)元素進(jìn)行搜索，符合要求的元素將會(huì)被返回.在對(duì)XML進(jìn)行整理的時(shí)候，通過(guò)DTD可以得到查詢Q1的有用信息，但是，姓名到學(xué)院的路徑只有一條.所以，在查詢的時(shí)候，“學(xué)院工作人員個(gè)人姓名”通常被作為一個(gè)整體進(jìn)行操作.

DTD能夠提供文檔模式的有用信息，利用這一點(diǎn)，能夠?qū)Σ樵儗?shí)現(xiàn)優(yōu)化.對(duì)查詢進(jìn)行優(yōu)化的重點(diǎn)就是對(duì)路徑表達(dá)式進(jìn)行優(yōu)化.優(yōu)化查詢有三步：一、根據(jù)擴(kuò)展正則表達(dá)式的含義對(duì)DTD進(jìn)行縮減；二、對(duì)交結(jié)點(diǎn)進(jìn)行定義；三、根據(jù)交結(jié)點(diǎn)提出路徑縮短和補(bǔ)路徑兩種路徑表達(dá)式優(yōu)化策略.

1.2 路徑表達(dá)式及其優(yōu)化策略

將XML文檔看成是若干路徑實(shí)例的組合[4]，每一個(gè)路徑實(shí)例都有相應(yīng)數(shù)據(jù)節(jié)點(diǎn)，所以將路徑表達(dá)式查詢和XML文檔路徑實(shí)例結(jié)合起來(lái)，就可得到所需要的元素實(shí)例.

定義1(交結(jié)點(diǎn))D(E,A,P,R,r)是XML的文檔模式，假設(shè)結(jié)點(diǎn)n1,n2,n3∈A∪E，每一條初始結(jié)點(diǎn)為n2終結(jié)點(diǎn)為n3的路徑都經(jīng)過(guò)n1，在XML模式中，就把n1叫作n2和n3的交結(jié)點(diǎn)，表示為：Ent(n2,n3)=n1.

基于Lore的系統(tǒng)，關(guān)于SPE的查詢方法有以下三種：混合查詢(hybrid)、從底到頂(bottom-up)、從頂?shù)降?top-down).而外延鏈接算法則是混合查詢方法的一個(gè)完善.對(duì)于外延算法，下面提出了兩種對(duì)路徑表達(dá)式進(jìn)行優(yōu)化的策略，同時(shí)，這兩種方法也同樣可以用到另外的路徑表達(dá)式的優(yōu)化中.這兩種方法分別是：路徑縮短(path shorten)和補(bǔ)路徑(path complementing).

1.2.1 路徑縮短

我們把下面提到的3個(gè)定理叫作關(guān)于路徑表達(dá)式查詢的路徑縮短策略，它們的原理相同，都是利用XML文檔模式信息，基于用戶查詢的本質(zhì)，對(duì)路徑表達(dá)式查詢進(jìn)行縮短.

定理1 假設(shè)XML文檔Td符合XML模式Gt，那么Td中除了被rootd用到的元素之外所有的都是它的后代，可以表示為,rootd的后代為(?n)n∈{Vd-rootd}→n.

定理2 假設(shè)Gt中只有通過(guò)絕對(duì)路徑表達(dá)式查詢Q={Gt,Td,roott,PE,RS}能夠訪問(wèn)最終目標(biāo)，同時(shí)，路徑PE最后元素的類型用End(PE)來(lái)表示，可以得到RS=EXT(End(P,E)).

定義2 設(shè)Q={Gt,Td,roott,PE,RS}是一個(gè)查詢,同時(shí)End(roott+PE)=En,并且(?e)(e∈EXT(En)→e∈RS)，則元素類型En只有PE這么一條訪問(wèn)路徑(unique accessing path)，我們將它寫(xiě)成UAP(En)=PE.

定義4 對(duì)于Gt和Td，并且E1,E2∈Vt，假設(shè)(?e2∈Vd)(e2∈EXT(E2)→(?e1)(e1∈EXT(E1)∧e1)，那么我們稱E2的關(guān)鍵祖先(key ancestor)是E1，它代表的含義是元素實(shí)例在對(duì)E2進(jìn)行訪問(wèn)的時(shí)候一定要經(jīng)過(guò)E1，寫(xiě)作KA(E2)=E1.

定理3n步絕對(duì)路徑表達(dá)式E1C1E2C2E3,…,Cn-1En中路徑連接符用Ei(1≤i≤n)和Ci(1≤i≤n-1)表示，對(duì)于Q1={Gt,Td,E1,C1E2C2E3,…,Cn-1En,RS1}，并且UAP(E2)=C1E2，也就是說(shuō)相對(duì)路徑查詢方式Q2={Gt,Td,E2,C2E3,…,Cn-1En,RS2}可來(lái)替換掉Q1，假設(shè)E3的關(guān)鍵祖先或者僅有的父元素為E2(C2可用‘/’，‘//’表示)，那么Q1可以用Q3={Gt,Td,E3,C3E4,…,Cn-1En,RS3}來(lái)替換，也就是說(shuō)UAP(E3)=C1E2C2E3.

由定理3可以知道，在某種條件下，對(duì)Q2進(jìn)行優(yōu)化可以得到Q3，證明我們可以對(duì)相對(duì)路徑查詢進(jìn)行優(yōu)化.上面所提到的定理推論，它們的性質(zhì)是一樣的，都是在基于用戶需要查詢的內(nèi)容基礎(chǔ)上，用XML文檔的相關(guān)模式簡(jiǎn)化并縮短路徑表達(dá)式，進(jìn)而減少了查詢的成本，它們共同構(gòu)成了簡(jiǎn)化路徑表達(dá)式的路徑縮短策略.

1.2.2 補(bǔ)路徑

通過(guò)對(duì)路徑表達(dá)式進(jìn)行優(yōu)化來(lái)提高查詢速度的方法稱為路徑縮短策略.而補(bǔ)路徑，是用簡(jiǎn)單的路徑表達(dá)式來(lái)代替用戶所建立的復(fù)雜度表達(dá)式，這樣也能提高查詢速度.同路徑縮短一樣都要用到XML文檔模式信息.

定義5(互補(bǔ)路徑) 對(duì)于XML數(shù)據(jù)Td={Vd,Ed,δd,∑d,rootd,oid,typed,oidd}和XML模式Gt={Vt,Et,δt,∑t,roott}，若E2∈V1,KA(E2)=E1，所有的n條路徑P1,P2,…，Pn都存在于E1和E2中，同時(shí)End(Pi)=E2(1≤i≤n)，我們可以將路徑Pi相對(duì)于E1和E2之間的互補(bǔ)路徑(complementary paths)定義為

可以寫(xiě)成

運(yùn)用補(bǔ)路徑方法對(duì)路徑表達(dá)式進(jìn)行優(yōu)化之后，仍然需要運(yùn)用路徑縮短方法來(lái)對(duì)路徑表達(dá)式進(jìn)行更深一步的簡(jiǎn)化.在使用補(bǔ)路徑簡(jiǎn)化方法中，最重要的問(wèn)題就是找出查詢路徑所對(duì)應(yīng)的互補(bǔ)路徑，然后估算補(bǔ)路徑的成本，選擇相關(guān)的查詢方法.

在這個(gè)方法中，通過(guò)反向路徑法來(lái)對(duì)關(guān)鍵祖先和互補(bǔ)路徑進(jìn)行確定，而確定互補(bǔ)路徑的經(jīng)過(guò)使用函數(shù)getCP(E1,E2,P)來(lái)代表.接下來(lái)，估算所有出現(xiàn)的查詢策略，并篩選出其中代價(jià)最少的執(zhí)行策略.在估算代價(jià)之前，運(yùn)用函數(shù)PS(P)和Cost(P)對(duì)路徑表達(dá)式P進(jìn)行縮短優(yōu)化，從路徑終端實(shí)行補(bǔ)路徑的方法，只要出現(xiàn)比之前代價(jià)小的方法就馬上結(jié)束.如此，對(duì)路徑比較長(zhǎng)的表達(dá)式該策略的效益比較高.

2 XML查詢語(yǔ)言及查詢處理

2.1 XML查詢語(yǔ)言

XML已經(jīng)逐漸成為Web上數(shù)據(jù)交換的新標(biāo)準(zhǔn)，基于XML數(shù)據(jù)的半結(jié)構(gòu)化，傳統(tǒng)數(shù)據(jù)庫(kù)所適用的查詢語(yǔ)言不能再用，需要重新創(chuàng)建合適的查詢語(yǔ)言.XQuery[5.6]擁有多種XML查詢語(yǔ)言的長(zhǎng)處，是目前公認(rèn)的XML查詢語(yǔ)言標(biāo)準(zhǔn).而Xpath是XQuery語(yǔ)言的核心部分.

2.2 Xpath查詢處理

2.2.1 Xpath表達(dá)式

下面介紹ISBaXI-I對(duì)涉及上面所提到的XPE路徑查詢方法[7].XPE中有多個(gè)約束謂詞，ISBaXI-I的方法是把XPE劃分成若干個(gè)僅包含一個(gè)謂詞約束的XPE.將劃分之后得到的XPE查詢結(jié)果，作為下一個(gè)XPE計(jì)算的輸入.在查詢中經(jīng)常碰到一階謂詞XPE，它可以映射為XPE-Tree.

定義6(XPE-Tree) 將XPE映射為XPE-Tree，而XPE最開(kāi)始的結(jié)點(diǎn)是XPE-Tree的根結(jié)點(diǎn)，寫(xiě)作r.將XPE中的結(jié)點(diǎn)定位標(biāo)志作為樹(shù)節(jié)點(diǎn)u的前綴，謂詞作為后綴，n(u)∈E∪A.而根據(jù)u的子結(jié)點(diǎn)在XPE中出現(xiàn)的先后順序定義它們的長(zhǎng)幼關(guān)系.

我們將條件節(jié)點(diǎn)c定義為具有謂詞匹配條件的葉節(jié)點(diǎn)；將目標(biāo)節(jié)點(diǎn)t定義為待求葉節(jié)點(diǎn).

定義7 (XPE-Tree分支節(jié)點(diǎn)) 在XPE-Tree中，如果節(jié)點(diǎn)b∈Ance(c)nAnce(t)，同時(shí)?d，d∈Ance(c)nAnce(t)，且level(b)≥level(d)，那么將b稱作XPE-Tree的分支節(jié)點(diǎn).

用Irb來(lái)表示從節(jié)點(diǎn)r到節(jié)點(diǎn)b的路徑，同理，Ibc表示節(jié)點(diǎn)b到節(jié)點(diǎn)c的路徑，Ibt表示結(jié)點(diǎn)b到結(jié)點(diǎn)t的路徑.

2.2.2 查詢處理

查詢處理[8]的方法如下：

(1)為了降低XML在結(jié)構(gòu)上匹配的復(fù)雜程度，先將XPE-Tree進(jìn)行模式的匹配；

(2)對(duì)XPE-Tree中的b，c，t的解鎖對(duì)應(yīng)的節(jié)點(diǎn)集進(jìn)行謂詞匹配和兩次路徑連接運(yùn)算，就可以確定在XML中XPE-Tree結(jié)點(diǎn)b，c，t的解.

對(duì)一階謂詞XPE查詢過(guò)程如下:

首先，對(duì)XPE-Tree進(jìn)行路徑匹配(在模式索引TSM中)，對(duì)VSM進(jìn)行判斷.若VSM為空，那么查詢結(jié)束；若VSM不為空，那么令i=1.對(duì)i與|VSM|的大小進(jìn)行比較，如果i>|VSM|，那么結(jié)束查詢過(guò)程；如果i<|VSM|，對(duì)vdi對(duì)應(yīng)的(TXML)xn結(jié)點(diǎn)進(jìn)行路徑連接運(yùn)算和謂詞匹配.然后，對(duì)WXML為空進(jìn)行判斷，如果不為空，在模式索引中尋找vdi在TSM中所對(duì)應(yīng)的路徑結(jié)構(gòu)，輸出滿足XPE的xn，XML路徑結(jié)構(gòu)和待求節(jié)點(diǎn)values，之后進(jìn)行運(yùn)算i++；如果WXML為空，那么直接令i++.此時(shí)再重新將i與|VSM|的大小進(jìn)行比較，直至VSM為空，或者i>|VSM|，最后結(jié)束查詢.

3 XML過(guò)濾算法

過(guò)濾引擎通過(guò)下面的過(guò)程實(shí)現(xiàn)過(guò)濾功能：首先，為了能夠過(guò)濾帶分支路徑的路徑表達(dá)式，將路徑表達(dá)式用不確定性的自動(dòng)機(jī)NFA代替，在這個(gè)自動(dòng)機(jī)中，需要用特殊的標(biāo)記來(lái)區(qū)分分支路徑，接著，通過(guò)XML Schema將NFA轉(zhuǎn)化成DFA，最終，將若干個(gè)DFA合并成巨大的過(guò)濾引擎DFA.

我們用路徑表達(dá)式來(lái)表示自動(dòng)機(jī)，如圖2和圖3.圖2表示開(kāi)始狀態(tài)1經(jīng)過(guò)任意元素轉(zhuǎn)移到結(jié)束狀態(tài)2.而我們用//來(lái)代表子孫關(guān)系，與(/*)*含義相同，其中，第一個(gè)*表示通配符，而第二個(gè)*表示kleene閉包，表示0或者幾個(gè)/*相連.

圖2 /*的表達(dá)方式

Fig. 2Theexpressionof/*

圖3 //*的表達(dá)方式Fig. 3 The expression of //*

當(dāng)對(duì)路徑表達(dá)式進(jìn)行簡(jiǎn)化之后，將它們形成的DFA集合生成一個(gè)大的DFA，這個(gè)過(guò)程類似于在Trie樹(shù)中多加一個(gè)串.如果路徑表達(dá)式為p，我們最終合并得到的自動(dòng)機(jī)為A，那么要將p合入到A中生成A’的步驟如下：

如果自動(dòng)機(jī)A開(kāi)始的狀態(tài)為q，并且它的第一個(gè)step是p；那么基于A的狀態(tài)q和step的名稱e來(lái)對(duì)下一個(gè)狀態(tài)r進(jìn)行查詢.如果r里面是空的，那么形成一個(gè)新的r，此時(shí)q指向r，e為傳遞符號(hào)，當(dāng)前的狀態(tài)變?yōu)閞.假設(shè)step有

分支，那么當(dāng)前狀態(tài)r會(huì)用遞歸法來(lái)對(duì)這個(gè)過(guò)程進(jìn)行調(diào)用，這個(gè)過(guò)程結(jié)束之后會(huì)開(kāi)始下一個(gè)step，屬性指針會(huì)記錄下屬性謂詞.當(dāng)p沒(méi)有分支點(diǎn)時(shí)候，在到達(dá)最終step的時(shí)候，節(jié)點(diǎn)會(huì)呈接受狀態(tài).如果有分支，那么在p的第一個(gè)分支節(jié)點(diǎn)，保證該節(jié)點(diǎn)的狀態(tài)是接受狀態(tài)，將p的id值添加到該節(jié)點(diǎn)的接受路徑表達(dá)式列表.

需要注意，要將XML分析完畢同時(shí)找出來(lái)所有滿足條件的接受狀態(tài)，此時(shí)才能終止DFA.而查詢過(guò)程僅僅能夠輸出一次，最終，給滿足條件的用戶傳輸整個(gè)XML文檔.

4 結(jié)論

相比于傳統(tǒng)的HMTL，XML的靈活性和擴(kuò)展性都非常好，得到了廣泛的應(yīng)用，成為互聯(lián)網(wǎng)數(shù)據(jù)共享的新標(biāo)準(zhǔn).在XML查詢語(yǔ)言中，最重要的部分就是路徑表達(dá)式.本文提出了兩種優(yōu)化策略：路徑縮短策略和補(bǔ)路徑，極大地縮短了查詢所需的時(shí)間，提高了查詢效率.對(duì)于查詢語(yǔ)言Xpath，它的查詢處理是通過(guò)對(duì)XPE-Tree進(jìn)行匹配以及兩次路徑連接運(yùn)算來(lái)實(shí)現(xiàn)查詢處理的.XML的過(guò)濾系統(tǒng)通過(guò)路徑表達(dá)式來(lái)進(jìn)行模式和內(nèi)容匹配，在用戶信息輸入系統(tǒng)之后，生成過(guò)濾引擎，過(guò)濾引擎與數(shù)據(jù)流進(jìn)行匹配，輸出用戶感興趣的信息，以此來(lái)完成過(guò)濾過(guò)程.