XML流的復(fù)雜查詢處理及其優(yōu)化技術(shù).pdf

1、XML已經(jīng)成為Intemet上數(shù)據(jù)交換的標(biāo)準(zhǔn)。XML不僅可以作為一個(gè)完整的文件傳輸，而且還有可以以一種串行數(shù)據(jù)流的方式傳輸。近年來，針對(duì)XML數(shù)據(jù)流的處理在研究領(lǐng)域引起了廣泛的興趣。XML流處理的挑戰(zhàn)是如何能有效地處理巨量的針對(duì)XML數(shù)據(jù)流的查詢集。這種查詢通常是基于路徑表達(dá)式的，如XPath、XQuery。 隨著應(yīng)用需求的增長，查詢表達(dá)式也變得越來越復(fù)雜。我們發(fā)現(xiàn)，對(duì)于具有嵌套AND／OR謂詞的復(fù)雜TwigPattem查詢，目

2、前還沒有有效的處理方法。為此，我們開發(fā)了一個(gè)稱為LeoXSQ的XML流處理系統(tǒng)。在LeoXSQ中，我們提出一種新的方法解決上述查詢問題。圍繞LeoXSQ，我們還開發(fā)了節(jié)點(diǎn)緩存管理組件和基于DTD的查詢優(yōu)化組件。本文的主要貢獻(xiàn)概括如下： 1)提出一種新的方法處理具有嵌套AND／OR謂詞的復(fù)雜twigpattern查詢。在該方法中，將AND／OR謂詞作為單獨(dú)的抽象語法樹來處理，利用基于運(yùn)行時(shí)棧的算法，結(jié)合自頂向下與自底向上的過程，有

3、效處理針對(duì)XML流的復(fù)雜twigpattem查詢。 2)將所有twigpattem組合成單個(gè)可共享前綴的查詢樹，從而可以節(jié)省查詢處理的空間與時(shí)間，并以輸入的XML流順序單遍處理所有的查詢。通過對(duì)查詢樹中邏輯表達(dá)式進(jìn)行公共子表達(dá)式的共享處理與短路計(jì)算，進(jìn)一步提高了查詢處性能。 3)提出了一種針對(duì)單個(gè)查詢的基于語義鏈的緩存管理算法，并將其擴(kuò)展并應(yīng)用到前綴共享的多查詢環(huán)境下。該算法能夠以盡可能小的緩存空間處理遞歸嵌套文檔與一對(duì)