摘 要:針對不確定的傳感器數(shù)據(jù)流，在對國外數(shù)據(jù)流管理原型系統(tǒng)研究的基礎(chǔ)上，采用客戶機(jī)/服務(wù)器體系結(jié)構(gòu)，在RedHat Linux 9.0平臺上部分地實現(xiàn)了不確定數(shù)據(jù)流數(shù)據(jù)庫系統(tǒng)(UCDS)。詳細(xì)描述了不確定數(shù)據(jù)流數(shù)據(jù)庫系統(tǒng)的基本定義、系統(tǒng)的體系結(jié)構(gòu)等，為不確定性數(shù)據(jù)庫的研究做出了有益的探索。

關(guān)鍵詞:不確定性數(shù)據(jù); 不確定性數(shù)據(jù)庫; 體系結(jié)構(gòu); 數(shù)據(jù)結(jié)構(gòu)

中圖分類號:TN919-37文獻(xiàn)標(biāo)識碼:A

文章編號:1004-373X(2010)17-0154-03

Construction and Realization of Uncertain Database Based on Dynamic Data Stream

HUANG Li

(Department of Computer Science and Technology， Baoji University of Arts and Sciences， Baoji 721007， China)

AbstractAimming at the uncertainty of the sensor data stream， an uncertain data stream databse system is partly realized on RedHat Linux9.0 platform by using client/server mode， based on the study on foreign dynamic data stream management system. The basic defination and architecture of the uncertain data stream databse system is elaborated.

Keywords: uncertain data; uncertain database; architecture; data structure

0 引 言

隨著計算機(jī)技術(shù)的快速發(fā)展，傳統(tǒng)的確定性數(shù)據(jù)(Deterministic Data)管理技術(shù)也得到了極大的發(fā)展。近年來，隨著具有感知能力、計算能力和通信能力的微型傳感器的廣泛應(yīng)用，不確定性數(shù)據(jù)(Uncertain Data)得到廣泛的重視。在許多現(xiàn)實的應(yīng)用中，例如:經(jīng)濟(jì)、軍事、物流、金融、電信等領(lǐng)域，數(shù)據(jù)的不確定性普遍存在，不確定性數(shù)據(jù)成為數(shù)據(jù)庫的主要數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)管理技術(shù)卻無法有效管理不確定性數(shù)據(jù)，這就引發(fā)了學(xué)術(shù)界和工業(yè)界對研發(fā)新型的不確定性數(shù)據(jù)管理技術(shù)的需求。

一般說來，傳感器數(shù)據(jù)是以一種實時動態(tài)、持續(xù)變化的數(shù)據(jù)流的形式存在，同時由于傳感器數(shù)據(jù)的精確度受到傳感器各方面參數(shù)的影響[1]，使得傳感器數(shù)據(jù)流是一種不確定信息。目前，基于傳感器數(shù)據(jù)流的不確定性數(shù)據(jù)庫的研究還比較少，其研究對象主要集中于無線傳感器網(wǎng)絡(luò)、無線射頻系統(tǒng)、數(shù)字化家庭、股票交易系統(tǒng)、網(wǎng)絡(luò)監(jiān)測系統(tǒng)、道路交通監(jiān)測系統(tǒng)、電信通話記錄系統(tǒng)等[2]。主要研究方向有:原型系統(tǒng)設(shè)計與實現(xiàn)[3]、查詢處理優(yōu)化[4]、分布式數(shù)據(jù)流[5]、不確定數(shù)據(jù)流的研究[6]等。

本文主要研究對象是傳感器數(shù)據(jù)流，其目的在于研究一個組織、管理傳感器不確定數(shù)據(jù)流的數(shù)據(jù)庫系統(tǒng)。在對國外數(shù)據(jù)流管理原型系統(tǒng)研究的基礎(chǔ)上[7]，比較了一般數(shù)據(jù)流數(shù)據(jù)庫和不確定數(shù)據(jù)流數(shù)據(jù)庫，在RedHat Linux 9.0平臺上部分地實現(xiàn)了不確定數(shù)據(jù)流數(shù)據(jù)庫系統(tǒng)UCDS(Uncertain Data Stream Database System)。實現(xiàn)的語言為C/C++，系統(tǒng)采用了面向?qū)ο蟮脑O(shè)計與實現(xiàn)方法。

