結構編碼與簇集索引相結合的ＸＭＬ混合索引

摘要：提出了一種結構編碼與簇集索引相結合的XML混合索引結構(HiSC)。引入簇集索引結構，將XML節(jié)點分類，盡量多地保存XML數據的結構信息，縮小查詢范圍，提高了查詢效率并能支持關鍵字的查詢。實驗表明此索引結構可以高效并準確地查詢XML數據中的結構信息。

關鍵詞：可擴展標記語言； 索引結構； 簇集索引結構； 結構編碼； 關鍵字查詢

中圖分類號：TP311;132.4 文獻標志碼：A

文章編號：1001-3695(2008)05-1415-04

XML標準被廣泛運用于Web數據交換[1]，現有的查詢語言如Xpath[2]、Xquery[3]都是通過路徑表達式對XML文檔進行查詢。專家和學者針對提高路徑表達式的查詢效率進行了大量研究，并提出了多種XML索引結構，這些索引結構各有優(yōu)點和適用范圍。Dataguide[4]僅適用于簡單的自根而下的路徑表達式，對于復雜的表達式則無法解決。文獻[5]提出兩種相似的結構連接算法Tree－Merge與Stack－Tree；XISS[6]用元素、屬性作為查詢的基本單元，將復雜路徑分解為簡單路徑，然后對各簡單路徑的處理結果進行連接。文獻[7~9]運用了區(qū)間編碼，通過區(qū)間編碼可以有效地找到與某個節(jié)點相關的節(jié)點區(qū)間碼，并運用B+樹來優(yōu)化索引結構。盡管對索引的結構和查詢算法進行了優(yōu)化，但只能減少查詢中結構連接的次數，不能避免復雜的結構連接運算。DBXI[10]利用DTD的結構信息對XML文檔及其遵循的DTD同時建立索引，結合了區(qū)間碼的思想，減少了XML文檔的遍歷。Apex[11]是一種基于工作流的索引結構，運用數據挖掘的方法將常用的查詢數據挖掘出來建立索引，當工作流改變時索引結構也會隨之更新；HOPI[12]基于2－Hop包含的有向圖在XML上建立面向連接的索引，提高了查詢的空間和時間效率，并能很好地支持XLink，但查詢算法過于復雜。結構編碼[13]不同于其他的索引結構，需要先將查詢拆分成若干子查詢，然后將子查詢的結果進行結構連接。結構編碼通過對XML數據和查詢同時編碼，將對XML的查詢轉變?yōu)閷Σ樵兙幋a序列的搜索，在一定程度上避免了復雜的結構連接。結構編碼還支持包含通配符路徑的查詢。應該說，將結構編碼用于XML文檔的查詢是一種新穎的索引方法，但還存在一些不足：a）沒有按節(jié)點屬性構建簇集索引，當查詢某節(jié)點是否存在時需要遍歷整個文檔。b)其索引結構忽略了XML文檔中的一些結構信息，查詢結果與XML文檔中相關部分不同。c)不支持對關鍵字的查詢。本文將在結構編碼的基礎上結合簇集索引提出一種新的索引結構來彌補結構編碼的不足。

1XML文檔結構及結構編碼

XML文檔是由嵌套的元素結構組成，XML數據通常被描述成樹結構，元素及其屬性由DTD定義。圖1（a）描述了一個交易文檔的結構；（b）表示的是一份由（a）定義的交易XML文檔樹結構。在圖1（b）中，V1~V8表示葉節(jié)點標志，即文檔中元素的屬性節(jié)點值和元素節(jié)點值，非葉節(jié)點的標志為元素的首字母。每個節(jié)點都加入了區(qū)間碼(begin， end)，用來標志XML文檔樹中節(jié)點的結構關系。節(jié)點間的祖先／后裔、雙親／孩子關系可以通過區(qū)間碼進行判斷。圖1（b）中，節(jié)點S(2，70)與節(jié)點I(8， 45)，(S.begin=2)<(I.begin=8)，(S.end=70)>(I.end=45)，由此可以判斷出節(jié)點I為S的后裔節(jié)點。 XML文檔中的每個節(jié)點與區(qū)間碼是一一對應的，可以引入傳統(tǒng)關系數據庫成熟的技術如B+樹。

