流數(shù)據(jù)的連續(xù)查詢優(yōu)化技術(shù)

摘要：介紹了流數(shù)據(jù)、連續(xù)查詢的概念以及連續(xù)查詢的語義，描述了流數(shù)據(jù)查詢模型，并對流數(shù)據(jù)查詢優(yōu)化進(jìn)行了討論。

關(guān)鍵詞：流數(shù)據(jù);查詢優(yōu)化;滑動(dòng)窗口;持續(xù)查詢 

中圖分類號：TP311．131文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2008)01－0131－03

流數(shù)據(jù)連續(xù)查詢及優(yōu)化研究已成為當(dāng)前國際數(shù)據(jù)庫研究領(lǐng)域的一個(gè)熱點(diǎn)。金融信息監(jiān)控、網(wǎng)絡(luò)監(jiān)控和安全、電信數(shù)據(jù)管理、Web 應(yīng)用、生產(chǎn)制造以及傳感檢測等領(lǐng)域產(chǎn)生的一系列連續(xù)且有序的數(shù)據(jù)組成的序列均統(tǒng)稱為流數(shù)據(jù)。流數(shù)據(jù)具有數(shù)據(jù)量大、數(shù)據(jù)變化頻繁、需要快速響應(yīng)、查詢次數(shù)有限的特點(diǎn)。流數(shù)據(jù)的特點(diǎn)決定了不可能控制它流出的順序，也不可能存儲(chǔ)所有的數(shù)據(jù)。所以，對它的查詢、存儲(chǔ)必須由傳統(tǒng)的方式向一個(gè)新型的方式轉(zhuǎn)變，即連續(xù)查詢及動(dòng)態(tài)處理歷史數(shù)據(jù)。

流數(shù)據(jù)查詢與傳統(tǒng)數(shù)據(jù)庫查詢有很大的差異。一方面，流數(shù)據(jù)查詢是實(shí)時(shí)的、連續(xù)的，流查詢是隨著數(shù)據(jù)的到達(dá)而不斷返回查詢結(jié)果的連續(xù)查詢，是一個(gè)主動(dòng)過程。它是由數(shù)據(jù)的到達(dá)來驅(qū)動(dòng)查詢，而不是傳統(tǒng)查詢中的依靠用戶的查詢要求來驅(qū)動(dòng)查詢（這是一個(gè)被動(dòng)過程）。另一方面，流查詢是不可預(yù)知的。傳統(tǒng)查詢中的數(shù)據(jù)庫結(jié)構(gòu)是已知的，所以可以根據(jù)數(shù)據(jù)庫的規(guī)模動(dòng)態(tài)地調(diào)整查詢并進(jìn)行優(yōu)化。而對于流數(shù)據(jù)來說，數(shù)據(jù)在不斷的變化，要想優(yōu)化查詢必須動(dòng)態(tài)地處理，并且查詢結(jié)果也是近似的。流數(shù)據(jù)管理系統(tǒng)對數(shù)據(jù)的處理必須采用近似值作為處理手段，對數(shù)據(jù)精確處理既不可能也沒必要。因而各種近似值查詢算法如窗口查詢、批處理、抽樣、摘要數(shù)據(jù)結(jié)構(gòu)、隨機(jī)投影技術(shù)、特征約簡技術(shù)成為流數(shù)據(jù)查詢處理的有效技術(shù)。

1基本概念

1．1流數(shù)據(jù)

由一系列連續(xù)且有序的數(shù)據(jù)組成的序列x1…xj…xn…，稱為流數(shù)據(jù)。這些序列按照固定的次序到達(dá)，到達(dá)的時(shí)間為該序列的時(shí)間戳t1…tj…tn…。

1．2流數(shù)據(jù)查詢

流數(shù)據(jù)查詢即對流數(shù)據(jù)的實(shí)時(shí)查詢處理，也叫做連續(xù)的查詢。指在某段時(shí)間間隔內(nèi)，對在這段時(shí)間內(nèi)流入系統(tǒng)中的數(shù)據(jù)連續(xù)地執(zhí)行查詢操作；同時(shí)，新進(jìn)來的數(shù)據(jù)連續(xù)地探測查詢處理系統(tǒng)中的查詢，匹配查詢條件，返回結(jié)果。與傳統(tǒng)的查詢相比，連續(xù)的查詢在現(xiàn)有的應(yīng)用中更具有價(jià)值。

