王洪亞，曹姣，金杰

東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620

基于Aurora系統(tǒng)的持續(xù)型查詢(xún)語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)

王洪亞，曹姣，金杰

東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620

隨著新型數(shù)據(jù)應(yīng)用的不斷出現(xiàn)，針對(duì)流形態(tài)數(shù)據(jù)的數(shù)據(jù)流管理系統(tǒng)已經(jīng)成為數(shù)據(jù)管理領(lǐng)域研究的新熱點(diǎn)。針對(duì)目前通用數(shù)據(jù)流管理系統(tǒng)只支持基于操作符流圖的查詢(xún)表達(dá)方式這一不足，設(shè)計(jì)了一種新的持續(xù)型數(shù)據(jù)流查詢(xún)語(yǔ)言，并在通用數(shù)據(jù)流處理系統(tǒng)Aurora上進(jìn)行了實(shí)現(xiàn)。為驗(yàn)證新語(yǔ)言的表達(dá)能力，該系統(tǒng)使用新語(yǔ)言定義了數(shù)據(jù)流基準(zhǔn)測(cè)試Linear Road Benchmark的查詢(xún)集，在Aurora系統(tǒng)上部署運(yùn)行。測(cè)試結(jié)果表明針對(duì)Linear Road Benchmark的測(cè)試用例，新語(yǔ)言具有較完備的語(yǔ)義和良好的表達(dá)能力。

數(shù)據(jù)流；數(shù)據(jù)流管理系統(tǒng)；持續(xù)型查詢(xún)語(yǔ)言

1 引言

數(shù)據(jù)流指只能以事先規(guī)定好的順序被讀取一次或幾次的數(shù)據(jù)的一個(gè)序列[1-3]。與傳統(tǒng)數(shù)據(jù)相比，數(shù)據(jù)流具有大量、快速、隨時(shí)間變化、數(shù)據(jù)量大小事先不確定等特點(diǎn)。這些特點(diǎn)使得需要對(duì)通用數(shù)據(jù)流管理系統(tǒng)進(jìn)行研究。近年來(lái)，國(guó)內(nèi)外在數(shù)據(jù)流管理領(lǐng)域開(kāi)展了很多工作，并取得了不少研究成果。目前代表性的數(shù)據(jù)流管理原型系統(tǒng)有Aurora[4-5]、STREAM[6]、Telegraph[7]等，其中Aurora系統(tǒng)是由美國(guó)布蘭代斯大學(xué)、布朗大學(xué)和麻省理工學(xué)院合作開(kāi)發(fā)的一個(gè)數(shù)據(jù)流管理原型系統(tǒng)。

雖然Aurora原型系統(tǒng)具有豐富的數(shù)據(jù)流操作符、可擴(kuò)展的軟件架構(gòu)和良好的數(shù)據(jù)流處理性能，但在Aurora中不支持聲明式（Declarative）的數(shù)據(jù)流查詢(xún)語(yǔ)言，所有用戶(hù)查詢(xún)需要通過(guò)圖形接口表示為操作符流圖。這對(duì)于大量熟悉SQL語(yǔ)句的數(shù)據(jù)庫(kù)開(kāi)發(fā)人員來(lái)說(shuō)很不方便，同時(shí)也不利于后續(xù)基于Aurora系統(tǒng)的研究與開(kāi)發(fā)。為此，基于Aurora系統(tǒng)設(shè)計(jì)和開(kāi)發(fā)了一種通用的持續(xù)型查詢(xún)語(yǔ)言Conger CQL，本文的主要工作包括：

（1）設(shè)計(jì)了一個(gè)具有精確語(yǔ)義和豐富表達(dá)能力的持續(xù)型查詢(xún)語(yǔ)言Conger CQL。

（2）在Aurora數(shù)據(jù)流原型系統(tǒng)上實(shí)現(xiàn)了Conger CQL，具體包括Conger CQL的BNF定義、CQL查詢(xún)解析和核心數(shù)據(jù)結(jié)構(gòu)生成以及Aurora操作符綁定等，最終根據(jù)用戶(hù)的查詢(xún)定義生成相應(yīng)的物理執(zhí)行計(jì)劃。

（3）為了驗(yàn)證Conger CQL的表達(dá)能力，使用新語(yǔ)言定義了標(biāo)準(zhǔn)測(cè)試程序Linear Road Benchmark的查詢(xún)集。測(cè)試結(jié)果表明Conger CQL具有精確的語(yǔ)義和豐富的表達(dá)能力，可以表達(dá)復(fù)雜的持續(xù)型查詢(xún)。