根據結構編碼的定義[13]：XML樹中每個節(jié)點被標志為（節(jié)點標志，前綴），每個節(jié)點被標志為一個字符，節(jié)點的前綴就由根節(jié)點到達此節(jié)點所經過節(jié)點的標志所組成的字符串。如例中，根節(jié)點P標志為(P，ε)，節(jié)點S被標志為(S，P)，值為V1的節(jié)點被標志為(V1，PSN)。

〈！ELEMENTpurchase(seller， buyer)〉

〈！ATTRISTsellerID IDLocation CDATA name CDATA〉

〈！ELEMENTseller(Item)〉

〈！ATTRISTbuyerID IDLocation CDATA name CDATA〉

〈！ELEMENTitem(Item)〉

〈！ATTRISTitemmanufacture CDATA name CDATA〉

(a) 交易文檔的DTD

(b) 一份交易XML文檔的樹結構圖1XML交易文檔結構

2索引基本結構

在XML文檔上建立索引的目的是能夠從大量的XML信息中高效而準確地抽取出滿足查詢條件的結果。圖2所示XML查詢過程其實質是XML文檔經過一定的方式處理后形成XML的索引。查詢時，由輸入查詢的路徑信息運用查詢算法從索引中找到滿足查詢條件的結果，查詢結果實際上是XML文檔中滿足查詢條件的部分。文獻[13]中的索引沒有將節(jié)點分類，查詢結果恢復后的信息與文檔中的部分會有出入。例如查詢到節(jié)點(13，14)結構編碼為(N，PSII)，不能判斷節(jié)點N是屬性還是元素節(jié)點，這是因為構建索引時忽略了文檔中節(jié)點的結構信息。

本文提出的索引結構是在結構編碼的基礎上混合簇集索引（HiSC），其基本思想是將XML中節(jié)點根據類型分類并按標志存儲，在查詢時根據節(jié)點的屬性迅速定位節(jié)點，縮小查詢范圍，減少查詢開銷。將XML文檔按下列規(guī)則組織索引：

規(guī)則1對每個節(jié)點進行結構編碼。

規(guī)則2為節(jié)點加上區(qū)間碼。

規(guī)則3將節(jié)點的結構編碼的前綴(Qpre)及區(qū)間編碼等信息存儲在包(packet)中。節(jié)點的區(qū)間碼被寫入包頭。

規(guī)則4XML樹中標志相同的元素節(jié)點存儲在相同的塊(block)中，結構編碼的標志寫入塊段頭。根據節(jié)點的區(qū)間碼，將包依次存入對應的塊中。

規(guī)則5帶(tape)TI用來存放非葉節(jié)點標志。元素節(jié)點和屬性節(jié)點的標志分別存入TI上的元素節(jié)點區(qū)(area)和屬性節(jié)點區(qū)。每個標志指向相對應的塊。

規(guī)則6用一條帶（tape）TV存儲XML屬性值、元素值、結構編碼前綴和尾部標志(end－id)。元素值末尾標志為(如V2)，屬性值末尾標志為@(如 V1)。節(jié)點的值與區(qū)間碼對應，并按區(qū)間碼的順序依次存儲在帶中。

以上的規(guī)則中，包、塊、區(qū)帶都是邏輯上的單元，它們可以按塊（注：這里的塊指硬盤上的基本存儲單元）存取在磁盤上。圖1例子的索引結構如圖3所示。

圖3中，XML中的非葉節(jié)點被分為元素節(jié)點和屬性節(jié)點，其標志都分別存入TI中對應的區(qū)域（元素節(jié)點被寫入無陰影的區(qū)域，屬性節(jié)點被寫入有陰影的區(qū)域）。TI、TV中包含“…”部分為空白區(qū)域，便于XML文檔存放新的節(jié)點。TV存放葉節(jié)點。元素值和屬性值用末尾標志符和@來區(qū)分。標志(ID)為P、S、N、B、I、L、M被打包并分別存放在對應的塊中，每個塊中包含若干個包，如標志為N的塊中包的個數為4，區(qū)間碼分別為(3，6)、(13，20)、(52，60)、(81，85)，結構編碼的前綴分別為PS、PSII、PSI、PB。

3查詢算法