1 UCDS系統(tǒng)概述

不確定性數(shù)據(jù)庫是高效地獲取不確定性數(shù)據(jù)，科學(xué)地組合和管理不確定性數(shù)據(jù)的數(shù)據(jù)庫系統(tǒng)。UCDS數(shù)據(jù)庫系統(tǒng)部分地實現(xiàn)了不確定數(shù)據(jù)流的管理功能，包括帶可信度的屬性值的查詢管理，具有動態(tài)性的屬性值的查詢管理，不確定輸入數(shù)據(jù)的預(yù)處理和一般數(shù)據(jù)流(即不包括不確定信息的數(shù)據(jù)流)的查詢管理等。

本文的不確定據(jù)庫系統(tǒng)中的算子分為兩類:一般數(shù)據(jù)操作算子和不確定的動態(tài)數(shù)據(jù)操作算子。一般數(shù)據(jù)操作算子還可以分為關(guān)系-數(shù)據(jù)操作算子和數(shù)據(jù)-數(shù)據(jù)操作算子。這兩種算子中既包含一元操作也包含二元操作。由于不確定數(shù)據(jù)的屬性是以一定概率取值的，因此對不確定性屬性值進(jìn)行連接、聚集等操作沒有意義。這里保留了大多數(shù)的一般數(shù)據(jù)操作算子，增加的不確定性動態(tài)數(shù)據(jù)算子主要有CONF，PROB和PDF算子。CONF表示求屬性值的隸屬度，PROB表示求動態(tài)屬性值的概率，PDF表示求動態(tài)屬性值的概率密度函數(shù)。這些算子和運(yùn)算符的詞法、語法分析由LEX與YACC兩個分析器完成。LEX是一個通用的詞法分析生成器。它可以分析任何語言的詞法，YACC由貝爾實驗室開發(fā)，是一個通用語法分析器。具體關(guān)于LEX和YACC的技術(shù)資料請參考文獻(xiàn)[8]。

2 UCDS的體系結(jié)構(gòu)

UCDS采用客戶機(jī)/服務(wù)器體系結(jié)構(gòu)，如圖1所示，主要的子系統(tǒng)有:用戶接口子系統(tǒng)、計劃子系統(tǒng)、執(zhí)行子系統(tǒng)和不確定數(shù)據(jù)預(yù)處理子系統(tǒng)。其中計劃子系統(tǒng)和執(zhí)行子系統(tǒng)是核心部分。計劃子系統(tǒng)負(fù)責(zé)把UCQL注冊和查詢語句進(jìn)行詞法語法分析并轉(zhuǎn)換成內(nèi)部表示方式，經(jīng)過優(yōu)化形成物理查詢計劃。執(zhí)行子系統(tǒng)負(fù)責(zé)查詢語句的執(zhí)行。

圖1 UCDS系統(tǒng)結(jié)構(gòu)圖

2.1 用戶接口子系統(tǒng)

用戶接口子系統(tǒng)由三部分組成:服務(wù)器模塊、數(shù)據(jù)源獲取模塊(關(guān)系或動態(tài)數(shù)據(jù)元組的獲得)和查詢結(jié)果輸出模塊。服務(wù)器模塊功能有:服務(wù)器的配置、動態(tài)數(shù)據(jù)或關(guān)系的注冊模塊、不確定數(shù)據(jù)查詢的注冊和運(yùn)行。

2.2 計劃子系統(tǒng)

計劃子系統(tǒng)的結(jié)構(gòu)如圖2所示。由詞法和語法分析、邏輯和物理計劃產(chǎn)生器、查詢管理器、表管理器和計劃管理器等組成。計劃子系統(tǒng)負(fù)責(zé)把UCQL語句進(jìn)行詞法語法分析并轉(zhuǎn)換成內(nèi)部形式，并經(jīng)過優(yōu)化形成物理查詢計劃。

圖2 UCDS中的計劃子系統(tǒng)

語法分析 將查詢字符串轉(zhuǎn)換成表示查詢的語法樹，語法解析也適用于動態(tài)數(shù)據(jù)與關(guān)系的注冊。該子系統(tǒng)主要是通過YACC與LEX對UCQL語句進(jìn)行語法分析與詞法分析。

