XML索引與查詢的若干關鍵技術研究.pdf

1、隨著Internet的快速發(fā)展，XML已成為Web數(shù)據(jù)表示和交換的新標準，越來越多的信息處理系統(tǒng)采用XML文檔作為信息存儲、交換和發(fā)布的載體。與此同時，XML文檔結構和用戶查詢需求也變得越來越復雜，包含大量引用邊的圖結構XML文檔，以及僅包含部分路徑信息和關鍵詞的XML IR(Information Retrieval)查詢變得越來越普遍，這給XML索引與查詢技術提出了嚴峻的挑戰(zhàn)。
　　 目前XML索引技術的研究主要集中在3個方

2、面：一是面向XML有向樹的節(jié)點記錄類索引；二是面向XML有向圖的結構摘要類索引(即XML結構索引)；三是XML數(shù)據(jù)與全文數(shù)據(jù)的聯(lián)合索引。與節(jié)點記錄類索引相比，后兩類索引的研究相對薄弱，索引的整體性能還比較低，離實際應用還存在較大的距離。針對XML結構索引目前存在的主要問題：索引創(chuàng)建時間較長、空間開銷較大、查詢效率較低以及分支路徑查詢研究較為薄弱，本文提出了三種高效的結構索引；針對XML數(shù)據(jù)與全文數(shù)據(jù)的聯(lián)合索引目前存在的主要問題：缺少XM

3、L數(shù)據(jù)與全文數(shù)據(jù)的統(tǒng)一索引模型以及配套的高效協(xié)同查詢機制，本文提出了一種高效的基于統(tǒng)一索引模型的XML聯(lián)合索引。本文的研究內(nèi)容和創(chuàng)新工作主要有以下4點：
　　 (1)支持簡單路徑查詢的半動態(tài)XML結構索引研究
　　 本文在互關聯(lián)后繼樹(IRST)的基礎上，引入一種新型的相似性約束條件--κ階相似關系，以及結構索引的相似性歸并思想，提出了一種基于互關聯(lián)后繼樹且支持簡單路徑查詢的高效半動態(tài)結構索引--IRST(κ)-inde

4、x，并給出相關算法和理論證明。該索引以互關聯(lián)后繼樹為實現(xiàn)方式，以κ階相似關系為相似性約束條件，能高效地查詢簡單路徑表達式。經(jīng)實驗驗證，與國際上同類索引相比，該索引的創(chuàng)建速度更快、查詢效率更高、空間開銷更小。
　　 (2)支持分支路徑查詢的半動態(tài)XML結構索引研究
　　 本文在IRST(κ)-index的基礎上，引入一種新型的相似性約束條件--κ-l階相似關系，以及前向、后向相似度的概念，提出了一種基于互關聯(lián)后繼樹且支持分

5、支路徑查詢的高效半動態(tài)結構索引--IRST(κ，l)-index，并給出相關算法和理論證明。該索引以互關聯(lián)后繼樹為實現(xiàn)方式，以κ-l階相似關系為相似性約束條件，能高效地查詢分支路徑表達式。經(jīng)實驗驗證，與國際上同類索引相比，該索引的創(chuàng)建速度更快、查詢效率更高、空間開銷更小。
　　 (3)支持分支路徑查詢的全動態(tài)XML結構索引研究
　　 本文在M(κ)-index的基礎上，引入κ-l階互模擬關系以及前向、后向相似度的概念，提

6、出了一種支持分支路徑查詢的高效全動態(tài)結構索引--MBF(κ，l)-index，并給出相關算法和理論證明。該索引以κ-l階互模擬關系為相似性約束條件，不僅能高效地查詢分支路徑表達式，還能利用頻繁查詢路徑的查詢結果來監(jiān)督和指導索引優(yōu)化的全過程，從而有效地避免了無關索引和數(shù)據(jù)節(jié)點的過度分裂。經(jīng)實驗驗證，與國際上同類索引相比，該索引的查詢效率更高、空間開銷更小。
　　 (4)XML數(shù)據(jù)與全文數(shù)據(jù)的聯(lián)合索引技術研究
　　 本文在互