基于Aurora系統的持續型查詢語言設計與實現

王洪亞，曹姣，金杰

東華大學計算機科學與技術學院，上海 201620

基于Aurora系統的持續型查詢語言設計與實現

王洪亞，曹姣，金杰

東華大學計算機科學與技術學院，上海 201620

隨著新型數據應用的不斷出現，針對流形態數據的數據流管理系統已經成為數據管理領域研究的新熱點。針對目前通用數據流管理系統只支持基于操作符流圖的查詢表達方式這一不足，設計了一種新的持續型數據流查詢語言，并在通用數據流處理系統Aurora上進行了實現。為驗證新語言的表達能力，該系統使用新語言定義了數據流基準測試Linear Road Benchmark的查詢集，在Aurora系統上部署運行。測試結果表明針對Linear Road Benchmark的測試用例，新語言具有較完備的語義和良好的表達能力。

數據流；數據流管理系統；持續型查詢語言

1 引言

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

雖然Aurora原型系統具有豐富的數據流操作符、可擴展的軟件架構和良好的數據流處理性能，但在Aurora中不支持聲明式（Declarative）的數據流查詢語言，所有用戶查詢需要通過圖形接口表示為操作符流圖。這對于大量熟悉SQL語句的數據庫開發人員來說很不方便，同時也不利于后續基于Aurora系統的研究與開發。為此，基于Aurora系統設計和開發了一種通用的持續型查詢語言Conger CQL，本文的主要工作包括：

（1）設計了一個具有精確語義和豐富表達能力的持續型查詢語言Conger CQL。

（2）在Aurora數據流原型系統上實現了Conger CQL，具體包括Conger CQL的BNF定義、CQL查詢解析和核心數據結構生成以及Aurora操作符綁定等，最終根據用戶的查詢定義生成相應的物理執行計劃。

（3）為了驗證Conger CQL的表達能力，使用新語言定義了標準測試程序Linear Road Benchmark的查詢集。測試結果表明Conger CQL具有精確的語義和豐富的表達能力，可以表達復雜的持續型查詢。

2 Aurora數據流處理系統簡介

Aurora數據流管理系統是由美國布蘭代斯大學、布朗大學和麻省理工學院合作開發的一個數據流管理原型系統。Aurora采用了類似于工作流的查詢語言，其最重要的結構是Box和Arrow，每一個Box代表一個操作符（Operator）；每一個有向的Arrow代表數據流從一個操作符傳遞到另外一個操作符。一個Aurora的查詢定義為由操作符組成的有向無環圖，如圖1所示。

圖1 Aurora系統模型圖

Aurora定義和實現了七種基本操作符，分別是選擇（Filter）、投影（Map）、合并（Union）、冒泡排序（BSort）、聚集（Aggregate）、連接（Join）和重采樣（Resample）。這些操作符和傳統的關系代數類似，但由于數據流具有潛在的無限性，對于連接這樣的阻塞型操作符，需要使用滑動窗口將數據流轉換為時變關系，然后再在滑動窗口上進行連接操作。這是數據流處理與傳統關系型數據庫查詢處理的重要區別之一。

Aurora系統支持三種類型的查詢，即持續查詢（Continuous Query）、視圖和Ad hoc查詢。持續查詢一旦由用戶注冊后就一直在系統中運行；視圖是調度器控制下物化的用戶定義查詢，通過視圖可以加快查詢的速度；Ad hoc查詢指一次性的針對數據流和歷史數據的用戶查詢。Aurora的系統模型如圖1所示。

Aurora系統只支持基于操作符流圖的查詢定義方式，雖然該方式具有比較直觀的特點，但用戶需要對底層操作符有足夠深入的理解才能構造出所需要的操作符網絡，而這一過程對大量熟悉SQL語言的數據庫開發人員來說過于復雜。為此，本文設計了面向數據流處理的持續型查詢語言Conger CQL[8]，并在Aurora數據流管理系統上進行了實現。需要強調的是Aurora的操作符圖和本文設計實現的持續型查詢語言各有自己的優點，是互為補充的關系。

3 持續性查詢語言設計與實現

3.1 Conger CQL設計

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

下面分別對語法中的主要組成部分進行詳細描述。

（1）滑動窗口定義（window_specification）[11]

滑動窗口是數據流處理中為了避免阻塞型操作符（如連接操作）長時間等待到達流數據而無法及時輸出結果所采用的一種機制，在數據流處理系統中被廣泛使用，Conger CQL的滑動窗口語法定義如下：

