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

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

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

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

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