基于Schema的XML混合編碼索引查詢技術(shù)

夏　剛　劉林靜　樓文高,2

1(上海理工大學(xué)光電信息與計(jì)算機(jī)學(xué)院　上海 200093)

2(上海商學(xué)院　上海 200235)

?

基于Schema的XML混合編碼索引查詢技術(shù)

夏剛1劉林靜1樓文高1,2

1(上海理工大學(xué)光電信息與計(jì)算機(jī)學(xué)院上海 200093)

2(上海商學(xué)院上海 200235)

摘要Web中存在著越來(lái)越多的XML的文檔，如何高效地從XML文檔查詢出有效信息已經(jīng)成為當(dāng)前在半結(jié)構(gòu)化數(shù)據(jù)研究領(lǐng)域中的熱點(diǎn)問(wèn)題。針對(duì)XML文檔節(jié)點(diǎn)進(jìn)行編碼和建立索引結(jié)構(gòu)可以有效地提高查詢速度，提出一種SBXHCI(Schema-Based XML Hybrid Coding Indexing)查詢技術(shù)，該方法充分利用Schema信息對(duì)XML文檔進(jìn)行編碼和構(gòu)建索引。對(duì)創(chuàng)建索引所花費(fèi)的時(shí)間和空間，查詢響應(yīng)的時(shí)間進(jìn)行大量的實(shí)驗(yàn)分析，結(jié)果表明SBXHCI方法的編碼機(jī)制降低了索引結(jié)構(gòu)在時(shí)間和空間的資源消耗，并且在路徑查詢的響應(yīng)速度有著顯著的提高。

關(guān)鍵詞SchemaXML路徑表達(dá)式混合編碼索引

QUERY TECHNOLOGY FOR SCHEMA-BASED XML HYBRID CODING INDEX

Xia Gang1Liu Linjing1Lou Wen’gao1,2

1

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)2(Shanghai Business School,Shanghai 200235,China)

AbstractThere are more and more XML documents in Web, how to efficiently query the effective information from XML document has become the hot issue in the field of semi-structured data research at present. Aiming at that coding for XML document nodes and the establishment of index structure can improve the query speed effectively, this paper proposes an SBXHCI (schema-based XML hybrid coding index) query technology, it makes full use of Schema information to encode the XML documents and to build index. Then we carry out a great deal of experimental analysis on the index creation time, space and query response time. Results show that the encoding mechanism of SBXHCI method reduces the resource consumption of the index structure in time and space, and the response speed of path query has improved significantly.

KeywordsSchemaXMLPath expressionHybridcodingIndex

0引言

隨著互聯(lián)網(wǎng)的迅速發(fā)展，可擴(kuò)展標(biāo)記語(yǔ)言XML由于其良好的數(shù)據(jù)格式、豐富的數(shù)據(jù)表示能力及驗(yàn)證機(jī)制，已經(jīng)成為Web中數(shù)據(jù)表示和交換的標(biāo)準(zhǔn)。XML在Web中廣泛應(yīng)用使得XML文檔的結(jié)構(gòu)變得越來(lái)越復(fù)雜和數(shù)據(jù)量越來(lái)越大，導(dǎo)航式的遍歷顯然已經(jīng)不能滿足查詢所需的要求，對(duì)XML文檔節(jié)點(diǎn)編碼并建立索引可以快速有效地定位出需要訪問(wèn)的節(jié)點(diǎn)[1]，提高XML數(shù)據(jù)訪問(wèn)的查詢效率。因此對(duì)XML數(shù)據(jù)建立索引是一個(gè)必要的手段，也成為了當(dāng)前XML查詢中研究的熱點(diǎn)問(wèn)題。

