Ｔｗｉｇ ｐａｔｔｅｒｎ查詢處理研究綜述和分析

收稿日期：2007-12-30；修回日期：2008-03-19

基金項目：國家自然科學基金資助項目(60773100);國家教育部科學技術研究重點資助項目(205014);河北省教育廳科研計劃資助項目(2006143)

作者簡介：張忠平(1972-)，男，吉林松原人，副教授，碩導，博士后，主要研究方向為網格技術、XML數據庫、數據挖掘;何麗榮(1984-)，女，碩士研究生，主要研究方向為XML數據庫（xt_lmk@sina.com）; 張艷(1984-)，女，碩士研究生，主要研究方向為數據倉庫;李麗樂(1982-)，女，碩士研究生，主要研究方向為數據庫視圖安全.

(燕山大學 信息科學與工程學院 計算機軟件與理論系，河北秦皇島066004)

摘 要：介紹了twig pattern查詢處理和索引技術的研究現狀，對一些典型的twig pattern查詢處理方法進行了分析和評價，指出其中存在的優點和不足，展望了未來twig pattern查詢處理研究的關鍵問題和研究方向。

關鍵詞：小枝模式；索引；連接算法

中圖分類號：TP311

文獻標志碼：A

文章編號：1001-3695(2008)10-2881-04

Analytical overview on twig pattern query processing

ZHANG Zhong-ping， HE Li-rong， ZHANG Yan， LI Li-le

(Dept. of Computer Software Theory， College of Information Science Engineering， Yanshan University，Qinhuangdao Hebei 066004，China)

Abstract:This paper provided studied status of twig pattern query disposal and index technology， analysed and estimated ty-pical productions， pointed out the advantages and disadvantages of solutions processing twig pattern query， viewed some future directions and key problems in twig pattern query disposal.

Key words：twig pattern; index; join algorithm

0 引言

可擴展標記語言XML目前被認為是互聯網上數據表示和數據交換的新標準，越來越多的網上資源將以XML的格式表示。XML的靈活、開放和基于標準的格式使它很快成為商業界中用來交換商業數據的最廣泛使用的語言。通過XML數據發布和交流信息已被企業廣泛采用，也得到了研究人員和產業界的廣泛關注。目前，XML的主要研究方向包括XML的數據模型和理論研究，具體包括XML數據模式的研究、XML查詢處理優化以及XML數據的高效存儲和索引等。在XML數據處理的眾多問題中，XML數據的查詢及索引技術是非常關鍵的。

近年來，海量的數據以XML文檔形式出現。對用戶而言，在XML數據源中對大量信息進行有效查詢就顯得非常重要，它能夠幫助用戶方便有效地瀏覽獲取信息。因此，對XML數據尤其是結構復雜的XML數據進行有效的查詢是當前XML研究中重要和緊迫的課題。

XML技術被人們廣泛接受的原因是多方面的，但一個非常重要的、不可忽視的因素是XML的樹狀數據模型具有非常強大的表達能力，能夠描述各種數據源的結構。但XML具有很多不同于傳統數據形式的特點，傳統的數據處理技術不能直接應用在XML數據上，許多問題都需要重新考慮。針對XML這種樹狀數據的查詢，學者們已經提出了多種XML查詢語言，如XML-QL[1]、Lorel[2]、Quilt[3]、XPath[4] 和XQuery[5]等。其中XPath是W3C所推薦的XML查詢語言標準，它能夠表達對各種數據源的查詢。這些查詢語言盡管各有特點，但它們的一個共同特點是將路徑表達式作為其核心內容，用戶可以用路徑表達式描述在XML數據層次中的定位。XML查詢中的路徑表達式可以表示為樹狀查詢獨立地描述查詢要求。XML數據查詢主要分為單路徑和多分支路徑查詢。在這兩種路徑查詢方面，XML查詢都可表示成twig pattern查詢。研究高效的twig pattern查詢處理方法可以對大規模XML 數據的查詢需求提供有力的支持，在XML數據庫中找到所有出現的twig pattern是當前XML查詢處理的核心操作。

