基于動態流式數據的不確定性數據庫的構建與實現

摘 要:針對不確定的傳感器數據流，在對國外數據流管理原型系統研究的基礎上，采用客戶機/服務器體系結構，在RedHat Linux 9.0平臺上部分地實現了不確定數據流數據庫系統(UCDS)。詳細描述了不確定數據流數據庫系統的基本定義、系統的體系結構等，為不確定性數據庫的研究做出了有益的探索。

關鍵詞:不確定性數據; 不確定性數據庫; 體系結構; 數據結構

中圖分類號:TN919-37文獻標識碼: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 引 言

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

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

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

1 UCDS系統概述

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

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

2 UCDS的體系結構

UCDS采用客戶機/服務器體系結構，如圖1所示，主要的子系統有:用戶接口子系統、計劃子系統、執行子系統和不確定數據預處理子系統。其中計劃子系統和執行子系統是核心部分。計劃子系統負責把UCQL注冊和查詢語句進行詞法語法分析并轉換成內部表示方式，經過優化形成物理查詢計劃。執行子系統負責查詢語句的執行。

圖1 UCDS系統結構圖

2.1 用戶接口子系統

用戶接口子系統由三部分組成:服務器模塊、數據源獲取模塊(關系或動態數據元組的獲得)和查詢結果輸出模塊。服務器模塊功能有:服務器的配置、動態數據或關系的注冊模塊、不確定數據查詢的注冊和運行。

2.2 計劃子系統

計劃子系統的結構如圖2所示。由詞法和語法分析、邏輯和物理計劃產生器、查詢管理器、表管理器和計劃管理器等組成。計劃子系統負責把UCQL語句進行詞法語法分析并轉換成內部形式，并經過優化形成物理查詢計劃。

圖2 UCDS中的計劃子系統

語法分析 將查詢字符串轉換成表示查詢的語法樹，語法解析也適用于動態數據與關系的注冊。該子系統主要是通過YACC與LEX對UCQL語句進行語法分析與詞法分析。

語義分析 把語法樹轉換成查詢的內部表示結構。語義分析主要解決以下問題:解決屬性參照;補充實現UCQL的缺省及缺失信息(例如“SELECT*”中的“*”);把基于字符串的動態數據流名稱、屬性標識符轉換成內部的表示形式。

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

物理計劃產生器 把查詢的邏輯計劃轉換成查詢的物理計劃。物理計劃中的算子可以準確地在執行子系統中應用。

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

表管理器 表管理器存儲注冊的動態數據流和關系的名稱和數據模式，這些數據流和關系可以是輸入的數據流和原始的關系，也可以是查詢得到的中間結果。

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

2.3 執行子系統的實現

執行子系統如圖3所示，負責查詢語句的執行。

圖3 執行子系統

執行子系統中的數據有三種類型:元組、元素和中間數據。元組是數據的基本單元。在邏輯上，元組是屬性值的集合;在實現時，一個元組是屬性值集合所對應的內存單元的指針。元素是一個帶有時間戳與符號的元組。中間數據是一種只有時間戳的元素，與元組的符號無關。中間數據將用于算子間時間進程的通訊。

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

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

(2) 隊列:連接輸入算子和輸出算子，隊列中包含部分數據流或整個關系，也可看作是執行算子前的一個緩存區。

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

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

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

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

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

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

(4) 調度器:調度器分成兩部分，一部分負責系統內算子的調度，另一部分負責持續查詢的事務調度。

3 結 語

針對傳感器數據流具有不確定性的特點，采用客戶機/服務器體系結構，在RedHat Linux 9.0平臺上部分地實現了基于UCDS系統。本數據庫系統雖然只是實現了部分功能，但對不確定性數據庫系統的研究仍不失為一次有益的探索。

參考文獻

[1]李建中，李金寶，石勝飛.傳感器網絡及其數據管理的概念、問題與進展[J].軟件學報，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]. 楊作梅，張旭東，譯.北京:機械工業出版社，2003.