對(duì)XML文檔建立索引，就是將具有相同標(biāo)簽的XML節(jié)點(diǎn)劃分在同屬一個(gè)索引節(jié)點(diǎn)類中[2]。目前，國(guó)內(nèi)外對(duì)XML建立索引技術(shù)的研究取得了豐富的研究成果。例如，最早提出對(duì)XML文檔建立索引的思想來(lái)源于文獻(xiàn)[3]提出的基于結(jié)構(gòu)概要的DataGuide索引方法，它的本質(zhì)是一個(gè)確定自動(dòng)機(jī)，能夠根據(jù)絕對(duì)路徑很好地給出響應(yīng)查詢，但卻不能提供相對(duì)路徑的查詢。文獻(xiàn)[4]提出帶有分支路徑查詢的F&B索引，它可以快速地查詢出帶有分支路徑的查詢，但是F&B在構(gòu)建索引時(shí)消耗的內(nèi)存資源過(guò)大。文獻(xiàn)[5,6]提出的基于元素、屬性和結(jié)構(gòu)的XISS索引，它將一個(gè)復(fù)雜的路徑表達(dá)式分解成若干個(gè)簡(jiǎn)單路徑，通過(guò)對(duì)XISS索引的訪問(wèn)來(lái)處理每個(gè)簡(jiǎn)單路徑的查詢處理得到滿足結(jié)構(gòu)關(guān)系的中間結(jié)果，最后對(duì)這些中間結(jié)果依次進(jìn)行結(jié)構(gòu)連接得到查詢的最終的結(jié)果。但該方法對(duì)具有N個(gè)元素或者屬性組成的路徑查詢表達(dá)式，XISS索引需要從XML文檔中訪問(wèn)N組節(jié)點(diǎn)，并且至少需要N-1次結(jié)果的結(jié)構(gòu)連接，因此會(huì)增加結(jié)構(gòu)連接運(yùn)算的時(shí)間。文獻(xiàn)[7-9]都是基于DTD的XML索引方法DBXI，該方法能夠很好地將DTD的結(jié)構(gòu)信息保存到XML文檔中元素和屬性中，并且能夠快速地訪問(wèn)到結(jié)果集。但該方法對(duì)XML文檔使用區(qū)間編碼的方法，這種編碼對(duì)于分解后的簡(jiǎn)單路徑查詢存在著很多不相關(guān)的結(jié)果和結(jié)構(gòu)連接運(yùn)算相對(duì)復(fù)雜，并且對(duì)于DTD自身也存在著很多的缺陷性。文獻(xiàn)[10,11]提出了基于Schema的SBXI索引方法，但這些方法中對(duì)XML文檔也是使用區(qū)間編碼的方法。

為了避免上述方法中存在的缺點(diǎn)，本文提出了一種基于XML Schema混合編碼的索引方法SBXHCI，其優(yōu)點(diǎn)在于：通過(guò)使用Schema，避免了DTD本身的多種缺陷；把Schema中的信息存入相應(yīng)的XML文檔中，可以快速地去除了不相關(guān)節(jié)點(diǎn)的訪問(wèn)，有效地減少結(jié)構(gòu)連接次數(shù)，并能確保所有待查詢節(jié)點(diǎn)都能被訪問(wèn)；根據(jù)前綴編碼和區(qū)間編碼各自的優(yōu)點(diǎn)，對(duì)XML文檔采用混合編碼建立索引結(jié)構(gòu)，這種編碼方法可以快速地查詢出待查詢的節(jié)點(diǎn)和加快了結(jié)構(gòu)連接的速度，從而提高查詢效率和準(zhǔn)確率。

1XML文檔和模式

1.1XML文檔模型

定義1XML文檔樹(shù)：一個(gè)XML文檔T可以表示成一顆帶有標(biāo)簽的有序樹(shù)(V，E，Label，Root)。其中V表示文檔中節(jié)點(diǎn)的有限集合，V=element∪attribut，element和attribute分別代表文檔中的元素節(jié)點(diǎn)和屬性節(jié)點(diǎn)；Root是文檔樹(shù)T中的根節(jié)點(diǎn)Root∈V；E=V×V是文檔中有向邊的集合；Label是文檔中V到V的集合，既文檔樹(shù)中每個(gè)節(jié)點(diǎn)分別指明一個(gè)標(biāo)簽作為節(jié)點(diǎn)標(biāo)識(shí)。下面給出了一個(gè)關(guān)于書架的XML文檔簡(jiǎn)略片段，圖1給出了對(duì)應(yīng)的文檔樹(shù)的模型，其中橢圓形代表節(jié)點(diǎn)，三角形代表屬性，矩形代表文本。

H.Cormen

E.Leierson

128.00

< publisher>China Machine Press

圖1　書架的XML Schema文檔示例