有鑒于索引技術在數據管理中的突出地位，眾多的XML文獻也將研究集中到了XML索引技術。如何捕獲XML數據中的結構特征、高效地支持路徑查詢的處理是其中的核心。針對不同的XML應用，人們提出了不同的索引結構DataGui-des[6]、index Fabric[7]、ToX[8]、XISS[9]、D(k)-index[10]、VIST[11]等，這些索引結構能夠滿足特定環境下的需求。雖然XML索引技術己經取得了一些研究成果，可以較快地處理一般路徑查詢。但是，由于XML數據的多樣性以及用戶日益增長的查詢需求，XML索引查詢技術在理論和實現上都還存在很多難點，人們很難找到一種能夠同時適應不同數據來源并能夠有效處理各種查詢請求的通用索引結構。

正是由于XML索引在XML數據庫領域中重要的理論意義和實踐意義，XML數據庫的索引技術對XML數據查詢處理起著至關重要的作用。如果沒有索引的支持可能帶來很大的I/O代價和語義支持方面的限制，因此，對XML數據索引技術的研究越來越受到重視。如何為XML數據建立高效的索引機制來提高查詢效率成為目前研究的關鍵問題。到目前為止，很少有把索引技術應用到XML文檔的整體twig pattern匹配中，如何利用索引技術高效處理twig pattern查詢將成為研究的重點。

1 Twig pattern查詢處理方法

在XML文檔中查找所有滿足twig pattern的內容是XML查詢處理的重要操作。早期的研究一般把twig pattern分解為一系列節點對的二元關系(父子關系或祖先后代關系)。Twig pattern查詢通過下列步驟進行匹配：a)在XML數據庫中匹配每一個二元關系；b)基于這些匹配進行縫合。關于twig pattern路徑查詢處理已有一些方法，下面簡要介紹幾種。

1. 1 一般處理方法

1）PathMPMJ 文獻[12]提出了一種二元連接算法PathMPMJNaive，對于路徑查詢每次只能處理一個數據流。考慮路徑查詢q1//q2//q3，其基本思想如下：數據流Tq1取得第一個元素并利用這個特定元素產生所有解決方法，接著處理下一個，直到Tq1為空；再按照此方法遞歸處理Tq2、Tq3。由于所有的標記需要指向能夠匹配當前元素最前面的片段，并且每一個數據流只有一個標記，效率比較低。當數據集和輸入查詢長度增加時這種方法的性能急劇下降。對此，文獻又提出了一種改進算法PathMPMJ，算法描述如下：

algorithm PathMPMJ(q)