2 Aurora數(shù)據(jù)流處理系統(tǒng)簡(jiǎn)介

Aurora數(shù)據(jù)流管理系統(tǒng)是由美國(guó)布蘭代斯大學(xué)、布朗大學(xué)和麻省理工學(xué)院合作開(kāi)發(fā)的一個(gè)數(shù)據(jù)流管理原型系統(tǒng)。Aurora采用了類(lèi)似于工作流的查詢(xún)語(yǔ)言，其最重要的結(jié)構(gòu)是Box和Arrow，每一個(gè)Box代表一個(gè)操作符（Operator）；每一個(gè)有向的Arrow代表數(shù)據(jù)流從一個(gè)操作符傳遞到另外一個(gè)操作符。一個(gè)Aurora的查詢(xún)定義為由操作符組成的有向無(wú)環(huán)圖，如圖1所示。

圖1 Aurora系統(tǒng)模型圖

Aurora定義和實(shí)現(xiàn)了七種基本操作符，分別是選擇（Filter）、投影（Map）、合并（Union）、冒泡排序（BSort）、聚集（Aggregate）、連接（Join）和重采樣（Resample）。這些操作符和傳統(tǒng)的關(guān)系代數(shù)類(lèi)似，但由于數(shù)據(jù)流具有潛在的無(wú)限性，對(duì)于連接這樣的阻塞型操作符，需要使用滑動(dòng)窗口將數(shù)據(jù)流轉(zhuǎn)換為時(shí)變關(guān)系，然后再在滑動(dòng)窗口上進(jìn)行連接操作。這是數(shù)據(jù)流處理與傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)查詢(xún)處理的重要區(qū)別之一。

Aurora系統(tǒng)支持三種類(lèi)型的查詢(xún)，即持續(xù)查詢(xún)（Continuous Query）、視圖和Ad hoc查詢(xún)。持續(xù)查詢(xún)一旦由用戶(hù)注冊(cè)后就一直在系統(tǒng)中運(yùn)行；視圖是調(diào)度器控制下物化的用戶(hù)定義查詢(xún)，通過(guò)視圖可以加快查詢(xún)的速度；Ad hoc查詢(xún)指一次性的針對(duì)數(shù)據(jù)流和歷史數(shù)據(jù)的用戶(hù)查詢(xún)。Aurora的系統(tǒng)模型如圖1所示。

Aurora系統(tǒng)只支持基于操作符流圖的查詢(xún)定義方式，雖然該方式具有比較直觀的特點(diǎn)，但用戶(hù)需要對(duì)底層操作符有足夠深入的理解才能構(gòu)造出所需要的操作符網(wǎng)絡(luò)，而這一過(guò)程對(duì)大量熟悉SQL語(yǔ)言的數(shù)據(jù)庫(kù)開(kāi)發(fā)人員來(lái)說(shuō)過(guò)于復(fù)雜。為此，本文設(shè)計(jì)了面向數(shù)據(jù)流處理的持續(xù)型查詢(xún)語(yǔ)言Conger CQL[8]，并在Aurora數(shù)據(jù)流管理系統(tǒng)上進(jìn)行了實(shí)現(xiàn)。需要強(qiáng)調(diào)的是Aurora的操作符圖和本文設(shè)計(jì)實(shí)現(xiàn)的持續(xù)型查詢(xún)語(yǔ)言各有自己的優(yōu)點(diǎn)，是互為補(bǔ)充的關(guān)系。

3 持續(xù)性查詢(xún)語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)

3.1 Conger CQL設(shè)計(jì)

完整的Conger CQL語(yǔ)法[9-10]如下所示：

下面分別對(duì)語(yǔ)法中的主要組成部分進(jìn)行詳細(xì)描述。

（1）滑動(dòng)窗口定義（window_specification）[11]

滑動(dòng)窗口是數(shù)據(jù)流處理中為了避免阻塞型操作符（如連接操作）長(zhǎng)時(shí)間等待到達(dá)流數(shù)據(jù)而無(wú)法及時(shí)輸出結(jié)果所采用的一種機(jī)制，在數(shù)據(jù)流處理系統(tǒng)中被廣泛使用，Conger CQL的滑動(dòng)窗口語(yǔ)法定義如下：