其中關鍵字RANGE定義窗口的大?。籗LIDE定義窗口的滑動距離；ON定義時間屬性；ROW定義該窗口是基于元組個數的。示例查詢2給出了一個窗口大小為10 min，滑動距離為1 min的窗口定義。

（2）SELECT子句

每個SELECT子句至少要有一個選擇列表（select_ expr）來指定要選擇的字段或表達式。在示例查詢1中，數據流stock_stream的所有字段都按原有的順序輸出，該子句對應Aurora的投影操作符。

（3）FROM子句

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

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

（4）WHERE子句

WHERE是Conger CQL中的可選子句，其中where_ condition指定對輸入數據流的選擇謂詞，該子句對應Aurora的選擇操作符。示例查詢3表示從輸入流中篩選出價格大于10的股票交易數據。

示例查詢3：SELECT*FROM stock_stream WHERE price>10

（5）GROUP BY子句

GROUP BY子句也是Conger CQL中的可選子句，對應Aurora的聚集操作符，用于對數據流進行常見的統計操作。示例查詢4中，該查詢首先計算最近一段時間（10 min）每個股票的最大價格，然后選擇最大價格大于10的輸出出來。

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

表1給出了Conger CQL與數據流常用關系操作符的對應關系，證明設計的語言在語義上是完備的。

表1 Conger CQL與關系操作符對應關系

3.2Conger CQL實現

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

首先使用自動編譯器生成工具ANTLR3定義了Conger CQL的BNF描述。下面給出了Conger CQL的BNF描述的一個片段，受篇幅限制（完整的BNF描述有超過700行的語法定義），沒有列出完整的Conger CQL的BNF描述。

在上述BNF語法定義中，sfw_block是最頂層的語法規則，表示一個完整SELECT-FROM-WHERE查詢語句，它由一個select_clause子句、from_clause子句，加上可選的opt_group_by_clause子句、opt_having_clause子句、opt_where_clause子句組成。關鍵字“->^”指定了生成抽象語法樹的結構。

完成BNF定義后，就可以對輸入的Conger CQL進行詞法和語法解析，并生成抽象語法樹。對示例查詢5解析后，可以得到圖2所示的抽象語法樹。

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

在編譯得到抽象語法樹后，需要遍歷抽象語法樹，將用戶的查詢參數寫入到自定義的核心數據結構中。同樣限于篇幅沒有給出所定義的核心數據結構，有興趣的讀者可以在https：//github.com/dhu/conger上下載。

完成核心數據結構的初始化后，最后需要根據這些數據結構的內容將Aurora的相關操作符組合成查詢網絡，完成物理執行計劃的生成。在目前的版本，主要支持對應一個和兩個Aurora操作符Conger CQL查詢，由多個操作符組成的查詢網絡可表達為多個查詢語句。首先介紹僅對應一個操作符的查詢類別：

（1）SELECT*FROM stream_name WHERE id>1，該類查詢對應Aurora的選擇操作符。

圖2 抽象語法樹

（2）SELECT id，name FROM stream_name，該類查詢對應Aurora的投影操作符。

（3）SELECTCOUNT（id）FROMstream_name [RANGE 10 MINUTES SLIDE 1 MINUTE]，該類查詢對應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，該類查詢對應Aurora的連接操作符。

下面，將介紹對應兩個Aurora操作符的復雜CQL。考慮Aurora中最重要的四個操作符：選擇、投影、連接和聚集，這四個操作符一共有如下12種組合方式：

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

（2）投影->選擇，可以用第一種情況代替，因為位置互換后兩者的語義是等價的。

（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）連接->選擇，與上一種情況語義是等價的。

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

（6）投影->連接，沒有Conger CQL語句對應這種組合。

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

（8）投影->聚集，沒有Conger CQL語句對應這種組合。

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

（10）聚集->連接，沒有Conger CQL語句對應這種組合。

（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。

上述兩個操作符組合的技術關鍵在于需將第一個操作符的輸出流命名為一個中間流，然后將其作為第二個操作符的輸入流，并最終組合成查詢網絡[12]。這些都涉及到對Aurora系統核心代碼的修改和擴充，具體代碼見https：//github.com/dhu/conger。

4 實驗評估

完成持續型查詢語言Conger CQL的設計和實現后，需要對其表達能力和語義正確性進行測試。本文使用目前數據流處理事實上的標準測試程序Linear Road Benchmark對Conger CQL進行了測試。

