基于Bloom Filter的路徑表達(dá)式查詢處理.pdf

1、近年來，XML語言已經(jīng)成為了互聯(lián)網(wǎng)上數(shù)據(jù)表示和交換事實(shí)上的標(biāo)準(zhǔn)。隨著Web服務(wù)和個(gè)性化信息訂閱等應(yīng)用的蓬勃發(fā)展，越來越多的信息以XML的格式通過網(wǎng)絡(luò)被發(fā)布和交換。在這些應(yīng)用中，XML數(shù)據(jù)以數(shù)據(jù)流的形式不斷地快速到達(dá)，而針對(duì)XML數(shù)據(jù)的查詢是大量的路徑表達(dá)式，傳統(tǒng)的查詢處理技術(shù)在性能上已經(jīng)不能夠滿足應(yīng)用的需求。在XML數(shù)據(jù)流上對(duì)大量的路徑表達(dá)式進(jìn)行查詢處理是科研技術(shù)人員所面臨的一個(gè)新的挑戰(zhàn)。 本文圍繞XML數(shù)據(jù)流的查詢處理問題展開

2、研究工作，分別探討了針對(duì)簡(jiǎn)單路徑表達(dá)式和復(fù)雜路徑表達(dá)式的查詢處理技術(shù)，提出了新的處理方法，并通過實(shí)驗(yàn)驗(yàn)證了所提出方法的有效性和高效性。同時(shí)，本文就XML數(shù)據(jù)流處理引擎的設(shè)計(jì)進(jìn)行了探討，并實(shí)現(xiàn)了一個(gè)原型系統(tǒng)。論文的主要貢獻(xiàn)可以總結(jié)為如下幾點(diǎn)： ·本文首先提出了將BloomFilter結(jié)構(gòu)應(yīng)用于解決XML數(shù)據(jù)流過濾問題的方法，該方法可以有效地支持對(duì)簡(jiǎn)單路徑表達(dá)式中的通配符㈣’號(hào)和后代軸“／／”的處理。同時(shí)本文設(shè)計(jì)了前綴過濾的方法，用

3、于減少解析過程中所生成候選路徑的數(shù)量，提高過濾處理的性能。詳盡的對(duì)比實(shí)驗(yàn)表明，本文提出的方法在創(chuàng)建路由表時(shí)的性能和所創(chuàng)建路由表的大小兩個(gè)方面明顯優(yōu)于已有的處理方法。同時(shí)，在查詢集很大并且XML文檔深度相對(duì)較小的情況下，本文提出的方法在過濾性能上也要優(yōu)于已有的方法。 ·本文提出了將包含有分支結(jié)構(gòu)的復(fù)雜路徑表達(dá)式分解成一組簡(jiǎn)單路徑表達(dá)式，在對(duì)簡(jiǎn)單路徑表達(dá)式進(jìn)行過濾處理的基礎(chǔ)上，實(shí)現(xiàn)對(duì)復(fù)雜路徑表達(dá)式進(jìn)行查詢處理的方法。與已有的方法不同

4、，本文所提出的方法以簡(jiǎn)單路徑過濾引擎輸出的查詢字符串流作為輸入，可以支持對(duì)元素內(nèi)容約束的處理，同時(shí)可以以連續(xù)查詢(ContinuousQueries)的方式實(shí)現(xiàn)對(duì)復(fù)雜路徑表達(dá)式的查詢處理。本文通過實(shí)驗(yàn)將所提出的處理方法與已有方法進(jìn)行了對(duì)比，證明該方法在對(duì)復(fù)雜路徑表達(dá)式的查詢處理上具有較好的性能。 ·本文在簡(jiǎn)單路徑表達(dá)式和復(fù)雜路徑表達(dá)式查詢處理技術(shù)的研究基礎(chǔ)之上，設(shè)計(jì)和實(shí)現(xiàn)了一個(gè)XML數(shù)據(jù)流處理引擎一一XSTRfXMLSTReam