從圖1中可以看出文檔的根節(jié)點(diǎn)為bookshelf，它的子節(jié)點(diǎn)是由book元素組成，每個(gè)book節(jié)點(diǎn)都有一個(gè)屬性id；節(jié)點(diǎn)集合及其邊對(duì)應(yīng)的關(guān)系都可以很容易從文檔書中看出。

1.2XML模式

模式定義語(yǔ)言使XML文檔遵循一定規(guī)則，可以有效地描述和確定出文檔的特性，從而得到一個(gè)良構(gòu)的XML文檔。它不僅規(guī)定了XML文檔中可以使用的元素和元素的數(shù)據(jù)類型，而且還定義了文檔中元素出現(xiàn)的順序和次數(shù)以及其節(jié)點(diǎn)的嵌套關(guān)系等。目前比較廣泛使用的是DTD和XML Schema模型。

DTD使用一種特殊的語(yǔ)法來(lái)表示XML文檔中的元素和屬性，如表示bookshelf元素包含一個(gè)或者多個(gè)book元素，表示book元素的屬性id是必須且只能出現(xiàn)一次。而Schema使用一種與XML文檔相同的語(yǔ)法來(lái)定義XML文檔的元素，如使用和來(lái)表示元素和屬性。因此使用DTD模式比使用Schema模式來(lái)判斷一個(gè)XML文檔是否有效，必然會(huì)增加解析的時(shí)間開(kāi)銷。并且DTD相對(duì)于Schema還有著其他的缺點(diǎn)：DTD只提供字符串類型的數(shù)據(jù)，而Schema中提供了豐富的數(shù)據(jù)類型并且可以自定義數(shù)據(jù)類型，具有很好的可擴(kuò)展性； DTD提供的約束限制僅有？(零或一個(gè))、*(零或多個(gè))和+(一個(gè)或多個(gè))三種，而Schema還可以提供范圍限制等。因此本文采用Schema模式限制約束XML文檔并對(duì)XML建立索引。

定義2Schema摘要樹(shù)：對(duì)于一個(gè)Schema文檔可以映射成一個(gè)文檔摘要樹(shù)(V,children)(本文不考慮Schema結(jié)構(gòu)中存在環(huán)的情況)，其中V表示文檔中標(biāo)簽生成的節(jié)點(diǎn)集合，children表示一個(gè)元素映射到子元素上的映射集合。

2基于Schema索引的關(guān)鍵技術(shù)

2.1文檔編碼和索引結(jié)構(gòu)

目前對(duì)XML文檔常用的編碼方法有基于區(qū)間編碼[12,13]和基于前綴編碼[14]：區(qū)間編碼是對(duì)XML文檔中的每個(gè)節(jié)點(diǎn)賦予一對(duì)整數(shù)值，父節(jié)點(diǎn)的編碼區(qū)間包含其子節(jié)點(diǎn)和后代的編碼區(qū)間；前綴編碼是保存了XML文檔節(jié)點(diǎn)的路徑信息，任何父節(jié)點(diǎn)的編碼都是其子節(jié)點(diǎn)和后代節(jié)點(diǎn)編碼的前綴。本文充分利用兩種編碼的特點(diǎn)，分別對(duì)XML文檔和Schema文檔分別進(jìn)行編碼。

Schema編碼：把Schema映射成一個(gè)摘要樹(shù)，節(jié)點(diǎn)n的編碼用(Code(n),Level(n),E/A)標(biāo)識(shí)，其中Code(n)表示節(jié)點(diǎn)n的前綴編碼，Level(n)表示節(jié)點(diǎn)n在摘要樹(shù)中的層數(shù)，E/A表示節(jié)點(diǎn)是元素節(jié)點(diǎn)還是屬性節(jié)點(diǎn)。

定理1給定一個(gè)有效的XML文檔樹(shù)T采用區(qū)間編碼，則對(duì)T中任意兩個(gè)節(jié)點(diǎn)m和n，若m是n的祖先節(jié)點(diǎn)的充分必要條件為Precode(m)·Order(m)是Precode(n)·Order(n)的一個(gè)前綴，其中Precode(m)表示節(jié)點(diǎn)m的前綴編碼，Oeder(m)表示節(jié)點(diǎn)m的順序碼。

