I-XISS：一種改進的XML文檔索引存儲方法.pdf

1、XML(eXtensible Markup Language，可擴展標記語言)憑借其結構簡單、易于理解、自描述、可擴展、可跨越系統(tǒng)平臺等特性，現(xiàn)在已成為Internet上數(shù)據(jù)表示和數(shù)據(jù)交換的事實上的標準。隨著XML數(shù)據(jù)的應用日益廣泛和深入，針對XML數(shù)據(jù)的研究也受到人們的關注。如何對XML數(shù)據(jù)進行有效的存儲和查詢成為一個研究的熱點，而快速有效地查詢XML文檔的一個重要方法就是為其建立索引。 目前XML文檔的索引主要有三種類型：路

2、徑索引、節(jié)點索引、基于串的索引。其中，路徑索引可以很好地支持簡單路徑表達式的查詢，但是對于正則路徑表達式，路徑索引的效果不是很理想。節(jié)點索引可以很好地支持正則路徑表達式，但是對于長的路徑表達式，尤其是在查詢產(chǎn)生的中間結果很多的時候，節(jié)點索引的結構連接操作會代價高昂?；诖乃饕梢灾С指鞣N查詢而不用進行連接操作，但在處理含有通配符的查詢時，由于要轉化為簡單路徑表達式，所以影響了查詢的執(zhí)行效率。 節(jié)點索引的一個典型例子是XISS(

3、XML Indexing and Storage System，XML索引和存儲系統(tǒng))，它以節(jié)點編碼和三種索引結構為基礎，以三種結構連接算法為查詢方法，通過把查詢路徑表達式分解成單個的元素或屬性節(jié)點的子路徑表達式，依次查詢子路徑表達式形成中間結果，最后通過中間結果之間的結構連接算法得到最終的查詢結果。但是XISS中的子路徑概念的基本單位是一個元素節(jié)點或屬性節(jié)點，導致查詢時結構連接操作的次數(shù)過多，因此影響了查詢效率。 本文的主要工

4、作是： (1)將XISS與路徑索引的思想相結合，對XISS的索引結構進行了改進，使得改進后的索引結構既可以靈活處理正則路徑表達式，又克服了XISS中結構連接操作次數(shù)過多的缺點。改進后的索引結構簡寫為I-XISS(Improved XISS)。 (2)以I-XISS的索引結構為基礎，提出了新的分解子路徑表達式的算法，使得子路徑表達式的基本單位由原來的一個節(jié)點變成了一個簡單路徑表達式，有效減少了子路徑表達式的數(shù)目。

5、(3)提出了新的查詢算法，以I-XISS的索引結構和分解子路徑表達式的算法為基礎，通過減少中間結果的結構連接操作次數(shù)，使得查詢時間與查詢路徑的長度無關，而只與查詢路徑的復雜度和中間結果的大小有關，有效縮短了XML查詢的執(zhí)行時間。 (4) 最后構建了一個實驗系統(tǒng)，本文提出的索引結構、子路徑表達式的分解算法和查詢算法在系統(tǒng)中初步實現(xiàn)，并且對改進前后索引結構的查詢效率進行了比較，實驗數(shù)據(jù)證明，改進后的索引結構比原來的查詢效率有了較大的