杜 紅

（山西職業(yè)技術(shù)學(xué)院，山西 太原 030006）

0 引言

目前，學(xué)術(shù)界將具有“實時、連續(xù)、潛在無界、有序（隱含的通過到達時間或者明確的時間戳）”這些特征的數(shù)據(jù)項的序列稱為“數(shù)據(jù)流（Data Stream）”，數(shù)據(jù)流同時具備了時效性、實時性、無限性和瞬間性等特點。而對于嵌入式系統(tǒng)，IEEE（國際電氣和電子工程師協(xié)會）給出的定義為：嵌入式系統(tǒng)是“用于控制、監(jiān)視或者輔助操作機器和設(shè)備的裝置”。嵌入式系統(tǒng)具有“嵌入”、“專業(yè)性”、“計算機”的基本要素和特征。

本文的研究目標(biāo)是：設(shè)計一個可以應(yīng)用于嵌入式系統(tǒng)的數(shù)據(jù)流查詢系統(tǒng)架構(gòu)。這個系統(tǒng)被部署在無線網(wǎng)絡(luò)環(huán)境中，系統(tǒng)中所需要處理的數(shù)據(jù)流對象主要由傳感器數(shù)據(jù)流構(gòu)成，而且這些數(shù)據(jù)流都是數(shù)值型的數(shù)據(jù)。該系統(tǒng)在實現(xiàn)對用戶感興趣的敏感數(shù)據(jù)實時提取的同時，實現(xiàn)對數(shù)據(jù)的過濾與篩選，以有效減少在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)流量，使用戶終端能夠得到更加優(yōu)質(zhì)的數(shù)據(jù)。

1 系統(tǒng)硬件平臺

嵌入式系統(tǒng)可以使用的硬件資源非常少，通常內(nèi)存在幾kB到幾十MB 范圍內(nèi)；同時對實時性的要求很高，該特點與數(shù)據(jù)流的實時性特點是完全一致的。這一點對該系統(tǒng)設(shè)計工作提出了很高的要求，既要盡最大可能地減少內(nèi)存的資源占用，又要提高效率、縮短處理時間。

本系統(tǒng)的嵌入式硬件平臺為基于S3C44B0X 的實驗板，這款實驗板的CPU 為Samsung S3C44B0X（ARM7 內(nèi) 核，主 頻 為66 MHz），8MB SDRAM ，2MB FLASH。嵌入式軟件開發(fā)環(huán)境為UCLinux（2.4版本的內(nèi)核），軟件開發(fā)工具為GNU，交叉編譯工具采用了Arm－elf－tools。

2 系統(tǒng)設(shè)計

2.1 存儲模塊設(shè)計

面對海量的數(shù)據(jù)，將這些數(shù)據(jù)全部保存下來是無法實現(xiàn)的，并且運行在嵌入式設(shè)備上的系統(tǒng)所能夠調(diào)用的內(nèi)存資源也非常有限。但為了能對數(shù)據(jù)流進行處理，依然需要實現(xiàn)保存部分數(shù)據(jù)功能。目前在數(shù)據(jù)流處理中存儲數(shù)據(jù)用得最多的是滑動窗口（sliding window）模型?；谌萘康幕瑒哟翱谀Ｐ腿鐖D1所示，其滑動窗口的大小是固定的。當(dāng)一個數(shù)據(jù)到來時如果滑動窗口沒有滿，則將它添加到滑動窗口中；如果此時滑動窗口已滿，則將滑動窗口中最舊的數(shù)據(jù)刪除后再插入新數(shù)據(jù)，滑動窗口用隊列實現(xiàn)。

圖1 基于容量的滑動窗口模型

2.2 聚合函數(shù)設(shè)計

聚 合 函 數(shù) 包 括 SUM、AVG、MAX、MIN、COUNT。對于聚合函數(shù)，本文采用增量式計算方法與普通的遍歷式計算方法相結(jié)合的方式來實現(xiàn)。增量式計算方法為：每當(dāng)數(shù)據(jù)進入滑動窗口時做一次計算，每次計算值都依賴于前一個值，只需要將要進入和退出滑動窗口的數(shù)據(jù)和保存值做計算就可以得出結(jié)果，查詢結(jié)果始終保存在內(nèi)存中，需要使用時只需要讀出這個結(jié)果。對于一些增量式計算方法不適用的特殊情況，則通過結(jié)合遍歷式計算方法來實現(xiàn)。