其中關(guān)鍵字RANGE定義窗口的大?。籗LIDE定義窗口的滑動(dòng)距離；ON定義時(shí)間屬性；ROW定義該窗口是基于元組個(gè)數(shù)的。示例查詢(xún)2給出了一個(gè)窗口大小為10 min，滑動(dòng)距離為1 min的窗口定義。

（2）SELECT子句

每個(gè)SELECT子句至少要有一個(gè)選擇列表（select_ expr）來(lái)指定要選擇的字段或表達(dá)式。在示例查詢(xún)1中，數(shù)據(jù)流stock_stream的所有字段都按原有的順序輸出，該子句對(duì)應(yīng)Aurora的投影操作符。

（3）FROM子句

每FROM子句包含至少一個(gè)數(shù)據(jù)流引用（stream_ references）。當(dāng)需要對(duì)多個(gè)流進(jìn)行連接操作時(shí)，使用stream1 JOIN stream2 ON stream1.attribute1=stream2. attribute2子句。選擇出的屬性還可用AS關(guān)鍵字指定別名。示例查詢(xún)2給出最近一段時(shí)間（10 min）某個(gè)股票的最大價(jià)格，查詢(xún)結(jié)果每分鐘更新一次。From子句中的數(shù)據(jù)流引用對(duì)應(yīng)Aurora操作符的輸入流。

示例查詢(xún)2：SELECTMAX（price）FROM stock_stream [RANGE 10 MINUTES SLIDE 1 MINUTE]

（4）WHERE子句

WHERE是Conger CQL中的可選子句，其中where_ condition指定對(duì)輸入數(shù)據(jù)流的選擇謂詞，該子句對(duì)應(yīng)Aurora的選擇操作符。示例查詢(xún)3表示從輸入流中篩選出價(jià)格大于10的股票交易數(shù)據(jù)。

示例查詢(xún)3：SELECT*FROM stock_stream WHERE price>10

（5）GROUP BY子句

GROUP BY子句也是Conger CQL中的可選子句，對(duì)應(yīng)Aurora的聚集操作符，用于對(duì)數(shù)據(jù)流進(jìn)行常見(jiàn)的統(tǒng)計(jì)操作。示例查詢(xún)4中，該查詢(xún)首先計(jì)算最近一段時(shí)間（10 min）每個(gè)股票的最大價(jià)格，然后選擇最大價(jià)格大于10的輸出出來(lái)。

示例查詢(xún)4：SELECT MAX（price）FROM mutil_stock_ stream[RANGE 10 MINUTES SLIDE 1 MINUTE]GROUP BY stock HAVING MAX（price）>10

表1給出了Conger CQL與數(shù)據(jù)流常用關(guān)系操作符的對(duì)應(yīng)關(guān)系，證明設(shè)計(jì)的語(yǔ)言在語(yǔ)義上是完備的。

表1 Conger CQL與關(guān)系操作符對(duì)應(yīng)關(guān)系

3.2Conger CQL實(shí)現(xiàn)

Aurora數(shù)據(jù)流管理系統(tǒng)提供了較完備的數(shù)據(jù)流處理功能，且在三個(gè)主流的數(shù)據(jù)流管理原型系統(tǒng)（Aurora，STREAM和TelegraphCQ）中具有最好的性能和可擴(kuò)展性，因此選擇在Aurora系統(tǒng)中實(shí)現(xiàn)對(duì)Conger CQL的支持。Aurora系統(tǒng)的核心代碼有十幾萬(wàn)行，而添加Conger CQL語(yǔ)言接口需要對(duì)Aurora的核心代碼進(jìn)行修改和擴(kuò)充，因此具有較大的難度和工作量。目前具有Conger CQL擴(kuò)展的Aurora系統(tǒng)代碼已經(jīng)放置在https：//github. com/dhu/conger上供有興趣的讀者下載，為支持Conger CQL新添加的源代碼超過(guò)7 000行。

首先使用自動(dòng)編譯器生成工具ANTLR3定義了Conger CQL的BNF描述。下面給出了Conger CQL的BNF描述的一個(gè)片段，受篇幅限制（完整的BNF描述有超過(guò)700行的語(yǔ)法定義），沒(méi)有列出完整的Conger CQL的BNF描述。

