（计算机软件与理论专业论文）数据流管理系统的研究与设计(1).pdf

南京航空航天大学硕士学位论文 摘要 传统的数据库管理系统用于处理永久的数据和进行瞬时的查询。 然而，随着网络，电信和传感器技术的发展，出现了一种新的数据处 理模型。在这种模型中，出现了一种瞬时流数据上的连续长时间的查 询。传统数据库存储的是相对静态的记录集，不是为快速和连续输入 的单个数据项设计的，而且它不能直接支持连续查询。传统数据库管 理系统在数据流应用方面的限制，引起了国内外很多学者和研究机构 的注意。 本文设计了一个通用的数据流管理系统p h o s h p o r ，它既支持传统 关系上的基本操作，也支持流数据上的连续查询。增加了对数据流存 档的支持，使得系统可以满足更广泛的应用。扩展了c q l 的窗口类型， 增加了标记窗口和快照窗口，形成了新的流式查询语言p h o s p h o r c q 。 同时，去除了c q l 中关系和流之间的复杂转化，使得语言本身简洁、 易写，语义更加明确。最后，在查询处理方面，对p s o u p 的查询处理 算法进行了改进，提高了系统处理的性能。丰富了系统中的查询模块， 使每个模块的功能更加明确，查询执行更易操作，并且统一了数据流 和关系的查询处理方式。 关键词：数据流，连续查询，数据库，数据库管理系统，数据流管理 系统，流式查询语言，查询处理 数据流管理系统的研究与设计 a b s t ra c t t r a d i t i0 n a ld a t a h a s e m a r l a g e m e n ts y s t e m sa r e d e s i g n e d t 0 h ar l d lep e r s is t er l td a t aa n da n s w e rt r a i l s i er l t 口u e r ie s h o w e v e rd u e t ot h ee v o l u t i o i lo ft i e t w o r k t e e c o m m l l i n _ ic a ti 0e la n ds e l 3 s o r t e c h n 0 1 0 9 i e s ，an e wd a t ap r o c e s s i n gm o d e lh a sr e c er l t l y8 r i s e l 3 。i r l t h iss c er l s r i0 ，c o r l t if t u o u sa n dl o n g r u l l r l ir l gq u e l ie sa r ep o s e do v e r t r a n s i er l t s t r e s , m i n gd a t a t r a d i t i 0 1 1 1 3 , l d b m sa r en o td e s i g n e df o r r a p i d8 , n dc 0 1 1 t i t 3 u o u s ly1o a d i n go fi n d iv i d u a ld a t ai te m s 。8 n dt h e y d o1 3 0 td ir e c t l ys u p p o r tt h ec or l t ir l u o u sq u e i ie s l i m i t a t i o n so f t r a d i t i 0r l a ld b m si ns u p p o r t i l l gs t r e a m i n ga p p l ic a t i 0r l sh a y eb e e n r e c o g r l iz e d p r o m p t i n gr e s e a r c ht oa u g m e n te x i s t i n gt e c h n 0 1 0 9 i e s a n db u il dn e ws y s t e m st om & n a g es t r e a l n i r i g d a t a t h is p a p e rp r o p o s e s an e wd a t as t r e a i i l m a n a g e m e n ts y s t e m p h o s p h o r ，v c h ic hs u p p o r t s 1 3 o to e l l yp e r s i s t e r l tr e l a t i 0 1 3 b u ta ls 0 t h es t r e a m i r l g d a t a t h e a u g m e n t o f s u p p o r t in g a r c h i v e dd a t a s t l e a mm a k e sp h o s h p o rs a t is f ym o r ea p p lic a t i o i l s e x t e n d i n gc q l ar l df o r m i n gm o t ec o r l c is ec or l t i n u o h sq u e r y 1 1 3 , f i g u a g ep h o s p h o r c q p h o s h p o ri m p r o v e st h eq u e r yp r o c e s s i n ga l g o t i t h m0 fp s o u p ，m a k i n g s y s t e mh a v eh i g h e rp e r f o r n l a n c e 。q u e r ym o d u l e sa r ee n r i c h e d a n d t h ew o r ko fp e rm o d u l eb e c o m e sm o r ec 1e a r l y ，t h eq u e r yp r o c e s s in g b e c o m e sm 0 1 - ee a s i e ri m d le m e l l t k e yv o r d s ：d a t as t r e a m c o r l t i f l u o l i s c o i l t in u o us q l i e r yl a n g u a g e ，q u e r y q u e r y ，d a t ab a s e ，d 1 3 i s ，d s m s p r o c e s s l n g 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立 进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本 论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明 确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：翌：兰亟 日 期：互：竺：! ：兰g d b m s d s m s c q s t r e a m q o s d d l d m l c q l s q c s o l s t e m s m a m e o t s h j 南京航空航天大学硕士学位论文 注释表 d a t a b a s em a d a t as t r e a m c 0 n t i l 3 u o u s s t a n f o r ds t q u a l i t y0 f d a t ad e f i n i d a t am a n i p u c 0 n ti n u 0 u s s t a n d i n gq u s t r u c t u r e d s t a t em o d u l s e le c t i o nm a c c e s sm o d u e n d0 ft r a d s y m m e t r i ch n a g e m e n ts y s t e m m a n a g e m e n ts y s t e m q u e r ie s r e a md a t am a n a g e r s e r v ic e ti o n l a n g u a g e l a ti o n l a n g u a g e q u e r yl a n g u a g e e r yc l a u s e q u e r yl a n g u a g e e o d u le 1 e s m ls s l o n a s hj o i f i v 儿 南京航空航天大学硕士学位论文 第一章绪论 近来一种新的数据密集的应用逐渐引起人们的注意，在这种应用 中，数据采用的模型不是永久的关系而是瞬时的数据流的形式。本文 将围绕数据流管理系统设计的相关主题进行研究和探讨。本章主要讨 论全文的研究背景、数据流管理系统的主要研究内容、国内外的研究 现状以及本文的组织。 1 1 课题研究背景 传统的数据库管理系统用于处理永久的数据和进行瞬时的查询。 然而，随着网络，电信和传感器技术的发展，出现了一种新的数据处 理模型。在这种环境中，出现了一种瞬时流数据上的连续长时间的查 询。这样的应用包括：金融报价、网络监控、安全、电信数据管理、 w e b 和交易日志分析、制造业、传感器等。这些应用中，数据以多个高 速数据流的形式到达，并且要求联机的处理以及提供近似实时的查询。 数据流是连续的、随时间变化的、无界的数据项的序列。在数据 流模型中，单个的数据项通常采用关系元组的形式，经过处理后就会 被销毁，这就意味着联机流算法是建立在一次查询的基础上。数据流 到达的频率是不被处理系统所控制的，它们是不可预测和随时间变化 的。由于数据流无界性的特点，所以不可能存储整个数据流。 在典型数据流上进行的最重要的一类查询就是连续查询 ( c o n t ir l u o u sq u e r i e s ) 。这种查询通常需要持续很长一段时间，随着 新数据的到达连续地进行评估，随时间的变化不断地产生结果。基本 的连续查询操作包括选择、投影、t o p - k 检测、聚集、多个数据流的 连接等等。 数据流上的另一种重要的查询就是在已经处理的数据和可能销毁 的数据上进行的即席( a d - h o c ) 查询。 在上面所提到的应用中，简单的把到达的数据放到传统的数据库 管理系统( d b m s ) 中进行处理是不可行的。传统的数据库管理系统不适 合快速连续地存储单个数据项，而且它不直接支持典型数据流应用的 连续查询。传统的d b m s 主要是利用固定的查询计划产生精确的结果。 数据流管理系统的研究与设计 另外，数据流上查询计划执行的近似和自适应的特点，以及在快速数 据流上实施的其它处理( 例如，数据分析和挖掘) ，都是传统数据库 管理系统不能处理的。传统的d b m s 在处理数据流应用方面的限制使得 人们开始研究如何利用现有的技术来建造一个新的系统来管理数据 流。 1 2 数据流管理系统的主要研究内容 研究的主要内容包括：数据流管理系统的体系结构、数据模型、 数据流处理的相关算法、连续查询处理、连续查询语言、数据流挖掘 技术、查询优化等。 i 3 国内外研究现状 数据流应用的出现引起了国内外专家和学者的关注，国外很多的 大学和机构在流式数据关系方面进行了大量的研究工作，国内在这方 面的研究还比较少。首先看一下国外的研究状况： 目前通用的d s m s 包括t e le g r a p h c q ，s t r e a m ，和a u r o f a 。 t e le g r a p h c q 致力于多数据流上的并发的连续查询的自适应和共享处 理。s t r e a m 集中于资源管理和近似连续查询。a r u o r a 是一个面向监测 应用的d s m s ，用于处理在线时序安排和负载平衡。 美国加州大学伯克莱分校正在构建个t e l e g r a p h c q 1 1 系统，该系 统用于连续的数据流的处理。t e le g r a p h c q 的目的在于处理对大量高速 变化的数据流而进行的大量连续查询流。在该项目的早期工作中 2 ，3 ，4 】 已经建立了一个j a v a 版本的自适应性数据流处理系统。如今他们决定 利用p o s t g r e s q l ( 一个源码公开的r d b m s ) 作为进一步研究的起点。 a u r o s a 工程 5 建造了一个专门用于流监控的数据处理系统。 a u r o r a , 系统的核心包括大量的网络触发器。每个触发器是一个数据流 图，每个节点是七个内置操作之一。对每个应用a u r o r a 系统的流监控 系统，应用管理员向a u r o r a 触发器网络中创建和增加一个或多个触发 器。a u r o r a 在触发器网络上实掩编译期优化( 比如，重排操作，共享 公共子表达式的状态) 和运行期优化。作为运行期优化的一部分， a u r o r a 发现资源过载并根据质量服务的应用描述进行负载平衡。另外， 他们还f 在设计一种可升级的分布式a u r o r a ，叫做a u r o r a 。a u r o r a 十 南京航空航天太学硕士学位论文 的主要目标在于使系统对分布式数据流处理应用达到一种比较高的可 量测性和实用性。 斯坦福大学已经开始了一种全面d s m s 的设计和原型实现，该系统 为s t r e a m ( s t a n f o r ds t r e a md a t am a n a g e r ) “。s t r e a m 是一个以关系 为基础的数据流管理系统，它重点在于内存管理和近似查询。它可以 用于处理快速的、易变的、大量涌入的数据流信息，其连续查询能力 非常好。s t r e a m 的主要处理技术包括：连续的自我监控和再优化；适 应于不同需要的良好近似；合理的资源分配和使用。如今s t r e a m1 0 版本已经设计完成并正在运行期间，它可以支持多种查询语言。 国内方面，这方面的研究正在起步，文献资料也比较少，有些学 校和研究所正在对数据流进行研究。复旦大学集中在流数据管理和挖 掘的研究，中科院计算机技术研究所试图构建一个面向网络信息安全 的数据流计算模型，重点研究的一些问题有网络数据流的获取、网络 数据流建模、数据流查询模型、数据流计算算法等，他们的目标是在 这个模型的基础上开发出具体的有显示度的宏观网络监控应用系统。 1 4 主要研究工作和内容安排 本文主要围绕数据流管理系统设计和查询处理的算法方面进行研 究，本文的主要研究工作有以下几个方面： 1 构建了一个通用的数据流管理系统p h o s p h o r ，给出了系统的体 系结构，对主要模块的功能进行了介绍。由于数据流管理系统可以看 作是传统数据库的扩展，而且数据流上的查询通常也需要与传统关系 进行连接操作，所以p h o s p h o r 在存储区增加了关系存储。因为有些应 用还需要对数据进行分析和挖掘等处理，所以为了满足更广泛的数据 流应用的需求，在存储区增加了数据流存档存储。 2 改进了c q l ，设计了流式查询语言p h o s p h o r c o 。由于数据流应 用的特殊需求以及数据流本身的特点，使得数据流上的查询与传统关 系上的查询有很大的不同，同时传统的关系查询语言s q l 也不支持连 续查询语义。作为数据流管理系统的一个重要组成部分，我们对c q l 【l i 进行了改进形成了流式查询语言p h o s p h o r c o 。p h o s p h o r c o 扩展了c q l 的窗口类型，增加了标记窗口和快照窗口，使得p h o s p h o r c q 支持更多 的查询类型。同时，p h 0 s p h o r c o 去除了c q l 中关系一流之间的复杂转 化，使得语言本身简洁、易写，语义更加明确。 数据流管理系统的研究与设计 3 对p s o u p 4 】的查询处理算法进行了改进。p h o s p h o r 系统采用 p s o u p 的查询处理引擎，并对它进行了改进：在查询搜索阶段，p h o s p h o r 充分利用查询的窗口信息，减少了数据的搜索量，同时也降低了结果 结构中数据的冗余；在数据结构上，对元组的状态信息进行了改进， 减少了数据结构中的冗余字段，并且熏新解释了每个字段所代表的信 息。另一个方面，引入了s t e m 1 0 1 ，丰富了系统中的查询模块，使每个 模块的功能更加明确，查询执行更易操作。由于s t e m 支持传统的关系 查询，这使得p h o s p h o r 同时增加了对关系查询的支持，统一了数据流 和关系的查询处理方式。 全文的组织如下： 第一章介绍了课题的研究背景，以及数据流管理系统研究的主要 内容和国内外的研究现状。 第二章对数据流的基本概念进行了说明，介绍了数据流的一些应 用，讨论了数据流查询的一些问题。 第三章主要讨论了数据流管理系统的相关问题，给出了p h o s p h o r 的体系结构并对主要模块的功能进行了描述。 第四章对c q l 语言进行了扩充形成了可以支持连续查询语义的 p h o s p h o r c q 语言，并把它与其他连续查询语言进行了比较。 第五章讨论了p h o s p h o r 系统的查询处理算法。 最后是对本文的总结。 南京航空航天大学硕士学位论文 第二章数据流 本章介绍了数据流的基本概念，列举了数据流相关的一些应用 在此基础上，重点讨论了数据流查询的相关问题和处理技术。 2 1 数据流 数据流是一个实时的、连续的、潜在无界的、有序的( 隐含的通 过到达时间或者明确的时间戳) 项的序列。 因特网、w e b 以及传感器网络等已经促使应用将数据看作一种连续 的数据流，而不是固定的数据集合。电话记录，股票报价以及从传感 器那里得出的数据都是数据流的例子。由此可见，数据流是连续的、 无限的、快速的、随时间变化的数据项的序列。 与传统的数据相比，数据流具有许多自己的特点：它是大量的连 续的无限的数据；数据变化很快，并且要求快速即时的响应；数据流 能很好地满足我们今日数据处理的需要；数据流管理中的随机存取采 用的是一种代价昂贵的单一线性的扫描算法；仅仅存储到目前为止的 现有数据；大多数数据流初始时处于相当低层次或者多维状态，需要 多层次化和多维化处理。 2 2 数据流模型 实时的数据流是一个以某种顺序到达的数据项的序列，可能只会 被访问一次。既然数据项可能是高速到达的，那么数据流就可以采用 元组链表的模型。单个数据项可能是一个关系元组，也可能是一个对 象实例。在基于关系的模型中，数据项是存储在虚拟关系中的瞬时元 组。在基于对象的模型中，数据源和数据项采用的是与方法相关联的 数据类型的模型。 在数据流模型中，一些或者所有输入数据的操作都是建立在一个 或多个连续到达的数据流的基础上，而不是在硬盘或者内存上。数据 流和传统的存储关系有以下的不同： 数据流中的元素是联机到达的。 数据流管理系统的研究与设计 系统不能控制数据元素到达的顺序。 数据流是潜在无限的。 一旦数据流的一个元素被处理之后，就会被丢弃或者存档：除 非明确地把数据存储在内存中，否则很难再次被检索，相对于数据流 的大小来说，内存是相对较小的。 数据流模型上的操作对象也包括存储在传统关系上的数据。通常， 数据流查询是在数据流和存储的关系数据上进行的。 2 3 数据流应用 下面介绍一些数据流的相关应用，以便于了解数据流管理系统应该 支持的查询。 2 3 1 传感器网络 传感器网络可以用在拥有复杂过滤和对异常情况进行响应的不同 的监测应用中。在多数据源上分析数据需要在多个流上进行聚集和连 接操作。 2 3 2 网络流量监控 在计算流量统计和发现紧急状况( 比如，拥塞和拒绝服务) 的应 用中已经使用即席系统来进行近似实时的i n t e r n e t 流量分析。 i n t e r n e t 的流量模式被认为遵从幂律分布，也就是说网络的大部分宽 带资源是被小部分的用户所占用，所以监测流行的资源和终端地址 是特别重要的。 2 3 3 金融报价器 联机的分析股票价格包括发现相关信息，确定趋势和套利的机会 以及预测未来的走势。 2 3 4 交易b 志分析 联机地挖掘w e b 同志、通话记录和自动取款机等都符合数据流的 模型。其目的是发现消费者有趣的行为模式，识别可能具有欺诈和可 疑的消费行为并预测未来的数据值。 南京航空航天大学硕士学位论文 2 4 需求分析 前面的例子说明了它们在数据模型和应用上的基本操作( 由于工 作量的特点，比如，在数据流到达的速率或者需要历史数据的数量上 还有些不同) 有着很大的相似。下面列出了数据流上的基本连续查询 操作，由于需求的变化。将来还可能会有其它的操作： 选择：所有的数据流应用都需要支持复杂的过虑功能。 嵌套的聚集：复杂的聚集操作，包括需要计算数据趋势的嵌套 聚集。 多路技术和多路分解：分别跟g r o u p - b y 和u n i o n 类似，用来分解 和合并逻辑数据流。 频繁数据查询：就是依赖于定点( c u t 一0 f f ) 状态的t o p k 或者阈 值查询。数据流挖掘：模式匹配，查找相似，预测等。 连接：包括多数据流的连接和数据流跟静态关系数据的连接。 窗口查询( w in d o w e dq u e r ie s ) ：上面所有的查询类型可能会 限制在一个窗口中返回数据( 例如，最近2 4 小时或最近1 0 0 个包) 。 2 5 数据流查询 连续数据流上的查询跟传统数据库管理系统中的查询有很多共同 点。然而，它们之间存在两个特有的区别：一个区别是一次查询和连 续查询。一次查询( 一类包含传统d b m s 的查询) 是实麓在数据集快照 上的查询，结果返回给用户。而连续查询是在数据流连续到达的过程 中进行连续求值的。连续查询的结果是随时间产生的，通常反映的是 到目前为止的流数据。连续查询结果可能被存储或随新数据的到达进 行更新，或者作为数据流产生。 第二个区别是预定义查询和即席查询。预定义查询是一类在任何 相关数据到来之前在数据流管理系统已经定义的查询。预定义的查询 通常产生连续的查询。即席查询也包括已经开始的数据流的联机情况。 即席查询为一次查询或连续查询。由于即席查询不能事先知道查询优 化的目的以及确定查询间共同子表达式的情况，所以使得数据流管理 系统的设计变得更加复杂。更重要的是，即席查询的准确结果需要参 考数掘流的历史数据。 数据流模型上的查询处理有它独特的难题。下面，我们讨论这些 数据流管理系统的研究与设计 难题的几个最主要的方面，并给出解决它们的几个可选方法。 2 5 1 无界的内存需求 既然数据流的大小是潜在无限的，那么计算一个准确的数据流查 询的结果所需的内存数量也是无限增长的。数据集处理的外存算法比 内存算法研究的多，因为外存算法不能有效地支持连续查询，所以它 不适于数据流的应用，另外它的实时响应时间通常比较慢。连续数据 流模型适合那些对实时响应要求比较高，并且速率随时间高速变化、 数据量产生比较大的应用。新数据是连续到达的，甚至在旧数据还没 有处理完，它就达到了；每个元素的处理时间要尽可能的短，否则计 算的执行时间将会很高，这样系统的处理就不能跟数据流同步。 a r a s u 1 7 1 等在应用有限的内存空间得到准确的结果和利用磁盘访 问得到近似结果之间的区别上做了初步的研究。他们主要考虑那些具 有潜在无限的内存需求( 跟输入数据流的大小是成比例的) 的有限查 询。其研究结果表明：在不知道输入数据流大小的情况下，对于诸如 连接的大多数普通查询，除非查询所涉及的属性的域有限，否则是不 可能在内存中分配一个有限空间的。一个基本的直觉知识就是没有域 的限制，因为它们r 有可能与将来到达的数据进行连接操作，所以必须 存储无限数量的属性值。 2 5 2 近似结果 正如前面所说的，当局限于有限的内存时，并不是总能产生准确 的查询结果，然而，取代准确结果的高质量的近似结果也是可以接受 的。定义在数据流上的近似算法的难题近年来在算法界的研究已经富 有成效，这项工作导致了一些为了数据简化和大纲构造的一些概括的 技术，包括：草图( s k e t c h e s 8 ，19 】) ，随机取样( r a n d o ms a m p l i n g 2 0 ，2 1 1 ) ， 柱状图( h is t o g r a m s 2 2 , 2 3 ) ，和小波( w a v e l e t s 2 4 , 2 5 】) 。根据这些概 括技术，我们已经看到在近似查询结果方面所做的一些工作。例如近 来的工作除了基于柱状图的技术来进行数据流上相关关系的聚集查询 的近似结果外，g i l b e r t 26 j 等还提出了一个在数据流上建立小空间概要 的通用技术，以提供很多类聚集查询的近似结果。下面的电个小节， 将介绍几个近似的方法，其中有些是数据流计算所特有的。 南京航空航天大学硕士学位论文 2 5 3 滑动窗口 一种产生数据流查询的近似结果的技术就是通过滑动窗口在最近 数据而不是在整个历史数据上进行查询评估。例如，仅用最近一个星 期的数据来产生查询结果，这个星期以前的数据将会被丢弃。 在数据流上实施滑动窗口是近似的一个很自然的方法。它是定义 良好且容易理解的，更重要的是，它着重于最近的数据，在大多数现 实应用中，相对于历史数据，最近数据更加重要：如果一个人想实时 地搞清楚网络流量模式，或电话记录或交易记录，或科学传感数据， 那么观察最近数据比观察陈l e l 的历史数据更具有参考价值。事实上， 很多类似的应用中，滑动窗口并不是作为由于计算整个历史数据的不 可行性而引入的一种近似的技术，而是用户查询的一种查询语义。 在如何于数据流上应用滑动窗口的问题上还存在很多有待于研究 的问题。首先一个基本的问题就是如何在数据流上定义时间戳以便更 容易使用窗口。滑动窗口查询的实现和它们的优化是一个有待于研究 的领域。如果滑动窗口大的足够存储窗口的整个内容，则将无法在内 存中缓冲。还有一个问题就是如何设计一个利用有限的内存得到近似 结果的算法，在 2 7 ，2 8 中可以找到一些最近的研究成果。 然而，在传统数据库环境上的序列( s e q u e l l c e ) 和时序( t e m p o r a l ) 数据库已经存在很多时间敏感的查询( 一类含有滑动窗口的查询) ， 数据流计算模型的不同特点提出了一些新的挑战。时序数据库研究的 主要是随时地维护整个历史的数据值，而数据流系统主要关心的是实 时地处理新的数据元素。序列数据库试图产生允许流访问的查询计划， 这意味着单次扫描输入数据的评估计划可行的，而且计划评估所需的 内存数量是不变的。这种模型假设数据库系统能够控制处理元组的顺 序，它可以合并多个序列，而在数据流系统中这是不可能的。 2 5 4 批处理、取样和大纲 另一类产生近似结果的技术用某种取样和批处理来加速查询执 行，而不是随数据的到达处理每一个数据元素。我们描述这些技术的 一个总的框架。假设数据流查询的结果采用的是一种可以增量维护的 数据结构。这种数据结构的最主要的特征就是支持两个操作，更新和 计算结果。更新操作是在每个新元素到达的时候被调用来更新这个数 据结构的，计算结果产生新的查询结果或者更新某查询的结果。处理 连续查询的时候，最好的情况就是相对于数据流数据到达的速率来说 数据流管理系统的研究与设计 这两个操作都是很快的。这种情况下，不需要使用与数据流同步和实 时的产生结果的特殊技术：当每个新数据到达的时候，更新数据结构， 根据数据结构计算出新的结果，这些都少于数据元素到达的时削。如 果数据结构的一个或两个操作比较慢的话，那么就不可能连续产生目 前为止的准确结果。我们考虑这两个可能的瓶颈和处理它们的方法。 批处理 第一种情况是更新操作快，计算结果操作慢。这样，一个自然的 解决方法就是对数据进行批处理。新数据到来的时候，不是立刻更新 结果，而是缓存起来，查询的响应是周期性的。因为查询结果不是及 时产生的，所以可以认为是近似的，也就是说它表示的是最近的那一 点的准确结果而不是当前时刻的准确结果。由于没有引起准确结果的 不确定性和降低实时性，批处理是一种很有效的近似方法。当数据流 爆发时，它是一个很好的处理方法。一个算法即使不能与数据流速率 的峰值同步，但是可以通过缓存来有效地处理数据流。 取样 另外一种情况就是，计算结果操作快，更新操作慢( 处理时间超 过数据元素平均的到达时间) 。因为数据到达的速度比系统处理的速 度快，所以在计算时获得整个数据是没有用的。一些元组必须被完全 的忽略掉，这种查询的执行是在数据流的样本而不是整个数据流上。 这样我们得到的是近似的结果，但是某些情况，取样处理可能会带来 某种程度的错误。不幸的是，多数情况下( 包括含有连接的多数查询) ， 基于取样的方法不能提供可靠的近似保证。设计一个被证明与准确结 果接近的基于取样的算法是研究中的一个活跃的领域。 大纲数据结构 很明显，我们期望更新和计算结果都很快的数据结构。对于那些 想要的属性上没有准确数据结构的数据流查询来说，可以设计一个维 护小的大纲或者概要的近似的数据结构来代替准确的表示，这样就可 以侵每个元素的计算量达到最小。通过大纲数据结构实施数据约减代 替批处理或取样是一个与数据流模型有关的富有成果的研究领域。 南京航空航天大学硕士学位论文 2 5 5 块操作 块操作就是那些只有获得整个输入才能产生输出的操作。排序就 是块操作的一个例子，还有一些聚集的操作如s u m 、c o u n t 、m in 、m a x 和8 v g 。如果想用传统的操作树进行连续查询求值的话，数据流进入叶 子节点，最终的查询结果在根节点产生，这样把块操作合并到查询树 就带来一些问题。因为数据流可能是无限的，一个块操作的一个输入 是数据流，它将永远得不到整个输入，这样也永远不能产生任何输出。 很明显，块操作不太适合数据流的计算模型，但是聚集操作是非常普 遍的，而且排序的数据比未排序的数据处理起来更有效率。处理这些 块操作是比较困难的，如何有效地处理它们是数据流计算的一个很有 挑战性的方面。 块操作作为查询操作的根节点要比作为内部节点，更容易处理， 例如，产生中间结果输入给其它操作进行进一步处理。当有一个聚集 查询在查询树的根部时，如果这个操作产生一个或少数几个值的话， 那么结果的更新能随它们的输入被流出。当结果集很大，产生的是一 个排序了的关系时，由于连续地转发整个结果是很麻烦的，所以维护 到现在为止的结果的数据结构是更有实际意义的。这两个方法都不能 使块操作很好地产生中间结果，然而，主要的问题是块操作产生的结 果可能是连续变化的，直到获得所有的数据为止，所以与这些结构相 关的操作不能根据查询执行中间阶段的结果做出可靠的决定。 一个处理查询树中块操作作为内部节点的方法就是用模拟近似的 同样任务的非块操作代替。这个方法的一个例子就是j u g g l e 【2 9 1 操作， 这是一个排序的非块操作版本。一个有趣的开放难题就是如何把这项 工作扩展到其它类型的块操作上，以及如何量化由非块操作产生的近 似块操作的错误。 t u c k e r d o 等已经提出了一个处理块操作的不同方法。他们建议在 数据流上增加一个断言，用于判断哪些能和哪些不能出现在数据流的 剩余部分。这个断言，叫做p u n c t u a t i o n s ，被数据流的数据元素交叉 存取。 2 ，5 6 参考历史数据的查询 在数据流计算模型中，一旦数据元素已经流过的话，就不会被再 一次访问到。这就意味着对那些与已经丢弃的数据有关的即席查询来 泌，要得到一个准确的结果是不可能的。解决这个问题的一个简单的 数据流管理系统的研究与设计 方法就是规定即席查询只能参考将来的数据：它们是在查询开始的时 候对数据流进行求值的，任何过去的流元素都被忽略( 为了查询的目 的) 。然而这种方法可能不会太令人满意，但是可以被很多应用所接 受。 一个更好地处理参考历史数据的方法就是维护数据流上的概要， 这可以使未来的即席查询得到近似的结果。采用这个方法需要提前决 定用最好的方式来使用内存资源为广阔范围的未来查询提供近似的结 果。这个问题与物理数据库设计的一些问题，如索引的选择和视图的 物化有些相似。然而，它们有很大的不同：在传统的数据库系统中， 在没有索引或视图的情况下，有可能去访问底层的关系，这样就增加 了代价。在数据流计算模型中，如果没有近似的概要结构，就没有可 用的资源。 即使即席查询声明仅适合将来数据，仍然有很多诸如如何更好地 处理数据的课题需要研究。在数据流应用中，大部分查询是长时间的 连续查询，而不是短暂的一次查询，多查询优化带来的收益要比传统 的数据要多。即席查询的出现把为查询找到最好的查询计划从脱机问 题转移成联机问题。即席查询引起了查询计划的自适应性问题。e d d y 查询执行框架引入了可伸缩查询计划的概念，用来适应数据到达速率 的变化和其它随时间变化的数据特征。如何扩展这个思想以适应连续 查询集上的连接计划( 新查询的增加和旧查询的移除) 是一个开放性 的研究领域。 2 6 小结 本章介绍了数据流的基本概念和数据流模型，并且列举了一些典 型的数据流方面的应用，随后对数据流查询有关的问题进行了说明并 讨论了相关的算法。 南京航空航天大学硕士学位论文 第三章p h o s p h or 的体系结构 为了满足数据流应用的需求，我们设计了一个通用的数据流管理 系统p h o s p h o r 。它是根据数据流应用的特点设计的，用于处理数据流 上的连续查询和即席查询。本章讨论了p h o s p h o r 系统的设计，给出了 p h o s p h o r 的体系结构，并且对系统主要模块的功能进行了说明。 3 1d s m s ( d a t as t r e a mm a n a g e m e n ts y s t e m ) 数据流是一个实耐的、连续的、潜在无界的、有序的( 隐含的通 过到达时间或者明确的时间戳) 项的序列。数据流的项通常采用关系 元组的形式。 一个数据流管理系统跟传统的数据库系统在功能和性能上是相似 的，它允许一些或者所有的数据以连续的数据流的形式到达。如果把 数据集看过一个特殊的数据流，可以把数据流管理系统定义为传统数 据库系统的扩展。 d s m s 增加了数据流的两个基本查询：连续查询和即席查询。 3 t 1 d s m s 与d b m s 的不同 首先了解一下d s m s 与d b m s 有哪些不同： 传统的d b m s 采用的是被动模式，大部分的数据处理的要求来自 于用户提出的事务和查询。d s m s 还需要一些主动的方法，例如监测数 据的流入并对异常的情况做出处理。 传统的d b m s 普遍地在它的表中管理数据。d s m s 通常需要通过 一些有界的窗口处理有限的数据，而不是在过去无限的范围内处理。 传统d b m s 提供的是精确查询上的精确结果，而且没有实时的限 制。d s m s 通常需要实时的响应( 例如，监测敌人位置的军事应用) ， 而且一般要提供合理的近似查询结果。 传统的查询处理器以统一方式( 典型的集中在响应时间) 优化 所有的查询。流数据管理通常耍满足特殊应用的优化标准( q o s ) 。 传统d b m s 是基于p u l l 的查询处理标准。基于p us h 的数据处理 是d s m s 的处理标准。 数据流管理系统的研究与设计 3 1 2d s m s 的基本需求 数据流独特的特点和连续查询使得d s m s 有以下的需求： 数据模型和查询语义必须允许基于顺序的和基于时间的操作 ( 例如，在5 分钟的滑动窗口上的查询) 。 由于无法存储整个数据流，所以可能要使用近似的摘要结构。 这样，在摘要上的查询可能就返回不了精确的结果。 流查询计划不能使用块操作，因为这些操作需要在产生结果之 前获得所有输入。 由于性能和存储的限制，无法对数据流进行再次访问。联机的 流算法是基于一遍扫描的。 监测流的应用必须对异常的数据做出快速的反应。 长期运行的量询在它们执行期可能会遇到系统状态变化的情况 ( 例如，流速率的变化) 。 许多连续的查询的共享执行必须保证可测量性。 3 1 3d s m s 的参考结构 更新静态 用户查询 数据 = = o = = o 数据流出 图3 i 数据流管理系统参考结构圈 图3 1 7 1 是数据流管理系统的一个参考的抽象结构。输入监听器可 以通过诸如取样的方法控制数据输入的流量。数据存储通常分为三个 部分：临时工作区( 用于窗口查询) ，流大纲的概要存储。元数据的 静态存储( 每个数据源的物理位置等信息) 。查询库存储的是系统已 经注册的连续查询，这些查询可以用作共享处理。除了连续查询，当 前数据流状态上的一次查询也是允许的。褒询处理器与输入监控器相 互通信，并且可以根据数据输入速率的变化重新优化查询计划。结果 嘉 南京航空航天大学硕士学位论文 以流的方式输出给用户或者存储在临时缓存中。 3 2 p h o s p h o r 的体系结构 这一节我们说明一下p h o s p h o r 的体系结构。图3 2 所示：p h o s h p o r 系统包含如下的组件： 用户接口：用户接口包括两个部分，数据输入接口和查询接口。 输入接口负责数据的收集，包括流和关系。查询接口接收用户的查询 请求，输入到查询库中进行处理，查询的类型包括传统关系上的基本 查询以及数据流上的连续查询和即席查询。 数据监控：主要是对数据流的流量进行监控和调整，以满足系 统处理能力的需求。 查询处理器：处理查询库的查询，输出结果到用户或缓冲区。 输出缓冲：缓冲查询的输出结果。 存储区：分为固定存储区和内存存储区。固定存储区有数据流 存档、关系存储和元数据。内存存储区包括工作区、概要存储，主要 负责数据流的存储。 控制信息匕= = = = = 数据信息 图3 2p h o s p h o r 的体系结构 与图3 1 的参考结构相比我们做了几个改变，主要是考虑到固定 关系的存储和处理。首先是在数据录入方面保留了传统关系的数据输 入方式，而且在存储方面增加了磁盘数据的存储。 数据流管理系统的研究与设计 3 3 模块功能说明 这一节将详细地说明主要模块的功能和主要作用。 33 1 用户接口 用户接口的功能就是d b m s 基本的数据定义功能和数据操纵功能。 由于p h o s p h o r 整合了数据流和关系，所以在数据输入的接口方面就出 现的一些区别。对于大多数数据流应用，数据是联机到达的，系统不 能控制数据到达的时间和顺序。除了可以使用数据定义语言( d a t a d e f i n i t i o nl a n g u a g e ，简称d d l ) 定义数据流以外，与关系数据的输 入不同，数据流的输入一般是通过监控程序获取的( 例如，传感器网 络，网络流量分析笔) 。 可以使用传统的数据操纵语言( d a t am a n i p u l a t i o nl a n g u a g e ， 简称d m l ) 对关系进行操作，如查询、插入、删除和修改等。数据流本 身独特的特点限制了在其上面的操作。对于数据流，只有查询操作。 查询接口的功能就是提供数据库的基本操作。 3 3 2 输入监控 数据流是一个实时的、连续的、潜在无界的、有序的数据项的序 列。由于数据流速率的变化是无法预测的，某一时刻到达的数据量可 能会超过系统的计算能力( 根据c p u 周期和主存的大小) ，所以需要 一个输入监视器在需要的时候销毁一些元组。一般是采用取样的方法 控制数据流的流量以适应系统的处理能力。 3 3 3 查询处理器 查询处理器的主要功能就是处理查询接口提交的数据库的基本操 作。包括传统关系上的查询、插入、删除和修改等，以及数据流上的 连续查询和即席查询。查询处理将在第五章详细说明。 3 3 4 存储区 存储区包括内存区和磁盘区。基于性能的考虑，p h o s i j h o r 系统是 基于主存实现的。查询处理时，待处理的数据是在内存中的工作区。 查询处理过程中，系统需要为当前查询分配临时工作区，用于缓存流 入的数据，相当于查询窗口。因为近似结果的需要，还为工作区中的 南京航空航天大学硕士学位论文 数据流设置了概要存储区，用来存储数据流的概要信息a 虽然我们主 要是对连续查询进行联机处理，然而在许多流式应用中还是需要对数 据流进行存档，以便长期保存并进行事后的代价分析及挖掘分析。磁 盘存储区的数据流存档存储的是最近的数据流以及概要数据。元数据 存储系统的元数据，相当于数据字典功能。传统的关系和元数据位于 磁盘存储区。 3 4 小结 本章首先讨论了设计一个通用d s m s 的基本需求，并把传统的d b m s 跟d s m s 进行了比较，给出了d s m s 的参考结构。然后讨论了p h o s p h o r 的体系结构，由于数据流管理系统可以看作是传统数据库的扩展，而 且数据流上的查询通常也需要与传统关系进行连接操作，所以 p h o s p h o r 在存储区增加了关系存储。作为一个通用的数据库流管理系 统，为了满足大多数数据流应用的需求，同时在存储区增加了数据流 存档，这是因为有些应用还需要对它们进行分析和挖掘等处理。最后 对p h o s p h o r 系统主要模块的功能进行了说明。 数据流管理系统的研究与设计 第四章流式查询语言p h o s p h or c o 的设计 查询语言的设计也是数据流管理系统的一个重要部分，由于传统 数据库的查询语言s q l 不支持连续查询语义，同对为了满足数据流应 用的特殊要求和规范，也需要重新设计用于处理数据流查询的查询语 言。本章主要讨论流式查询语言p h o s p h o r c o 的设计。 4 1 流式查询语言 为了满足数据流应用的特殊要求和规范，数据流的数据模型和查 询语言必然具有其自身的特点。本节讨