通過(guò)對(duì)Schema編碼采用倒排索引建立一個(gè)Schema索引結(jié)構(gòu)，在倒排索引中把關(guān)鍵詞存儲(chǔ)在一個(gè)索引文件中，使用指針鏈表指向關(guān)鍵詞相關(guān)的文檔，從而有效的完成倒排索引列表。如圖2所示，本文把具有相同元素/屬性的節(jié)點(diǎn)歸并到一個(gè)索引中，這樣可以通過(guò)在Schema索引中快速的訪問(wèn)指定元素/屬性節(jié)點(diǎn)。

圖2　Schema編碼索引示例

XML編碼：XML文檔采用混合編碼，每個(gè)節(jié)點(diǎn)的編碼都包含前綴編碼和區(qū)間編碼信息。節(jié)點(diǎn)n編碼為(Start(n),End(n),S_Code(n))。其中Start(n)和End(n)分別表示節(jié)點(diǎn)n的前序遍歷和后續(xù)遍歷值，S_Code(n)是節(jié)點(diǎn)n所對(duì)應(yīng)的元素或者屬性在Schema文檔樹(shù)中具有相同路徑相同位置的節(jié)點(diǎn)前綴編碼Code(n)，Level(n)表示節(jié)點(diǎn)n在XML文檔樹(shù)中的層數(shù)。因此，XML文檔將Schema的前綴編碼信息存入節(jié)點(diǎn)，通過(guò)使用S_Code(n)使得每個(gè)節(jié)點(diǎn)都包含了相應(yīng)的Schema中的結(jié)構(gòu)信息，這使得在SBXHCI可以直接判斷出無(wú)效的路徑表達(dá)式中，并且在結(jié)構(gòu)連接運(yùn)算中提供精確的定位和減少結(jié)構(gòu)連接的次數(shù)。

定理2給定一個(gè)有效的XML文檔樹(shù)T采用區(qū)間編碼，則對(duì)T中任意兩個(gè)節(jié)點(diǎn)m和n，若m是n的祖先節(jié)點(diǎn)的充分必要條件為Start(m)

根據(jù)Schema索引可以建立一個(gè)XML文檔索引結(jié)構(gòu)，如圖3所示。首先根據(jù)Schema摘要樹(shù)先序遍歷的節(jié)點(diǎn)建立一個(gè)目錄，然后把XML文檔中具有相同前綴編碼的元素歸并到一起，這樣可以快速地定位某個(gè)節(jié)點(diǎn)的祖先節(jié)點(diǎn)，最后根據(jù)B+樹(shù)將XML文檔中具有相同元素/屬性的節(jié)點(diǎn)歸并到一個(gè)索引中。從XML編碼可以看出，任意一個(gè)節(jié)點(diǎn)的前綴編碼都包含了從根節(jié)點(diǎn)到該節(jié)點(diǎn)的簡(jiǎn)單路徑信息。

圖3　XML文檔索引示例

一般實(shí)際的應(yīng)用中，Schema文檔和XML文檔之間是多對(duì)多的關(guān)系。本文為了方便測(cè)試SBXHCI方法的效率，提出的索引技術(shù)是基于一個(gè)Schema文檔對(duì)應(yīng)一個(gè)XML文檔的，因此在實(shí)際開(kāi)發(fā)中，我們只需要在schema文檔和XML文檔編碼過(guò)程中分別加入Schema_ID(n)和XML_ID(n)即可。

2.2路徑查詢語(yǔ)言

XML查詢語(yǔ)言共同的特點(diǎn)是使用路徑表達(dá)式在XML文檔中導(dǎo)航到待查詢節(jié)點(diǎn)并返回指定路徑的節(jié)點(diǎn)集合，目前最常用的XML查詢語(yǔ)言是XPath。XPath使用路徑表達(dá)式來(lái)查找XML文檔中的節(jié)點(diǎn)、節(jié)點(diǎn)集合、原子值等，節(jié)點(diǎn)是沿著路徑選取的，它的基本語(yǔ)法為Step1/Step2/…/StepN，其中Step=Axis::Node_test[Predicate*]。軸Axis實(shí)際上是指一個(gè)方向，即查詢是沿著選著的軸的方向移動(dòng)，節(jié)點(diǎn)測(cè)試Node_test是指選著的節(jié)點(diǎn)類型或者是節(jié)點(diǎn)名，謂詞Predicate對(duì)定位步選擇的節(jié)點(diǎn)作更進(jìn)一步的篩選。

