基于共享技術(shù)的謂詞窗口數(shù)據(jù)流查詢優(yōu)化研究.pdf

1、近年來，隨著網(wǎng)絡(luò)、電信和傳感器技術(shù)的發(fā)展，數(shù)據(jù)庫技術(shù)得到了新的應(yīng)用。在其中一種應(yīng)用中，數(shù)據(jù)不再來自存儲于永久介質(zhì)的數(shù)據(jù)庫，而是以連續(xù)、快速、隨時間變化、無限的數(shù)據(jù)流的形式到達(dá)。在許多領(lǐng)域中存在這類應(yīng)用，如網(wǎng)絡(luò)監(jiān)控，網(wǎng)絡(luò)流量管理，入侵檢測，傳感器的數(shù)據(jù)處理，生產(chǎn)線管理，股市信息分析等等。 數(shù)據(jù)流具有連續(xù)性和無限性的特點，數(shù)據(jù)流管理系統(tǒng)在大多數(shù)的情況下無法處理全部的數(shù)據(jù)。為了適應(yīng)數(shù)據(jù)流的諸多特點和其實際應(yīng)用的需要，在數(shù)據(jù)流管理系統(tǒng)中

2、廣泛采用了窗口技術(shù)，對數(shù)據(jù)流中的數(shù)據(jù)進(jìn)行分片處理。目前在數(shù)據(jù)流上應(yīng)用最廣泛的是滑動窗口查詢模型。盡管滑動窗口模型能滿足數(shù)據(jù)流查詢中通常關(guān)心最近到達(dá)的數(shù)據(jù)的特點，但是它不能反映出整個數(shù)據(jù)流的變化，因此，普渡大學(xué)提出了一種新的窗口查詢模型——謂詞窗口查詢模型，并引入了負(fù)元組的概念，用以表示過期元組或不符合窗口謂詞的元組。 謂詞窗口查詢模型是一種新的窗口查詢模型，目前對它的研究還比較少。本文主要研究了基于共享技術(shù)的謂詞窗口數(shù)據(jù)流查詢優(yōu)

3、化。針對兩種不同的查詢——預(yù)定義查詢和即席查詢，分別提出了不同的優(yōu)化方法。 對于預(yù)定義查詢，由于查詢是在相關(guān)數(shù)據(jù)到來之前已經(jīng)在數(shù)據(jù)流管理系統(tǒng)定義的，可以預(yù)先制定查詢計劃進(jìn)行優(yōu)化。具體來講，就是采用多重查詢處理優(yōu)化的方法，對一組查詢語句，求出它們的公共子表達(dá)式，在查詢過程中，公共子表達(dá)式僅被執(zhí)行一次，得到一個中間結(jié)果，所有包含該公共子表達(dá)式的查詢都使用這一中間結(jié)果。這樣就使得查詢代價大為降低，提高了查詢處理的效率。 對于即

4、席查詢，由于查詢是當(dāng)需要獲得相關(guān)信息時而提交的，不能預(yù)先制定查詢計劃進(jìn)行優(yōu)化，需要動態(tài)地決定查詢執(zhí)行的過程。本文中采用了一種基于負(fù)元組的增量式結(jié)果估算方法。具體來講，由于在謂詞窗口查詢模型中引入了負(fù)元組，使得各個操作符需要處理的元組大大增加。考慮到連接操作的耗費比較大，通過設(shè)置“時間信息”元組，避免處理與相應(yīng)的正元組相同的負(fù)元組的連接操作。同時，在以前的計算結(jié)果的基礎(chǔ)上估算新的結(jié)果，避免全部重新計算，達(dá)到查詢優(yōu)化的目的。通過文中的例子可