基于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定义窗口的大小；SLIDE定义窗口的滑动距离；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的车辆所收到的部分输出数据流。可以看出在694号车辆行驶过程中，每当进入一个新路段时都会收到系统发送的该路段的费率情况。

图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