一般情況下路徑表達(dá)式為復(fù)雜路徑，即表達(dá)式會(huì)存在多個(gè)謂詞使得查詢過(guò)程中存在多個(gè)分支幾點(diǎn)。本文處理復(fù)雜路徑的基本思想是路徑分解的方法，即將復(fù)雜路徑查詢分解成若干個(gè)簡(jiǎn)單路徑表達(dá)式，對(duì)每個(gè)簡(jiǎn)單路徑查詢的結(jié)果集進(jìn)行連接得到需要查詢的結(jié)果集。

2.3算法分析

SBXHCI查詢文檔分為四個(gè)步驟：建立索引，路徑分解，與Schema索引匹配，與XML文檔匹配。SBXHCI查詢算法流程圖如圖4所示，具體算下如下：

(1) 建立索引。分別對(duì)Schema和XML文檔建立索引，具體步驟可參見(jiàn)2.1節(jié)中的說(shuō)明。為了減小索引空間，本文改進(jìn)了Schema摘要樹(shù)中前綴編碼的方法，根據(jù)摘要樹(shù)層次中最大的兄弟節(jié)點(diǎn)個(gè)數(shù)(記作bNode)來(lái)決定編碼的長(zhǎng)度1=[log2max(bNode)]，既每層的編碼長(zhǎng)度，從而減小了Schema編碼中前序編碼的Code(n)的長(zhǎng)度。如圖1中第三層節(jié)點(diǎn)中最大的兄弟節(jié)點(diǎn)為5，則可以用3位來(lái)表示每個(gè)節(jié)點(diǎn)的編號(hào)。

圖4　SBXHCI查詢算法流程圖

(2) 路徑分解。在進(jìn)行路徑表達(dá)式查詢過(guò)程中將復(fù)雜路徑分解為若干個(gè)簡(jiǎn)單路徑的子查詢，對(duì)于分解后含有目標(biāo)節(jié)點(diǎn)的簡(jiǎn)單路徑稱為目標(biāo)匹配路徑，只含有一個(gè)謂詞約束的簡(jiǎn)單路徑稱為條件匹配路徑。例如一個(gè)復(fù)雜路徑表達(dá)式a/b[c>d]/e/f[g=h]/i，可以分解為條件匹配路徑a/b[c>d],b/e/f[g=h]和目標(biāo)匹配路徑f/i。

(3) 與Schema索引匹配。對(duì)分解后的子查詢?cè)赟chema索引中進(jìn)行有效性的驗(yàn)證，可以通過(guò)定理1來(lái)判斷一個(gè)簡(jiǎn)單路徑是否合法。如果子查詢中存在Schema索引文檔中無(wú)相匹配結(jié)構(gòu)的路徑信息，則說(shuō)明待查詢的路徑表達(dá)式不合法，返回?zé)o查詢結(jié)果。因?yàn)镾chema中定義了XML文檔遵循的規(guī)則，即XML文檔中可以使用的元素和元素的數(shù)據(jù)類型，而且還定義了文檔中元素出現(xiàn)的順序和次數(shù)及其嵌套關(guān)系等， 如果在Schema中查詢不到相應(yīng)的路徑信息，則在相應(yīng)的XML文檔中也不會(huì)存在此路徑表達(dá)式的查詢結(jié)果集。因?yàn)镾chema文檔的大小比XML文檔的小的多，所以加快了對(duì)無(wú)效路徑的查詢效率。如果在Schema索引中有相應(yīng)匹配的路徑信息，則說(shuō)明待查詢的路徑是一個(gè)合法的表達(dá)式。

(4) 與XML文檔匹配可以根據(jù)待查詢的路徑表達(dá)式的復(fù)雜度分為兩種情況：

a) 如果查詢路徑為簡(jiǎn)單路徑，即查詢路徑為目標(biāo)路徑，則可以直接根據(jù)路徑的目標(biāo)節(jié)點(diǎn)在Schema摘要樹(shù)中找到對(duì)應(yīng)的S_Code(n)值，從而在XML文檔的索引中直接獲取到待求的XML節(jié)點(diǎn)；

