I-XISS：一種改進(jìn)的XML文檔索引存儲(chǔ)方法.pdf

1、XML(eXtensible Markup Language，可擴(kuò)展標(biāo)記語(yǔ)言)憑借其結(jié)構(gòu)簡(jiǎn)單、易于理解、自描述、可擴(kuò)展、可跨越系統(tǒng)平臺(tái)等特性，現(xiàn)在已成為Internet上數(shù)據(jù)表示和數(shù)據(jù)交換的事實(shí)上的標(biāo)準(zhǔn)。隨著XML數(shù)據(jù)的應(yīng)用日益廣泛和深入，針對(duì)XML數(shù)據(jù)的研究也受到人們的關(guān)注。如何對(duì)XML數(shù)據(jù)進(jìn)行有效的存儲(chǔ)和查詢(xún)成為一個(gè)研究的熱點(diǎn)，而快速有效地查詢(xún)XML文檔的一個(gè)重要方法就是為其建立索引。 目前XML文檔的索引主要有三種類(lèi)型：路

2、徑索引、節(jié)點(diǎn)索引、基于串的索引。其中，路徑索引可以很好地支持簡(jiǎn)單路徑表達(dá)式的查詢(xún)，但是對(duì)于正則路徑表達(dá)式，路徑索引的效果不是很理想。節(jié)點(diǎn)索引可以很好地支持正則路徑表達(dá)式，但是對(duì)于長(zhǎng)的路徑表達(dá)式，尤其是在查詢(xún)產(chǎn)生的中間結(jié)果很多的時(shí)候，節(jié)點(diǎn)索引的結(jié)構(gòu)連接操作會(huì)代價(jià)高昂。基于串的索引可以支持各種查詢(xún)而不用進(jìn)行連接操作，但在處理含有通配符的查詢(xún)時(shí)，由于要轉(zhuǎn)化為簡(jiǎn)單路徑表達(dá)式，所以影響了查詢(xún)的執(zhí)行效率。 節(jié)點(diǎn)索引的一個(gè)典型例子是XISS(

3、XML Indexing and Storage System，XML索引和存儲(chǔ)系統(tǒng))，它以節(jié)點(diǎn)編碼和三種索引結(jié)構(gòu)為基礎(chǔ)，以三種結(jié)構(gòu)連接算法為查詢(xún)方法，通過(guò)把查詢(xún)路徑表達(dá)式分解成單個(gè)的元素或?qū)傩怨?jié)點(diǎn)的子路徑表達(dá)式，依次查詢(xún)子路徑表達(dá)式形成中間結(jié)果，最后通過(guò)中間結(jié)果之間的結(jié)構(gòu)連接算法得到最終的查詢(xún)結(jié)果。但是XISS中的子路徑概念的基本單位是一個(gè)元素節(jié)點(diǎn)或?qū)傩怨?jié)點(diǎn)，導(dǎo)致查詢(xún)時(shí)結(jié)構(gòu)連接操作的次數(shù)過(guò)多，因此影響了查詢(xún)效率。 本文的主要工

4、作是： (1)將XISS與路徑索引的思想相結(jié)合，對(duì)XISS的索引結(jié)構(gòu)進(jìn)行了改進(jìn)，使得改進(jìn)后的索引結(jié)構(gòu)既可以靈活處理正則路徑表達(dá)式，又克服了XISS中結(jié)構(gòu)連接操作次數(shù)過(guò)多的缺點(diǎn)。改進(jìn)后的索引結(jié)構(gòu)簡(jiǎn)寫(xiě)為I-XISS(Improved XISS)。 (2)以I-XISS的索引結(jié)構(gòu)為基礎(chǔ)，提出了新的分解子路徑表達(dá)式的算法，使得子路徑表達(dá)式的基本單位由原來(lái)的一個(gè)節(jié)點(diǎn)變成了一個(gè)簡(jiǎn)單路徑表達(dá)式，有效減少了子路徑表達(dá)式的數(shù)目。

5、(3)提出了新的查詢(xún)算法，以I-XISS的索引結(jié)構(gòu)和分解子路徑表達(dá)式的算法為基礎(chǔ)，通過(guò)減少中間結(jié)果的結(jié)構(gòu)連接操作次數(shù)，使得查詢(xún)時(shí)間與查詢(xún)路徑的長(zhǎng)度無(wú)關(guān)，而只與查詢(xún)路徑的復(fù)雜度和中間結(jié)果的大小有關(guān)，有效縮短了XML查詢(xún)的執(zhí)行時(shí)間。 (4) 最后構(gòu)建了一個(gè)實(shí)驗(yàn)系統(tǒng)，本文提出的索引結(jié)構(gòu)、子路徑表達(dá)式的分解算法和查詢(xún)算法在系統(tǒng)中初步實(shí)現(xiàn)，并且對(duì)改進(jìn)前后索引結(jié)構(gòu)的查詢(xún)效率進(jìn)行了比較，實(shí)驗(yàn)數(shù)據(jù)證明，改進(jìn)后的索引結(jié)構(gòu)比原來(lái)的查詢(xún)效率有了較大的