while(eof(Tq)∧(isRoot(q)∨nextL(q)

for(qi∈subtreeNodes(q)) //advance descendants

while(nextL(qi) < nextL(parent(qi)))

advance(Tqi)

pushMark(Tqi)

if(isLeaf(q)) //solution in the streams’ heads outputSolution()

else PathMPMJ(child(q))

advance(Tq)

for(qi∈subtreeNodes(q)) //backtrack descendants

popMark(Tqi)

PathMPMJ算法利用一系列標記表示，每一個查詢點在數據流中不再是單個標記。若查詢中有k個祖先，那么就有k個標記，數據流中每個標記都指向前一個位置。該算法能夠準確地返回滿足查詢的所有答案，但該算法需要重復讀取和返回大量不必要的數據。

2）PathStack 文獻[13]提出了一種基于棧的二元關系連接算法PathStack。該算法的主要思想是：對于一個路徑模式查詢q，在順序掃描所有查詢節點的流T1，T2，…，Tn的過程中，重復構造它的局部或整體匹配結果的棧鏈。算法描述如下：

algorithm PathStack(q)

while end(q)

qmin=getMinSource(q)

// return qi∈subtreeNodes(q):isLeaf(qi)eof(Tqi)

for qi in subtreeNodes(q) //clean stacks

while(empty(Sqi)∧topR(Sqi)

pop(Sqi)

moveStreamToStack(Tq min， Sq min，pointer to top(Sparent(q min))

if (isLeaf(qmin))

showSolutions(Sq min，1)

pop(Sq min)

procedure moveStreamToStack(Sq，p)

push(Sq，(next(Tq)，p))

advance(Tq)

procedure showSolutions(SN，)

index[SN]=SP

if (SN==1)//we are in the root ，output solutions from the stacks

output(S[n].index[n]，…，S[1].index[1])

else //recursive call

for i=1 to S[SN].index[SN].pointer.to.parent

showSolutions(SN-1，i)

在算法PathStack中，假設所有數據節點來自同一個XML文檔，將它擴展到對多文檔的支持是非常容易的，只需要在對每個流Ti和棧Si中的數據節點操縱之前，增加對它們的doc-ID是否相等的判斷。

該算法查詢路徑模式節點時，從查詢根節點到葉子節點進行匹配，能有效處理查詢路徑中僅包含“//”的邊。在最壞情況下，該算法的I/O和CPU時間復雜度與輸入大小和最后匹配結果大小的總和呈線性相關；空間復雜度(即棧鏈的大小)是輸入列表大小總和與XML文檔樹高度兩者中的最小值。其優點是每個輸入的列表僅僅需要被分別掃描一次，并且算法I/O和CPU時間復雜度與多步路徑模式查詢的所有二元結構連接的中間匹配結果的大小無關。

該twig pattern查詢的方法是把twig分解為多個從根到葉子路徑模式，再利用PathStack算法確定每條獨立路徑的局部匹配結果；接著歸并連接這些局部匹配結果，得到twig pattern查詢的最終匹配結果。這種處理的方法會產生大量不是最終結果的中間結果，并且計算結果可能是錯誤的。

3)TwigStack 為從整體上解決twig pattern查詢，文獻[14]首次提到holistic twig結構連接算法——TwigStack。其描述如下：

algorithm TwigStack(q)

//phase 1

while end(q)

qact=getNext(q)

if (is Root(qact))

cleanStack(parent(qact)，nextL(qact))

if (isRoot(qact)∨empty(Sparent(qact)))

cleanStack(qact， next(qact))

moveStreamToStack(Tqact， Sqact，pointer to top(Sparent(qact))))

if (isLeaf(qact))

showSolutionsWithBlocking(Sqact，1)

pop(Sqact)

else advance(Tqact)

//phase 2

mergeAllpathSolutions()

Function getNext(q)

if (isLeaf(q)) return q

for qi in children(q)

ni=getNext(qi)

if (ni ≠ qi) return ni

nmin=min argni nextL(Tni)

nmax=max argni nextL(Tni)

while(nextR(Tq)

advance(Tq)

if(nextL(Tq)

else return nmin

procedure cleanStack(S，actL)

while(empty(S)∧(topR(S)<(actL)))

pop(S)

TwigStack算法分為兩個階段：a)Twig pattern查詢中的一些(但不是全部)從根到葉子的單個路徑查詢的局部匹配結果被計算；b)這些單個路徑查詢的局部匹配結果被歸并成twig pattern的最終匹配結果。在階段a)中，數據流中某個節點進棧之前，TwigStack先確保該節點的后代節點在它們的數據流中，并遞歸滿足該節點的每一個后代節點。因此，當twig pattern查詢僅僅存在“//”時，每一個單獨的從根到葉子路徑查詢的局部匹配結果確保都能與其他從根到葉子路徑查詢結果中至少一個歸并連接。沒有一個局部匹配結果是大于twig pattern查詢最終匹配結果的，這樣避免了大量不構成最終結果的中間結果。

在最壞情況下，對于僅僅包含“//”邊的twig pattern查詢，TwigStack算法的I/O和CPU時間復雜度與輸入大小和最后匹配結果大小的總和呈線性相關，與從根到葉子路徑查詢的局部匹配結果的大小無關；空間復雜度（即棧鏈的大小）是輸入列表大小總和與XML文檔樹高度的n倍兩者中的最小值。

當twig pattern查詢中存在“/”時，TwigStack算法不能確保I/O和 CPU是最優的。特別地，對于一條從根到葉子的路徑查詢，算法可能產生一個局部匹配結果，它不能夠與其他任何從根到葉子路徑查詢的局部匹配結果進行歸并連接。

4)TJFast 文獻[15]介紹了一種新的區間編碼模式extended Dewey，并提出了基于該編碼模式處理twig pattern的holistic twig連接算法TJFast。TJFast算法的操作步驟分為兩階段：a)計算從根到葉子路徑模式的局部匹配結果；b)歸并連接局部匹配結果得到twig pattern查詢的最終匹配結果。算法描述如下：

