動態(tài)XML編碼技術(shù)研究.pdf

1、隨著網(wǎng)絡(luò)應(yīng)用的快速發(fā)展,XML(eXtonsible Markup Language)數(shù)據(jù)正成為主流的數(shù)據(jù)形式,如何對XML數(shù)據(jù)建立有效索引進(jìn)而實現(xiàn)高效查詢是當(dāng)前的研究熱點。大部分XML相關(guān)索引和查詢技術(shù)基于某種對XML樹的編碼方法。XML編碼方法保存了文檔樹的結(jié)構(gòu)信息,使得在執(zhí)行查詢時不必遍歷整個XML文檔。傳統(tǒng)的區(qū)間編碼方法和前綴編碼方法支持XML節(jié)點間位置關(guān)系和結(jié)構(gòu)關(guān)系計算,但是不能有效處理文檔更新,一旦更新發(fā)生,整個樹需要重新編

2、碼,系統(tǒng)代價高。為解決該問題,研究人員提出了動態(tài)XML編碼方法,包括浮點數(shù)區(qū)間、CDBS(Compact Dynamic Binary String)、QED(Dynamic Quaternary Encoding)以及DDE(Dynamic Dewey)等。動態(tài)XMK編碼方法一定程度上避免了文檔更新時的重新編碼,但仍存在時空開銷大、對傾斜插入敏感、不能重用已刪編碼等問題。本文研究集中于動態(tài)XML編碼機制的性能優(yōu)化。XML首先,XML文

3、檔更新涉及節(jié)點插入和刪除,當(dāng)在刪除位置插入新節(jié)點時,如果新節(jié)點能夠?qū)σ褎h編碼進(jìn)行重用,則可以控制編碼長度的增長速度,提高查詢性能。CDBS和QED的編碼重用已經(jīng)有相關(guān)研究,而對于DDE編碼,卻是一個難點?；赟tern-Brocot樹,提出了DDE編碼的改進(jìn)方法——IDD(ImprovodDDE)。IDD將最短位長中間編碼賦予新節(jié)點,能夠?qū)σ褎h編碼進(jìn)行重用,有效控制了刪除和操作都發(fā)生的更新環(huán)境下DDE編碼位長,提高了XML頻繁更新時的編

4、碼效率和查詢性能。
　　 此外,針對已有動態(tài)區(qū)間編碼方法普遍存在的初始編碼空間復(fù)雜度高,傾斜插入編碼長度增長迅速等問題,本文提出了新的適用于XML文檔更新環(huán)境下的區(qū)間編碼方法-DCLS(Dynamic Containment Labeling Scheme)。DCLS利用整數(shù)進(jìn)行初始編碼,具有計算簡單,額外空間復(fù)雜度低、存儲效率和查詢性能高等優(yōu)點;同時,DCLS將整數(shù)視為特殊向量,不僅支持文檔更新,而且更新效率高,特別是傾斜插入