XML結(jié)構(gòu)索引技術(shù)及查詢優(yōu)化研究.pdf

1、為了實(shí)現(xiàn)XML的查詢優(yōu)化，近年來人們相繼提出了很多索引技術(shù)和連接算法[12,13,14，15,16,23,24]。這些索引主要是根據(jù)邊標(biāo)簽和元素值建立的。然而有的索引不包含所有的元素結(jié)點(diǎn)，因而在進(jìn)行查詢時(shí)許多路徑仍需要檢測(cè)；有的在向前或向后遍歷時(shí)產(chǎn)生了大量的冗余數(shù)據(jù)，從而造成查詢代價(jià)較大。另外，在所提出的算法中，盡管有的算法，如MPMGJN算法[23]優(yōu)于標(biāo)準(zhǔn)的RDBMS連接算法，但是該算法為匹配基本的結(jié)構(gòu)關(guān)系，特別是在父子關(guān)系情況下，

2、執(zhí)行了大量不必要的計(jì)算和占用了大量的I/O資源；有的算法雖然代表了結(jié)構(gòu)連接算法的先進(jìn)水平，如Stack-Tree-Desc[24]連接算法，但是它沒有利用索引結(jié)構(gòu)而是順序?yàn)g覽輸入列表。這樣，必然浪費(fèi)I/O資源，影響連接的速度。 針對(duì)以上情況，本文做了以下幾個(gè)方面的工作： ①由于采用傳統(tǒng)的NumberingSchema方法來表示XML文件結(jié)構(gòu)不便于元素更新，本文在改進(jìn)的基礎(chǔ)上提出了SparseNumberingSchema

3、方法。與傳統(tǒng)方法相比，其優(yōu)點(diǎn)在于：由于在插入新結(jié)點(diǎn)時(shí)不需要重新計(jì)算其結(jié)點(diǎn)的start和end值，樹結(jié)構(gòu)更新效率得到提高；樹的創(chuàng)建只需遍歷一次文檔，進(jìn)一步地節(jié)省了建樹開銷；此外，它還能為索引提供一個(gè)相對(duì)持久和穩(wěn)定的參考。 ②鑒于目前關(guān)于NumberingSchema存儲(chǔ)方法的研究較為少見，本文針對(duì)SparseNumberingSchema進(jìn)行研究，給出了在關(guān)系數(shù)據(jù)庫中的存儲(chǔ)方法。該存儲(chǔ)方法不僅有利于根據(jù)start值快速建立索引，而

4、且可以節(jié)省存儲(chǔ)空間。 ③本文將關(guān)系數(shù)據(jù)庫中B+樹索引技術(shù)與SparseNumberingSchema相結(jié)合，提出了一種新的XML文件索引結(jié)構(gòu)——B+樹結(jié)構(gòu)索引，它對(duì)XML查詢中連接操作和元素定位操作的優(yōu)化有著重要作用。進(jìn)而，通過引入指針對(duì)該索引進(jìn)行改進(jìn)，提出了一種帶有SiblingPointer的B+樹結(jié)構(gòu)索引(簡(jiǎn)稱B+-SP)。利用這種索引可以克服元素查找總是從樹的根部開始進(jìn)行的缺陷。 ④基于B+-SP索引，本文還研究

5、給出了Anc-Desc-B+-sp連接算法。經(jīng)理論分析，其算法的時(shí)間復(fù)雜度O(|A|+log|A|)比沒有采用該索引的Stack-Tree-Desc算法[24]的時(shí)間復(fù)雜度O(|A|+|D|outlist|)明顯降低，因|D|≥|A|，故|D|+outlist|＞＞log|A|。經(jīng)初步實(shí)驗(yàn)表明，本算法是一個(gè)有效、快速的連接算法。 ⑤在XML查詢中，影響查詢時(shí)間的另一個(gè)重要因素是對(duì)涉及的XML數(shù)據(jù)源的定位問題。為解決XML數(shù)據(jù)源的