在上述BNF語(yǔ)法定義中，sfw_block是最頂層的語(yǔ)法規(guī)則，表示一個(gè)完整SELECT-FROM-WHERE查詢(xún)語(yǔ)句，它由一個(gè)select_clause子句、from_clause子句，加上可選的opt_group_by_clause子句、opt_having_clause子句、opt_where_clause子句組成。關(guān)鍵字“->^”指定了生成抽象語(yǔ)法樹(shù)的結(jié)構(gòu)。

完成BNF定義后，就可以對(duì)輸入的Conger CQL進(jìn)行詞法和語(yǔ)法解析，并生成抽象語(yǔ)法樹(shù)。對(duì)示例查詢(xún)5解析后，可以得到圖2所示的抽象語(yǔ)法樹(shù)。

示例查詢(xún)5：SELECT time，COUNT（car_id）AS volume FROM positionreport[RANGE 30 SECONDS SLIDE 3 SECONDS]

在編譯得到抽象語(yǔ)法樹(shù)后，需要遍歷抽象語(yǔ)法樹(shù)，將用戶(hù)的查詢(xún)參數(shù)寫(xiě)入到自定義的核心數(shù)據(jù)結(jié)構(gòu)中。同樣限于篇幅沒(méi)有給出所定義的核心數(shù)據(jù)結(jié)構(gòu)，有興趣的讀者可以在https：//github.com/dhu/conger上下載。

完成核心數(shù)據(jù)結(jié)構(gòu)的初始化后，最后需要根據(jù)這些數(shù)據(jù)結(jié)構(gòu)的內(nèi)容將Aurora的相關(guān)操作符組合成查詢(xún)網(wǎng)絡(luò)，完成物理執(zhí)行計(jì)劃的生成。在目前的版本，主要支持對(duì)應(yīng)一個(gè)和兩個(gè)Aurora操作符Conger CQL查詢(xún)，由多個(gè)操作符組成的查詢(xún)網(wǎng)絡(luò)可表達(dá)為多個(gè)查詢(xún)語(yǔ)句。首先介紹僅對(duì)應(yīng)一個(gè)操作符的查詢(xún)類(lèi)別：

（1）SELECT*FROM stream_name WHERE id>1，該類(lèi)查詢(xún)對(duì)應(yīng)Aurora的選擇操作符。

圖2 抽象語(yǔ)法樹(shù)

（2）SELECT id，name FROM stream_name，該類(lèi)查詢(xún)對(duì)應(yīng)Aurora的投影操作符。

（3）SELECTCOUNT（id）FROMstream_name [RANGE 10 MINUTES SLIDE 1 MINUTE]，該類(lèi)查詢(xún)對(duì)應(yīng)Aurora的聚集操作符。

（4）SELECT stream1.name，stream2.name FROM stream1[RANGE 10 MINUTES SLIDE 1 MINUTE] JOIN stream2[RANGE 10 MINUTES SLIDE 1 MINUTE] ON stream1.id=stream2.id，該類(lèi)查詢(xún)對(duì)應(yīng)Aurora的連接操作符。

下面，將介紹對(duì)應(yīng)兩個(gè)Aurora操作符的復(fù)雜CQL?？紤]Aurora中最重要的四個(gè)操作符：選擇、投影、連接和聚集，這四個(gè)操作符一共有如下12種組合方式：

（1）選擇->投影，例子：SELECT a，b，c FROM s1 WHERE c>2。

（2）投影->選擇，可以用第一種情況代替，因?yàn)槲恢没Q后兩者的語(yǔ)義是等價(jià)的。

（3）選擇->連接，例子：SELECT s1.a，s1.b，s2.c，s2.d FROM s1[10]JOIN s2[20]ON s1.a=s2.c WHERE s1. b>3 AND s2.d<4 AND s1.e=10。

（4）連接->選擇，與上一種情況語(yǔ)義是等價(jià)的。

（5）連接->投影，例子：SELECT s1.a/2，s1.b-3，s2.c，s2.d FROM s1[10]JOIN s2[20]ON s1.a=s2.c。此類(lèi)查詢(xún)只需要在連接操作符輸出流后面增加一個(gè)投影操作符即可。

（6）投影->連接，沒(méi)有Conger CQL語(yǔ)句對(duì)應(yīng)這種組合。

（7）聚集->投影，例子：SELECT MAX（a）/2-c+，d FROM s1[10]GROUP BY c，d。

（8）投影->聚集，沒(méi)有Conger CQL語(yǔ)句對(duì)應(yīng)這種組合。