2流數(shù)據(jù)查詢

數(shù)據(jù)流查詢操作與一般的RDBMS 提供的查詢有很多相似的地方，但是由于數(shù)據(jù)流本身的特點(diǎn)，數(shù)據(jù)不再像傳統(tǒng)的存儲(chǔ)在數(shù)據(jù)庫中的數(shù)據(jù)一樣通過拉的方式獲得，而是通過推的方式提供給查詢系統(tǒng)。這要求數(shù)據(jù)流查詢機(jī)制具有更高的處理效率、更好的自適應(yīng)性以及處理突發(fā)流量進(jìn)行負(fù)載平衡的能力。

2．1流數(shù)據(jù)近似查詢模型

圖1是一個(gè)基于流數(shù)據(jù)的近似查詢模型。當(dāng)用戶發(fā)出查詢Q，經(jīng)過查詢重寫，得到一個(gè)等價(jià)重寫查詢Q′，它通過數(shù)據(jù)流處理引擎對數(shù)據(jù)流進(jìn)行查詢。在此過程中， 流數(shù)據(jù)查詢處理器在對數(shù)據(jù)流處理的同時(shí)與存儲(chǔ)概要之間不斷交互更新數(shù)據(jù)，以保持存儲(chǔ)概要的有效性和準(zhǔn)確性，數(shù)據(jù)流查詢處理器從存儲(chǔ)概要中按照概要計(jì)算規(guī)則提取查詢信息，最終將獲得的快速的近似查詢結(jié)果返回用戶。關(guān)于數(shù)據(jù)流存儲(chǔ)概要的計(jì)算，通常有水庫樣本法、直方圖法及小波法等。

如果利用傳統(tǒng)技術(shù)處理流模型，必須將數(shù)據(jù)全部存儲(chǔ)到介質(zhì)中，然后通過提交DML語句訪問存儲(chǔ)介質(zhì)來獲取精確的查詢結(jié)果。但由于流數(shù)據(jù)量大且到達(dá)速度快，傳統(tǒng)數(shù)據(jù)庫技術(shù)難以實(shí)現(xiàn)實(shí)時(shí)處理。數(shù)據(jù)流的特性決定了數(shù)據(jù)流的處理以自適應(yīng)的、近似查詢?yōu)槠浜诵募夹g(shù)。流數(shù)據(jù)管理系統(tǒng)中，傳統(tǒng)數(shù)據(jù)庫中所用的一次查詢技術(shù)被連續(xù)查詢技術(shù)取代，傳統(tǒng)數(shù)據(jù)庫只注重執(zhí)行穩(wěn)定的查詢計(jì)劃，進(jìn)行精確的回答技術(shù)已被既支持預(yù)訂查詢又支持Ad hoc查詢的流數(shù)據(jù)的技術(shù)所擴(kuò)展。

2．2連續(xù)查詢語義

假定時(shí)間為自然數(shù)集合，A(Q，t)為連續(xù)查詢Q在時(shí)間t的應(yīng)答集， 而0為起始時(shí)間，τ為當(dāng)前時(shí)間，則一個(gè)單調(diào)連續(xù)查詢Q在時(shí)間τ的應(yīng)答集為