本章介紹具體的查詢算法。對XML文檔的結構查詢分為：a）簡單路徑查詢， 即查詢路徑中不存在支路，如P/S/N。b）復雜路徑查詢，即查詢的路徑中帶有支路，如查詢節(jié)點P/S/I/M，且節(jié)點I的子節(jié)點N的屬性值為V3，即I匹配P/S/I/N/V3。c）帶通配符（*和//）的查詢。“*”可以替代任一節(jié)點，如查詢路徑P/*/N ，其結果就是路徑P/S/N和P/B/N；“//”則可以替代多個節(jié)點。

3．1簡單路徑查詢算法

簡單路徑查詢算法是其他查詢算法的基礎。先對查詢節(jié)點結構編碼，算法的輸入為目標節(jié)點的結構編碼序列Q=(qn，q1，q2，…，qn-1)，輸出結果集θ1=(begin，end，end－id)。其中：(begin，end)為區(qū)間碼；end－id為尾部標志，用來標志節(jié)點的類型。

算法1判斷目標節(jié)點類型。若目標節(jié)點為葉節(jié)點則掃描TV，為非葉節(jié)點則掃描TI中的屬性節(jié)點區(qū)或元素節(jié)點區(qū)。通常目標節(jié)點的前向遍歷值較大所以應從后向前掃描TI中對應的區(qū)域。根據目標節(jié)點標志，迅速查詢到儲存目標節(jié)點的塊中去匹配結構編碼序列。如要查詢的是P/S/I/M，首先掃描TI中的元素節(jié)點區(qū)，發(fā)現存在標志為M元素節(jié)點；然后到標志為M的塊中匹配Qpre=PSI；最后返回包含M的區(qū)間碼(9，13)的結果集。若目標節(jié)點V為葉節(jié)點，算法1在TV中匹配V的節(jié)點值Value及Qpre。如輸入為(V3，PSIIN)，在TV中查詢節(jié)點值為V3，Qpre=PSIIN 的節(jié)點。

3．2復雜路徑以及通配符路徑查詢算法

復雜路徑查詢實際上是將復雜路徑拆分成若干簡單路徑，再分別查詢拆分后的簡單路徑，最后運用區(qū)間碼將所有查詢結果進行結構連接，得到滿足條件的目標節(jié)點。區(qū)間碼被用來優(yōu)化結構連接（詳細算法見文獻[13]）。

