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

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

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

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