XML文檔編碼機制的研究.pdf

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

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

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

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