b) 如果查詢路徑為復(fù)雜路徑，可以將查詢路徑分解為若干個(gè)分支路徑集合{bPath}和一個(gè)包含目標(biāo)節(jié)點(diǎn)的目標(biāo)路徑TPath。如果{bPath}包含兩條及兩條以上的路徑集合，首先從{bPaht}依次取出兩條路徑找出葉子節(jié)點(diǎn)的前綴編碼S_Code(i)，并找出對(duì)應(yīng)的Schema摘要樹(shù)中的相同的前綴編碼Code(i)，使用“與”操作計(jì)算出相鄰路徑中節(jié)點(diǎn)的最長(zhǎng)的前綴編碼，循環(huán)操作{bPath}既可以得到分支路徑結(jié)果集bResult；如果{bPath}只包含一條路徑，則直接可以求出bResult。最后使用同樣的方法對(duì)bResult和tPath進(jìn)行連接，得到待求的XML節(jié)點(diǎn)。具體算法如下所示：

輸入：分支路徑集合{bPaht}，目標(biāo)路徑tPath

輸出：待求的XML節(jié)點(diǎn)集Result

if({bPath},length>2){

for each bPathi→bPath{

//獲取bPaht中葉節(jié)點(diǎn)對(duì)應(yīng)的前綴編碼Code(i)

Code(i)=GetPreCode(bPathi)

Code(i+1)=GetPreCode(bPathi+1)

//獲取相鄰路徑的最長(zhǎng)前綴編碼，Align先根據(jù)編

//碼層次獲得其編碼長(zhǎng)度然后使用與操作連接

MaxCode(i)=Align(Cod(i)&Code(i+1));

}

//獲取分支路徑結(jié)果集bResult

}

else{

Code(1)=GetPreCode(bPath1);

bResult=Code(Code(1));

}

Result=Align(bResult&tPath);

3實(shí)驗(yàn)及其分析

為了測(cè)試和評(píng)估本文提出SBXHCI查詢系統(tǒng)中的混合索引方法性能和查詢效率，本文使用了Java語(yǔ)言實(shí)現(xiàn)SBXHCI查詢系統(tǒng)。實(shí)驗(yàn)運(yùn)行在一臺(tái)CPU主頻為2.3 GHz雙核，內(nèi)存大小為4 GB，操作系統(tǒng)為Windows 7電腦上。實(shí)驗(yàn)采用的數(shù)據(jù)有兩種：第一種是廣泛應(yīng)用于XML測(cè)試的DBLP數(shù)據(jù)，它的特點(diǎn)是結(jié)構(gòu)簡(jiǎn)單，樹(shù)的深度不高；第二種是XML基準(zhǔn)數(shù)據(jù)庫(kù)XMark，它包含了復(fù)雜的樹(shù)形記錄結(jié)構(gòu)。本文實(shí)驗(yàn)中忽略了XML數(shù)據(jù)中的空格，并且所有的實(shí)驗(yàn)都是經(jīng)過(guò)多次實(shí)驗(yàn)所取得穩(wěn)定的平均結(jié)果值。表1表示兩種不同數(shù)據(jù)及的特征。

表1　表示兩種不同數(shù)據(jù)及的特征

根據(jù)實(shí)驗(yàn)的可行性和可獲得性，本文選取文獻(xiàn)[6]中的XISS方法、文獻(xiàn)[8]中DBXI方法、文獻(xiàn)[11]中SBXI方法三種具有代表性的方法和本文提出的SBXHCI方法進(jìn)行分析和比較測(cè)試。

3.1構(gòu)建索引的時(shí)間和空間比較

衡量一種索引機(jī)制的性能可以從以下三個(gè)方面來(lái)考察：① 創(chuàng)建索引所花費(fèi)的時(shí)間；② 存儲(chǔ)索引所需的空間；③ 查詢響應(yīng)消耗的時(shí)間。創(chuàng)建索引所花費(fèi)的時(shí)間越短，消耗的存儲(chǔ)空間越少，查詢響應(yīng)的時(shí)間越短，則說(shuō)明索引的性能越好。圖5分別表示不同方構(gòu)建索引的時(shí)間和空間比較。