algorithm TJFast

for each f∈leafNodes(root)

locateMatchedLabel(f)/*Assume that the path from the root to element get(Tf) is n1/n2/…/nk and pf denotes the path pattern from the root to leaf node f */

endfor

while(end(root)) do

//return f∈leafNodes(root)→eof(Tf)

fact=getNext(topBranchingNode)/*accomplish two tasks: the first is to identify the next stream to process; and the second is to update the sets Sb associated with branching nodes b */

outputSolutions(fact) /*output path solutions of current(Tf act) to pattern pf such that in each solution s，e∈ s: element e matches a branching node b →e∈Sb*/

advance(Tfact)

locateMatchedLabel(fact)

end while

mergeAllPathSolutions()

對于每一個訪問元素，TJFast算法首先使用FST(finite state transducer)沿著從根到該元素的路徑把它們的標簽轉換為元素名稱，再實現字符串匹配。如果從根到該元素的路徑匹配要求的路徑模式，則直接輸出匹配結果。通過掃描一次輸入列表可以有效地處理路徑模式并能保證每個輸出結果都是人們需要的最終結果。對于每個根葉子路徑輸出結果時，其他路徑節點也被考慮，這樣能有效地控制中間結果的大小。該算法僅需要訪問查詢節點葉子節點標簽，能有效處理帶有通配符“*”和分支節點存在“//”的查詢。其缺點與TwigStack算法一樣，不能有效處理帶有分支節點存在“/”的查詢。

1. 2 采用索引技術的處理方法

1）TSGeneric+ 文獻[16]提出了TSGeneric+算法，它是在TSGeneric算法的基礎上利用各種索引來盡可能多地跳過不參與連接的節點。算法描述如下：

algorithm TSGeneric(root，C1，…，Cn)

while (end(root))

//end(q) is return qi∈subtreeNodes(q): isLeaf(qi)eof(Ci)

q=getNext(root)

if (isRoot (q))

cleanStack(Sparent(q)，Cq)

// pop all nodes from Sq that are not ancestors of Cq

if (isRoot(q) ∨ (empty(Sparent(q))))

cleanStack(Sq， Cq)

if (isLeaf(q))

push(Sq， Cq， Sparent(q))

//push the pair(Cq， Sparent(q)) onto stack Sq

else outputPathSolutionsWithBlocking(Cq)

Cq→advance()

mergeAllpathsolutions()

TSGeneric算法與TwigStack算法類似，其核心是調用getNext函數來選擇下一個處理的查詢節點。GetNext函數首先通過自遞歸調用向下遍歷到查詢的最左邊的孩子節點，然后從葉子節點開始，試圖在子查詢中找到一個盡可能高的且有一個解擴展的查詢節點。為了使用索引技術來定位流指針，對算法TSGeneric中的getNext函數進行改造，得到選擇下一個待處理查詢節點的函數為getNextCursor，通過該函數能夠在結構連接過程中利用索引技術跳過一些不參與連接的數據節點。但是跳過的數據節點的潛能并沒有被充分挖掘。對getNextCursor函數進行改進得到getNextExt函數，該函數先判斷查詢節點的棧是否為空。如果為空試著尋找查詢節點的解擴展；如果不為空接著查詢節點的孩子節點遞歸調用函數。將算法TSGeneric中的函數getNext改為函數getNextExt，則稱TSGeneric算法為TSGeneric+算法。該方法跳過元素流，實現了線性處理twig pattern查詢，但在處理存在“/”的查詢時有大量的冗余中間結果。