（9）連接->聚集，例子；SELECT MAX（s1.e）FROM s1[10]JOIN s2[20]ON s1.a=s2.c GROUP BY s1.b，s2.d。

（10）聚集->連接，沒(méi)有Conger CQL語(yǔ)句對(duì)應(yīng)這種組合。

（11）選擇->聚集，例子：SELECT MAX（a），MIN（b）FROM s1[10]GROUP BY c，d WHERE e>10。

（12）聚集->選擇，例子：SELECT MAX（a），MIN（b）FROM s1[10]GROUP BY c，d HAVING MAX（a）> 10 OR MIN（b）<3。

上述兩個(gè)操作符組合的技術(shù)關(guān)鍵在于需將第一個(gè)操作符的輸出流命名為一個(gè)中間流，然后將其作為第二個(gè)操作符的輸入流，并最終組合成查詢(xún)網(wǎng)絡(luò)[12]。這些都涉及到對(duì)Aurora系統(tǒng)核心代碼的修改和擴(kuò)充，具體代碼見(jiàn)https：//github.com/dhu/conger。

4 實(shí)驗(yàn)評(píng)估

完成持續(xù)型查詢(xún)語(yǔ)言Conger CQL的設(shè)計(jì)和實(shí)現(xiàn)后，需要對(duì)其表達(dá)能力和語(yǔ)義正確性進(jìn)行測(cè)試。本文使用目前數(shù)據(jù)流處理事實(shí)上的標(biāo)準(zhǔn)測(cè)試程序Linear Road Benchmark對(duì)Conger CQL進(jìn)行了測(cè)試。

Linear Road Benchmark[13]模擬了一個(gè)高速公路的收費(fèi)系統(tǒng)，在系統(tǒng)中假設(shè)一個(gè)城市由10條并行的高速公路組成，每條高速公路被分成100段，每段都有一個(gè)進(jìn)出口，汽車(chē)可以隨意根據(jù)當(dāng)前的路況選擇在某一段進(jìn)入或離開(kāi)某一個(gè)高速公路。高速公路中的汽車(chē)每30 s向服務(wù)器發(fā)送一個(gè)位置信息。

下面以Linear Road Benchmark中的車(chē)輛計(jì)費(fèi)模塊為例介紹Conger CQL測(cè)試結(jié)果。車(chē)輛計(jì)費(fèi)模塊的功能是實(shí)時(shí)地統(tǒng)計(jì)每段道路的擁塞程度，并根據(jù)路況計(jì)算收費(fèi)額度，同時(shí)對(duì)離開(kāi)該段道路的車(chē)輛發(fā)送計(jì)費(fèi)信息[3]。

車(chē)輛計(jì)費(fèi)模塊的輸入數(shù)據(jù)流（positionreport）的字段包括時(shí)間（time）、車(chē)輛編號(hào)（car_id）、速度（speed）、高速公路編號(hào)（exp_way）、車(chē)道編號(hào)（lane）、行駛方向（dir）、路段編號(hào)（seg）、位置信息（x-pos）。輸出數(shù)據(jù)流的模式包括車(chē)輛編號(hào)、收費(fèi)信息、公路編號(hào)、行駛方向以及該車(chē)輛所行駛的路段等字段。為完成車(chē)輛計(jì)費(fèi)模塊的功能，使用Conger CQL定義了如下的七條查詢(xún)，這里請(qǐng)注意查詢(xún)七的輸出流是最終需要的，其他查詢(xún)的輸出數(shù)據(jù)流為中間流。

查詢(xún)?nèi)?jì)算平均車(chē)速小于40 mile/h的路段，該查詢(xún)將查詢(xún)一和查詢(xún)二的輸出數(shù)據(jù)流segvol、segavgspee進(jìn)行連接操作。查詢(xún)?nèi)妮敵鰯?shù)據(jù)流為segmenttoll_filter，輸出流的模式為（way，dir，seg，volume，vol_time，avgspeed_ time，avg_speed）。

查詢(xún)四根據(jù)收費(fèi)規(guī)則計(jì)算每一段平均車(chē)速小于40 mile/h的公路的當(dāng)前費(fèi)率。費(fèi)率計(jì)算公式為15×（volume-150）×（volume-150），其中volume為當(dāng)前該路段上的車(chē)流量。該查詢(xún)的輸入流為查詢(xún)?nèi)妮敵隽鱯egmenttoll_filter。輸出流為segmenttoll，其模式為（time，way，dir，seg，vol_time，avgspeed_time，toll）。