語義分析 把語法樹轉(zhuǎn)換成查詢的內(nèi)部表示結(jié)構(gòu)。語義分析主要解決以下問題:解決屬性參照;補(bǔ)充實現(xiàn)UCQL的缺省及缺失信息(例如“SELECT*”中的“*”);把基于字符串的動態(tài)數(shù)據(jù)流名稱、屬性標(biāo)識符轉(zhuǎn)換成內(nèi)部的表示形式。

邏輯計劃產(chǎn)生器 把查詢的內(nèi)部表示形式轉(zhuǎn)換成查詢的邏輯計劃。該邏輯計劃是由邏輯算子組成，邏輯算子與關(guān)系代數(shù)算子類似(例如:SELECT，PROJECT，JION)。增加邏輯計劃查詢層的原因是:由邏輯計劃到物理計劃的轉(zhuǎn)換比直接到物理計劃層要容易，同時，邏輯計劃中的算子比與底層細(xì)節(jié)有緊密關(guān)系的物理計劃算子更抽象。

物理計劃產(chǎn)生器 把查詢的邏輯計劃轉(zhuǎn)換成查詢的物理計劃。物理計劃中的算子可以準(zhǔn)確地在執(zhí)行子系統(tǒng)中應(yīng)用。

查詢管理器 查詢管理器存儲注冊的查詢，它為每個查詢分配一個惟一的ID號，目的在于方便系統(tǒng)其他部分的使用。

表管理器 表管理器存儲注冊的動態(tài)數(shù)據(jù)流和關(guān)系的名稱和數(shù)據(jù)模式，這些數(shù)據(jù)流和關(guān)系可以是輸入的數(shù)據(jù)流和原始的關(guān)系，也可以是查詢得到的中間結(jié)果。

計劃管理器 計劃管理器存儲了與所有注冊查詢相對應(yīng)的物理查詢計劃。

2.3 執(zhí)行子系統(tǒng)的實現(xiàn)

執(zhí)行子系統(tǒng)如圖3所示，負(fù)責(zé)查詢語句的執(zhí)行。

圖3 執(zhí)行子系統(tǒng)

執(zhí)行子系統(tǒng)中的數(shù)據(jù)有三種類型:元組、元素和中間數(shù)據(jù)。元組是數(shù)據(jù)的基本單元。在邏輯上，元組是屬性值的集合;在實現(xiàn)時，一個元組是屬性值集合所對應(yīng)的內(nèi)存單元的指針。元素是一個帶有時間戳與符號的元組。中間數(shù)據(jù)是一種只有時間戳的元素，與元組的符號無關(guān)。中間數(shù)據(jù)將用于算子間時間進(jìn)程的通訊。

每個查詢計劃包括三種元素:算子、隊列和大綱。

(1) 算子:算子用于處理輸入并把輸出放入輸出隊列。

(2) 隊列:連接輸入算子和輸出算子，隊列中包含部分?jǐn)?shù)據(jù)流或整個關(guān)系，也可看作是執(zhí)行算子前的一個緩存區(qū)。

(3) 大綱:存儲了查詢計劃的中間狀態(tài)，連接算子必須能獲得當(dāng)前窗口輸入的所有數(shù)據(jù)流元組，所以連接算子必須具有一個大綱。而投影操作和不消除重復(fù)數(shù)據(jù)的并操作就不需要大綱。

如有如下兩個對數(shù)據(jù)流S1，S2的查詢Q1和Q2:

Q1:SELECT B，MAX(A) FROM TS1[ROWS 10 000] GROUP BY B;

Q2:SELECT*FROM S1[ROWS5000]，S2[RANGE 500 SECONDS] WHERE S1.A=S2.A;