可以看出，如果為非單調(diào)模式，即查詢結(jié)果集中的元組可能隨時(shí)間變化而發(fā)生狀態(tài)變化，這時(shí)每次計(jì)算均需要從頭開始。而在單調(diào)模式下，連續(xù)查詢只需要計(jì)算新到的數(shù)據(jù)單元，將所得的新元組子集添加到結(jié)果集合中，這樣就節(jié)省了大量的計(jì)算資源。A.Arasu等人[1]對數(shù)據(jù)流中連續(xù)查詢的單調(diào)模式和非單調(diào)模式均作了比較深入的探討。當(dāng)連續(xù)查詢中存在＝、≠、〈、〉這些比較算子時(shí)，一般情況下此查詢?yōu)閱握{(diào)查詢。 

2．3流數(shù)據(jù)連續(xù)查詢常見的操作

現(xiàn)有流數(shù)據(jù)查詢語言支持的連續(xù)查詢操作有選擇、連接、窗口查詢、嵌套的聚集、多路復(fù)用與多路分解等，未來支持的操作可能會(huì)隨著需求變化而增加。 

選擇：所有的流應(yīng)用均需要復(fù)雜過濾功能的支持。

連接：包括流與靜態(tài)元數(shù)據(jù)的連接與多重流之間的連接。

窗口查詢：所有上述查詢類型返回結(jié)果可能都會(huì)受限在一窗口內(nèi)(如最近1天或最近到達(dá)的100個(gè)元組)。

3查詢優(yōu)化

3．1流數(shù)據(jù)查詢優(yōu)化與傳統(tǒng)數(shù)據(jù)庫查詢優(yōu)化的區(qū)別

查詢優(yōu)化在數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位。傳統(tǒng)RDBMS大都采用基于代價(jià)的優(yōu)化，這種方法要求優(yōu)化器要考慮系統(tǒng)中的各種參數(shù)，如表的大小（cardinalities）、存取路徑、緩沖區(qū)大小、數(shù)據(jù)的分布等，再通過某種代價(jià)模型計(jì)算出各種查詢執(zhí)行方案的執(zhí)行代價(jià)，然后選取代價(jià)最小的執(zhí)行方案。流數(shù)據(jù)中流入元組數(shù)目是未知的或者是不可能知道的，所以這種基于代價(jià)優(yōu)化方法對于無限流數(shù)據(jù)的在線處理不適合。例如在基于代價(jià)的傳統(tǒng)數(shù)據(jù)庫優(yōu)化策略中，σ1(σ2(E))=σ2(σ1(E))，因此查詢計(jì)劃σ1(σ2(E))與查詢計(jì)劃σ2(σ1(E))代價(jià)是相等的，但是在流數(shù)據(jù)查詢時(shí)，在同樣情況下，它們的輸出速率可能不一樣，如圖2所示。在圖例條件下，σ2(σ1(E))輸出速率為1元組/s，而σ1(σ2(E))輸出速率為10元組/s，因此在基于速率的查詢計(jì)劃中，σ1(σ2(E))計(jì)劃要優(yōu)于σ2(σ1(E))計(jì)劃。

傳統(tǒng)的RDBMS往往將選擇操作下推，盡量靠近查詢樹的葉節(jié)點(diǎn)。但是這個(gè)規(guī)則不適合數(shù)據(jù)流 ，因?yàn)檫@樣做就無法對連接操作進(jìn)行共享處理。文獻(xiàn)[2]提出一種合理放置選擇操作的策略，用于優(yōu)化連續(xù)查詢。所以，流數(shù)據(jù)查詢優(yōu)化方法與傳統(tǒng)查詢優(yōu)化方法存在著很大的區(qū)別。

傳統(tǒng)RDBMS的查詢優(yōu)化器利用數(shù)據(jù)字典中的元數(shù)據(jù)、關(guān)系代數(shù)的性質(zhì)和系統(tǒng)性能選擇一個(gè)占用時(shí)間盡可能少的查詢計(jì)劃。這種優(yōu)化是在查詢執(zhí)行之前的一種靜態(tài)優(yōu)化。而在數(shù)據(jù)流管理系統(tǒng)中，由于數(shù)據(jù)流的流速、數(shù)據(jù)本身的特性，在查詢執(zhí)行過程中會(huì)出現(xiàn)突發(fā)流量等動(dòng)態(tài)特性和特殊情況，系統(tǒng)性能也會(huì)隨著數(shù)據(jù)特性的變化動(dòng)態(tài)地波動(dòng)，需要在查詢執(zhí)行過程中對查詢計(jì)劃進(jìn)行動(dòng)態(tài)優(yōu)化，以適應(yīng)數(shù)據(jù)流的流速、流中數(shù)據(jù)的變化。

3．2流數(shù)據(jù)查詢優(yōu)化度量方法