含有通配符的路徑表達式根據通配符的位置可分為以通配符結尾的表達式（如P/S/N/*）和以其他節(jié)點結尾的表達式（如 P/S//I）。為方便描述，將前者定義為Ⅰ型，后者為Ⅱ型。

對算法1稍作改動便可用于Ⅱ型表達式的查詢，具體辦法是：當算法1執(zhí)行步驟（4）（8）（13）時，Ⅱ型表達式是把“*”作為任意一個標志（“/”作為任意若干個標志）進行匹配；對于Ⅰ型的算法如算法2所示，輸入Q=(q1，q2，…，qn，*)=Q1*，返回結果集合θ2。算法2中(1)(2)是運用簡單路徑查詢算法查詢qn；(4)~(8)將所用qn的子節(jié)點找出來，然后匹配子節(jié)點的結構編碼后綴(Qpre)，將滿足條件的節(jié)點區(qū)間碼和尾部標志加入θ2。對于查詢含有通配符“/”的Ⅰ型表達式，(6)將“/”代表若干個節(jié)點匹配Qpre。

算法2帶通配符“*”的Ⅰ型表達式查詢算法

算法2用來查詢帶通配符的簡單路徑，對于帶有通配符的復雜路徑采用類似一般的復雜路徑的查詢辦法，將其拆分為多個簡單路徑分別查詢，最后進行結構連接。

3．3關鍵字查詢

在XML文檔中，關鍵字查詢主要是針對XML文檔中的元素節(jié)點、元素的屬性、元素值進行查詢。在文獻[14]中，提出smallest lowest common ancestor(SLCA) semantics，即關鍵字查詢的結果集中節(jié)點應滿足以下兩個條件：a)它們的標志或它們的后代標志中包含關鍵字；b）它們的后代節(jié)點中不包含關鍵字。依照SLCA對關鍵字的搜索應該是一種至下而上的，搜索到的結果應該是XML樹中包含關鍵字節(jié)點中較底層的節(jié)點。本文提出的索引結構采用如下的算法進行關鍵字查詢：對輸入的關鍵字，先掃描TV，因為人們感興趣的關鍵字信息往往存在于元素的屬性和元素的值中；TV中的葉節(jié)點通常處于樹結構的底層，并且沒有后裔節(jié)點，不用考慮其后裔是否含有關鍵字的問題。返回滿足條件的結果集C1；C1為五元組集合(begin，end，value，end－id，Qpre )，value為節(jié)點值（若無節(jié)點值則為空）；然后掃描T1的節(jié)點區(qū)，返回滿足條件的結果集C2；接著對C1、C2通過區(qū)間碼進行連接，找到可能存在的祖先/后裔、雙親/孩子關系，并從C1中刪除祖先或雙親元素；刪除后的C1與C2的并集C為查詢的目標節(jié)點集。若C1為空，則關鍵字包含于非葉節(jié)點中，查詢結果是包含關鍵字的元素為節(jié)點的XML樹結構。

4實驗結果

筆者對文獻[13]中的算法(ViST)和HiSC索引進行了性能測試和比較，測試代碼用Delphi 7編寫。實驗平臺是Pen-tium Ⅳ PC主頻2．4 GHz CPU，內存256 MB，80 GB硬盤，操作系統(tǒng)為Windows 2000 professional。采用了The XML benchmark database XMARK[8]生成大型XML文檔，大小為68．2 MB。

為全面地測試索引的查詢能力，對XML查詢進行分類后將測試表1中的查詢路徑。其中：Q1為簡單的路徑查詢；Q2是包含元素值的簡單查詢；Q3和Q7分別包含了通配符“*”和“/”的查詢；Q4是包含屬性值的復雜查詢，其路徑是分叉的；Q5和Q8在Q4的路徑中分別包含了通配符“*”和“/”；Q6為關鍵字查詢，因ViST不支持關鍵字查詢，只對HiSC進行測試。對以上查詢測試后，將XML文檔減小，節(jié)點總數減為70 529個，然后重復查詢測試，觀察算法在不同大小XML文檔中的表現。

由表2分析測試的結果如圖4所示。從圖4可知HiSC比ViST在查詢效率上普遍好得多，特別是包含了元素值的查詢(Q2)。正如前文所指出ViST中，其元素值和屬性值都被映射成為編碼，查詢時都不可避免地先查詢它們的編碼，并且ViST的索引結構中并沒有將元素值和屬性值區(qū)分開。當查詢帶有葉節(jié)點的路徑時，算法要遍歷所有葉節(jié)點的編碼；而HiSC將葉節(jié)點分類，分別進行查詢，這樣在相同條件下ViST需要查詢的范圍比HiSC要大些。HiSC采用簇集索引的形式存放數據，查詢時可以跳過一些不符合條件的值，減少了算法的開銷。觀察查詢結果集可以發(fā)現，從ViST查詢結果不能判斷出目標節(jié)點是元素節(jié)點還是屬性節(jié)點，因為ViST沒有完整地保留XML文檔中的結果信息。對于那些具有復雜DTD的文檔，或是對于不熟悉DTD文檔的人來說，很難完整地根據查詢結果恢復出XML文檔中滿足查詢要求的部分。

在圖75中，橫軸是按查詢所需時間遞增排列，虛線和實線分別表示XML文檔減少前后的測試結果。由圖分析：對于相同路徑的查詢， XML文檔的大小對兩種索引結構的影響基本相同，即查詢的效率會因文檔變大而下降。特別是關鍵字的查詢（Q6），其查詢效率很大程度上取決于XML文檔的大小。

當操作者因為不熟悉文檔而輸入無效節(jié)點（不存在于XML文檔）時，因為HiSC采取簇集索引結構，能迅速返回無此節(jié)點；而ViST須遍歷所有節(jié)點之后才能返回結果，顯然在查詢錯誤路徑時，HiSC無疑更優(yōu)異。本文提出的索引結構缺點是對于海量XML文檔，其關鍵字查詢的效率仍然很低，需要進一步改進以提升其效率；索引結構較ViST復雜，從XML文檔生成索引結構需要更多的時間，但卻能提高查詢效率，提供更多結構信息。

5結束語

本文介紹了一種混合索引結構。在文獻[13]的基礎上混合了簇集索引結構，優(yōu)化了查詢算法，提高了查詢效率。與文獻[13]相比，本文的貢獻和進步如下：采用簇集索引結構存儲結構編碼，可以迅速判斷出目標節(jié)點的有效性（即是否存在于XML文檔中），而無須遍歷所有節(jié)點;將XML文檔中的節(jié)點進行分類，查詢結果包含更多的節(jié)點結構信息，縮小了查詢范圍，提高了查詢效率;支持關鍵字查詢。其不足之處是結構比較復雜，由XML文檔生成索引結構開銷較大;索引結構復雜，不利于文檔的更新;關鍵字查詢受文檔大小的影響較大。這些不足之處還需通過進一步研究來彌補。

參考文獻：

[1]BRAY T， PAOLI J， SPERBERG－McQUEEN C M， et al. Extensible markup language 1．0(2nd ed)[EB/OL].(2005-05－10).http://www.W3c.org/TR/REC －xml/.

[2]CLARK J，DeROSE S.XML path language(XPath) version 1．0[EB/OL].[2005-05－10].http://www.w3.org/TR/2005/WD－xpath20-20050404.

[3]CHAMBERLIN D， FLORESCU D， ROBIE J. XQuery: a query language for XML W3C working draft[EB/OL].[2005-05－10].http://www.w3.org/TR/2005/WD－xquery－ 20050404.

[4]GOLDMAN R， WIDOM J. Dataguides: enabling query formulation and optimization in semistructured databases[C]//Proc of the 23rd Int’l Conference on Very Large Data Bases(VLDB). Athens: Morgan Kaufmann， 1997:436-445.

[5]SRIVASTAVA D， Al－KHALIFA S， JAGADISH H， et al. Structural joins: a primitive for efficient XML query pattern matching[C]//Proc of ICDE. 2002:141－152.

[6]HARDING P J， LI Q Z， MOON B. XISS/R:XML indexing and storage system using RDBMS[C]//Proc of the 29th Int’l Conference on Very Large Data Bases (VLDB). Berlin: Morgan Kaufmann Publishers， 2003:1073－1076.

[7]IANG H F， LU H J， WANG W. XR－Tree: Indexing XML data for efficient structural joins[C]//Proc of the 19th Int’l Conf. on Data Engineering(ICDE). Bangalore: IEEE Computer Society， 2003:253-264.

[8]XMARK: The XML－benchmark project[EB/OL].(2002)[2005-05－10].http:// monetdb.ewi.nl/xml.

[9]王靜，孟小峰，王珊.基于區(qū)域劃分的XML結構連接[J].軟件學報，2004，15(5):720-729.

[10]王靜，孟小峰，王宇，等. 以目標節(jié)點為導向XML路徑查詢處理[J]. 軟件學報，2005，16(5):827-837.

[11]CHUNG C， MIN J， SHIM K. APEX:an adaptive path index for XML data[C]//Proc of SIGMOD. Madison:[s.n.]， 2002:121－132.

[12]SCHENKEL R， THEOBALD A， WEIKUM G. HOPI: an efficient connection index for complex XML document collections[C]//Proc of EDBT， LNCS 2992. 2004:237-255.

[13]WANG H X， PARK S， FAN W. ViST: a dynamic index method for querying XML data by tree structure[C]//Proc of ACM SIGMOD Int’l Conference on Management of Data (SIGMOD). San Diego: ACM Press， 2003:110－121.

[14]XU Y， PAPAKONSTANTINOU Y. Efficient keyword search for smallest LCAs in XML databases[C]//Proc of ACM SIGMOD Int’l Conference on Management of Data (SIGMOD). Baltimore: ACM Press， 2005.

[15]萬常選，劉云生，陳升華，等.基于區(qū)間編碼的XML索引結構的有效結構連接[J].計算機學報，2005，28(1): 113－127.

[16]WANG W， WANG H Z， LU H J， et al. Efficient processing of XML path queries using the disk－based FB index[C]//Proc of the 31st Int’l Conference on Very Large Data Bases(VLDB). Trondheim: ACM Press， 2005:145－156.

[17]路燕，張亮，施伯樂，等. 一種基于DTD的XML索引方法[J]. 計算機研究與發(fā)展，2005，42(1): 30-37.

[18]孔令波，唐世渭，楊冬青，等. XML數據索引技術[J].軟件學報，2005，16(12):2063-2079.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”