2)iTwigJion 文獻[17]提出了iTwigJoin算法，該算法與TwigStack算法類似。為了避免中間的冗余結果，iTwigJoin算法反復從流管理系統從未處理的流中選取元素，試圖選擇一個可匹配的元素，直到所有主要元素都處理完畢；接著用這個元素更新與twig pattern中的每個查詢節點都相關聯的棧的內容。在更新過程中，部分匹配的路徑將作為中間結果被輸出。當與twig pattern葉子節點相對應的所有流都結束時，上述處理過程結束，最后將中間結果路徑的列表歸并產生最終結果。該方法利用結構索引技術能夠處理同時存在“//”和“/”的twig pattern查詢，并且沒有大量的中間結果；但是在處理含有“/”的情況時，不能確保最后的結果是正確的。該算法的CPU和I/O的時間復雜度為twig pattern查詢中的節點數目、所使用流的總數目以及輸入/輸出總和的乘積；空間復雜度為XML源文檔中最長路徑的長度與查詢中的節點數目的乘積。算法描述如下：

algorithm iTwigJoin

Prune-Streams(Q)

while end(root) do

/*return true if all streams associated with leaf nodes of Qq end， otherwise return 1 */

q=getNext(root)

Tmin=the stream with the smallest startPos among all streams of class q

pop out elements in Sq and Sparent(q) which are not ancestor of head(Tmin)

if isRoot(q)∨existParAnc(head(Tmin)， q) then

/*return true if Tmin has a parent or ancestor element in stack Sparent(q) depending on edge〈parent(q)， q〉*/

push head(Tmin) into stack Sq

if isLeaf(q) then

showSolutionWithBlocking(Sq)

end if

end if

advance(Tmin)

end while

mergeAllpathSolutions()

文獻[18]結合結構索引和區間編碼處理XML路徑查詢，該方法存儲列表中相同標記的所有元素，但沒有使用整體匹配技術。文獻[19]利用已有的索引技術提出一種新的算法提高處理XPath的查詢能力。文獻[20]提出了一種基于后綴樹的索引結構，將路徑轉換為字符串，可以高效地處理存在通配符“*”的路徑。文獻[21]提出的索引結構利用關系查詢處理器解決與分支有關的問題。這些方法主要是針對分支表達式的某一部分進行處理，不能有效處理一般的twig pattern查詢。文獻[22，23]提出了處理部分指定twig查詢的思想，該思想主要集中處理存在“//”的查詢，提高了返回結果的有效性。

2 Twig pattern查詢處理的關鍵問題

1)查詢任意節點問題 XML已成為一種網上數據交換和信息集成的工具，隨著XML應用的普及，對XML文檔查詢的要求也越來越高。如何高效地對多分支路徑進行查詢成為今后研究的重點。基于根到葉子路徑的查詢處理方法大部分只能返回葉子節點或根節點，而對于中間節點的查詢不是很方便，即不能很好地滿足用戶查詢任意節點的要求。如何查詢任意節點的信息成為研究的關鍵問題，并且當用戶提出的路徑查詢在待查詢的XML文檔中不存在正確的匹配時，需要能快速給出無查詢結果的判斷。

2)處理twig pattern中存在“//”“/”“*”“[]”等的問題 目前，基于整體連接的算法大部分都只能處理只包含“//”或者“/”的問題，對于同時存在“//”和“/”的twig pattern查詢效率不是很高。當元素名稱不清楚或不知道時，XPath通常用通配符“*”表示，已經存在的算法大部分不能有效地處理分支節點中含有通配符的查詢。因此，如何更有效地處理更多存在“//”“/”“*”“[]” 等的twig pattern查詢是目前研究的關鍵問題。

