论文部分内容阅读
摘 要 数据流系统以连续查询为特点，连续查询的处理机制能够保证数据处理做到实时处理。但是现有的通用的数据流系统没有对空间数据处理的支持，而基于位置服务显然是一种需要空间数据处理的应用。本文从支持位置服务的后台数据处理出发，提出用基于数据流系统的流数据库来支持基于位置服务的数据处理的思想，并结合当今数据流系统的发展和基于位置的服务的需求，对数据流系统进行空间扩展，提出一种空间数据流系统的模型。
关键词 数据流 空间连续查询 LBS
1 数据流系统
数据流（data stream）应用的出现引起了国内外专家和学者的关注，数据流管理技术作为一种新兴的技术已经被广泛的研究，目前通用的DSMS（data stream management system）包括TelegraphCQ[1]，Aurora[2]和STREAM[3]。
数据流的查询过程是持续的查询（continuous query）[4]，持续查询所关心的并不是全部的数据，而是近期最近到达的部分数据，所以数据流中的持续查询采用滑动窗口（moving window）机制，基于滑动窗口的查询。
本文基于通用流数据库[5][6]，构建一个空间数据流系统模型。在此过程中，借鉴交通导航应用开展工作。这里的空间流数据库模型系统的主要的工作仅包括增加空间数据类型、空间滑动窗口和空间谓词，为了实现简单易懂的空间连续查询语言，本文在设计时，尽量和原有的空间数据库查询语言和连续查询语言做到统一。本文依据标准SQL和CQL设计空间数据类型和空间谓词，并参考OGIS标准，尽量不修改原有查询语言的结构，采用通用的空间数据类型表示方法，通过增加通用的关键词的方式，扩展连续查询查询语言。
2 空间数据类型扩展
我们考虑交通导航LBS（Location Based Service）应用，在这种应用中，需要知道移动对象前方道路的交通状况，根据交通状况选择合适的运行路线。假定每个移动对象每隔30秒向导航服务中心报告移动对象当前的速度和位置信息。前方的交通状况由运行在前方的一定范围的移动对象数量和这些移动对象的平均速度来决定，数量多并且平均速度小于40km/h就表示交通状况差，否则交通状况良好。随着移动汽车位置的改变，其维持的空间查询窗口也在不断的改变位置，如果设计一种空间滑动窗口，使之能够随着移动对象的改变而改变，就可以解决这个问题。
根据例子应用的需要，拟增加的空间数据类型有Point和SSwin两种。Point用来表示一个移动对象，而SSwin用来表示一个空间滑动窗口。
（1）Point[x:float, y:float]，在这里Point表示某个移动对象，它的值为移动对象的二维空间坐标；
（2）SSwin [Point1, Point2]，表示某一空间滑动窗口，为了简化问题，此处的SSwin，仅表示一个矩形的空间滑动窗口，由两个Point标识。
3 增加空间滑动窗口查询函数
为了支持空间查询，需要增加空间谓词和空间函数，本文需要增加空间函数Inside，用来判断空间移动物体是否在空间滑动窗口内。
（1）Inside（Obj，SSwin）
这里的SSwin表示空间滑动窗口，Obj表示移动对象位置，此运算符的结果为整型，当Obj在SSwin 的内部时，其值为0，否则，返回值为1。
（2）空间滑动窗口的连续查询
通过以上增加了空间数据类型和空间谓词以后，流数据库可以支持空间滑动窗口的连续查询。粗体字部分表示本文增加的空间谓词：
:
……
:
|
:
INSIDE (, )
……
4 空间滑动窗口查询的实现
本文的空间流数据库模型的实现工作是基于STREAM流数据库管理系统，通过修改此系统的代码，实现空间流数据库系统。此系统是斯坦福大学开发的一个的通用的流数据管理模型。此数据库管理系统模型是开放源代码的。它能够处理对多个连续的数据流和存储关系的连续查询。它提供大量的复杂流查询，用来处理高容量和高突发性的数据流。它提供丰富的连续查询语言，有良好的交互操作界面。
本文的实现是要在流数据库管理系统的基础上进行扩展，虽然仅是对原有系统的扩展，但是需要做的工作仍然涉及到整个数据库管理设计的全过程。一个数据库管理系统的设计包括一系列的阶段，一般遵循以下的顺序。同时以下这些步骤也是实现此空间流数据库的过程中，主要的工作：
（1）生成词法分析树：由抽象的查询语言生成词法分析树，这个过程是数据流管理系统实现的最初阶段。根据上节定义的空间连续查询语法，在本文的空间数据流系统中，用Yacc[7]生成查询语言的语法分析树。
（2）语义分析：对词法分析树进行语义分析，将词法分析树转换为系统能够识别的内部表示。这一步生成的语义表示仍然不是一个操作符树。这个过程的设计主要是将空间数据类型和空间谓词转换为系统能够识别的形式，具体的实现类似于算术表达式的语义转换。
（3）生成逻辑计划：将查询的内部表示转换为逻辑查询计划。逻辑查询计划由逻辑操作符组成。逻辑操作符大多是关系代数操作符（比如：选择，投影，连接等），当然也有一些连续查询特有的操作符（比如滑动窗口操作符）。逻辑操作符不需要和查询执行中的操作符有关，它仅仅是一种关系代数的抽象表示。
（4）生成物理计划：将逻辑查询计划转换为物理查询计划。物理查询计划中的操作符是直接和在查询执行期间执行的操作符相关的。之所以要生成一个单独的逻辑查询计划，是因为逻辑查询计划更加容易生成，而物理查询计划涉及到底层细节。 （5）查询执行：组织存储空间的分配，物理操作符的执行等。
5 实验
5.1 LBS运动模型
构造如图1所示的导航应用，移动汽车每30秒向导航中心报告当前位置信息和行驶速度并且进行空间滑动窗口的聚集查询，这里我们主要涉及count和avg聚集查询，分别计算滑动窗口内汽车数量和平均速度。移动汽车根据查询结果了解前方路况，以起到交通导航的作用。
5.2 输入设计
（1）MovCar
MovCar的结构如下表所示：
（2）SpaSliWindow
空间滑动窗口（SpaSliWindow）数据流，该数据流包含空间滑动窗口标志信息和空间滑动窗口位置信息：
5.3 空间滑动窗口查询设计
上一节中构造了两个输入数据流，分别模拟移动汽车信息数据流和空间滑动窗口数据流，下面编写空间滑动窗口查询的脚本语言，该查询脚本基于前面分析的简单的交通导航应用以CQL（持续查询语言）编写，脚本文件如图2所示。
5.4 结果输出
注册了输入数据流，并且定义了空间滑动窗口查询之后，经过我们设计的空间流数据库模型的处理得出图3和图4所示的结果。图3所示为导航查询结果，可以看出，在61时刻的滑动窗口3内有6辆移动汽车，汽车平均速度为34.1667km/h，小于40km/h，满足查询条件，由此汽车A得知此刻前方路段交通状况差，可以采取积极的应对措施，绕过此拥挤的路段。图4所示为每个查询时刻对应空间滑动窗口内的汽车信息，可以看出，1时刻的空间滑动窗口内有移动汽车A、B、C、D、E，31时刻的空间滑动窗口内有移动汽车A、B、C、D，61时刻的空间滑动窗口内有移动汽车A、B、C、D、E、F，91时刻的空间滑动窗口内有移动汽车A、B、C，121时刻的空间滑动窗口内有移动汽车A、C。
6 小结
本文结合交通导航应用对数据流系统进行空间扩展，扩展了空间点和空间滑动窗口，及基于空间滑动窗口的查询操作，并依据数据库的设计步骤，实现了空间数据流系统。以导航应用为例，构造了一个基于空间滑动窗口的运动模型，通过试验分析，输出的结果均符合我们设计的运动模型。
参 考 文 献
[1] Sirish C, Owen C, Amol D, Michael JF, Joseph MH, Wei H, Sailesh K, Samuel RM, Fred R, Mehul AS. TelegraphCQ: Continuous dataflow processing[R]. In: Alon YH, ed. Proc. of the 2003 ACM SIGMOD Int’l Conf. on Management of Data. New York: ACM Press, 2003. 668—668.
[2] Daniel JA, Don C, Ugur C, Mitch C, Christian C, Sangdon L, Michael S, Nestime T, Stan Z. Aurora: A new model and architecture for data stream management[J]. The Int’l Journal on Very Large Data Bases, 2003,12(2):120—139.
[3] A. Arasu, B. Babcock, S. Babu, M. Datar, K. Ito, I. Nishizawa, J. Rosenstein, and J.
Widom. STREAM: The stanford stream data manager[J]. IEEE Data Engineering Bulletin, 2003,26(1):19—26.
[4] Shivanath B, Jennifer W. Continuous queries over data streams[J]. SIGMOD Record,2001,
30(3):109—120.
[5] 姜芳艽.DBMS与DSMS的比较研究.微计算机信息，2007.2，3:33-36.
[6] 金澈清，钱卫宁，周傲英.流数据分析与管理综述.软件学报，2004，15(8):1172-1181
A Model of Spatial Data Stream Systembased on Data Stream System
Gong Piqiang，Jiang Jie
（Jiangsu Provincial Posts and Telecommunications Planning and design institute limited liability company，Nanjing 210003，China）
Abstract The data stream system has the characteristic of continuous query which can provide real-time data processing. The existing general data stream system does not support spatial data processing, but location based service appearntly require spatial data processing.This paper proposed the method which implements LBS applications by stream database based on data stream system from the data processing view. Futhermore, this paper expands the stream database to support spatial operation which can provide data processing for LBS applications and satisfy the requirement of LBS applications and finally proposed a model of spatial data stream system.
Key words data stream，Spatial Continuous Query，LBS
（收稿日期：2012年8月21日）
关键词 数据流 空间连续查询 LBS
1 数据流系统
数据流（data stream）应用的出现引起了国内外专家和学者的关注，数据流管理技术作为一种新兴的技术已经被广泛的研究，目前通用的DSMS（data stream management system）包括TelegraphCQ[1]，Aurora[2]和STREAM[3]。
数据流的查询过程是持续的查询（continuous query）[4]，持续查询所关心的并不是全部的数据，而是近期最近到达的部分数据，所以数据流中的持续查询采用滑动窗口（moving window）机制，基于滑动窗口的查询。
本文基于通用流数据库[5][6]，构建一个空间数据流系统模型。在此过程中，借鉴交通导航应用开展工作。这里的空间流数据库模型系统的主要的工作仅包括增加空间数据类型、空间滑动窗口和空间谓词，为了实现简单易懂的空间连续查询语言，本文在设计时，尽量和原有的空间数据库查询语言和连续查询语言做到统一。本文依据标准SQL和CQL设计空间数据类型和空间谓词，并参考OGIS标准，尽量不修改原有查询语言的结构，采用通用的空间数据类型表示方法，通过增加通用的关键词的方式，扩展连续查询查询语言。
2 空间数据类型扩展
我们考虑交通导航LBS（Location Based Service）应用，在这种应用中，需要知道移动对象前方道路的交通状况，根据交通状况选择合适的运行路线。假定每个移动对象每隔30秒向导航服务中心报告移动对象当前的速度和位置信息。前方的交通状况由运行在前方的一定范围的移动对象数量和这些移动对象的平均速度来决定，数量多并且平均速度小于40km/h就表示交通状况差，否则交通状况良好。随着移动汽车位置的改变，其维持的空间查询窗口也在不断的改变位置，如果设计一种空间滑动窗口，使之能够随着移动对象的改变而改变，就可以解决这个问题。
根据例子应用的需要，拟增加的空间数据类型有Point和SSwin两种。Point用来表示一个移动对象，而SSwin用来表示一个空间滑动窗口。
（1）Point[x:float, y:float]，在这里Point表示某个移动对象，它的值为移动对象的二维空间坐标；
（2）SSwin [Point1, Point2]，表示某一空间滑动窗口，为了简化问题，此处的SSwin，仅表示一个矩形的空间滑动窗口，由两个Point标识。
3 增加空间滑动窗口查询函数
为了支持空间查询，需要增加空间谓词和空间函数，本文需要增加空间函数Inside，用来判断空间移动物体是否在空间滑动窗口内。
（1）Inside（Obj，SSwin）
这里的SSwin表示空间滑动窗口，Obj表示移动对象位置，此运算符的结果为整型，当Obj在SSwin 的内部时，其值为0，否则，返回值为1。
（2）空间滑动窗口的连续查询
通过以上增加了空间数据类型和空间谓词以后，流数据库可以支持空间滑动窗口的连续查询。粗体字部分表示本文增加的空间谓词：
……
INSIDE (
……
4 空间滑动窗口查询的实现
本文的空间流数据库模型的实现工作是基于STREAM流数据库管理系统，通过修改此系统的代码，实现空间流数据库系统。此系统是斯坦福大学开发的一个的通用的流数据管理模型。此数据库管理系统模型是开放源代码的。它能够处理对多个连续的数据流和存储关系的连续查询。它提供大量的复杂流查询，用来处理高容量和高突发性的数据流。它提供丰富的连续查询语言，有良好的交互操作界面。
本文的实现是要在流数据库管理系统的基础上进行扩展，虽然仅是对原有系统的扩展，但是需要做的工作仍然涉及到整个数据库管理设计的全过程。一个数据库管理系统的设计包括一系列的阶段，一般遵循以下的顺序。同时以下这些步骤也是实现此空间流数据库的过程中，主要的工作：
（1）生成词法分析树：由抽象的查询语言生成词法分析树，这个过程是数据流管理系统实现的最初阶段。根据上节定义的空间连续查询语法，在本文的空间数据流系统中，用Yacc[7]生成查询语言的语法分析树。
（2）语义分析：对词法分析树进行语义分析，将词法分析树转换为系统能够识别的内部表示。这一步生成的语义表示仍然不是一个操作符树。这个过程的设计主要是将空间数据类型和空间谓词转换为系统能够识别的形式，具体的实现类似于算术表达式的语义转换。
（3）生成逻辑计划：将查询的内部表示转换为逻辑查询计划。逻辑查询计划由逻辑操作符组成。逻辑操作符大多是关系代数操作符（比如：选择，投影，连接等），当然也有一些连续查询特有的操作符（比如滑动窗口操作符）。逻辑操作符不需要和查询执行中的操作符有关，它仅仅是一种关系代数的抽象表示。
（4）生成物理计划：将逻辑查询计划转换为物理查询计划。物理查询计划中的操作符是直接和在查询执行期间执行的操作符相关的。之所以要生成一个单独的逻辑查询计划，是因为逻辑查询计划更加容易生成，而物理查询计划涉及到底层细节。 （5）查询执行：组织存储空间的分配，物理操作符的执行等。
5 实验
5.1 LBS运动模型
构造如图1所示的导航应用，移动汽车每30秒向导航中心报告当前位置信息和行驶速度并且进行空间滑动窗口的聚集查询，这里我们主要涉及count和avg聚集查询，分别计算滑动窗口内汽车数量和平均速度。移动汽车根据查询结果了解前方路况，以起到交通导航的作用。
5.2 输入设计
（1）MovCar
MovCar的结构如下表所示：
（2）SpaSliWindow
空间滑动窗口（SpaSliWindow）数据流，该数据流包含空间滑动窗口标志信息和空间滑动窗口位置信息：
5.3 空间滑动窗口查询设计
上一节中构造了两个输入数据流，分别模拟移动汽车信息数据流和空间滑动窗口数据流，下面编写空间滑动窗口查询的脚本语言，该查询脚本基于前面分析的简单的交通导航应用以CQL（持续查询语言）编写，脚本文件如图2所示。
5.4 结果输出
注册了输入数据流，并且定义了空间滑动窗口查询之后，经过我们设计的空间流数据库模型的处理得出图3和图4所示的结果。图3所示为导航查询结果，可以看出，在61时刻的滑动窗口3内有6辆移动汽车，汽车平均速度为34.1667km/h，小于40km/h，满足查询条件，由此汽车A得知此刻前方路段交通状况差，可以采取积极的应对措施，绕过此拥挤的路段。图4所示为每个查询时刻对应空间滑动窗口内的汽车信息，可以看出，1时刻的空间滑动窗口内有移动汽车A、B、C、D、E，31时刻的空间滑动窗口内有移动汽车A、B、C、D，61时刻的空间滑动窗口内有移动汽车A、B、C、D、E、F，91时刻的空间滑动窗口内有移动汽车A、B、C，121时刻的空间滑动窗口内有移动汽车A、C。
6 小结
本文结合交通导航应用对数据流系统进行空间扩展，扩展了空间点和空间滑动窗口，及基于空间滑动窗口的查询操作，并依据数据库的设计步骤，实现了空间数据流系统。以导航应用为例，构造了一个基于空间滑动窗口的运动模型，通过试验分析，输出的结果均符合我们设计的运动模型。
参 考 文 献
[1] Sirish C, Owen C, Amol D, Michael JF, Joseph MH, Wei H, Sailesh K, Samuel RM, Fred R, Mehul AS. TelegraphCQ: Continuous dataflow processing[R]. In: Alon YH, ed. Proc. of the 2003 ACM SIGMOD Int’l Conf. on Management of Data. New York: ACM Press, 2003. 668—668.
[2] Daniel JA, Don C, Ugur C, Mitch C, Christian C, Sangdon L, Michael S, Nestime T, Stan Z. Aurora: A new model and architecture for data stream management[J]. The Int’l Journal on Very Large Data Bases, 2003,12(2):120—139.
[3] A. Arasu, B. Babcock, S. Babu, M. Datar, K. Ito, I. Nishizawa, J. Rosenstein, and J.
Widom. STREAM: The stanford stream data manager[J]. IEEE Data Engineering Bulletin, 2003,26(1):19—26.
[4] Shivanath B, Jennifer W. Continuous queries over data streams[J]. SIGMOD Record,2001,
30(3):109—120.
[5] 姜芳艽.DBMS与DSMS的比较研究.微计算机信息，2007.2，3:33-36.
[6] 金澈清，钱卫宁，周傲英.流数据分析与管理综述.软件学报，2004，15(8):1172-1181
A Model of Spatial Data Stream Systembased on Data Stream System
Gong Piqiang，Jiang Jie
（Jiangsu Provincial Posts and Telecommunications Planning and design institute limited liability company，Nanjing 210003，China）
Abstract The data stream system has the characteristic of continuous query which can provide real-time data processing. The existing general data stream system does not support spatial data processing, but location based service appearntly require spatial data processing.This paper proposed the method which implements LBS applications by stream database based on data stream system from the data processing view. Futhermore, this paper expands the stream database to support spatial operation which can provide data processing for LBS applications and satisfy the requirement of LBS applications and finally proposed a model of spatial data stream system.
Key words data stream，Spatial Continuous Query，LBS
（收稿日期：2012年8月21日）