支持動態(tài)更新的XML編碼方法及小枝模式查詢算法研究.pdf

1、隨著數(shù)據(jù)庫和網(wǎng)絡(luò)技術(shù)的迅速發(fā)展,XML已經(jīng)成為網(wǎng)絡(luò)上信息表達(dá)和數(shù)據(jù)交換的事實(shí)標(biāo)準(zhǔn)。隨著XML數(shù)據(jù)的不斷增長,尤其是大規(guī)模XML數(shù)據(jù)的出現(xiàn),如何對這些XML數(shù)據(jù)進(jìn)行有效的管理和查詢成為當(dāng)前的研究熱點(diǎn)。由于XML文檔具有的半結(jié)構(gòu)特性,使得傳統(tǒng)的針對關(guān)系數(shù)據(jù)庫的查詢算法對其不再適用,因此如何高效地存儲和查詢XML數(shù)據(jù)成為新的研究課題。
　　 對于XML結(jié)構(gòu)查詢,可以通過對XML文檔樹中的結(jié)點(diǎn)或邊進(jìn)行編碼,根據(jù)編碼直接判斷結(jié)點(diǎn)之間的結(jié)構(gòu)

2、關(guān)系,而無需對原XML文檔樹進(jìn)行遍歷,從而將XML結(jié)構(gòu)查詢的計算轉(zhuǎn)化為結(jié)構(gòu)連接的計算。目前對XML文檔的編碼方法主要有區(qū)間編碼、路徑編碼等。同時,隨著不同編碼方案的研究,各種相應(yīng)的結(jié)構(gòu)查詢算法也提了出來。對于XML文檔基于結(jié)構(gòu)連接的小枝模式匹配查詢,是從文檔樹中查找與查詢模式匹配的結(jié)點(diǎn),然后將查找到的匹配結(jié)果再組裝成最終符合查詢表達(dá)式的完整樹結(jié)構(gòu)。
　　 本文首先針對已有XML編碼機(jī)制時空效率不高、對XML文檔動態(tài)更新支持不夠的

3、問題,結(jié)合前綴編碼機(jī)制的思想,提出了一種新的XML文檔樹編碼方案-EBCL編碼,該編碼方案不僅能完全高效地支持XML文檔動態(tài)更新、具有較好的查詢效率,而且大大降低了空間成本。
　　 另外,針對已有小枝模式查詢匹配算法或基于歸并有很高計算代價或非常復(fù)雜的問題,尤其是在考慮了大部分查詢表達(dá)式中只有一個結(jié)點(diǎn)是最終的輸出結(jié)點(diǎn)這個特點(diǎn)基礎(chǔ)上,提出了一種新的XML小枝模式查詢匹配算法TwigDirect。該算法和以往大部分的小枝模式查詢算法