2.3 查詢指令的解析

查詢指令的結(jié)構(gòu)和語法類似于SQL 語句，如：Select＊from sl where tmp ＞10。解析時的主要工作由以下4個步驟組成：解析數(shù)據(jù)流對象、解析輸出列和聚合函數(shù)、解析查詢條件、對解析結(jié)果排序。當(dāng)用戶輸入的查詢語句不符合正確的語法要求時，需要給出錯誤提示信息。在這個方面，系統(tǒng)被設(shè)計為每當(dāng)遇到一個解析錯誤就返回一個錯誤信息提示用戶。系統(tǒng)在其解析式中會得到的信息主要包括數(shù)據(jù)流對象信息、輸出信息、聚合函數(shù)信息、查詢條件信息。其中查詢條件包括產(chǎn)生條件判斷的列、操作符、條件比較數(shù)、多重表達式邏輯關(guān)系信息。系統(tǒng)針對所采集到的數(shù)據(jù)，專門設(shè)計了特殊數(shù)據(jù)結(jié)構(gòu)來保存這些解析結(jié)果。

3 查詢引擎設(shè)計

查詢引擎的工作就是根據(jù)解析出的結(jié)果來進行查詢，以得到最終的處理結(jié)果。下面對該體系中的兩個主要模塊的設(shè)計過程進行介紹。

3.1 單數(shù)據(jù)流選擇和投影模塊

單數(shù)據(jù)流選擇和投影操作，就是通過遍歷當(dāng)前滑動窗口中存儲的數(shù)據(jù)來檢索出滿足條件的數(shù)據(jù)，之后再進行一次投影操作，并將數(shù)據(jù)保存。對單數(shù)據(jù)流做選擇和投影操作時的大致算法如下：

（1）解析出Ifmask（條件掩碼）和Getmask（投影完成后的輸出掩碼），并在解析過程中得出輸出列的數(shù)量。在解析的過程中需要注意的是：如果用于等值連接的列未出現(xiàn)在最后的輸出列中，為了等值連接運算的完成仍需要對這一列進行保存，這時，則需要修改Getmask，使得這一列能夠得到正常的輸出。

（2）選擇操作，即從滑動窗口中取出一個單元的數(shù)據(jù)流，根據(jù)邏輯表達式條件，來判斷這個數(shù)據(jù)是否滿足提取條件。

（3）投影操作，即將滿足條件的查詢結(jié)果保存到存儲查詢結(jié)果的Query＿res中，并在保存結(jié)果的同時對關(guān)鍵列進行投影操作。

（4）判斷當(dāng)前指針是否已經(jīng)達到滑動窗口的末尾，若是則算法結(jié)束，否則返回到步驟（2）繼續(xù)。

3.2 多數(shù)據(jù)流連接模塊

多數(shù)據(jù)流連接，就是在對單數(shù)據(jù)流做了選擇和投影后將具有相同屬性的列中值相同的數(shù)據(jù)單元提取出來。連接操作通過鏈表實現(xiàn)，每當(dāng)有數(shù)據(jù)流參與連接，就將連接的結(jié)果加入到鏈表中。對多數(shù)據(jù)流做等值連接的大致算法如下：

（1）設(shè)置兩個指針Dtqrpt和Srcqrpt，Dtqrpt指向保存最后結(jié)果的Query＿res，Srcqrpt指向保存新連入數(shù)據(jù)流選擇和投影后結(jié)果的Query＿res。設(shè)置指針Dstqrdpt用來指向查詢結(jié)果中的數(shù)據(jù)流表（數(shù)據(jù)流表以二級鏈表的結(jié)構(gòu)來實現(xiàn)），即Dstqrdpt＝Dtqrpt→Srcqrpt。

（2）找到Dstqrdpt指向Query＿res中的查詢結(jié)果信息頭部鏈表的尾部，將Srcqrpt指向的Query＿res中所保存的查詢結(jié)果信息的頭部插入到所找到節(jié)點的尾部。