查詢(xún)五計(jì)算當(dāng)前公路上正在行駛的車(chē)輛數(shù)量，輸入數(shù)據(jù)流為positionreport，輸出數(shù)據(jù)流為curactivecars，其模式為（car_id，way，dir，seg，time，car_count）。

查詢(xún)六統(tǒng)計(jì)哪些車(chē)輛第一次進(jìn)入一個(gè)新路段。輸入數(shù)據(jù)流為curactivecars，輸出數(shù)據(jù)流為newcarentry，輸出流模式為（car_id，way，dir，seg，time，car_count）。

查詢(xún)七對(duì)那些正要離開(kāi)前一段公路進(jìn)入新段公路的車(chē)輛進(jìn)行計(jì)費(fèi)，該查詢(xún)有兩個(gè)輸入流，分別為查詢(xún)四和查詢(xún)六的輸出流segmenttoll和newcarentry。該查詢(xún)的輸出數(shù)據(jù)流為cartoll，其模式為（car_id.Toll，way，dir，seg），該輸出數(shù)據(jù)流也是最終要得到的數(shù)據(jù)流。

上述七個(gè)查詢(xún)組合在一起完成了車(chē)輛計(jì)費(fèi)模塊功能。這些查詢(xún)經(jīng)過(guò)查詢(xún)解析模塊解析后可得到如圖3所示的物理執(zhí)行計(jì)劃。該執(zhí)行計(jì)劃包括了三個(gè)聚集操作符、兩個(gè)連接操作符、兩個(gè)選擇操作符和三個(gè)投影操作符。根據(jù)車(chē)輛計(jì)費(fèi)模塊查詢(xún)定義可以看出，Conger CQL提供了良好的表達(dá)能力，可使用戶(hù)不用直接使用這些底層操作符構(gòu)建查詢(xún)網(wǎng)絡(luò)。

圖3 物理執(zhí)行計(jì)劃

將車(chē)輛計(jì)費(fèi)模塊的七個(gè)查詢(xún)?cè)贏uraro系統(tǒng)上進(jìn)行了部署和運(yùn)行。查詢(xún)的輸入數(shù)據(jù)流為MIT開(kāi)發(fā)的交通微觀仿真軟件MITSIMLab生成的3 h的道路交通信息，這些數(shù)據(jù)由客戶(hù)端實(shí)時(shí)地發(fā)送給Aurora系統(tǒng)，圖4給出了編號(hào)為694的車(chē)輛所收到的部分輸出數(shù)據(jù)流?？梢钥闯鲈?94號(hào)車(chē)輛行駛過(guò)程中，每當(dāng)進(jìn)入一個(gè)新路段時(shí)都會(huì)收到系統(tǒng)發(fā)送的該路段的費(fèi)率情況。

圖4 編號(hào)為694車(chē)輛的部分輸出數(shù)據(jù)流

還利用Linear Road Benchmark自帶的正確性校驗(yàn)程序?qū)?chē)輛計(jì)費(fèi)模塊完整的輸出數(shù)據(jù)流進(jìn)行了正確性檢驗(yàn)。實(shí)驗(yàn)結(jié)果表明，查詢(xún)的輸出數(shù)據(jù)流在內(nèi)容上和時(shí)間順序上與標(biāo)準(zhǔn)輸出數(shù)據(jù)流一致。

通過(guò)Linear Road Benchmark測(cè)試表明針對(duì)這些測(cè)試用例，Conger CQL具有良好的表達(dá)能力和較好的完備性和正確性。此外，本文所設(shè)計(jì)的語(yǔ)言可根據(jù)新的持續(xù)性查詢(xún)語(yǔ)言的規(guī)范進(jìn)行擴(kuò)充和完善[14]。

5 結(jié)束語(yǔ)

本文設(shè)計(jì)了一個(gè)語(yǔ)義完備且具有豐富表達(dá)能力數(shù)據(jù)流持續(xù)型查詢(xún)語(yǔ)言Conger CQL，并在Aurora數(shù)據(jù)流管理系統(tǒng)上對(duì)該語(yǔ)言進(jìn)行了實(shí)現(xiàn)。為驗(yàn)證Conger CQL的正確性和有效性，使用Conger CQL對(duì)Linear Road Benchmark的查詢(xún)集進(jìn)行了定義并在Aurora部署運(yùn)行。實(shí)驗(yàn)結(jié)果表明Conger CQL能夠完整地表達(dá)Linear Road Benchmark的查詢(xún)集，為這些查詢(xún)集提供了正確的查詢(xún)語(yǔ)義。