流數(shù)據(jù)查詢優(yōu)化度量的方法有：基于速率(流速)的度量方法、基于資源（內(nèi)存）消耗度量方法、基于QoS的度量方法。文獻(xiàn)[3]給出了一個(gè)基于單位時(shí)間查詢的度量標(biāo)準(zhǔn)，根據(jù)查詢延遲和使用的存儲(chǔ)容量作為衡量標(biāo)準(zhǔn)可度量查詢優(yōu)化的程度。S.Viglas[4]提出一個(gè)基于速率(流速)的查詢優(yōu)化算法。實(shí)驗(yàn)結(jié)果表明，該方法生成的查詢執(zhí)行計(jì)劃能夠?qū)⑤敵鏊俾首畲蠡Ｋ惴ㄔ趯ΨQ非阻塞操作執(zhí)行情況下，考慮不同信息源有著不同的傳送速率，每個(gè)操作用非阻塞查詢計(jì)劃來表達(dá)，通過引入以上兩個(gè)參數(shù)進(jìn)行查詢優(yōu)化，定義每個(gè)操作的查詢輸出率作為查詢操作輸入元組速率的函數(shù)。

其中:r(t)為輸入元組速率對時(shí)間t的函數(shù)。查詢優(yōu)化問題為：給定一查詢計(jì)劃Pi的集合和輸出速率rPi(t)，最優(yōu)化輸出量，即給定一個(gè)輸出量N，想找出實(shí)現(xiàn)這個(gè)輸出所需的最小時(shí)間。具體計(jì)算方法為給定一個(gè)計(jì)劃集合，一個(gè)時(shí)間點(diǎn)t0，計(jì)算積分，可得到t0時(shí)輸出多少元組，要找出產(chǎn)生最大輸出的查詢計(jì)劃。這種方法要求流的速率大小已知或可以估計(jì)其大小。不是尋找代價(jià)最小的計(jì)劃，而是尋找輸出速率最大的計(jì)劃。

優(yōu)化總的目標(biāo)是：使用盡可能少的資源，得到高的QoS，獲得大的輸出速率、查詢精度。但是它們之間往往是矛盾的，需要根據(jù)具體對象進(jìn)行一個(gè)折中。

3．3查詢優(yōu)化技術(shù)

3．3．1查詢重寫?yīng)?/p>

在關(guān)系數(shù)據(jù)庫中，查詢重寫是一個(gè)非常有用的技術(shù)，用來最小化連接操作代價(jià)。在基于速率的優(yōu)化模型中，文獻(xiàn)[4]在流的join次序方面做了一些初步的工作，通過對查詢重寫，達(dá)到輸出速率最大化。文獻(xiàn)[5]在主存窗口連接方面也做了一些工作。已有的許多查詢語言均引入了一些查詢重寫技術(shù)，如滑動(dòng)窗口上[1]的選擇和投影操作的可交換性。

3．3．2自適應(yīng)[6~8]

所謂適應(yīng)性指的是，查詢計(jì)劃能夠動(dòng)態(tài)地隨著查詢操作處理時(shí)間的變化、謂詞的選擇率改變及流數(shù)據(jù)到達(dá)速率的變化而改變[7]。最初的自適應(yīng)查詢計(jì)劃是中間查詢的重估算。為了進(jìn)一步增加自適應(yīng)性，Eddies方法取代了維護(hù)一個(gè)生硬的樹結(jié)構(gòu)的查詢計(jì)劃，而是執(zhí)行每個(gè)元組的調(diào)度，并通過補(bǔ)償查詢計(jì)劃的操作項(xiàng)來路由。實(shí)際上，查詢計(jì)劃動(dòng)態(tài)地重新排序以匹配當(dāng)前的系統(tǒng)條件。這是通過元組路由策略，試圖去發(fā)現(xiàn)哪一個(gè)操作項(xiàng)可選并運(yùn)行快，哪個(gè)操作項(xiàng)就先調(diào)度來實(shí)現(xiàn)。然而，在結(jié)果的自適應(yīng)與分別路由每一個(gè)元組的開銷之間存在重要的平衡問題。

3．3．3物化視圖