從圖5(a)中可以看出，不管是結(jié)構(gòu)相對(duì)簡(jiǎn)單的DBLP文檔，還是相對(duì)復(fù)雜的XMark文檔，SBXHCI方法建立索引所需的時(shí)間都是最小的。原因是解析Schema與解析XML文檔使用相同的解析器，相對(duì)于解析DTD時(shí)減小了消耗的時(shí)間，加快了索引的構(gòu)建，因此使用Schema構(gòu)建索引的方法SBXHCI和SBXI所消耗的時(shí)間小于使用DTD構(gòu)建索引的方法DBXI。

從圖5(b)中可以看出，XISS構(gòu)建索引消耗的空間最小，原因是XISS在構(gòu)建索引的過(guò)程中只對(duì)XML文檔中每個(gè)節(jié)點(diǎn)賦予一個(gè)二元組(pre，post)編碼，并沒(méi)有包含模式信息，因此構(gòu)建索引使用的空間最小；對(duì)于結(jié)構(gòu)相對(duì)簡(jiǎn)單的DBLP文檔，SBXHCI方法建立索引所需空間則比DBXI和SBXI要小，而對(duì)于結(jié)構(gòu)相對(duì)復(fù)雜的XMark文檔，SBXHCI方法建立索引所需空間則比DBXI和SBXI要大，雖然本文優(yōu)化了前綴編碼標(biāo)識(shí)節(jié)點(diǎn)的位數(shù)，但在構(gòu)建索引的過(guò)程中比區(qū)間編碼使用了更多的存儲(chǔ)空間，因此SBXHCI方法在構(gòu)建XMark索引過(guò)程中比DBXI方法使用了更多的存儲(chǔ)空間。

圖5　不同方法建立索引所需時(shí)間和空間消耗對(duì)比

3.2查詢響應(yīng)時(shí)間的比較

為了測(cè)試文檔索引的查詢響應(yīng)時(shí)間，本文針對(duì)表1中數(shù)據(jù)2-DBLP和數(shù)據(jù)4-XMark兩種數(shù)據(jù)集，分別給出了4種具有代表性的路徑表達(dá)式查詢語(yǔ)句，如表2所示。其中D1-D5是關(guān)于DBLP的查詢表達(dá)式，X1-X4是關(guān)于XMark的查詢表達(dá)式，D1和X1是不包含謂詞的簡(jiǎn)單路徑查詢，D2和X2是含有謂詞的簡(jiǎn)單路徑查詢，D3和X3是含有謂詞的復(fù)雜路徑查詢，D4、D5和X4是錯(cuò)誤路徑查詢。查詢響應(yīng)時(shí)間實(shí)驗(yàn)結(jié)果如圖6所示。

表2　實(shí)驗(yàn)中的查詢路徑表達(dá)式

圖6　查詢響應(yīng)時(shí)間

從圖6中可以看出，對(duì)于無(wú)效路徑的查詢，DBXI、SBXI和SBXHCI三種方法都可以快速的判斷出無(wú)查詢結(jié)果。在XML文檔建立索引中有效的利用了模式信息，都是先從相應(yīng)的模式信息中進(jìn)行匹配，無(wú)需查詢XML文檔，可以直接判斷出無(wú)效查詢，因此大大降低無(wú)效路徑的查詢響應(yīng)時(shí)間。

對(duì)于有效路徑的查詢，SBXHCI方法相對(duì)于其他三種方法明顯的降低了查詢響應(yīng)時(shí)間。對(duì)于XISS查詢具有N個(gè)元素組成的路徑查詢時(shí)，需要N-1次的結(jié)果結(jié)構(gòu)連接，因此查詢響應(yīng)消耗的時(shí)間最大；DBXI和SBXI方法都是采用區(qū)間編碼建立索引，在結(jié)構(gòu)連接算法的性能低于采用前綴編碼的索引；而SBXHCI采用混合編碼索引的機(jī)制，在結(jié)構(gòu)連接中去除了不相關(guān)節(jié)點(diǎn)的連接操作，減少了結(jié)構(gòu)連接次數(shù)，加快了結(jié)構(gòu)的連接運(yùn)算，這使得查詢效率得到更進(jìn)一步的提高，優(yōu)于其他三種方法。

4結(jié)語(yǔ)

