基于索引的XML小枝模式匹配問題的研究.pdf

1、Internet發(fā)展到至今已經(jīng)完全滲入到人們生活工作的各個方面。作為半結(jié)構(gòu)化語言XML已經(jīng)成為一種最重要的數(shù)據(jù)載體，在Web服務(wù)、電子商務(wù)、數(shù)字圖書館等諸多網(wǎng)絡(luò)等領(lǐng)域的數(shù)據(jù)描述標(biāo)準(zhǔn)。研究表明，當(dāng)今國內(nèi)外研究的重點集中在以下兩點：如何有效查詢和管理XML數(shù)據(jù)與如何方便用戶從海量的XML數(shù)據(jù)中提取他們所需要的信息。因此，許多對XML數(shù)據(jù)查詢的研究就由此出現(xiàn)了，從而使得XML數(shù)據(jù)查詢成為XML數(shù)據(jù)管理領(lǐng)域的一個熱點。
　　 本文從XM

2、L數(shù)據(jù)庫系統(tǒng)角度出發(fā)，透徹分析了目前存在的XML文檔樹的小枝查詢技術(shù)與面臨的不足。通過研究與改進(jìn)編碼方案來快速的組織XML文檔，并且根據(jù)XML查詢的特性，本文提出了一種新的索引REI，這是一種有著簡單的數(shù)據(jù)結(jié)構(gòu)和嚴(yán)謹(jǐn)?shù)倪壿嫿Y(jié)構(gòu)的索引技術(shù)。同時，為了進(jìn)一步提高查詢的效率，本文的索引還利用了改進(jìn)的區(qū)間編碼方案來組織和引用XML數(shù)據(jù)。
　　 基于以上的研究，本文還對XML文檔的查詢做了細(xì)致研究。XML查詢中的路徑表達(dá)式可以表示為樹狀查

3、詢獨立地描述查詢要求。XML數(shù)據(jù)查詢主要分為單路徑和多分支路徑查詢。在這兩種路徑查詢方面，XML查詢都可表示成小枝模式查詢，在XML數(shù)據(jù)庫中找到所有出現(xiàn)的小枝模式是當(dāng)前XML查詢處理的核心操作。基于這個思想，本文提出了一種新的基于索引的查詢模型。在借鑒已有相關(guān)算法的優(yōu)點，摒棄其中諸多缺點的基礎(chǔ)上，采用改進(jìn)的區(qū)間編碼快速判斷結(jié)點之間的祖先-后裔或父-子關(guān)系，并利用索引REI，進(jìn)一步設(shè)計了一種新的高效的算法RE-TWIG，該算法可以有效的減

4、小查詢中的復(fù)雜度和冗余，快速的得到目標(biāo)結(jié)點。
　　 本文的主要工作和創(chuàng)新點有以下幾個方面：
　　 1、研究了主流XML文檔的結(jié)點編碼方案，研究了小枝路徑索引的分解方法與查詢方式。根據(jù)本文查詢算法的特點，采用改進(jìn)的區(qū)間編碼方式，以此快速的判斷結(jié)點直接的邏輯關(guān)系。
　　 2、本文提出了一種索引REI來存儲XML文檔。對于任何XML索引，在設(shè)計與實現(xiàn)的過程中都要考慮到XML查詢的基本特征，其中包括邏輯結(jié)構(gòu)的保存以及基于

5、結(jié)構(gòu)信息快速判斷結(jié)點間的關(guān)系，除了以上兩點還必須做到一條：滿足高效處理XML查詢的請求。通過其與將經(jīng)典索引進(jìn)行的數(shù)據(jù)集對比實驗的結(jié)果來看，對本文提出的索引完全符合這一要求。
　　 3、在前兩點研究的基礎(chǔ)上，提出、設(shè)計并實現(xiàn)了一種基于改進(jìn)區(qū)間編碼和REI索引的小枝模式查詢算法。該算法包括目標(biāo)結(jié)點篩選和小枝查詢模式匹配兩部分。并通過實驗給予了性能驗證。為了便于對以上研究點的理解，論文以一個XML文檔樹的例子為依據(jù)，舉了一個通用查詢實