3)用戶使用問題 如何使用戶在構造XML查詢時無須了解待查XML文檔的結構。傳統的查詢語言多數是基于嚴格匹配概念定義的，即在查詢和數據的指定條件間進行精確匹配。用戶書寫的查詢表達式中的節點和標記的前后順序必須與數據庫中相應節點和標記對應，這對發出查詢請求的用戶要求很高，需要對數據庫結構、查詢模式有很清楚的了解，增加了用戶的難度。如何讓用戶方便地發出查詢請求成為現在研究的熱點問題。

3 Twig pattern查詢處理的研究內容

1)基于twig pattern查詢的索引結構 針對傳統twig pattern查詢處理方法和現有改進twig pattern查詢處理方法的脆弱之處，結合已經存在的XML文檔模型的研究，確定今后所采用的XML文檔樹模型和twig pattern，建立一種基于一般的twig pattern的索引結構，用它來管理索引XML文檔數據，解決任意節點信息查詢處理、存在“//”“/”“*”“[]”等的twig pattern查詢問題。

2)基于twig pattern查詢的索引結構的連接算法 在上述索引結構的基礎上，充分考慮twig pattern查詢的特點，利用已經存在的holistic twig連接思想，考慮與上述索引結構相對應的連接算法。該算法充分權衡時間和空間需求，縮短執行時間，減少中間冗余結果的輸出，提高twig pattern查詢處理效率。當用戶提出的路徑查詢在待查的XML文檔中不存在正確的匹配時，能夠快速給出答案或提示。

3)基于twig pattern查詢的匹配方法 在已經存在的嚴格匹配的基礎上考慮一種新的匹配方法——靈活匹配，并把這種匹配方法應用到查詢匹配中，增加發出查詢的用戶對數據庫模式的透明度，使用戶較容易地發出用XPath表示的復雜twig pattern查詢。這種查詢不用遵循固定的模式，并且在靈活匹配方式下可以最大限度地利用XML數據庫中的語義信息，完成傳統查詢機制無法處理的查詢，最大限度地給出結果，解決用戶發出查詢的便捷問題。

4)實驗測試 建立實驗平臺，在PC機上利用研究提出的索引結構和連接算法在相關的實驗數據集(如Shakespeare、DBLP、Xmark等)上進行模擬實驗，同時實現已有的相關索引結構和處理twig pattern查詢的方法，并進行性能比較分析。

4 結束語

索引技術和XML查詢處理是近年來關于XML數據研究的熱點，twig pattern查詢處理是XML查詢處理的關鍵問題。關于索引技術和twig pattern查詢處理的研究已經取得了一定的成績，并得到了研究人員和產業界的廣泛關注。本文論述了twig pattern查詢處理和索引技術的相關研究現狀，指出了現有twig pattern查詢處理方法中存在的不足。如何利用索引技術高效地處理twig pattern查詢、如何實現與靈活匹配思想相結合方便用戶查詢等都是以后需要進一步研究的問題。

參考文獻：

[1]DEUTSCH A， FERNANDEZ M， FLORESCU D. A query language for XML[C]//Proc of the 8th International World Wide Web Confe-rence. Toronto: ACM Press， 1999: 1155-1169.

[2]ABITEBOUL S， QUASS D， MCHUGH J. The Lorel query language for semistructured data[J]. International Journal on Digital Libra-ries， 1997，1(1):68-88.

[3]CHAMBERLIN D， ROBIE J， FLORESCU D. Quilt: an XML query language for heterogeneous data sources[C]//Proc of the 3rd Interna-tional Workshop on World Web and Oatatbases. London: Springer-Verlag，2000:1-25.

