（计算机应用技术专业论文）数据流管理系统中的概要数据结构算法的研究和实现.pdf

东南大学硕士学位论文 摘要 近年来，在金融服务、网络监控、电信数据管理及传感器检测等领域中，出现了一类新的数据密集 型应用。这类应用的特征是：数据以大量、快速、时变的数据流形式持续到达，所以数据不宣用持久稳 定关系建模，而适合用数据流建模。论文在研究目前国际上最新的数据流管理技术的基础上，介绍了东 南大学自行开发的基于硬件预处理器的数据流管理系统原型s e u s t r e a m 的体系结构和一种可以支持 对数据流上进行持续查询的查询语言x - s q l 。 在根多实际应用中，例如决策支持系统、查询优化等，用户并不需要获得确切值，而仅需要一个近 似值。因此，设计单遍扫描算法( o n e - p a s sa l g o r i t h m ) ，实时地给出近似查询结果就成为数据流模型下数 据处理的目标。算法的关键在于设计一个远小于数据集规模的结构，从而可以在内存中处理数据。相对 于数据流的规模而言，这种名为概要数据结构( s y n o p s i sd a t as n u c t u r e ) 的规模至少是次线性的。 小波变换大纲作为高效的数据压缩还原技术引起了数据流领域的高度关注。论文详细介绍了哈尔小 波的变换过程，并且引入了误差树的概念对这个变换过程进行了详细的分析。在此基础上实现了用哈尔 小波方法生成概要数据结构的算法，选用了不同的固定阈值并进行了性能测试，实验表明不同的压缩率 导致了重构数据与原始数据存在一定的误差。同时基于测试结果分析了固定阈值方案的不足之处，数据 重建的质量变化很大，并且对于单独的近似解答缺少特别的质量保证。在此基础上提出并实现了基于概 率的可变阈值的小波变换，比较好地解决了这个问题。 关键字：数据流管理系统，概要数据结构，h a m 小波变换，x - s q l ，阅值 查堕盔兰堡主兰垡丝苎 a b s t r a c t i nr e c e n ty e a r s ，an e wk i n do fi n t e n s i v ed a t aa p p l i c a t i o n sh a sf o u n df r o ms o m ef i e l d s ，s u c ha sf i n a n c i a l s e r v i c e , n e t w o r km o n i t o r i n g , t e l e c o m m u n i c a t i o i l sd a t a , n s wd e t e c t i o n , a n ds o f o r t h 1 1 1 ec o m m o n c h a r a c t e r i s t i co f s u c ha p p l i c a t i o n si st h a t , t h ed a t au s e di nt h e s ea p p l i c a t i o n si sm o r fs u i t a b l ef o rb e i n gm o d e l e d b yt r a n s i e n td a t as t r e a m s c o n s i d e r i n gt h ec h a r a c t e r i s t i co f h u g es i z e , h i g hs p e e do f d a t aa r r i v i n g , l i m e - v a r i n g , t h ed a t ai nd a t as t r e a mm o d e lc o u l dn o tb em a n a g e db yt r a d i t i o n a ld a t a b a s e s o , an e w “落e w c ha l e ao f d 刮：a b a s e d a t as t r e a m sm a n a g e m e n to c c 峨 o nt h eb a s i so fs t u d yo ft h en e wi n t e m a t i o n a lt e c h n o l c l g yo fd a t as t r e a mm a n a g e m e n t , w ed e v e l o p e da n wd a t as t r e a mm a n a g e m e n ts y s t e mp r o t o t y p eb a s e do np r e - p r o c e s s i o no fh a r d w a r e , n a m e ds e u s t r e a m f i r s t l yt h ee c h i l e c t u r eo f s e u s t r e a m a r ei n t r o d u c e d t h e l lt h ep a p e rg i v e st h ed e s i g no f ac o n t i n u o u sq u e r y l a n g u a g ex - s q l w h i c hc o u l ds u p p o r tt h ec o n t i n u o u sq u e r yo nd a t as l r e a m s mg e n e r a lw a y st om a k e a b s t r a c td a t as l n k 慨i sa l s oi n t r o d u c e di nt h i sp a p e r h a r tw a v e l e ts y n o p s e si si m p l e m e n t e di ns e u s t r e a m a n dt h ep e r f o r m a n c ei st e s t e d f r o mt h et e s tr e p o r t , i m p r o v e m e n ta d d e di nt h ea r i t h m e t i c w eu s eav a r i n g t h r e s h o l d i n gv a l u et om a k eh e a rw a v e l e ts y n 0 d s o s k e yw o r d s ：d s m s ，a b s t r a c td a t as 仃1 l c t i 鹏，h a r tw a v e l e ts y n o p s e s , x - s q l ，t h r e s h o l d i n gv a l - - 东南大学学位论文 独创性声明及使用授权的说明 、学位论文独创性声明 本人声明所节交的学位论文是我个人在导师指导下进行的研究r 作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 二、关于学位论文使用授权的说明 签名：题磋嘞趔丘笠z 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电 子文档，可以采j _ 影印、缩印或其他复制手段保存论文。本入电子文档的内容和纸质论文的内容相 一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 签名：篡- 独缝导师签名日期：丝篮笙1 东南大学硕士学位论文 1 1 数据流的出现 第一章数据流管理技术概述 近年来，出现了一类新的数据密集型应用，这类应用中数据的特征是：大量、连续、无限、快速、 随时间改变。这类数据持续到达，数据到达速度及数据量可能是不可预知的，我们把这种数据称为数据 流【1 1 这类应用出现在许多领域中，包括传感器网络嘲【1 日、交通管理【3 l 、网络监控 4 1 、电信数据管理嘲、股 票分析1 6 1 、生产制造过程等。在这类数据流模型中，单独的数据单元可能是相关的元组，例如网络测量、 呼叫记录、网页访问、传感读数等产生的数据。也有可能是无关的独立元组，例如交通管理、生产制造 过程等。由于这些数据以大量、快速、随时间改变的数据流形式持续到达，以一种流的形式源源不断地 进入系统，所以无法以永久的关系形式全部保存下来之后再进行处理。因此，许多已有的数据库技术难 以应用于数据流，由此产生了一些新的基础性研究问题。有关数据流处理技术的研究逐渐成为数据库领 域的一个新研究热点。 1 1 1 数据流特征 电话记录、股票报价以及从传感器中读取数据都是数据流的例子。数据流是一个实时的、连续的、 潜在无界的、有序的( 隐含地通过到达时间或者明确的时间戳) 项的序列。 与传统关系数据库中的数据相比，数据流数据具有许多自己的特点川： 数据实时到达，数据流速度有可能不可预知，要求快速即时的响应 系统无法控制数据元素的到达次序 数据随时间变化，规模宏大且无界( 即不能预知其最大值) 数据处理基本上采用单遍扫描算法，数据一经处理很难再次被取出 数据结构化程度较低，需要多层次化和多维化处理 1 1 2 数据流模型 在数据流模型中，部分或全部需处理的输入数据并不在可随机访问的磁盘或内存中。它们以一个或 多个“连续数据流”( c o n t i n u o u sd a t as t e a m s ) 的形式到达。令t 表示任一时间戳，a t 表示在该时间戳到达 的数据，数据流可以表示成 ，弘l 钆鼬i ，) 。 数据流模型中的操作并不捧除传统的关系型数据的存在。通常，数据流查询操作将建立数据流和关 系型数据的联系。我们假定，如果使用了存储关系，则它们的内容保持静态不变。在数据流处理过程中， 更新存储关系的同时可能会产生传输处理问题，通过上述假设，我们捧除了任何潜在的此类传输处理问 题嗍。 实时数据流是一个以某种顺序到达的数据项的序列，可能只会被访问一次。虽然数据流数据不同于 东南大学硕士学位论文 传统数据数据库中的数据，但是也有类似之处，数据流中单个数据项可能是一个关系元组，也可能是一 个对象实侧 s q 。在基于关系的模型中，数据项是存储在虚拟关系中的瞬时元组。在基于对象的模型中， 数据源和数据项采用的是与方法相关联的数据类型的模型。 1 1 3 传统d b m s 处理数据流遇到的问题 在数据流出现的应用中，如果把持续到达的数据存储到传统的数据库管理系统( d b m s ) 中，用 d b m s 的传统操作方式对数据流数据进行操作是非常困难的。传统的d b m s 并不是为快速连续地存放 独立的数据单元而设计的，而且也并不支持“连续查询”( c o n t i n u o u sq u e r i e s ) ，而“连续查询”是数据流应 用的典型特征另外，现在人们都认识到，“近似性”( a p p r o x i m a t i o n ) 和“自适应性”( a d a p t i v i t y ) 是对 数据流进行快速查询和其他处理( 如数据分析和数据采集) 的关键要素，而传统d b m s 的主要目标恰 恰与之相反：通过稳定的查询设计，得到精确的答案唧。表1 1 列出了数据流与传统数据库在数据管理 上的差异。 d b m sd s m s 持久稳固的关系 瞬时的数据流 一次查询 长时间连续查询 随机访问 顺序存取 极大的磁盘存储有限的主存空间 仅表示当前的事件状态历史到达暇序是关键性特征 被动的储藏库主动存储 相对低的更新速率可能是多路g b 级到达速率 不具有实时服务功能实时服务是必要功能 假定精确数据数据可能是陈旧或不精确的 访问计划由查询处理器，物理数据库设计确定不可预知，变化的数据抵达方式和特征 表1 1 数据流与传统数据库的对比 数据流数据的特征要求新的数据处理技术，下面我们开始介绍当前正在研究的一些数据流处理的技 术。 1 2 数据流查询 由于数据流数据与传统关系数据库数据的不同，连续数据流上的查询跟传统数据库管理系统中的查 询存在两个主要的差别：一个区别是一次查询和连续查询；另一个是预定义查询和即席查询i i j 。 一次查询是实施在数据集快照上的查询，结果返回给用户。而连续查询是在数据流连续到达的过程 中进行连续求值，连续查询的结果是随时间产生的，通常反映的是到目前为止的数据流。连续查询结果 可能被存储或随新数据的到达进行更新，或者产生新数据流。 预定义查询是一类在任何相关数据到来之前在数据流管理系统已经定义的查询。预定义查询通常产 生连续的查询。即席查询可能为一次查询或连续查询。由于即席查询不能事先知道查询优化的目的以及 确定查询间共同子表达式的情况，所以使得数据流管理系统的设计变得更加复杂。更重要的是。即席查 询的准确结果需要参考数据流的历史数据。 2 东南大学硕士学位论文 l 。3 数据流管理技术研究现状 目前，国外已经在数据流管理领域开展了大量的研究工作，取得了一定的成果，并且开发出了一些 数据流管理系统原形。最具典型的原型系统主要有s t a n f o r d 大学的s t a n f o r ds t r e a md a t am a g 呱简称 s t r e j v 0 、b e r k e l e y 大学的t e l e g r a p h 系统和b r a n d e i s u n i v e r s i t y 、b r o w n u n i v e r s i t y 与m z z 联合开发的 a u r o r a 系统。其它数据流系统主要有t a p e s t r y 、t r i b e c a 、n i a g a r a 、c o u g a r 、a t l a s 、f j o r d s 、h a n c o c k 等 1 3 1s t r e a m 系统 s t r e a i v l 系统是由s t a n f o r d 大学开发的一个通用的数据流管理系统。它的设计目标是处理高速数 据流，支持大量并发的连续查询。在数据流速和查询负载超出可获得资源的情况下t 系统优化内部配置， 可以为连续查询提供相对准确的近似结果。系统内部的多查询优化策略、有效的资源分配算法和灵活的 调度策略保证了系统的高性能。有限资源和结果近似性的自动平衡是系统最重要的关键技术。 s t r e a m 系统支持连续查询语言c q l ( c o n t i n u o u sq u e r yl a n g u a g e ) ，用户可以采用c q l 注册数据 流查询，也可以直接输入查询计划。s t r e a m 可按照用户的查询需求针对数据流进行实时的连续查询。 用户或应用程序向系统注册查询，被注册的查询将一直被保留到查询被显式地注销为止。 s t r e a m 系统中。查询首先被注册，随着新数据的到来，查询不停地被执行。c q l 是s t r e a m 系 统标准查询语言，它既支持传统的关系操作，又支持流操作。c q l 扩展了s q l 语言，主要表现在f r o m 子句。f r o m 子句包含一个可选的滑动窗口和一个取样子句。滑动窗口由分割子句( p a r t i t i o nb y ) 、窗口 大小和可选的过虑谓词组成。分割子句把数据分成几组，在窗口内计算每组的值，然后合并结果t 类似 标准s q l 中的g r o u pb y 。窗口大小由r o w 或r a n g e 确定，如；r a n g e1 0 m i n u t e sp r x e o i r l g 。取样子句定 义了取样的百分比，如s a m p l e ( 3 ) 。 对于无限的数据流，s t r e a m 系统通过滑动窗口将其转化为有限的关系元组集合。系统又定义了 一些新的运算符，如i s t r e o a n ( 插入流) 和d s t r e a m ( 删除流) ，通过它们将关系元组转化为流，为用户 提供连续的查询结果。 s t r e a m 系统中，每一个查询都有一个独立的查询计划。查询计划由三种不同的结构组成：查询 运算符( q u e r yo p a a t o r s ) 、操作队列( i n t e r - o p e r a t o rq u e s ) 、大纲( s y n o p s e s ) 。一般来说，队列是内存 中用来存储数据的一块缓冲区，有最大容量限制。因此当数据量超出缓冲区的最大容量时，旧的数据就 被丢弃，以便容纳新数据。队列可以为多个运算符提供数据源。在传统的关系数据库中，两个关系的连 接操作需要多次扫描关系表，而数据流具有瞬时性，数据不停地被更新，为了实现上述功能，s t r e a m 系统定义了大纲数据结构，用于暂时存储数据。当然，大纲不仅仅用于连接操作。大纲与队列的重要区 别是：大纲是为某种操作而服务的，容量大小通常根据操作的需要而决定。 有效的资源管理是数据流管理系统的关键技术之一。有限资源和结果近似性的平衡是s t r e a m 系 统最重要的关键技术。s t r e a m 系统中，重点关注的是内存的管理。针对内存管理主要采用了两种技 术：根据统计信息和查询注册信息，对大纲进行压缩：采用优化的调度策略，降低队列所占用的存储空 间。在数据流的流速和查询负载超出可以获得资源的情况下，可以为连续的查询提供相对准确的近似结 果。那么如何在有限的资源下获得最佳的查询结果呢? s t r e a m 系统采用的主要技术是静态近似策略 3 东南大学硕士学位论文 和动态近似策略。其中相较而言，动态近似策略是更有挑战性的课题，它比静态近似具有更多的优越性。 s t r e a m 系统最主要的资源消耗在于大纲和队列。因此主要的动态近似方法有：采用柱状图、小波压 缩等技术实现大纲的压缩；采用动态取样、数据流丢弃等技术减少队列所占用存储空间。 s t r e a m 系统还有不少不完善的地方。它是一个基于关系模型的集中式数据库，而对于许多数据 流的应用，分布式处理更为重要。因此s t a n f o r d 大学正在计划s t r e a m 系统升级为分布式系统。查询 计划的形成策略还有待于进一步研究，资源分配算法还不能很好的支持近似回答。 1 3 2a u r o r a 系统 a u r o r a 系统”是由b r a n d e i su n i v e r s i t y 、b r o w nu n i v e r s i t y 和i v l l t 联合开发的数据流管理系统，它 支持大量的触发器，因此又被称为触发器网络。 a u r o r a 系统是一个面向数据流监测应用的数据流管理系统。采用了工作流系统中常用的b o x ( 功能 盒操作符) & a r r o w ( 数据流向符) 模型。用户根据查询需要，将查询表示为由a r r o w 流向符连接起来的若 干b o x 操作符组合而成的网络模式，这个模式就是初步查询计划。用户注册一个查询，就是要生成一个 相应的查询计划。查询计划被简单变换成调度器中的不同查询处理队列。调度器的调度分两个层次： ( 1 ) 确定选择哪个查询进行调度； ( 2 ) 确定每个查询如何执行。即操作符序列的执行顺序。 a u r o r a 系统采用了批处理技术来降低调度代价和操作符执行代价。系统支持两种方式的批处理：对 操作符调度的批处理和对元组的批处理。a m o r a 系统对于大量实时数据，根据定义的服务质量( 0 0 s ) 模 型，采用l o a d - s h e d d i n g 技术，必要时，修改查询计划，卸掉一定的过量负载，以保证系统的响应速 度。 a u r o r a 系统中最基本的结构是b o x 和a r r o w ，每个b o x 是一个处理单元，w 反映了数据的流动方 向和b o x 处理数据的先后次序。查询是通过图形化的用户界面，以b o x 和a r r o w 形式。这是a u z o r a 与其 它数据流管理系统的显著不同。 a u r o r a 系统定义了专用的运算符，以完成各种查询需要，这主要包括f i l t e r 、d r o p ，u n i o n 、w s o r t 、 t u m b l e 、w i n d o w e d 、s l i d e 、l a t c h 、r c * a m p l e 、m a p 、g r o u p b y 和j o j l i 等。其中f i i t e r 对输入流过虑； u n i o n 将多个输入流合并为一个输出流；w s o r t 缓冲所有的输入流，并按属性排序输出；g r o u p b y 按照 属性进行分组；j o i n 是连接操作；w i n d o w e d 截取一段数据流，即固定时间窗口；s l i d c ，滑动窗口；r c s a m p l e ， 是再取样；m a p ，映射；t u m b l e 和l a t c h 运算符比较复杂。 a u r o r a 系统支持三种查询模式：连续查询( 实时处理) 、视图和a d 查询。第一层结构为连续查询， 该层的数据被实时处理后，不保存。服务质量规范( q o ss p e c i f i c a t i o n ) 决定资源如何分配给各个处理单 元。通常，一个用户查询被分解为若干个b o x ，b o x 由连接点增加或删除，连接点可以将数据暂存一段 时间。第二层结构是视图，是在调度器的控制下物化或者部分物化的视图。通过视图可以加快查询的速 度，服务质量规范说明各个视图的重要程度。第三层结构为a d 查询，a d 查询可以在任意时刻附加到连 接点，实现对历史数据的查询。 归纳起来，a u r o r a 系统具有如下特点：1 ) d a h p 模式( d b m s - a c t i v e ，h u m a n - p a s s i v e ) ：2 ) 适宜 处理时间序列信息，便于获取数据的新值和旧值；3 ) 触发器居于主导地位，能够有效实现大量的触发 器：4 ) 能够根据负荷和资源的情况，实现精确查询或近似查询；5 ) 具有实时性，可以在线处理数据。 4 东南大学硕士学位论文 因此a u x o r a 系统的主要应用环境是：处理的对象是数据流；需要大量的触发器；有较高的实时性要求； 以非精确的数据处理为主或近似查询为主。 对许多的数据流应用，其本质上是分布式的。因此开发分布式的数据流管理系统是必要的。a r u o r a * 是以a t w o r a 为基础的分布式数据流管理系统。 1 3 3t e l e g r a p h c q 系统 t e l e g r a p h c q ”系统是通用数据流管理系统，在开放式关系数据库管理系统p o s t g r e s q l 基础上开 发。它继承了u cb e r k e l e y 的t e l e g r a p h 数据流项目开发成果，以p s o u p 系统为查询处理系统，以f l u x 系统作为负载平衡和容错处理系统。在系统中，注册的数据流查询经过预处理后被变换成一个操作符执 行序列，而后交给元组路由选择器e d d y 。 p s o u p 是b e r k e l e y 大学的t e l e g r a p h 系统的查询处理器。在p s o u p 中查询首先要被注册，注册后返回 用户一个旬柄。接下来不停地执行查询请求。查询语句的一般模式是：s e l e c t s e l e c t - l i s t f r o m f r o m 1 i s t w 眦r e c o n j o i n e d b o u l e a n f a c t o r s b e g i n b e g i n t i m e e n d e n d t i m e 。 查询被分解为两部分：s e l e a 碾o m - w h e r e 子句和b e g i n e n d 子句。s e l e c t - f r o m w h e r e 子句为标准查询子句( s q c ) ，存储在数据结构q u e r ys t e m 中。满足s q c 的元组记录在r e s u l ts t n l c t u r e 中。b e g i n - e n d 子句表达了一个滑动的窗口，该子句存储在一个独立的结构w i n d o w s t a b l e 中。新的数 据流入系统后，被分配一个全局的元组i d ( 称为t u p l e l d ) 和物理时间戳( p h y s i c a l i d ) ，然后插入到数 据结构d a m s h u c t u r e 中，r e s u l t s t r u c t u r e 中的元组中包含元组的t u p l e i d 和p h y s i c a l l d 。新的数据元组也 可以检索其它的d a t as t e m ，实现连接操作。注册一个查询后，被分配一个唯一的d 号( q u e r y i d ) ，标 准查询子旬插入去q u e r ys t e m 中。新查询主动检索d a t as t e m ，满足条件的元组记录到r e s u l ts m t c t u r e 中。由此可见，p s o u p 将数据和查询都作为流来处理。最终查询结果的获得是根据b e g i n - e n d 子句检 索r e s u l ts t r u c t u r e ，获取t u p l 卸d 后，根据t u p m d 从d a t as t e m 中得到元组。查询的执行过程如图1 - l 所示。 图1 ip s o u p 查询的执行 由上述分析可以看出，d a t as t e m ，q u e r ys t e m 和r e s u l ts u u c a a e 是p s o u p 中最重要的三种数据结 构。每个数据流有个d a t as t e m 数据结构，用于存储和索引数据流，d a t as t e m 采用基于树的索引结 构，每个属性建立一棵树。整个系统有一个q u e r ys t e m 结构，用于存储和索引查询，树结构是用来表 示满足s q c 的元组，常用的结构有两种：a 、二维表结构，每个f r o m - i i s i 有一个独立二维表结构，行根 5 东南大学硕士学位论文 据元组的物理时间戳进行捧序，列根据查询d 来排序；b 、每个查询带有一个链表，包含所以满足查询 条件的元组。 从p s o u p 的基本实现技术可以看出，p s o u p 将数据和查询都作为流来处理，因此新数据可以主动检 索已注册的旧查询，新查询也可以查询已经存在的旧数据，而其他数据管理系统要么将数据作为流，要 么将查询作为流，不能将二者同时作为流来处理。p s o u p 将查询和结果的传送分开处理，查询在服务器 端不停地被执行，结果记录在r e s u l ts t r u c t u r e 中，客户端通过r e s u l t 姗c t i r 获得结果，因此客户端短 时间的离线也不会影响查询结果。 目前p s o u p 仅支持内存操作。它今后的研究方向是支持磁盘上的流存储和研究物化视图与滑动窗口 之问的关系。 1 3 4 国内研究情况 国内，这方面的研究正在起步。文献资料也比较少，有些学校和研究所正在对数据流进行研究。复 旦大学集中在流数据管理和挖掘的研究，中科院计算机技术研究所试图构建一个面向网络信息安全的数 据流计算模型，重点研究的一些问题有网络数据流的获取、网络数据流建模、数据流查询模型、数据流 计算算法等，他们的目标是在这个模型的基础上开发出具体的有显示度的宏观网络监控应用系统。我们 现在正在研究基于硬件预处理器的数据流管理原型系统s e u s t r e a m ，通过基于硬件预处理器的体系架 构，该系统能够处理多条高速数据流上的多用户并发查询。 1 4 基于硬件预处理器的数据流管理原型系统s e u s t r e a m 1 4 1s e u s t r e a m 体系结构 为了能够快速及时地处理高速数据流，对数据流使用专门硬件进行预处理是一个很好的选择。基于 硬件预处理数据流管理系统s e u s t r e a m ”3 并不仅仅依靠查询优化、系统调用等传统手段来提高数据流 的处理速度，而是考虑一种全新的体系结构来达到目的。图1 2 是基于硬件预处理数据流管理系统的体 系结构示意图： 6 东南大学硕士学位论文 图1 2 基于硬件预处理的数据流管理系统体系结构图 基于硬件预处理的数据流管理系统分为两部份：前端预处理器和后端数据引擎。前端预处理器主要 负责对进入系统的数据流进行预处理，主要是通过系统后端传送来的控制命令进行状态初始化，对数据 流数据进行滤波、数据压缩和数据加标记处理。前端预处理器采用软硬件协同的方式以提高数据处理速 度。经过前端处理之后的数据通过网络传往后端，经过数据流划分控制器，在并行调度器的控制下，根 据用户查询请求得出的调度策略动态划分数据流元组，在并行查询执行器的控制下由各自的处理器并行 地完成查询处理。 在系统后端的数据引擎端，带有时间参数的连续查询经过查询语法分析器系统后保存在注册查询缓 冲中，连续查询被解析和分解为多个操作算子，由并行调度器生成动态查询计划，依照查询计划执行策 略将某些操作算子组成查询因子，经过查询输出控制器下载到前端硬件查询处理模块。 系统后端的数据引擎主要负责连续查询的语法分析、并行查询计划生成、将预处理过的元组划分到 不同的数据缓存，对并行处理得到的查询结果进行最后组装分发及负载均衡和服务质量监控等功能。系 统前端的查询预处理层接收并行数据引擎的查询请求，对多路采集来的模拟量或开关量进行本地预处理 或部分计算，形成分布式查询代理，将预处理结果送交至后端查询引擎。 1 4 2 连续流查询语言x s q l 1 4 2 1x - s q l 概述 x s q l 是基于硬件预处理的数据流管理系统( s s n ) 中所使用的连续流查询语言。x s o l 是一种 7 东南大学硕士学位论文 基于关系的类s q l 语言，这便于我们利用关系代数的理论基础和s q l 语言的技术基础。x - s q l 通过对 滑动窗口操作的支持来实例化连续查询的抽象语义。用户可以通过在系统的后端输入x s q l 的连续查 询，然后通过交叉编译后得到的查询指令及相关信息通过网络传送到数据流预处理器中去，完成对数据 流的各种查询操作。 x - s q l 语言由两部分组成，数据流定义语言( d s d l ) 和数据流查询语言( d s q l ) i l 目。其中d s d l 用来为数据流管理系统输入有关的元数据信息，d s q l 可以被用户使用对数据流管理系统中的数据流进 行查询。 1 , 4 2 2 滑动窗口概念 在数据流的持续查询系统中，滑动窗口可以看作是数据流的有限部分的集合。任意时刻的滑动窗口 包含数据流的有限片段的历史快照。 数据流上连续查询处理的执行方式有两类：一类是立即执行方式：一类是周期执行方式。立即执行 是指数据流上每个新数据到来，均触发执行一次查询；而周期执行是指每氍固定的瞬间闻隔触发执行一 次查询。由于连续查询的执行方式不同，所以滑动窗口的滑动方式也随之不同。当连续查询是立即执行 方式时，窗口的滑动是以元组为单位的，即每到一个新的元组，窗口就向前滑动，计算查询结果；当连 续查询是周期执行方式时，窗口的滑动是以固定个数的元组或固定的时间间隔为单位向前滑动，计算查 询结果。 x - s q l 支持的连续查询是基于滑动窗口概念的。x - s q l 支持两种类型的滑动窗口操作符：基于时 间的滑动窗口和基于元组的的滑动窗口。 1 4 2 3x - s q l 数据流定义语言s d l ) 在关系数据库管理系统( r d b m s ) 中，每个关系对应一张表，每张表保持一个固定的模式，这个 模式由一组有名字的属性组成。在数据流管理系统( d s m s ) 中，查询的对象是数据流，类似r d b m s 中 的表，在d s m s 中，每一个流也有自己的模式定义。这些元数据信息存放在数据字典中。有关数据流的 元数据信息通过x s q l 语言进行输入。 x - s q l 支持标准的s q l 类型i n t ，s m a l l i n t ，r e a l ，d o u b l ep r e c i s i o n ，c h a r 0 町，v 口c h a r c n ) ，d a t e ， t i m e ，t i m e s t a m p 等。 创建流( c r e a l es t r e a m ) c r e a t es t r e a m 略t r e a mn m 庐f 【，基于时间的滑动窗口 流s 基于时间的滑动窗1 3 用一个时间段t 作为输入参数作为滑动窗口的大小，在x - s q l 查询语句 f r o m 后的相应位置加上t 。我们不具体说明时间段t 的语法限制，但我们假定它是可以计算的时间。 基于时间的滑动窗口模型通过在一个有序的输入流上滑动大小为t 的窗口来捕捉最新的部分来定义它 的输出关系。正式的讲“s e l e c t + f r o mp o s s p e e a s t rw i n d o wr a n g er 的输出关系r 的定义如下： r ( f ) = j l s ( f 。研究哈尔小波的变换过程，并且引入了误差树的概念对这个变换过程进行了详细的分析 实现哈尔小波方法生成概要数据结构的算法，并进行了性能测试 提出并实现了基于概率的可变阈值的小渡变换 全文的组织如下： 第一章介绍了课题的研究背景和国内外的研究现状 1 0 东南大学硕士学位论文 第二章介绍和分析现今主要的生成概要数据结构的方法 第三章实现哈尔小波方法生成概要数据结构的算法 第四章提出并实现了基于概率的可变阈值的小波变换 第五章是对本文的总结 东南大学硕士学位论文 第二章生成概要数据结构的主要方法 在很多实际统计类应用中，例如决策支持系统、查询优化等，查询的解答大部分是定性的，用户并不 需要获得确切值，牺牲部分准确性来换取速度是可取的。因此，设计一遍扫描算法，实时地给出查询的近 似结果就成为数据流模型中数据处理的目标。此类算法的关键在于设计一个远小于数据集规模的结构， 从而可以在内存中完成对数据的处理。相对于数据流的规模而言，这种名为概要数据结构( s y n o p s i sd a t a s m 蛐r e ) 的规模至多是次线性的，即如果流的长度为，则概要数据结构大小不超过o ( p o l y l o g ( 柳) ，并且 处理流上每一组数据的时间不超过o ( p o l y l o g ( n ) ) e 。 数据流模型根据不同时序范围可以划分成多种子模型，包括界标模型、滑动窗口模型和快照模型1 1 4 j 。 界标模型和滑动窗口模型由于能不断处理新来的数据，更接近于真实应用，因而得到更加广泛的研究。生 成概要数据结构也有很多常用方法，如基本窗口、直方图、抽样方法和小波方法，下面将具体介绍这些 类型和方法。 2 1 数据流模型分类 界标模型( 1 a n d m a r km o d e l ) 界标模型指所要处理的数据范围从一个固定时间戳到当前时间戳。令初始时间戳为s ，当前时间戳 为n ，则查询范围可以表示为 ，a n 。 滑动窗口模型( s l i d i n g w i n d o w m o d e l ) 假设窗口的大小w ，在任一时间点n ，滑动窗口模型的查询范围是 a 。( 口_ w + l ”，a n ) 。时间点 m a x ( 0 ，n w ) 之前的数据全部忽略不计。在滑动窗口模型下构造概要数据结构比在界标模型下更具挑战 性的原因在于，不仅新数据不断到达，而且旧数据会过期。因此，如何处理过期数据，使得查询结果一 直可靠，就成为一大难题。 快照模型( s n a p s h o tm o d e l ) 快照模型将操作限制在两个预定义的时间戳之间，假设起始的时间戳为s 终止时间戳为e ，则查询 范围可以表示为 ，a e 。快照模型由于不能处理即时到来的数据，所以只适用于对实时性要求比较低 的场合，不能满足大多数应用。 2 1 生成概要数据结构的主要方法 2 2 1 基本窗( b a s i cw i n d o w ) 基本窗口技术6 1 将大小为w 的窗口按照时间次序划分成k 个等宽的子窗口，称为基本窗口，每个基 本窗口包含w k 个元素，且由一个小结构表示基本窗口的特征。如果窗口所包含的元素均已过期，则删 除表征这个基本窗口的小结构。用户可以基于这些未过期的小结构得到查询结果。这种方法还可以用于 获得数据集中的热门元素列表。 东南大学硕士学位论文 2 2 2 直方i g l ( h i s t o g r a m l 直方图技术【1 6 11 1 1 就是将一个大数据集划分为很多个连续的桶( b u c k e t ) ，也就是小数据集，每个桶都 由一个数字来代表其特征。直方图表示法直观、简洁，能够很好地表示大数据集的轮廓，因此在一些商业 数据库中采用。直方图又可以划分成多种，例如等宽直方图( c q u i - w i d l hh i s t o g r a m ) 、压缩直方图 ( c o m p r i s e dh i s t o g r a m ) 、v - 优化直方图( 州m a lh i s t o g r a m ) 等。 等宽直方图( e q u i - w i d t hh i s t o g r a m ) 等宽直方图的目标是使各个桶的高度( 即桶所含的数据量) 比较平均。