XML文檔編碼機(jī)制的研究.pdf

1、近年來,XML在網(wǎng)絡(luò)應(yīng)用上日益發(fā)展,尤其是電子商務(wù)、web服務(wù)等一系列應(yīng)用理念的進(jìn)一步發(fā)展,XML類型的數(shù)據(jù)便成為了數(shù)據(jù)表示和交換的主流形式。作為半結(jié)構(gòu)化數(shù)據(jù)的表示模型XML從提出到現(xiàn)在只不過幾年時(shí)間,已經(jīng)顯現(xiàn)出其強(qiáng)大而廣泛的應(yīng)用前景。
　　 最近幾年,在各領(lǐng)域中XML都得到了廣泛應(yīng)用,逐漸被用來作為信息表現(xiàn)和交換的標(biāo)準(zhǔn),這使得與XML數(shù)據(jù)相關(guān)的領(lǐng)域成為研究熱點(diǎn)。由于查詢是數(shù)據(jù)庫最為頻繁的操作,所以,理所當(dāng)然的,如何提高XML數(shù)

2、據(jù)查詢的效率成為主要的研究方向之一。目前Native XML數(shù)據(jù)庫的查詢求解有以下三種算法:基于XML索引的導(dǎo)航遍歷算法;基于XML文檔編碼的結(jié)構(gòu)鏈接算法;基于XML文檔序列標(biāo)示的序列匹配算法等。在以上算法中,利用結(jié)點(diǎn)編碼進(jìn)行結(jié)構(gòu)連接的算法是主流技術(shù)之一。提出XML文檔編碼就是為了降低查詢處理的成本,提高查詢求解的效率。對(duì)于一個(gè)查詢(路徑表達(dá)式),一個(gè)較為簡單的方法是自項(xiàng)向下遍歷XML文檔樹中的結(jié)點(diǎn)來匹配路徑表達(dá)式。但是,如果為XML文

3、檔樹中嵌入有效的編碼方案,就能很快檢測(cè)出XML文檔樹中的任意兩個(gè)結(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。
　　 本文在深入研究現(xiàn)已提出的編碼方案的基礎(chǔ)上,結(jié)合了前綴編碼和區(qū)間編碼的優(yōu)點(diǎn),利用了子樹劃分的思想,首先,提出了一種基于矩陣劃分的XML文檔樹編碼MBL,該編碼方案包括三部分,進(jìn)行編碼前,要先對(duì)樹進(jìn)行矩陣劃分,以便得到矩陣編碼,剩余的兩部分編碼分別是矩陣塊內(nèi)的前綴編碼和覆蓋子樹塊得區(qū)間編碼。該編碼基本是定長的,所以,編碼長度不會(huì)隨著結(jié)點(diǎn)的插入

4、增長。該方案對(duì)某些情況下的插入代價(jià)基本為零。
　　 本文還基于MBL編碼設(shè)計(jì)了相應(yīng)的存儲(chǔ)策略,針對(duì)可能出現(xiàn)的存儲(chǔ)溢出問題給出了子樹分裂算法;基于MBL編碼自身的特點(diǎn)設(shè)計(jì)了索引機(jī)制,該索引結(jié)構(gòu)的記錄之間不需要相互保存對(duì)方的地址,提高了記錄間的獨(dú)立性,有效降低了更新代價(jià)。這樣,即使結(jié)點(diǎn)的記錄地址發(fā)生了改變,也不需要對(duì)索引進(jìn)行修改,降低了索引的維護(hù)代價(jià)。
　　 分析了基于此編碼的祖先/后裔關(guān)系的判斷,通過分析得出采用該編碼方案