本文提出了一種基于Schema混合編碼的索引查詢技術(shù)SBXHCI，充分利用Schema信息并將Schema編碼信息引入到XML文檔節(jié)點(diǎn)編碼中，對(duì)XML文檔綜合利用混合編碼建立索引。這種編碼方法充分利用了區(qū)間編碼的可以快速訪問(wèn)節(jié)點(diǎn)的優(yōu)點(diǎn)和前綴編碼的可以加快結(jié)構(gòu)連接運(yùn)算的優(yōu)點(diǎn)，并且在結(jié)構(gòu)連接中去除了不相關(guān)節(jié)點(diǎn)的連接操作，可以快速地訪問(wèn)到查詢結(jié)果。通過(guò)實(shí)驗(yàn)結(jié)果表明SBXHCI方法的索引結(jié)構(gòu)在時(shí)間和空間方面都有較大的提高，并且可以有效地提高文檔的查詢速度。但目前對(duì)XML文檔查詢研究工作還存在眾多的問(wèn)題，如沒(méi)有考慮XML的存在的“參考”屬性，這使得XML文檔對(duì)應(yīng)一個(gè)圖形結(jié)構(gòu)而不是一個(gè)簡(jiǎn)單的樹(shù)形結(jié)構(gòu)，從而處理起來(lái)更加復(fù)雜，這需要在將來(lái)的工作中進(jìn)一步的提高。

參考文獻(xiàn)

[1] 孟小峰,王寧,王小峰.XML查詢優(yōu)化研究[J].軟件學(xué)報(bào),2006,17(10):2069-2086.

[2] 季玉梅.一種基于XML模式的XML索引技術(shù)[D].北京:北京工業(yè)大學(xué),2013.

[3] Goldman R,Widom J.DataGuides:Enabling Query Formulation and Optimization in Semistructured Databases[C]//Proceedings of the 23rd International Conference on Very Large Data Bases,1997:436-445.

[4] Wang W,Jiang H,Wang H,et al.Efficient processing of XML Paht queries using the disk-based F&B Index[C]//Proceeding of the 31st Interational Conference on Very Large Data Bases,Trondheim,Norwey,2005:145-156.

[5] Li Q,Moon B.Indexing and querying XML data for regular path expressions[C]//Proceeding of the 27th International Conference on Very Large Data Bases,Roma,Italy,2001:361-370.

[6] 王錦,何先波,賀春林.改進(jìn)的XISS索引技術(shù)的仿真研究[J].計(jì)算機(jī)科學(xué),2012,39(1):148-151.

[7] 路燕,張亮,段起陽(yáng),等.一種基于DTD的XML索引方法[J].計(jì)算機(jī)研究與發(fā)展,2005,42(1):30-37.

[8] 滿慎江,陳近森,郭希娟,等.面向XML文檔檢索的索引技術(shù)[J].小型微型計(jì)算機(jī)系統(tǒng),2008,29(1):89-92.

[9] Che D,Ling T,Hou W.Holistic boolean-twig pattern matching for efficient XML query processin[J].IEEE Trans on Knowledge and Data Engineering,2012,24(11):2008-2024.

[10] 肖芳橋.基于模式的XML索引技術(shù)研究[D].濟(jì)南:山東大學(xué),2010.

[11] 鄒為偉,宋余慶,耿飆,等.基于Schema的XML索引方法研究[J].計(jì)算工程,2011,37(6):74-76.

[12] 萬(wàn)常選,劉云生,許升華,等.基于區(qū)間編碼的XML索引結(jié)構(gòu)的有效結(jié)構(gòu)連接[J].計(jì)算機(jī)學(xué)報(bào),2005,28(1):113-127.

[13] 莊燦偉,馮少榮,林子雨,等.XML動(dòng)態(tài)區(qū)間編碼方法[J].軟件學(xué)報(bào),2012,23(3):582-593.

[14] 萬(wàn)里勇.基于索引技術(shù)的XML查詢優(yōu)化研究[D].長(zhǎng)沙:中南大學(xué),2012.

中圖分類號(hào)TP311

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.02.008

收稿日期：2014-06-04。上海高校知識(shí)平臺(tái)“上海商貿(mào)服務(wù)知識(shí)服務(wù)中心”建設(shè)項(xiàng)目(ZF1226)。夏剛，碩士生，主研領(lǐng)域：軟件工程，數(shù)據(jù)挖掘，人工智能。劉林靜，碩士生。樓文高，教授。