基于滑動窗口的數(shù)據(jù)流查詢處理技術(shù)的研究與實現(xiàn).pdf

1、隨著網(wǎng)絡(luò)的發(fā)展，許多應(yīng)用中的數(shù)據(jù)不再是數(shù)據(jù)庫中靜態(tài)的數(shù)據(jù)，而是以一種流的方式在線到達的動態(tài)數(shù)據(jù)。這樣的數(shù)據(jù)具有數(shù)據(jù)無界，數(shù)據(jù)量大，流速快，并且要求實時處理等特性，這種新型的數(shù)據(jù)被稱為流數(shù)據(jù)。對應(yīng)的，包含流數(shù)據(jù)的應(yīng)用被稱為數(shù)據(jù)流的應(yīng)用。而這種新型的數(shù)據(jù)使得傳統(tǒng)的查詢處理方法產(chǎn)生了很多的問題，比如數(shù)據(jù)的無限性就使得傳統(tǒng)的阻塞處理方法變得無效。針對數(shù)據(jù)流應(yīng)用中產(chǎn)生的問題，專家學(xué)者們開展了廣泛的研究工作。如同傳統(tǒng)數(shù)據(jù)庫中存在數(shù)據(jù)庫管理系統(tǒng)一樣，

2、在研究數(shù)據(jù)流時需要開發(fā)數(shù)據(jù)流管理系統(tǒng)，這樣的系統(tǒng)負責(zé)對流式數(shù)據(jù)進行查詢處理。 數(shù)據(jù)流管理系統(tǒng)中的核心是查詢處理功能模塊。通常情況下，在數(shù)據(jù)流上基本的查詢處理包括選擇、投影和連接(SPJ)操作。相對于選擇與投影，連接操作更為復(fù)雜。由于數(shù)據(jù)流的無限性和連接操作的阻塞性質(zhì)，使得在數(shù)據(jù)流上的連接操作必須要加以限制。因此滑動窗口的概念也就很自然的引入到數(shù)據(jù)流中，通過對處理的數(shù)據(jù)加上滑動窗口的限制，變傳統(tǒng)的阻塞操作為流上的非阻塞操作。對流上

3、連接操作的研究也是廣泛的展開，但是當(dāng)前的研究都是針對于等值連接來開展的，并沒有考慮到非等值連接操作的處理該如何進行。然而在一些實際的應(yīng)用中非等值連接的查詢處理也是十分重要的。例如在線拍賣的應(yīng)用中，需要對出價時間與拍賣商品的有效時間進行比較從而檢查系統(tǒng)中注冊的查詢的合法性。因此我們對非等值連接操作也會進行詳細介紹。 另外，由于數(shù)據(jù)流的特性，通常情況下數(shù)據(jù)流的查詢處理都是在主存中進行的，其目的是為了避免頻繁的磁盤讀取操作，從而提高了

4、查詢處理的效率。除此之外，如果直接對流數(shù)據(jù)進行查詢處理無疑效率是很低的，為了能夠進一步的提高效率，我們采用了基于紅黑樹索引的查詢處理方法。紅黑樹易于建立和維護，所以這種數(shù)據(jù)結(jié)構(gòu)是一種適用于主存的數(shù)據(jù)結(jié)構(gòu)。通過紅黑樹索引的技術(shù)能夠提高查詢處理的效率。這樣在查詢處理過程中將首先對流式數(shù)據(jù)建立索引，而后利用索引進行高效的查詢處理。 我們開發(fā)了數(shù)據(jù)流管理原型系統(tǒng)RealStream，在多流多查詢環(huán)境下能夠?qū)α鲾?shù)據(jù)進行基本的查詢處理以及優(yōu)