（计算机软件与理论专业论文）分布式数据流查询处理技术的研究.pdf

摘要 摘要 随着网络监控、w e b 应用、传感器网络、金融分析等信息处理应用领 域的发展，一种新的数据形式数据流受到人们越来越多的关注。数据 流的特点是数据持续到达，且速度快、规模大。有关数据流的研究是目前 国际数据库研究领域的一个热点。尽管传统数据库技术发展迅速且得到了 广泛应用，但是它不能够处理数据流。 在大量的数据流应用系统中，数据流是来自于地理上分布的数据源， 非常适合于分布式查询处理。分布式处理是数据流管理系统发展的必然趋 势。本文主要对分布式数据流查询处理的相关技术进行了研究。 首先，对分布式数据流查询处理模型和现有分布式数据流查询操作放 置技术进行了详细的介绍。在透彻分析基于弹簧张弛的查询操作放置算法 的基础上，对基于弹簧张弛的查询操作放置算法中优化的目标函数和查询 操作的初始位置进行了改进，并通过实验验证了改进算法的有效性。 其次，给出了查询计划的定义，并针对如何生成优化的查询计划问题， 提出了两种贪心算法：基于左深连接树的贪心算法和基于浓密树的贪心算 法。分析了分布式数据流查询处理中的查询重叠问题，针对现有查询重用 算法存在的问题，提出了一种基于查询树匹配的查询重用算法。 最后，分析了现有的几个典型的数据流管理系统，设计并实现了一个 通用的分布式数据流管理系统g d d s m s ( g e n e r i cd i s t r i b u t e dd a t as t r e a m m a n a g e m e n ts y s t e m ) 。 关键词数据流；查询操作；弹簧张弛；贪心算法；查询重用 燕山大学工学硕士学位论文 a b s t r a c t w i t ht h er c c e n td e v e l o p m e n ti nt h ef i e l do fi n f o r m a t i o nm a n a g e m 踟ta n d a p p l i c a t i o n , s u c ha si n t e r n c tm o n i t o r i n g , w e ba p p l i c a t i o n , 8 e 1 1 s o rn e t w o r k ，a n d f i n a n c i a la n a l y s i s ，an e wf o r mo fd a t am o d e l ，t h ed a t as t r e a m ，h a sc o m eu n d e r i n c r e a s i n ga t t e n t i o n d a t as t r e a mf e a t u r e sc o n t i n u o u sa r r i v a lo fd a t a , w i t hs p e e d a n dv e r yl a r g es c a l e t h es t u d yo nd a t as t r e a mi so n eo f t h eh o tt o p i c sa m o n gt h e d a t a b a s ec i r c l ea l lo v e rt h ew o r l dr e c e n t l y c o n v e n t i o n a ld a t a b a s et e c h n o l o g i e s h a v eb e e nw e l ld e v e l o p e da n dw i d e l ya p p l i e d u n f o r t u n a t e l y , t h e yc o u l dn o tb e a d o p 慨i t oh a n d l ed a t as t r e a m m a n ya p p l i c a t i o n so fd a t as t r e a ma r en a t u r a l l yd i s t r i b u t e da n dt h e ya r ev e r y s u i t a b l ef o rd i s t r i b u t e dp r o c e s s i n g d i s t r i b u t e dp r o c e s s i n gi sav e r yp r o m i s i n g r o u t et o w a r d sam o r ee f f e c t i v ea n da d a p t i v ed a t as t r e a mp r o c e s s i n gm o d e l t h i s p a p e rf o c u s e st h er e s e a r c ho nt h eq u e r yp r o c e s s i n gt e c h n o l o g i e so f d i s t r i b u t e d d a t as t r e a m f i r s t l y , t h ed i s t r i b u t e dd a t as t r e a mq u e r yp r o c e s s i n gm o d e lc o n c e p ta n dt h e e x i s t i n gq u e r yo p e r a t o rp l a c e m e n to fd i s t r i b u t e dd a t as t r g a l l lt e c h n o l o g ya r e i n t r o d u c e di nd e t a i l o nt h ef o u n d a t i o no fa n a l y z i n gt h ea l g o r i t h mb a s e do n s p r i n g r e l a x a t i o no fq u e r yo p e r a t o rp l a c e m e n to fd i s t r i b u t e dd a t a s t r e a m t h o r o u g h l y , a ni m p r o v e m e n tt o t h ea l g o r i t h mt h r o u g ha l t e r i n gt h eo b j e c t f u n c t i o no p t i n f i z e db yt h ea l g o r i t h ma n di n i t i a l i z a t i o no fc o o r d i n a t e a n d e x p e r i m e n _ t a lr e s u l t ss h o w t h a tt h ei m p r o v e m e n ti se f f e c t i v e l y s e c o n d l y , q u e r yp l a ni sd e f i n e da n dt w og r e e d ya l g o r i t h m sa r ep r o p o s e d t o p r o d u c eo p t i m i z e dq u e r yp l a ni nd i s t r i b u t e dd a t a s t r e a mm a n a g e m e n ts y s t e m i n a d d i t i o n , aq u e r yr e u s i n ga l g o r i t h mi sp r o p o s e dt or e u s et h eo v e r l a p p e dq u e r yi n d i s t r i b u t e dd a t as t r c a r nm a n a g e a n e n ts y s t e m f i i l a l l y , ag e n e r i c d i s t r i b u t e dd a t as t r e a mm a n a g e m e n ts y s t e m , n a m e d g d d s m s ，i sd c v e l o p e do ht h eb a s i so fa n a l y z i n gt h ee x i t e dt y p i c a ld a ms t r e a m m a n a g e m e n ts y s t e m s k e y w o r d sd a t as t r e a m ；q u e r yo p e m t o r ；s p r i n gr e l a x a t i o n ；g r e e d y 姆f i t h m ； q u e r yr e u s m g 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文分布式数据流查询处理 技术的研究，是本人在导师指导下，在燕山大学攻读硕士学位期闯独立进 行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他 人己发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和 集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字桫氟 日期：印年f 月7 日 燕山大学硕士学位论文使用授权书 分布式数据流查询处理技术的研究系本人在燕山大学攻读硕士学 位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学 所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完 全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关 部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕 山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的 全部或部分内容。 保蟹u ，= 正年解罾后逋用本授权吊。 本学位论文属于 不保密d 。 ( 请在以上相应方框内打“”) 作者签名f 初瑰蔹 日期：唧年月f 7 日 导师签名：j 惫u 寺芑 日期：加夕年，月，f 7 日 第1 章绪论 第1 章绪论 近来一种新的数据密集的应用逐渐引起人们的注意，在这种应用中， 数据模型不是永久的关系而是瞬时的数据流的形式。本文将围绕分布式数 据流查询处理的相关主题进行研究和探讨。本章主要讨论全文的研究背景、 分布式数据流查询处理的主要研究内容、国内外的研究现状以及本文的组 织结构。 1 1 课题的研究背景 传统的数据库管理系统( d b m s ) 用于处理永久的数据和进行瞬时的查 询。通常数据库是由一系列对象组成，插入、更新、删除等操作没有查询 发生得频繁，查询的结果反映的是数据库的静态状态。然而在近几年的许 多应用中，数据大多表现为连续的流的动态形式，而不是有限存储的静态 数据集合，例如，传感器网络数据分析、网络流量监控、工厂装配线管理、 事务日志的在线分析、商品交易即时分析等应用中产生的数据都表现为源 源不断的流的形式。可以将这种连续不断的数据看作是数据流l 。 数据流是实时的、连续的、有序的( e h 到达时间隐含表示或显式地由时 间戳指定) 、潜在无穷的序列。 在数据流应用中，通常需要的是长期的连续查询( c o n t i n u o u sq u e r y ) ， 在规定的时间内用户需要不断的得到查询结果，而不是传统d b m s 中常用 的一次查询( o n e - t i m eq u e r y ) 。若把持续到达的数据流简单的放到传统的数 据库管理系统中，并在其中进行操作，是不切实际的。 传统的d b m s 的设计目标是通过稳定的查询设计，为用户的一次查询 产生精确的答案，查询针对的是数据的静态快照且一旦产生结果查询即行 结束。同时，d b m s 不是为快速连续的存放单独的数据单元而设计的，也 不支持连续查询。 燕山大学工学硕士学位论文 目前很多应用程序为了达到在数据流上持续查询的目的，往往通过编 辑客户端代码、脚本、或使用其他的即时查询工具来完成。这种方式的缺 点是非常明显的。首先，程序是脆弱的，应用程序的逻辑修改是非常困难 的。其次，应用要求的少许变动都可能需要程序源代码级的修改。为了克 服以上的缺点，将数据流与数据库的两者相结合的思想成为自然而然的选 择，数据流管理系统应运而生。近年来，随着数据流应用的大量涌现，数 据流管理系统的研究引起了越来越多的数据库工作者和研究者的关注。 1 2 国内外的研究状况 数据流查询处理技术并不保存整个数据集，仅维护一个远小于其规模 的摘要数据结构，从而使得数据流查询算法在内存中就可完成各种计算。 数据流查询处理技术往往包含两部分算法：一部分监控流中的数据，更新 摘要数据结构；另一部分响应用户查询请求，返回近似查询结果。举例来 说，假设上海证券公司想要获知某一天交易量最大的地区以及交易规模大 于某个值的大客户。在传统方法下，首先所有交易记录必须存放在磁盘等 i o 外部介质中，然后调入内存进行分析，得到最终查询结果。由于数据 规模巨大，需要大量的i o 交换，可能需要几十分钟以后才能够得到查询 结果。而用数据流查询处理模式，仅仅需要访问内存中的摘要数据结构， 因而可能仅仅需要几秒就能获得答案。可以看出，数据流查询处理模式比 传统的处理方法要快很多。尽管该方法得到的结果并不精确，但是往往并 不影响用户的最终决策。 数据流查询模型根据不同应用需求可有多种划分标准。常用的数据流 查询模型为按时序范围划分，数据流查询模型按时序范围可以划分成多种 子模型，包括界标模型( l a n d m a r km o d e l ) ，滑动窗口模型( s l i d i n gw i n d o w m o d e l ) 和快照模型( s n a p s h o tm o d e l ) 等。界标模型的查询范围是从某一个已 知的初始时间点到当前时间点为止。滑动窗口模型则仅关心数据流中最新 的数据，随着数据的不断到达，窗口中的数据也不断平移从而新到达的数 据元素被插入和过时的元素被删除。快照模型则将操作限制在两个预定义 2 第l 章绪论 的时间戳之间。界标模型和滑动窗口模型由于要不断处理新来的数据，更 接近于真实应用，因而得到更加广泛的研究。 随着数据流技术的快速发展，最近几年出现了很多数据流模型下的管 理系统，即数据流管理系统( d s m s ) 。下面介绍几个具有代表性的数据流管 理系统。 斯坦福大学的s t r e a m ( s t a n f o r ds 汪md a t am 黝g e r ) 系统f 2 j 是一个 以关系为基础的通用的数据流管理系统，它重点在于内存管理和近似查询。 加州大学伯克利分校的t e l e g r a p hc q 3 , 4 1 主要用于传感器网络的查询 处理，也是一种数据流管理系统。该系统致力于多数据流上的并发的连续 查询的自适应和共享处理。 布朗大学、布兰代斯大学和麻省理工学院联合开发的b o r e a l i s t 5 ，6 】是在 a u r o r a 7 s 和m e d u s a t g a o l 的基础上开发的分布式数据流处理引擎。b o r c a l i s 不但继承了a u r o r a 系统的数据流处理的功能而且还利用了m e d u s a 系统的 分布式特点。 o p e n c q t l l l 系统与n i a g a r a c q t l 2 1 系统都支持对分布于网络上的持久性 数据进行连续的查询监控，如i n t e m e t 上的w e b 站点。o p e n c q 采用一种 基于增量视图维护的查询处理方法，而n i a g a r a c q 则在许多查询中使用了 分组连续查询技术，该技术的使用提高了查询求值的效率。 另外，连续查询还被用于t a p e s t r y l l 3 1 系统，该系统对只增型电子邮件 信息和电子公告信息数据库进行以内容为基础的过滤。s q l 的一个有限的 子集作为该系统的查询语言，以确保查询求值的有效执行以及生成只增型 查询结果。 c o u g a r t l 4 是一个传感器数据库，它将传感器建模为a d t s ，同时它 的输入为一个时间序列。 g i g a s e o p e l l 5 是一个分布式网络监控结构，它提议将一些查询操作加到 数据源中( 如：路由) 。 s t a t s t r e a m 0 6 1 是一个流监控系统，它用于同时在线统计多个数据流。 国内方面，这方面的研究正在起步，有些学校和研究所正在对数据流 进行研究。 燕山大学工学硕士学位论文 北京大学数据库实验室的数据流小组研发了数据流管理系统a r g u s ， a r g u s 既可以作为通用的数据流管理系统存在，也可以以库的形式提供给 其它系统，以便方便的嵌入到其它系统中。 东北大学研发的数据流管理系统r e a l s t r e a m 1 7 a 8 实现对嵌入式应用中 传感器产生的流式数据的查询管理任务。 中科院计算技术研究所试图构建一个面向网络信息安全的数据流计算 模型，重点研究的一些问题有网络数据流的获取、网络数据流建模、数据 流查询模型、数据流算法等。 1 3 本文的主要工作 本文主要围绕分布式数据流查询处理的相关技术进行研究，在吸收前 人的大量研究成果的基础上，主要完成以下3 个方面的研究工作。 ( 1 ) 对分布式数据流查询处理模型和现有分布式数据流查询操作放置 技术进行了详细的介绍。在透彻分析基于弹簧张弛的查询操作放置算法的 基础上，对基于弹簧张弛的查询操作放置算法中优化的目标函数和查询操 作的初始位置进行了改进，并通过实验验证了改进算法的有效性。 ( 2 ) 针对如何生成优化的查询计划问题，提出了两种贪心算法：基于左 深连接树的贪心算法和基于浓密树的贪心算法。分析了分布式数据流查询 处理中的查询重叠问题，针对现有查询重用算法存在的问题，提出了一种 基于查询树匹配的查询重用算法。 ( 3 ) 分析了现有的几个典型的数据流管理系统，设计并实现了一个通用 的分布式数据流管理系统原型。 1 4 论文结构 本文共分为5 章，内容包括。 第1 章为绪论，阐明了课题的背景和意义、国内外研究现状、本文的 主要研究内容和组织结构。 4 第1 章绪论 第2 章介绍了数据流的概念和数据流模型，并且列举了一些典型的数 据流方面的应用，随后对数据流查询有关的问题进行了说明并讨论了相关 的算法。总结了数据流管理系统与传统数据流管理系统的对数据处理的不 同要求和特点，最后给出了数据流管理系统的参考结构。 第3 章对分布式数据流查询处理技术中的查询操作放置问题进行了深 入研究，首先论述了分布式数据流查询处理模型；然后介绍了现有的数据 流查询操作放置技术，并在详细分析p e t e r 等人提出的基于弹簧张弛技术 的查询操作放置算法实质的基础上，针对其不足，对p e t e r 等人提出的查 询操作放置算法进行了改进；仿真实验表明改进后的算法在网络使用情况， 时延和张弛迭代的次数方面优于原算法。 第4 章对分布式数据流查询处理中查询计划的相关问题进行了深入的 研究，首先详细论述了分布式数据流的查询计划模型，然后对查询计划的 生成进行了研究，并提出了两种贪心算法来实现查询计划的生成。针对查 询重叠问题提出了一种查询重用算法，并通过模拟实验对提出的查询重用 算法进行了验证。 第5 章首先介绍了现有的几个典型的数据流管理系统；其次设计了一 个通用的分布式数据流管理系统原型g d d s m s 并对其进行了实现；最后 在l i n e a rr o a d 平台上，把本章实现的分布式数据流管理系统原型 g d d s m s 与s t r e a m 进行了性能对比，对比结果表明分布式数据流查询 处理优于集中式数据流查询处理。 最后，在结论中对本文的工作进行总结，并对进一步的研究进行分析 和展望。 燕山大学工学硕士学位论文 第2 章数据流查询处理相关技术 本章介绍了数据流的基本概念，列举了数据流相关的一些应用，在此 基础上，重点讨论了数据流查询的相关问题和处理技术。 2 1 数据流 数据流是一个实时的、连续的、潜在无界的、有序的( 隐含的到达时间 或者明确的时间戳) 序列。 因特网、w e b 以及传感器网络等已经促使应用将数据看作一种连续的 数据流，而不是固定的数据集合。电话记录，股票报价以及从传感器那里 得出的数据都是数据流的例子。由此可见，数据流是连续的、无限的、快 速的、随时间变化的数据项的序列。与传统的数据相比，数据流具有许多 自己的特点【1 9 1 ：它是大量的连续的无限的数据；数据变化很快，并且要求 快速即时的响应；数据流能很好地满足今日数据处理的需要；数据流管理 中的随机存取采用的是一种代价昂贵的单一线性的扫描算法；仅仅存储到 目前为止的现有数据；大多数数据流初始时处于相当低层次或者多维状态， 需要多层次化和多维化处理。 2 2 数据流模型 实时的数据流是一个以某种顺序到达的数据项的序列，可能只会被访 问一次。既然数据项可能是高速到达的，那么数据流就可以采用元组链表 的模型。单个数据项可能是一个关系元组，也可能是一个对象实例。在基 于关系的模型中，数据项是存储在虚拟关系中的瞬时元组。在基于对象的 模型中，数据源和数据项采用的是与方法相关联的数据类型的模型。 在数据流模型中，一些或者所有输入数据的操作都是建立在一个或多 6 第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 的流量模式被 认为是遵从幂律分布，也就是说网络的大部分宽带资源是被- - 4 , 部分的用 户所占用，所以监测流行的资源和终端地址是特别重要的。网络传输管理 系统负责监控各种网络数据流，包括数据包跟踪、网络性能评估等。这些 7 燕山大学工学硕士学位论文 数据流的特征是不可预知的，同时到达的速率也是不可控制的。通过实时 在线的对网络数据流进行分析，可以检测网络的运行状况，分析网络协议， 或通过对网络数据的分析来进行入侵检测。显然，传统的数据库系统不适 合于这种在线连续查询处理，而这一需求恰恰是这一领域中最有价值的研 究问题。随着网络流量的快速增长和网络安全问题的凸显，对海量网络数 据流的实时分析也变得越来越重要。 2 3 3 金融报价器 金融证券交易中往往需要跟踪大量的流式数据，系统从交易中心等数 据源获取数据，通过对股票价格和股票交易等金融数据流进行实时在线分 析，可以发现相关性，识别股市趋势，套汇时机和预测未来价格走势等。 联机的分析股票价格包括发现相关信息，确定趋势和套利的机会以及预测 未来的走势。 2 3 4 事务日志分析 事务日志有多种，如因特网访问记录、商品交易记录、电话记录、信 用卡消费记录等。事务日志的特点是产生速度快，数据规模宏大。通过对 事务日志的分析，可以发现有趣的客户行为模式，鉴别预示着欺诈的可疑 消费行为和预测未来的数据值等；同时通过对商品交易日志的分析，可以 得出客户的消费倾向，指导商家生产或进货。 2 4 数据流查询 连续数据流上的查询跟传统数据库管理系统中的查询有很多共同点。 然而，它们之间存在两个特有的区别。 ( 1 ) 一次查询和连续查询一次查询( 一类包含传统d b m s 的查询) 是实 施在数据集快照上的查询，结果返回给用户。而连续查询是在数据流连续 到达的过程中进行连续求值的。连续查询的结果是随时间产生的，通常反 映的是到目前为止的流数据。连续查询结果可能被存储或随新数据的到达 8 第2 章数据流查询处理相关技术 进行更新，或者作为数据流产生。 ( 2 ) 预定义查询和即席查询预定义查询是一类在任何相关数据到来 之前在数据流管理系统已经定义的查询。预定义的查询通常产生连续的查 询。即席查询也包括已经开始的数据流的联机情况。即席查询为一次查询 或连续查询。由于即席查询不能事先知道查询优化的目的以及确定查询间 共同子表达式的情况，所以使得数据流管理系统的设计变得更加复杂。更 重要的是，即席查询的准确结果需要参考数据流的历史数据。 数据流模型上的查询处理有它独特的难题。下面，讨论这些难题的几 个最主要的方面，并给出解决它们的几个可选方法。 2 4 1 无界的内存需求 既然数据流的大小是潜在无限的，那么计算一个准确的数据流查询的 结果所需的内存数量也是无限增长的。数据处理的外存算法比内存算法研 究的多，因为外存算法不能有效地支持连续查询，所以它不适于数据流的 应用，另外它的实时响应时间通常比较慢。连续数据流模型适合那些对实 时响应要求比较高，并且速率随时间高速变化、数据量比较大的应用。新 数据是连续到达的，每个元素的处理时间要尽可能的短，否则计算的执行 时间将会很高，这样系统的处理就不能跟数据流同步。 a r a s u 2 0 l 等在应用有限的内存空间得到准确的结果和利用磁盘访问得 到近似结果之间的区别上做了初步的研究。他们主要考虑那些具有潜在无 限的内存需求( 跟输入数据流的大小是成比例的) 的有限查询。其研究结果 表明：在不知道输入数据流大小的情况下，对于诸如连接的大多数普通查 询，除非查询所涉及的属性的域有限，否则是不可能在内存中分配一个有 限空间的。一个基本的直觉知识就是没有域的限制，因为它们有可能与将 来到达的数据进行连接操作，所以必须存储无限数量的属性值。 2 4 2 近似结果 正如前面所说的，当局限于有限的内存时，并不是总能产生准确的查 询结果，然而，取代准确结果的高质量的近似结果也是可以接受的。定义 9 燕山大学工学硕士学位论文 在数据流上的近似算法的难题近年来在算法界的研究已经富有成效，这项 工作导致了一些为了数据简化和大纲构造的一些概括的技术，包括：草图 技术, 2 2 1 、随机取t , - , 4 1 2 3 洲、柱状图【2 5 , , 2 6 1 和小波口7 ，2 蜘。根据这些概括技术已 经看到在近似查询结果方面所做的一些工作。近来的工作除了基于柱状图 的技术来进行数据流上相关关系的聚集查询的近似结果外2 9 j o 】，g i l b e r t 等 人还提出了一个在数据流上建立小空间概要的通用技术，以提供很多类聚 集查询的近似结果【3 l 】。 2 4 3 滑动窗口 一种产生数据流查询的近似结果的技术就是通过滑动窗口在最近数据 而不是在整个历史数据上进行查询评估。例如，仅用最近一个星期的数据 来产生查询结果，这个星期以前的数据将会被丢弃。在数据流上实施滑动 窗口是近似的一个很自然的方法。它是定义良好且容易理解的，更重要的 是，它着重于最近的数据，在大多数现实应用中，相对于历史数据，最近 数据更加重要。如果一个人想实时地搞清楚网络流量模式，或电话记录或 交易记录，或科学传感数据，那么观察最近数据比起观察陈旧的历史数据 要更具有参考价值。 事实上，很多类似的应用中，滑动窗口并不是作为由于计算整个历史 数据的不可行性而引入的一种近似的技术，而是用户查询的一种查询语义。 对于如何在数据流上应用滑动窗口的问题，还存在很多有待于研究的问题。 首先，一个基本的问题就是如何在数据流上定义时间戳以便更容易使 用窗口。滑动窗口查询的实现和它们的优化是一个有待于研究的领域。如 果滑动窗口大的足够存储窗口的整个内容，则将无法在内存中缓冲。 其次，一个问题就是如何设计一个利用有限的内存得到近似结果的算 法，在文献 3 2 ，3 3 】中可以找到一些最近的研究成果。然而，在传统数据库 环境上的序列( s e q u e n c e ) 和时序( t e m p o r a l ) 数据库已经存在很多时间敏感 的查询( 一类含有滑动窗口的查询) ，数据流计算模型的不同特点提出了一 些新的挑战。时序数据库研究的主要是随时地维护整个历史的数据值，而 数据流系统主要关心的是实时地处理新的数据元素。 1 0 第2 章数据流查询处理相关技术 序列数据库试图产生允许数据流访问的查询计划，这意味着单次扫描 输入数据的评估计划可行的，而且计划评估所需的内存数量是不变的。这 种模型假设数据库系统能够控制处理元组的顺序，它可以合并多个序列， 而在数据流系统中这是不可能的。 2 4 4 批处理、取样和大纲 另一类产生近似结果的技术用某种取样和批处理来加速查询执行，而 不是随数据的到达处理每一个数据元素。假设数据流查询的结果采用的是 一种可以增量维护的数据结构。这种数据结构的最主要的特征就是支持两 个操作，更新和计算结果。更新操作是在每个新元素到达的时候被调用来 更新这个数据结构的，计算结果产生新的查询结果或者更新某查询的结果。 处理连续查询的时候，最好的情况就是相对于数据流数据到达的速率来说 这两个操作都是很快的。这种情况下，不需要使用与数据流同步和实时的 产生结果的特殊技术：当每个新数据到达的时候，更新数据结构，根据数 据结构计算出新的结果，这些都少于数据元素到达的时间。如果数据结构 的一个或两个操作比较慢的话，那么就不可能连续产生到目前为止的准确 的查询结果。 ( 1 ) 批处理第一种情况是更新操作快，计算结果操作慢。这样，一个 自然的解决方法就是对数据进行批处理。新数据到来的时候，不是立刻更 新结果，而是缓存起来，查询的响应是周期性的。因为查询结果不是及时 产生的，所以可以认为是近似的，也就是说它表示的是最近的那一点的准 确结果而不是当前时刻的准确结果。由于没有引起准确结果的不确定性和 降低实时性，批处理是一种很有效的近似方法。当数据流爆发时，它是一 个很好的处理方法。一个算法即使不能与数据流速率的峰值同步，但是可 以通过缓存来有效地处理数据流。 ( 2 ) 取样另外一种情况就是计算结果操作快，更新操作慢( 处理时间 超过数据元素平均的到达时间) 。因为数据到达的速度比系统处理的速度 快，所以在计算时获得整个数据是没有用的。一些元组必须被完全的忽略 掉，这种查询的执行是在数据流的样本而不是整个数据流上。这样得到的 燕山大学工学硕士学位论文 是近似的结果，但是某些情况，取样处理可能会带来某种程度的错误。不 幸的是，多数情况下( 包括含有连接的多数查询) ，基于取样的方法不能提 供可靠的近似保证。设计一个被证明与准确结果接近的基于取样的算法是 研究中的一个活跃的领域。 ( 3 ) 大纲很明显，数据流期望有一个更新和计算结果都很快的数据结 构。对于那些想要的属性上没有准确数据结构的数据流查询来说，可以设 计一个维护小的大纲或者概要的近似的数据结构来代替准确的表示，这样 就可以使每个元素的计算量达到最小。通过大纲数据结构实施数据约减代 替批处理或取样是一个与数据流模型有关的富有成果的研究领域。 2 4 5块操作 块操作就是那些只有获得整个输入才能产生输出的操作。排序就是块 操作的一个例子，还有一些聚集的操作如s 啪，c o u n t , m i l l , m a x 和a v g 。如果 想用传统的操作树进行连续查询求值的话，数据流进入叶子节点，最终的 查询结果在根节点产生，这样把块操作合并到查询树就带来一些问题。因 为数据流可能是无限的，一个块操作的一个输入是数据流，它将永远得不 到整个输入，这样也永远不能产生任何输出。很明显，块操作不太适合数 据流的计算模型，但是聚集操作是非常普遍的，而且排序的数据比未排序 的数据处理起来更有效率。处理这些块操作是比较困难的，如何有效地处 理它们是数据流计算的一个很有挑战性的方面。 块操作作为查询操作的根节点要比作为内部节点，更容易处理。例如， 产生中间结果输入给其它操作进行进一步处理。当有一个聚集查询在查询 树的根部时，如果这个操作产生一个或少数几个值的话，那么结果的更新 能随它们的输入被流出。当结果集很大，产生的是一个排序了的关系时， 由于连续地转发整个结果是很麻烦的，所以维护到现在为止的结果的数据 结构是更有实际意义的。这两个方法都不能使块操作很好地产生中间结果， 然而，主要的问题是块操作产生的结果可能是连续变化的，直到获得所有 的数据为止。所以与这些结构相关的操作不能根据查询执行中间阶段的结 果做出可靠的决定。 第2 章数据流查询处理相关技术 一个处理查询树中块操作作为内部节点的方法就是用模拟近似的相同 任务的非块操作代替。这个方法的一个例子就是j u g g l e 操作刚，这是一个 排序的非块操作版本。一个有趣的开放难题就是如何把这项工作扩展到其 它类型的块操作上，以及如何量化由非块操作产生的近似块操作的错误。 t u c k e r l 3 5 等已经提出了一个处理块操作的不同方法。他们建议在数据 流上增加一个断言，用于判断哪些能和哪些不能出现在数据流的剩余部分。 这个断言被数据流的数据元素交叉存取。 2 4 6 参考历史数据的查询 在数据流计算模型中，一旦数据元素已经流过的话，就不会被再一次 访问到。这就意味着对那些与已经丢弃的数据有关的即席查询来说，要得 到一个准确的结果是不可能的。 解决这个问题的一个简单的方法就是规定即席查询只能参考将来的数 据：它们是在查询开始的时候对数据流进行求值的，任何过去的流元素都 被忽略( 为了查询的目的) 。然而这种方法可能不会太令人满意，但是可以 被很多应用所接受。 一个更好地处理参考历史数据的方法就是维护数据流上的概要，这可 以使未来的即席查询得到近似的结果。采用这个方法需要提前决定用最好 的方式来使用内存资源为广阔范围的未来查询提供近似的结果。这个问题 与物理数据库设计的一些问题，如索引的选择和物化视图 3 6 1 有些相似。然 而，它们有很大的不同：在传统的数据库系统中，在没有索引或视图的情 况下，有可能去访问底层的关系，这样就增加了代价。 在数据流计算模型中，如果没有近似的概要结构，就没有可用的资源。 即使即席查询声明仅适合将来数据，仍然有很多诸如如何更好地处理数据 的课题需要研究。 在数据流应用中，大部分查询是长时间的连续查询，而不是短暂的一 次查询，多查询优化带来的收益要比传统的数据要多。即席查询的出现把 为查询找到最好的查询计划从脱机问题转移成联机问题。即席查询引起了 查询计划的自适应性问题。e d d y 查询执行框架引入了可伸缩查询计划的概 燕山大学工学硕士学位论文 念，用来适应数据到达速率的变化和其它随时间变化的数据特征。如何扩 展这个思想以适应连续查询集上的连接计划( 新查询的增加和旧查询的移 除) 是一个开放性的研究领域。 2 5 数据流管理系统 由于数据流的特点，传统的数据库管理系统已经不再适合与对数据流 的处理。 传统的数据库管理系统并不是为处理大量的连续的数据流而设计，因 此很难将大量的数据流存储到数据库管理系统中。 针对数据库管理系统所设计的操作符难以处理无界的数据流的查询。 例如，连接操作和聚集操作都需要得到所有的数据才能进行查询处理，而 在数据流中，由于数据会持续地到达，这些操作会因为等待数据结束而被 永远的阻塞起来。显然这些操作需要进行改进才能够适应数据流环境中的 计算。 传统的数据库管理系统不支持实时的元组处理方式。它们难以应用在 需要对数据进行实时分析的应用中，如网络监控。 传统的数据库管理系统通常需要产生的是精确的答案，且没有实时性 的限制，而数据流应用通常对数据的处理速度具有一定的要求，往往希望 在线的获得数据处理结果。 对流数据的处理通常是基于持续查询模型的，而数据库管理系统所能 处理的是一次查询，虽然触发器能够解决一定的持续查询问题，但是它缺 乏通用性，并且传统数据流系统难以处理大量的触发器。 在数据流管理系统中，不但数据可以以多种形式存在，而且对数据流 的查询也可能具有不同的形式。对传统的数据库的查询多为一次性的查询， 返回数据集中的当前状态。而在数据流系统中，查询可以是一次性的也可 以是连续的，并且当前的应用大多要求连续的查询，系统可以持续长时间 的对数据流进行查询操作，并持续的向用户返回操作结果。 针对数据流的特点，如何研制一个有效的数据流管理系统( d s m s ) 用以 1 4 第2 章数据流查询处理相关技术 管理流式数据便成了一个需要解决的问题。从功能上看，数据流管理系统 跟传统的数据库管理系统在功能和性能上是相似的，不同的是前者允许数 据都以连续的数据流的形式出现。 为了设计数据流管理系统，首先需要明确数据流管理系统与数据库管 理系统的区别。 ( 1 ) 模型在数据库管理系统中仅存在持久关系，除非刻意修改，该关 系不会改变；在数据流管理系统中，仅仅存在瞬时关系，它随着数据流上 元组的到达而不断变化。 ( 2 ) 关系数据库管理系统中一个关系表现为元组的集合，可以随机访 问；而在数据流管理系统中，一个关系实质上是一个元组序列，只能够顺 序访问。 ( 3 ) 数据更新数据库管理系统和数据流管理系统均可以对关系进行 操作。不同的是，前者可以有插入( i l l s e n ) 、删除( d e l e t e ) 、更新( u p d a t e ) 等多 种方式，而后者却仅有添力l ( a p p e n d ) - - 种方式。 ( 4 ) 查询在数据库管理系统中，查询是瞬时的，执行完毕之后就不再 有效；在数据流管理系统中，查询是永久的，除非被强制取消，否则该查 询会一直存在以处理新到达的元组。 ( 5 ) 查询结果数据库管理系统产生的是确切的查询结果；数据流管理 系统产生的查询结果往往是近似的。 ( 6 ) 查询执行在数据库管理系统中，可以任意多次访问关系中的元 组；但是在数据流管理系统中，却只能够一次遍历访问关系。 ( 7 ) 查询计划在数据库管理系统中，查询计划一旦生成就不能更改； 但是在数据流管理系统中，查询计划往往需要随着外部环境的变化而更改。 一种典型的数据流管理系统的结构如图2 1 所示。 数据流通过输入监控器进入到数据流管理系统。输入监控器可用于控 制数据的输入速率。数据流被分为三部分分别存储：临时工作存储( 用于窗 口查询) 、数据流的概要存储和数据流的静态存储( 每个数据源的物理地 址) 。虽然可能对数据流现有状态只进行一次查询，但长时间的连续查询也 要注册到查询库，并插入到查询队列中等待处理。查询处理器与输入监控 整当查堂三兰堡主堂垒笙苎 器进行交互，当数据流的输入速率改变时对查询计划进行重新优化。数据 流管理系统最后生成数据流查询的结果也以数据流的形式显示给用户或者 把进入l 临时缓存。 、r 工作存储i i 输输 l 概要存储l查询 出 入 l_ 监 处理器 缓 - _ 控 存 静态存储 查询存储 图2 - 1 数据流管理系统结构 f i g 2 - 1s t r u c t u r eo f d a t as t r e a mm a n a g e m e n ts y s t e m 2 6 本章小结 本章介绍了数据流的基本概念和数据流模型，并且列举了一些典型的 数据流方面的应用，随后对数据流查询有关的问题进行了说明并讨论了相 关的算法。总结了数据流管理系统与传统数据流管理系统的对数据处理的 不同要求和特点，最后给出了数据流管理系统的参考结构。 1 6 第3 章分布式数据流查询操作放置算法 第3 章分布式数据流查询操作放置算法 3 1分布式数据流查询处理模型 在大量数据流应用中，数据流是来自分布在不同地理位置上的数据源， 其本身非常适合于分布式处理1 3 ”。对数据流查询进行分布式处理可以更好 地满足数据流应用的需求【3 s 】。如图3 1 所示，一个分布式数据流查询处理 模型主要由3 部分组成：数据源、分布式数据流管理系统和应用。 数据源向分布式数据流管理系统提供连续的数据流。分布式数据流管 理系统是一个由许多数据流查询处理结点组成的庞大的数据流查询处理网 络，负责对来自不同地理位置上的数据流进行分布式的查询处理，并把最 终的处理结果交给应用。分布式数据流管理系统把应用或用户提交的查询 需求透明地分解到多个处理结点进行处理，提高了系统的可扩展性、高效 性。应用向分布式数据流管理系统提交查询，并从分布式数据流管理系统 获得查询结果。 图3 1 分布式数据流查询处理模型 f i g 3 - ld i s t r i b u t e dd a t as t r e a mq u e r yp r o c e s s i n gm o d e l 1 7 燕山大学工学硕士学位论文 定义3 1 ：查询树( q u e r yt r e e ) 。一颗树q r = ( v ，l ) ，其中v 为结点的 有穷集合，三为结点之间的连接的集合；若q r 满足下列条件则称q r 为一 颗查询树。 ( 1 ) 树的根结点为基于数据流的应用爿； ( 2 ) 树的分支结点( 根结点除外) 为数据流查询操作o ； ( 3 ) 树的叶子结点为数据流的数据源s ； ( 4 ) 树中的结点至多有2 个孩子结点； ( 5 ) w l ，是有向的且从孩子结点指向双亲结点，n 己为( f ，) ，i 为 孩子结点，为双亲结点。 分布式数据流查询处理模型中的连续查询是由数据流、数据流查询操 作和数据流应用组成的查询树，如图3 2 所示。查询树是一颗定向树，数 据流总是从孩子结点流向双