在查詢優(yōu)化問題中，找到某個(gè)物化視圖集的查詢重寫就能夠獲得一種更有效的查詢執(zhí)行方案。關(guān)于查詢優(yōu)化，用預(yù)先物化的視圖計(jì)算查詢能夠提高查詢處理的速度，主要是因?yàn)樵诓樵円晥D時(shí)對查詢所需要的計(jì)算已經(jīng)完成了。當(dāng)視圖和查詢包含分組和聚集操作時(shí)，這種改進(jìn)在應(yīng)用中特別重要，它可通過計(jì)算出的聚集視圖來計(jì)算查詢，從而有效減少對多個(gè)視圖的聚集計(jì)算量。由此，計(jì)算一個(gè)查詢執(zhí)行方案的問題(必須存取物理存儲(chǔ)模式)與尋找基于視圖的查詢計(jì)算相關(guān)[9]。一個(gè)查詢集Q包含另一查詢集Q′，若Q至多且有Q′的不同能力。或更形式化地說，若對于每對實(shí)例I1、I2，如果有Q是相同的，則它們有Q′也是相同的。考察用視圖重寫查詢，該查詢由基于簡單關(guān)系表達(dá)式的簡單聚集來表示。

3．3．4負(fù)載脫落技術(shù)

當(dāng)突發(fā)流量超過系統(tǒng)的處理能力，如果不采取相應(yīng)的措施，會(huì)導(dǎo)致整個(gè)系統(tǒng)的吞吐量和響應(yīng)時(shí)間都惡化。負(fù)載脫落通過丟棄一定數(shù)量的數(shù)據(jù)，在犧牲部分準(zhǔn)確性和完整性的條件下，保證系統(tǒng)的性能。負(fù)載脫落算法可以根據(jù)采用的處理方式分為兩種，即隨機(jī)負(fù)載脫落算法和基于語義的負(fù)載脫落算法。

隨機(jī)負(fù)載脫落是指在發(fā)現(xiàn)數(shù)據(jù)輸入超出系統(tǒng)處理能力時(shí)，通過按一定的比重隨機(jī)丟棄部分元組保證系統(tǒng)的正常運(yùn)行。基于語義的負(fù)載脫落，通過用戶對流處理語義的理解，有選擇地丟棄一部分元組，使元組損失對系統(tǒng)性能和輸出結(jié)果的影響最小化。目前普遍采用的負(fù)載脫落算法一般是基于語義的。基于語義的負(fù)載脫落算法與系統(tǒng)的上下文有關(guān)，主要考慮的問題是：何時(shí)、何地以及如何進(jìn)行。D.Carney等人提出了通過丟棄元組實(shí)現(xiàn)的隨機(jī)負(fù)載脫落和通過過濾元組實(shí)現(xiàn)的語義負(fù)載脫落。過濾指有控制地丟棄一些不重要的元組來保證系統(tǒng)的QoS。B.Babcock等人指出了D.Carney等人的不足，即該基于語義的負(fù)載脫落并不能有效地保證查詢的精確性，從而提出改善精確性的方法，并通過配置隨機(jī)抽樣算子來具體實(shí)現(xiàn)基于語義的負(fù)載脫落。Stream與Aurora系統(tǒng)均采用了負(fù)載脫落技術(shù)。

抽樣和負(fù)載脫落雖減少了內(nèi)存占用，但增大了查詢結(jié)果誤差。假定知道每兩次操作的準(zhǔn)確度和查詢使用的存儲(chǔ)容量的關(guān)系，便可以制定一個(gè)查詢評價(jià)標(biāo)準(zhǔn)。

3．3．5操作調(diào)度