[4]BERGLUND A， BOAG S， CHAMBERLIN D， et al. XML path language (XPath) 2.0[DB/OL]. (2005-02-11).http://www.w3.org/TR/2005/WD-xpath20-20050211/.

[5]BOAG S， CHAMBERLIN D， FLORESCU D， et al. XQuery 1.0: an XML query language[DB/OL]. (2005-02-11). http://www.w3.org/TR/2005/WD-xquery-20050211/.

[6]GOLDMAN R， WIDOM J. DataGuides: enabling query formulation and optimization in semistructured databases[C]//Proc of the 23rd International Conference on Very Large DataBases. San Francisco: Morgan Kaufmann Publishers， 1997:436-445.

[7]COOPER B， SAMPLE N， FRANKLIN M. A fast index for semistructured data[C]//Proc of the 27th International Conference on Very Large DataBases. San Francisco: Morgan Kaufmann Publishers，2001:341-350.

[8]BARBOSA D， BARTA A， MENDELZON A， et al. ToX: the Toronto XML engine[C]//Proc of the Workshop on Information Integration on the Web. 2001:66-73.

[9]LI Q， MOON B. Indexing and querying XML data for regular path expressions[C]//Proc of the27th International Conference on Very Large DataBases. San Francisco: Morgan Kaufmann Publishers， 2001:361-370.

[10]CHEN Qun， LIM A， ONG K W. D(k)-index:an adaptive structural summary for graph structured data[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 2003:134-144.

[11]WANG Hai-xun， PARK S， FAN Wei， et al. VIST: a dynamic index method for querying XML data by tree structures[C]//Proc of ACM ACM SIGMOD International Conference on Management of Data. New York: ACM Press，2003:110-121.

[12]ZHANG C， NAUGHTON J， DEWITT D. On supporting containment queries in relational database management systems[C]//Proc ofACM SIGMOD International Conference on Management of Data. New York: ACM Press，2001:425-436.

[13]ALKHALIFA S， JAGADISH H， KOUDAS N， et al. Structural joins: a primitive for efficient XML query pattern matching[C]//Proc of the 18th International Conference on Data Engineering. Washington DC: IEEE Computer Society， 2002:141.

[14]BRUNO N， SRIVASTAVA D， KOUDAS N. Holistic twig joins: optimal XML pattern matching[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 2002:310-321.

[15]LU Jia-heng， LING T W， CHAN C Y， et al. From region encoding to extended Dewey: on efficient processing of XML twig pattern matching[C]//Proc of the 31st International Conference on Very Large Data Bases. 2005:193-204.

[16]JIANG Hai-feng， WANG Wei， LU Hong-jun， et al. Holistic twig joins on indexed XML documents[C]//Proc of the 29th International Conference on Very Large Data Bases. 2003:273-284.

[17]CHEN Ting， LU Jia-heng， LING T W. On boosting holism in XML twig pattern matching using structural indexing techniques[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press，2005:455-466.

[18]KAUSHIK R， KRISHNAMURTHY R， NAUGHTON J， et al. On the integration of structure indexes and inverted lists[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 2004:779-790.

[19]MADRIA S， CHEN Y， PASSI K. Efficient processing of XPath queries using indexes[J]. Information Systems， 2007，32(1):131-159.

[20]LIANG Zuo-peng， HU Kong-fa， YE Ning， et al. An efficient index structure for XML based on generalized suffix tree[J]. Information System， 2007，32(1):283-294.

[21]CHEN Zhi-yuan， GEHRKE J， KORN F， et al. Index structures for matching XML twigs using relational query processors[J]. Data Knowledge Engineering， 2007，60(2):283-302.

[22]ZHOU Jun-feng. Efficient processing of partially specified twig queries[C]//Proc of ACM SIGMOD International Conference on Manegement of Data. New York: ACM Press， 2007.

[23]THEODORATOS D， WU Xiao-ying. Assigning semantics to partial tree-pattern queries[J]. Data Knowledge Engineering， 2008，64(1):242-265.