（3）找到Dstqrdpt中的數(shù)據(jù)單元鏈表（二級鏈表Sdpt）尾部節(jié)點后，將尾部數(shù)據(jù)單元中用于等值連接的數(shù)據(jù)列與Srcqrpt指針?biāo)赶虻臄?shù)據(jù)鏈表中的對應(yīng)列做比較，若相等則將這部分數(shù)據(jù)單元添加到Srcqrpt所指數(shù)據(jù)的尾部；反之則將Dstqrdpt 做后移操作（Dstqrdpt＝Dstqrdpt→next），最后刪除Dstqrdpt所指向的節(jié)點。

（4）若Dstqrdpt！＝NULL，則繼續(xù)執(zhí)行步驟（3）；否則，算法結(jié)束。

3.3 連續(xù)查詢機制的實現(xiàn)

連續(xù)查詢是數(shù)據(jù)流處理工作的主要特征，也是該系統(tǒng)不可缺少的重要組成部分。連續(xù)查詢用兩個參數(shù)來控制：時間間隔和重復(fù)的次數(shù)。時間間隔參數(shù)用來控制連續(xù)查詢的間隔，即在間隔一定的次數(shù)之后執(zhí)行一次查詢；重復(fù)的次數(shù)參數(shù)用來指定重復(fù)查詢的執(zhí)行次數(shù)。連續(xù)查詢采用定時器實現(xiàn)，即每到設(shè)置的定時時間觸發(fā)一次查詢。本文中采用了CCS算法來處理滑動窗口中數(shù)據(jù)的連續(xù)查詢操作，CCS算法主要針對滑動窗口以元組為單位進行滑動的情況，這種細粒度的算法非常適合大量連續(xù)數(shù)據(jù)流。在有新的數(shù)據(jù)元組到達需要查詢時，CCS及時更新滑動窗口和數(shù)據(jù)緩存隊列，該處理算法的測試結(jié)果如圖2所示。

4 結(jié)論

本文設(shè)計并實現(xiàn)了一個數(shù)據(jù)流檢索系統(tǒng)的架構(gòu)，系統(tǒng)采用相對簡化的方法實現(xiàn)了數(shù)據(jù)流查詢的一些基本操作，并在嵌入式設(shè)備上檢驗了系統(tǒng)的運行，實現(xiàn)了對數(shù)據(jù)的有效過濾，提高了實時數(shù)據(jù)的提取效率。

圖2 連續(xù)查詢的運算結(jié)果

［1］ 谷峪.復(fù)雜數(shù)據(jù)流滑動窗口連接建模和查詢優(yōu)化［J］.東北大學(xué)學(xué)報，2007（11）：22－24.

［2］ 黃暉.數(shù)據(jù)流自適應(yīng)查詢系統(tǒng)研究［J］.科學(xué)咨詢，2007（10）：46－48.

［3］ 李娜.時間滑動窗口內(nèi)基于密度的數(shù)據(jù)流算法［J］.計算機應(yīng)用，2007（5）：39－41.

［4］ 閆巧梅.基于滑動窗口的流數(shù)據(jù)聚類算法研究［J］.計算機工程與設(shè)計，2008（21）：16－18.

［5］ 王偉平.基于滑動窗口的數(shù)據(jù)流連續(xù)查詢的處理方法［J］.軟件學(xué)報，2008（4）：42－44.

［6］ 王國仁.數(shù)據(jù)流連續(xù)聚集查詢預(yù)測研究［J］.東北大學(xué)學(xué)報，2009（8）：19－20.

［7］ 董逸生.基于滑動窗口的在線數(shù)據(jù)流增量聚集查詢［J］.計算機工程，2009（21）：55－57.

［8］ 鄺祝芳.一種有效的數(shù)據(jù)流檢索算法［J］.計算機應(yīng)用研究，2010（2）：113－115.

［9］ 王永利.基于滑動窗口的數(shù)據(jù)流閉合檢索模式的研究［J］.計算機研究與發(fā)展，2011（10）：76－78.

［10］ 李建中.數(shù)據(jù)流上的連續(xù)預(yù)測查詢的研究［J］.計算機研究與發(fā)展，2011（8）：51－53.