[1]Datar M，Gionis A，Indyk P，et al.Maintaining stream statistics over sliding windows[C]//Proc of the 2002 Annual ACM-SIAM Symp on Discrete Algorithms，2002：635-644.

[2]Gilbert A，Guha S，Indyk P，et al.Fast small-space algorithms for approximate histogram maintenance[C]//Proc of the 2002 Annual ACM Symp on Theory of Computing，2002：389-398.

[3]Zhu Y，Shasha D.StatStream：statistical monitoring of thousands of data streams in real time[C]//Proc of Int Conf on Very Large Data Bases，2002：358-369.

[4]Abadi D，Carney D，Cetintemel U，et al.Aurora：a new model and architecture for data stream management[J]. VLDB Journal，2003，12（2）：120-139.

[5]Arasu A，Cherniack M，Galvez E，et al.Linear road：a stream data management benchmark[C]//Proceedings of the 30th International Conference on Very Large Data Bases Conference，2004：480-491.

[6]Arasu A，Babcock B，Babu S，et al.STREAM：the stanford stream data manager[J].IEEE Data Eng Bull，2003，26（1）：19-26.

[7]ChandrasekaranS，CooperO，DeshpandeA，etal. TelegraphCQ：continuous dataflow processing[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data，2003.

[8]Kramer J，Seeger B.Semantics and implementation of continuous sliding window queries over data streams[J].ACM Trans on Database Systems，2009，34（1）：4-20.

[9]Tucker P，Maier D，Sheard T，et al.Enhancing relational operators for querying over punctuated data streams[EB/OL]. [2012-09-17].http：//www.cse.ogi.edu/dot/niagara/pstream/ punctuating.pdf.

[10]Arasu A，Babcock B，Babu S，et al.Characterizing memory requirements for queries over continuous data streams[J]. ACM Transactions on Database Systems，2004，29（1）：162-194.

[11]陳思寧，陳磊松.數(shù)據(jù)流持續(xù)查詢(xún)系統(tǒng)的窗口語(yǔ)義研究[J].漳州師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2006（4）：50-53.

[12]Chandrasekaran S，F(xiàn)ranklin M J.Streaming queries over streaming data[C]//Proc Int Conf on Very Large Data Bases，2002：203-214.

[13]Jain N，Amini L，Andrade H，et al.Design，implementation，and evaluation of the linear road benchmark on the stream processing core，Technical Report TR-06-18[R]. Department of Computer Sciences，University of Texas at Austin，2006.

[14]Jain N，Mishra S，Srinivasan A，et al.Towards a streaming SQL standard[C]//Proc of VLDB，2008：1379-1390.

WANG Hongya,CAO Jiao,JIN Jie

College of Computer Science and Technology,Donghua University,Shanghai 201620,China

The research on data stream management systems has gained much attention recently because of the emergence of many real-time data processing applications.Aurora is a general-purpose fully functional data stream management system, which only supports queries in the form of operator network.To this end,this paper designs and implements a continuous query language called Conger CQL based on Aurora.In order to verify the expression ability of Conger CQL,it implements the Linear Road Benchmark using Conger CQL,which shows that Conger CQL is able to express complex continuous queries defined by the Linear Road Benchmark.

data stream;data stream management system;continuous query language

A

TP311

10.3778/j.issn.1002-8331.1211-0275

WANG Hongya,CAO Jiao,JIN Jie.Design and implementation of continuous query language based on Aurora system. Computer Engineering and Applications,2014,50（21）：133-138.

國(guó)家自然科學(xué)基金（No.60903160，No.61103046）。

王洪亞（1976—），男，博士，副教授，主要研究方向?yàn)閿?shù)據(jù)庫(kù)理論與系統(tǒng)、實(shí)時(shí)計(jì)算和移動(dòng)計(jì)算；曹姣（1989—），女，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)庫(kù)理論、查詢(xún)處理；金杰（1987—），男，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)流管理系統(tǒng)。E-mail：hy-wang@dhu.edu.cn

2012-11-23

2013-03-18

1002-8331（2014）21-0133-06

CNKI出版日期：2013-04-08，http://www.cnki.net/kcms/detail/11.2127.TP.20130408.1650.024.html