一種基于XML數(shù)據(jù)流查詢算法的設(shè)計與實現(xiàn).pdf

1、隨著互聯(lián)網(wǎng)的迅猛普及，網(wǎng)絡(luò)在人們生活中所占的比重也越來越大，網(wǎng)絡(luò)中出現(xiàn)大量與XML數(shù)據(jù)流有關(guān)的應(yīng)用，比如網(wǎng)絡(luò)日志、股票分析、互聯(lián)網(wǎng)監(jiān)控、數(shù)據(jù)安全管理、位置信息、電子信息查詢等。以XML數(shù)據(jù)流為形式傳輸?shù)臄?shù)據(jù)有以下特點：數(shù)據(jù)量較大，而且不可預(yù)知；所有的數(shù)據(jù)都是在線到達(dá)，實時性高，并且無法確定其到達(dá)的順序。顯而易見，如果按照傳統(tǒng)的數(shù)據(jù)管理方式進(jìn)行處理將會非常困難而且浪費資源，因為傳統(tǒng)的數(shù)據(jù)管理方式中的數(shù)據(jù)都是可以預(yù)知的，所有的數(shù)據(jù)都是預(yù)先存

2、儲的。近幾年，研究人員已經(jīng)提出很多種對于XML數(shù)據(jù)流的查詢算法，如TurboXPath和StreamTX算法等。但TurboXPath已被證明在遞歸調(diào)用時存在潛在的隱患，StreamTX對于處理Parent-Child(PC)關(guān)系的查詢時，會有很高的計算代價，在效率和靈活性上一直不能體現(xiàn)出令人滿意的性能，所以設(shè)計一種更有效的查詢算法成為了當(dāng)務(wù)之急。
　　針對以上問題，提出一種XML數(shù)據(jù)流小枝匹配算法TwigPM，在處理可能具有復(fù)雜

3、的遞歸、層次結(jié)構(gòu)的XML數(shù)據(jù)流時能通過獲取查詢節(jié)點的結(jié)構(gòu)關(guān)系，進(jìn)行有效的剪枝操作，節(jié)省了存儲數(shù)據(jù)所占用的內(nèi)存空間，避免了匹配的過程中可能產(chǎn)生的大量中間結(jié)果。算法功能分為兩部分，第一部分得到查詢樹各節(jié)點的結(jié)構(gòu)關(guān)系（包括父親-孩子關(guān)系和祖先-后代關(guān)系），并將不同性質(zhì)的節(jié)點進(jìn)行分類；第二部分是剪枝和匹配過程。對于先后到達(dá)的元素事件，根據(jù)第一部分的節(jié)點分類對進(jìn)行剪枝操作，移除一定不會存在于最終結(jié)果中的節(jié)點元素，并且在每個與查詢根節(jié)點對應(yīng)的End