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

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

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

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

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

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