基于索引技術(shù)的XML查詢研究.pdf

1、具有優(yōu)良特性的XML逐漸成為了網(wǎng)絡(luò)信息交換的載體，越來越多的數(shù)據(jù)采用XML格式存儲和交換，而傳統(tǒng)的查詢技術(shù)不再適應(yīng)新的應(yīng)用，XML索引及查詢方法的研究就顯得更加迫切。 論文對與索引查詢技術(shù)相關(guān)的編碼、查詢、索引等技術(shù)進(jìn)行了深入研究和分析，指出了現(xiàn)有編碼、索引技術(shù)的優(yōu)缺點(diǎn)，同時給出了優(yōu)秀索引、編碼模式的標(biāo)準(zhǔn)。由于現(xiàn)有的索引多數(shù)都是通過路徑表達(dá)式來表達(dá)和實(shí)現(xiàn)XML的結(jié)構(gòu)查詢，而這種方法最核心的技術(shù)之一就是：利用索引編碼方法有效地判斷

2、XML文檔中的元素或?qū)傩蚤g的祖先/后代關(guān)系、父子關(guān)系、左右兄弟等位置關(guān)系，只有有效判斷出任意節(jié)點(diǎn)間的結(jié)構(gòu)關(guān)系，才能避免對整棵文檔樹的遍歷，從而提高結(jié)構(gòu)連接效率。本文提出了兩種新的編碼模式，其中一種是通過引入了虛擬節(jié)點(diǎn)建立的區(qū)間編碼模式，該模式首先給樹的葉子節(jié)點(diǎn)處添加編好序號的虛擬邏輯葉子節(jié)點(diǎn)，然后利用這些編號給該虛擬葉子節(jié)點(diǎn)的祖先節(jié)點(diǎn)賦予區(qū)間編碼。分析證明這種編碼模式可通過節(jié)點(diǎn)間的區(qū)間包含關(guān)系有效地判斷出祖先/后裔關(guān)系、父子關(guān)系，并提高

3、了編碼更新效率。 為了能夠提供更多有效判斷節(jié)點(diǎn)間的位置關(guān)系的結(jié)構(gòu)信息，我們又提出了PSB--基于素?cái)?shù)和序列串的編碼模式，它充分利用素?cái)?shù)的整除特性和序列串匹配技術(shù)，只需要對文檔樹進(jìn)行一次前序遍歷就可以完成所有編碼并且可以在常數(shù)復(fù)雜度的時間內(nèi)實(shí)現(xiàn)節(jié)點(diǎn)之間祖先/后裔、父子、層次、兄弟關(guān)系的判斷；該編碼較好地支持文檔的各種更新。采用標(biāo)準(zhǔn)的Sharks數(shù)據(jù)對編碼更新有效性進(jìn)行性能評估，與以Dietz編碼機(jī)制為代表的區(qū)間編碼機(jī)制編碼更新率進(jìn)

4、行了對比。當(dāng)XML文檔樹中插入或者刪除節(jié)點(diǎn)時，PSB編碼機(jī)制需要重新編碼的節(jié)點(diǎn)數(shù)目相對較小。因此，PSB編碼是支持更新的動態(tài)編碼。 編碼模式反映了元素在樹結(jié)構(gòu)中的位置關(guān)系，而路徑索引描述了源數(shù)據(jù)的路徑結(jié)構(gòu)信息。我們傳統(tǒng)的XML路徑表達(dá)式查詢處理方法中：一種實(shí)現(xiàn)方法是建立XML文檔的路徑索引，通過路徑索引來加速XML路徑表達(dá)式查詢的計(jì)算；另一種方法是對XML文檔樹中的節(jié)點(diǎn)進(jìn)行編碼，將XML路徑表達(dá)式的計(jì)算轉(zhuǎn)化為結(jié)構(gòu)連接的計(jì)算。本文

5、提出將路徑索引與編碼模式相結(jié)合的索引查詢方法，具體方法原理就是利用已有文檔模式信息或者從現(xiàn)有文檔中抽取DTD模式信息的方法，然后對獲取的模式信息再利用簡化DTD的規(guī)則進(jìn)行簡化，獲取較小的模式結(jié)構(gòu)充當(dāng)文檔的路徑索引。之后，我們利用新提出的虛擬節(jié)點(diǎn)建立的區(qū)間編碼模式對簡化模式和XML文檔樹進(jìn)行編碼。在對XML文檔索引結(jié)構(gòu)進(jìn)行查詢時，首先在此簡化DTD模式上進(jìn)行查詢路徑表達(dá)式合法性驗(yàn)證，對合法的查詢才繼續(xù)到XML索引中進(jìn)行查詢，否則及時給出查