基于結(jié)構(gòu)摘要思想的時態(tài)XML索引方案.pdf

1、隨著網(wǎng)絡(luò)和信息技術(shù)的發(fā)展，XML(Extensible Markup Language)已逐步成為互聯(lián)網(wǎng)上數(shù)據(jù)表示和數(shù)據(jù)交換的一種新的標(biāo)準(zhǔn)。可以預(yù)見，將來XML會成為Web信息交換的統(tǒng)一標(biāo)準(zhǔn)。通常，隨著時間推移，我們會對XML文檔進(jìn)行一些修改。之后，我們希望快速對文檔歷史信息進(jìn)行查詢。在這樣的應(yīng)用背景下，如何在XML文檔中表達(dá)時間相關(guān)的數(shù)據(jù)，跟蹤歷史信息，和恢復(fù)文檔在以前任意時刻的狀態(tài)的研究中受到越來越多的關(guān)注。 對XML(包括

2、時態(tài)XML和非時態(tài)XML)數(shù)據(jù)建立有效的索引，是左右XML數(shù)據(jù)處理性能的重要因素。在非時態(tài)XML索引研究領(lǐng)域，研究成果較多，索引總體上可以分為節(jié)點(diǎn)記錄類索引和結(jié)構(gòu)摘要類索引。而時態(tài)XML索引的研究才剛剛開始。雖然一些文獻(xiàn)提出模型和索引算法，但大多基于對版本信息的維護(hù)，尤其對于版本間數(shù)據(jù)查詢處理效率較低。同時，由于時態(tài)XML文檔中包含時間信息，文檔更新較為復(fù)雜，這就對索引更新提出了更高的要求。重新建立索引結(jié)構(gòu)，重新對節(jié)點(diǎn)編碼將嚴(yán)重影響索引

3、的效率。 本文針對時態(tài)XML文檔特點(diǎn)，提出一種新的時態(tài)XML索引方案，TF&B索引。從索引結(jié)構(gòu)、查詢算法和更新維護(hù)算法三個方面對該索引進(jìn)行介紹。 本文的主要工作在于： 1.論文對TF&B索引的結(jié)構(gòu)進(jìn)行詳細(xì)介紹，給出了構(gòu)建算法。 2.論文根據(jù)時態(tài)XML查詢表達(dá)式的特點(diǎn)，將其分為四大類進(jìn)行算法研究，最后給出查詢比較的實(shí)驗(yàn)數(shù)據(jù)。通過分析比較，證明了該索引具有較好的性能。 3.論文從時態(tài)XML文檔片段增加

4、、刪除和更新方面，對TF&B索引的更新算法進(jìn)行討論。 本文工作的意義是給出了有效索引時態(tài)XML文檔的一套完整方案，具體體現(xiàn)在以下方面：在時態(tài)XML文檔模型設(shè)計(jì)上，本文采用的模型只保存不同時刻節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系，而不是保存某些時刻的快照，從而解決了分散在不同版本間的數(shù)據(jù)查詢問題。在節(jié)點(diǎn)編碼設(shè)計(jì)上，本文采用預(yù)留編碼空間的方法，使得文檔更新時，不需進(jìn)行重新編碼。在查詢算法設(shè)計(jì)上，通過等價類劃分和聚簇存儲，減少了樹遍歷和磁盤讀取次數(shù)。在