窗口算子1從隊列1中讀入數(shù)據(jù)流元組S1，更新大綱1，并把帶有元素的數(shù)據(jù)流輸出到隊列3和隊列4，大綱1包括最近到達(dá)的10 000個元組，這里選擇查詢1和查詢2中較大的一個。同理，大綱2則存儲最近500 s到達(dá)的元組。聚集算子求出對相同S1.B數(shù)據(jù)流元組中最大的S1.A的值，并將結(jié)果存儲在大綱6中，將帶有元素的數(shù)據(jù)流放入隊列6中，因為大綱6中的結(jié)果是持續(xù)增長的，所以必有較舊的結(jié)果被剔除出大綱6，從而大綱6必須從大綱3中尋找新的滿足查詢的結(jié)果。所以大綱3僅僅是隊列1的一個時間戳較小的數(shù)據(jù)流拷貝，可以看出大綱3和大綱1是共享的關(guān)系而不是簡單復(fù)制的關(guān)系，同理大綱4和大綱1，及大綱5和大綱2。連接算子結(jié)果為大綱4和隊列5進(jìn)行連接，已經(jīng)大綱5和隊列4進(jìn)行連接的結(jié)果。

同時，圖3中的還有四個功能模塊起著重要的作用:

(1) 存儲分配:系統(tǒng)中的所有元組由存儲分配算符對象進(jìn)行分配空間。一個存儲分配算符由一個算子擁有，用來分配空間給算子輸出元素的元組。不是所有的算子都擁有一個存儲分配符，例如，選擇算子只是簡單地輸出、輸入元組，并不產(chǎn)生新元組。存儲分配算符也跟蹤元組的空間使用與收回元組不使用的空間。

(2) 存儲單元:存儲分配算符與大綱的描述主要集中在算子的接口上。大多數(shù)存儲分配算符與大綱的實際邏輯是在存儲單元內(nèi)實現(xiàn)。每一個存儲單元支持一個存儲分配單元和一個大綱集合。每一個大綱與一個存儲單元關(guān)聯(lián)，并且大綱中的所有元組的分配由存儲單元進(jìn)行分配。

(3) 內(nèi)存管理器:內(nèi)存管理器管理一個公共內(nèi)存池，按照需要以頁為單位為存儲單元、索引、隊列分配內(nèi)存。

(4) 調(diào)度器:調(diào)度器分成兩部分，一部分負(fù)責(zé)系統(tǒng)內(nèi)算子的調(diào)度，另一部分負(fù)責(zé)持續(xù)查詢的事務(wù)調(diào)度。

3 結(jié) 語

針對傳感器數(shù)據(jù)流具有不確定性的特點(diǎn)，采用客戶機(jī)/服務(wù)器體系結(jié)構(gòu)，在RedHat Linux 9.0平臺上部分地實現(xiàn)了基于UCDS系統(tǒng)。本數(shù)據(jù)庫系統(tǒng)雖然只是實現(xiàn)了部分功能，但對不確定性數(shù)據(jù)庫系統(tǒng)的研究仍不失為一次有益的探索。

參考文獻(xiàn)

[1]李建中，李金寶，石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進(jìn)展[J].軟件學(xué)報，2003，14(10):1717-1727.

[2]BABCOCK B， BABU S， DATAR M， et al. Models and issues in data streams system[C]//Proceedings of the 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Madison:ACM Press，2002:1-16.

[3]ARASU A， BABCOCK B， BABU S. STREAM:the Stanford data stream management system[J]. IEEE Data Engineering Bulletin，2003，26(1):19-26.

[4]GOLAB L， TAMER M. Processing sliding window multi-joins in continuous queries overdata streams[C]//Proceedings of the 29th Internationall Conference on VLDB. Berlin:Morgan Kaufmann Publishers，2003:500-511.

[5]BULUT A， SINGH A K， VITENBERG R. Distributed data streams indexing using content-based routing paradigm[C]//Parallel and Distributed Processing Symposium 2005， Proceedings 19th IEEE International. Washington DC: IEEE Computer Society， 2005: 94-94.

[6]SARMA A D， HEFFERY S R， FRANKLIN M J， et al. Estimating data stream quality for object-detection applications[C]//Proceedings of the 3rd International ACM SIGMOD Workshop on Information Quality in Information Systems. Chicago: Illinois， 2006: 16-28.

[7]BONNET P， GEHRKE J， SESHADR P. Towards sensor database systems[C]//Proceedings of the 2nd International Conference Mobile data Management. Hong Kong:Springer-Verlag，2001: 3-14.

[8]LEVINE J R， MASON T， BROWN D. Lex與Yacc[M]. 楊作梅，張旭東，譯.北京:機(jī)械工業(yè)出版社，2003.