Linear Road Benchmark[13]模擬了一個高速公路的收費系統，在系統中假設一個城市由10條并行的高速公路組成，每條高速公路被分成100段，每段都有一個進出口，汽車可以隨意根據當前的路況選擇在某一段進入或離開某一個高速公路。高速公路中的汽車每30 s向服務器發送一個位置信息。

下面以Linear Road Benchmark中的車輛計費模塊為例介紹Conger CQL測試結果。車輛計費模塊的功能是實時地統計每段道路的擁塞程度，并根據路況計算收費額度，同時對離開該段道路的車輛發送計費信息[3]。

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

查詢三計算平均車速小于40 mile/h的路段，該查詢將查詢一和查詢二的輸出數據流segvol、segavgspee進行連接操作。查詢三的輸出數據流為segmenttoll_filter，輸出流的模式為（way，dir，seg，volume，vol_time，avgspeed_ time，avg_speed）。

查詢四根據收費規則計算每一段平均車速小于40 mile/h的公路的當前費率。費率計算公式為15×（volume-150）×（volume-150），其中volume為當前該路段上的車流量。該查詢的輸入流為查詢三的輸出流segmenttoll_filter。輸出流為segmenttoll，其模式為（time，way，dir，seg，vol_time，avgspeed_time，toll）。

查詢五計算當前公路上正在行駛的車輛數量，輸入數據流為positionreport，輸出數據流為curactivecars，其模式為（car_id，way，dir，seg，time，car_count）。

查詢六統計哪些車輛第一次進入一個新路段。輸入數據流為curactivecars，輸出數據流為newcarentry，輸出流模式為（car_id，way，dir，seg，time，car_count）。

查詢七對那些正要離開前一段公路進入新段公路的車輛進行計費，該查詢有兩個輸入流，分別為查詢四和查詢六的輸出流segmenttoll和newcarentry。該查詢的輸出數據流為cartoll，其模式為（car_id.Toll，way，dir，seg），該輸出數據流也是最終要得到的數據流。

上述七個查詢組合在一起完成了車輛計費模塊功能。這些查詢經過查詢解析模塊解析后可得到如圖3所示的物理執行計劃。該執行計劃包括了三個聚集操作符、兩個連接操作符、兩個選擇操作符和三個投影操作符。根據車輛計費模塊查詢定義可以看出，Conger CQL提供了良好的表達能力，可使用戶不用直接使用這些底層操作符構建查詢網絡。

圖3 物理執行計劃

將車輛計費模塊的七個查詢在Auraro系統上進行了部署和運行。查詢的輸入數據流為MIT開發的交通微觀仿真軟件MITSIMLab生成的3 h的道路交通信息，這些數據由客戶端實時地發送給Aurora系統，圖4給出了編號為694的車輛所收到的部分輸出數據流?？梢钥闯鲈?94號車輛行駛過程中，每當進入一個新路段時都會收到系統發送的該路段的費率情況。

圖4 編號為694車輛的部分輸出數據流

還利用Linear Road Benchmark自帶的正確性校驗程序對車輛計費模塊完整的輸出數據流進行了正確性檢驗。實驗結果表明，查詢的輸出數據流在內容上和時間順序上與標準輸出數據流一致。

通過Linear Road Benchmark測試表明針對這些測試用例，Conger CQL具有良好的表達能力和較好的完備性和正確性。此外，本文所設計的語言可根據新的持續性查詢語言的規范進行擴充和完善[14]。

5 結束語

本文設計了一個語義完備且具有豐富表達能力數據流持續型查詢語言Conger CQL，并在Aurora數據流管理系統上對該語言進行了實現。為驗證Conger CQL的正確性和有效性，使用Conger CQL對Linear Road Benchmark的查詢集進行了定義并在Aurora部署運行。實驗結果表明Conger CQL能夠完整地表達Linear Road Benchmark的查詢集，為這些查詢集提供了正確的查詢語義。

[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]陳思寧，陳磊松.數據流持續查詢系統的窗口語義研究[J].漳州師范學院學報：自然科學版，2006（4）：50-53.

[12]Chandrasekaran S，Franklin 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.

國家自然科學基金（No.60903160，No.61103046）。

王洪亞（1976—），男，博士，副教授，主要研究方向為數據庫理論與系統、實時計算和移動計算；曹姣（1989—），女，碩士研究生，主要研究方向為數據庫理論、查詢處理；金杰（1987—），男，碩士研究生，主要研究方向為數據流管理系統。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