操作調(diào)度主要實(shí)現(xiàn)對流速率的改變、查詢請求操作的變更、查詢響應(yīng)時(shí)間和服務(wù)質(zhì)量、載荷脫落、隊(duì)列存儲(chǔ)之間相互作用進(jìn)行協(xié)調(diào)。其目標(biāo)為:對于給定的查詢計(jì)劃和選擇率估計(jì)，通過操作鏈調(diào)度元組實(shí)現(xiàn):最小化總隊(duì)列存儲(chǔ)需求，最小化元組響應(yīng)時(shí)間，同時(shí)還要考慮一些元組存在饑餓的危險(xiǎn)，而操作鏈調(diào)度元組又不能超過存儲(chǔ)邊界。操作調(diào)度需要在準(zhǔn)確性與資源之間進(jìn)行權(quán)衡。這里資源包括存儲(chǔ)空間、計(jì)算及I/O。準(zhǔn)確性是分配到查詢和操作上的資源函數(shù)。全局最優(yōu)問題為:輸入為多個(gè)可選擇的查詢計(jì)劃，目標(biāo)為選擇計(jì)劃，合理地分配資源，最優(yōu)化查詢結(jié)果的準(zhǔn)確性。

3．3．6其他策略

流數(shù)據(jù)查詢優(yōu)化是一個(gè)復(fù)雜的問題，需要考慮很多方面，如資源、QoS、數(shù)據(jù)流入速率、操作的處理速率等多種因素。所以在優(yōu)化時(shí)：a)基于增量數(shù)據(jù)庫的連續(xù)查詢，僅處理數(shù)據(jù)庫中變化的數(shù)據(jù)，而不是大面積刷新信息;b)多線程的并行操作，減少瓶頸，提高查詢速度;c)相似性查詢合并處理，避免產(chǎn)生運(yùn)算瓶頸;d)共享計(jì)算。當(dāng)數(shù)據(jù)流系統(tǒng)中存在很多查詢時(shí)，共享計(jì)算就顯得非常重要。系統(tǒng)的擴(kuò)展性能夠通過共享計(jì)算或者多查詢優(yōu)化措施來達(dá)到。在NiagaraCQ系統(tǒng)中，一些具有相同子表達(dá)式的查詢被共享執(zhí)行，性能提升很大， Madden等人擴(kuò)展了適應(yīng)性Eddy架構(gòu)，能夠?qū)τ诙鄠€(gè)查詢共享計(jì)算和內(nèi)存。

流查詢優(yōu)化方面的研究，國外作了一些研究[5，7，10，11]，但還不是很成熟。國內(nèi)在此方面的研究很少。總之，該方面還有待于進(jìn)一步研究。

4查詢系統(tǒng)原型

近幾年來，國外許多數(shù)據(jù)庫研究者在數(shù)據(jù)流查詢處理技術(shù)方面開展了大量的研究工作，并取得了一些研究成果。1）斯坦福大學(xué)的Stream項(xiàng)目[12]其研究內(nèi)容涵蓋了數(shù)據(jù)流查詢處理的各個(gè)方面，如近似查詢處理、數(shù)據(jù)流查詢語言的定義等方面，拓展了SQL語言在數(shù)據(jù)流上的處理功能，開發(fā)連續(xù)查詢和關(guān)系的查詢語言。通過特殊的窗口操作項(xiàng)將流數(shù)據(jù)轉(zhuǎn)換為關(guān)系處理，并將結(jié)果轉(zhuǎn)換為數(shù)據(jù)流；同時(shí)采用了負(fù)載脫落等技術(shù)進(jìn)行查詢優(yōu)化。

2)布朗大學(xué)的Aurora[13]是一個(gè)應(yīng)用于監(jiān)控的面向工作流的系統(tǒng)。它允許用戶通過安排盒子(操作項(xiàng))和箭頭(操作項(xiàng)間的工作流)來創(chuàng)建查詢計(jì)劃。Aurora提供了基于時(shí)間響應(yīng)時(shí)間的QoS方案。

3)美國加州大學(xué)伯克利分校的TelegraphCQ[14]它用于連續(xù)數(shù)據(jù)流的處理，其重點(diǎn)在于共享查詢估算和自適應(yīng)查詢處理。

4)威斯康星州立大學(xué)的NiagaraCQ[15]是一個(gè)為監(jiān)控動(dòng)態(tài)Web目錄而設(shè)計(jì)的執(zhí)行多個(gè)連續(xù)查詢系統(tǒng)。它在許多查詢中使用了分組連續(xù)查詢技術(shù)。而該技術(shù)的使用提高了查詢的效率。

5結(jié)束語

