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

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

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

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

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

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