查詢是數(shù)據(jù)庫最重要的操作，查詢優(yōu)化對提高系統(tǒng)性能至關(guān)重要。本文對流數(shù)據(jù)連續(xù)查詢過程、查詢常用操作、查詢優(yōu)化進(jìn)行了比較詳細(xì)的討論，并對流數(shù)據(jù)查詢優(yōu)化與傳統(tǒng)查詢優(yōu)化進(jìn)行了比較。傳統(tǒng)RDBMS大都采用基于代價(jià)的優(yōu)化，由于流數(shù)據(jù)中流入元組數(shù)目是未知或是不可能知道的，這種基于代價(jià)優(yōu)化方法對于無限流數(shù)據(jù)的在線處理不適合。

由于篇幅所限，本文對流數(shù)據(jù)的查詢及優(yōu)化只是作了簡單討論，查詢優(yōu)化深入研究將以后進(jìn)行詳細(xì)的討論。

參考文獻(xiàn)：

[1]ARASU A，BABU S，WIDOM J.An abstract semantics and concrete language for continuous queries over streams and relations[EB/OL].(2002 05－07）.[2006 11 10].http://dbpubs.stanford.edu:8090/pub/.

[2]CHEN J，DEWITT D J，NAUGHTON J F.Design and evalution of alternative selection placement strategies in optimizing continuous queries[C]//Proc ofICDE.2002:345－356.

[3]CHANDRASEKARAN S，F(xiàn)RANKLIN M J.Streaming queries over streaming data[C]//Proc of Int Conf on Very Large Data Bases.2002:203－214.

[4]VIGLAS S，NAUGHTON J.Rate based query optimization for strea ming information sources[C]//Proc ofSIGMOD.2002:37－48.

[5]GOLAB L，OZSU M T.Processing sliding window multi joins in continuous queries over data streams[C]//FREYTAG J C，et al.Proc of the 29th Int’l Conf on Very Large Data Bases.Berlin: Morgan Kaufmann Publishers，2003:500－511.

[6]AVNUR R，HELLERSTEIN J.Continuously adaptive query processing[C]//Proc of ACM Int Conf on Management of Data.2000:261－272.

[7]MADDEN S，SHAH M，HELLERSTEIN J，et al.Continuously adaptive continuous queries over streams[C]//Proc ACM Int Conf on Management of Data.2002:49－60.

[8]RAMAN V，DESHPANDE A，HELLERSTEIN J M.Using state modu￣les for adaptive query processing[C]//Proc of the 19th Int’l Conf Data Engineering(ICDE).Los Alamitos: IEEE Computer Society Press，2003:353－364.

[9]陳昕，宋瀚濤.基于數(shù)據(jù)流的近似查詢計(jì)算及其應(yīng)用研究[J].計(jì)算機(jī)應(yīng)用研究，2003，20(11):113 114，122.

[10]HAMMAD M A，F(xiàn)RANKLIN M J，AREF W G，et al.Scheduling for shared window joins over data streams[C]//Proc ofVLDB.2003:297－308.

[11]KANG J，NAUGHTON J F，VIGLAS S.Evaluating window joins over unbounded streams[C]//Proc of ICDE.2003:341－352.

[12]BABCOCK B，BABU S，DATAR M，et al.Models and issues in data streams[C]//Proc of ACM Symp on Principles of Database Systems. New York:ACM Press，2002:1 16.

[13]CARNEY D，CETINTERNEL U，CHERNIACK M，et al.Monitoring streams: a new class of data management applications[C]//Proc of Int Conf on Very Large Databases.2002:215－225.

[14]CHANDRASEKARAN S，COOPER O，DESHPANDE A，et al.TelegraphCQ:continuous dataflow processing for an uncertain world[C]//Proc ofConf on Innovative Data Syst Res.2003:269－280.

［15］CHEN J，DEWITT D，TIAN F，et al.NiagaraCQ:scalable continuous query system for a Internet databases[C]// Proc of ACM Int Conf on Management of Data.2000:379－390.

[16]劉景春，王永利.數(shù)據(jù)流處理技術(shù)[J].佳木斯大學(xué)學(xué)報(bào):自然科學(xué)版，2004，22(4):556－558.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”