（计算机应用技术专业论文）数据流查询操作算法的研究.pdf

中文摘要 中文摘要 随着计算机应用的飞速发展，数据流的查询处理逐渐成为当前数据 库领域新的研究热点。在数据流的查询处理中，查询操作算法对于查询 处理的性能有着很大影响，本文致力予数据流查询操作算法的研究。 数据流上的查询主要是连续查询。连续查询处理的执行方式有两类： 一类是立即执行方式：一类是周期执行方式。目前，基于滑动窗口的查 询操作算法都是适用于立即执行的连续查询。但是在实际应用中，有时需 要周期执行的连续查询。 本文提出了适用于周期执行的连续查询的滑动窗口查询操作算法， 即滑动窗口是以基本窗口为单位周期更新的复合滑动窗口查询操作算 法。本文研究的内容主要包括复合滑动窗口的连接操作算法、复合滑动 窗口的聚集操作算法和复合滑动窗口的连接聚集操作算法。 本文提出的复合滑动窗口的连接算法是一种基于流水线的对称连接 算法。我们考虑了复合滑动窗口中的基本窗口结构对连接算法的影响， 给出了不同的实现算法。本文提出了复合滑动窗口的简单聚集算法和分 组聚集算法。对于简单聚集算法我们通过利川第次的聚集值米计算第 + 1 次的聚集值，提高了查询的效率。对于分组聚集算法还考虑了复合 滑动窗口中的基本窗口结构对分组聚集算法的影响，给出了多个的实现 算法。本文提出的复合滑动窗口的连接聚集算法在处理连接的同时计算 聚集值，不再保存复合滑动窗口的连接结果，从而有效的节省了查询操 作的内存丌销。理论分析和试验结果证明了本文提出的算法具有良好的 时间和空间复杂性。 关键词：数据流复合滑动窗1 3连接算法聚集算法连接聚集算法 - l - a b s t r a c t w i t ht h ef a s t d e v e l o p m e n to fc o m p u t e ra p p l i c a t i o n ，n o w d a y sd a t a s t r e a mp r o c e s s i n gi sb e c o m i n gt h en e wh o tf i e l do fd a t a b a s er e s e a r c h q u e r y o p e r a t o r sa l g o r i t h m si sak e yi s s u ef o rq u e r yp r o c e s s i n gp e r f o r m a n c ei nd a t a s t r e a mq u e r yp r o c e s s i n g ，w ec o n d u c td a t as t r e a mq u e r yo p e r a t o r sa l g o r i t h m s i nt h i sp a p e r q u e r i e so nd a t as t r e a m sc o n s i s tm a i n l yo fc o n t i n u o u sq u e r i e s i nd a t a s t r e a ms y s t e m sc o n t i n u o u sq u e r i e sh a v et w ot y p e so fe x e c u t i o nm a n n e r ： i m m e d i a t e l ye x e c u t i o nm a n n e ra n dp e r i o d i c a l l ye x e c u t i o nm a n l i e r a l lt h e e x i s t i n gq u e r yp r o c e s s i n ga l g o r i t h m so nd a t as t r e a m sa r eb a s e do nt h e i m m e d i a t e l ye x e c u t i o nm a n n e r b u tc o n t i n o u sq u e r yb a s e do nt h e p e r i o d i c a l l ye x e c u t i o nm a n n e ri ss o m e t i m e sn e e d e di na c t u a lp r a c t i c e t h i sp a p e rp r e s e n t sq u e r yo p e r a t o r sa l g o r i t h m so fs l i d i n gw i n d o w t h e a l g o r i t h m sa r eb a s e do nt h ep e r i o d i c a l l ye x e c u t i o nm a n n e r , n a m e l yi nt h e q u e r yo p e r a t o r sa l g o r i t h m so fc o m p o u n ds l i d i n gw i n d o w , s l i d i n gw i n d o wi s p e r i o d i c a l l yu p d a t e da c c o r d i n gt o t h eu n i to fb a s i cw i n d o w t h i sp a p e r m a i n l ys t u d y sj o i na l g o r i t h mo fc o m p o u n ds l i d i n g ，a g g r e g a t ea l g o r i t h mo f c o m p o u n ds l i d i n ga n dj o i na g g r e g a t ea l g o r i t h mo f c o m p o u n ds l i d i n gw i n d o w t h ej o i na l g o r i t h mo fc o m p o u n ds l i d i n gw i n d o wp r e s e n t e di nt h i sa r t i c l e i sas o r to fs y m m e t r i cj o i na l g o r i t h mb a s e do np i p e l i n e w ep r e s e n td i f f e r e m j o i na l g o r i t h mb yc o n s i d e r i n ga ne f f e c tb a s e do nt h es t r u c t u r eo fb a s i c w i n d o w s t h i sp a p e rp r o p o s e sas i m p l ea g g r e g a t ea l g o r i t h mo fc o m p o u n d s l i d i n gw i n d o wa n dag r o u pa g g r e g a t ea l g o r i t h mo fc o m p o u n ds l i d i n g w i n d o w t h es i m p l ea g g r e g a t ea l g o r i t h mo fc o m p o u n ds l i d i n gw i n d o w m e n t i o n e di nt h i sp a p e rw i l li n c r e a s eq u e r ye f f i c i e n c yw i t ht h em e t h o do f u s i n gc u r r e n ta g g r e g a t ea n s w e rt oc o m p u t et h en e x ta g g r e g a t ea n s w e r w e 外文j 茼要 p r e s e n ts o m ea l g o r i t h m sb yc o n s i d e r i n ga l le f f e c tb a s e do nt h es t r u c t u r eo f b a s i cw i n d o w sf o rt h eg r o u pa g g r e g a t ea l g o r i t h m t h i sp a p e rp r e s e n t sj o i n a g g r e g a t ea l g o r i t h m o fc o m p o u n ds l i d i n gw i n d o ww h i c hc a nc o m p u t e a g g r e g a t ea n s w e rw h i l ec o m p u t i n gj o i n a n s w e ra tt h es a m et i m e j o i n a g g r e g a t ea l g o r i t h mo fc o m p o u n ds l i d i n gw i n d o wd o e sn o ts a v ej o i na n s w e r a n ym o r e ，t h u si tr e d u c e sm e m o r yc o s to f q u e r yo p e r a t o r se f f e c t i v e l y t h e o r y a n a l y s e sa n de x p e r i m e n tr e s u l t ss h o wt h a tt h ea l g o r i t h m sp r o p o s e di nt h i s p a p e rh a v ev e r yg o o dc o m p l e x i t yo f t i m ea n ds p a c e k e y w o r d s ：d a t as t r e a m ，c o m p o u n ds l i d i n gw i n d o w , j o i na l g o r i t h m ， a g g r e g a t ea l g o r i t h m ，j o i na g g r e g a t ea l g o r i t h m 1 1 1 第1 章引言 _ ii 皇葺| _ 1 1 研究背景 第1 章引言 随着计算机应用的飞速发展，数据流处理逐渐成为当前数据库领域 新的研究热点。数据流是一种新型的数据处理模型。在许多应用领域中 管理的数据都是数据流的形式。例如：对网络进行监测时的i p 数据包、 对股票进行分析时的股票信息、电信公司的通话记录、传感器监测到的 各类数据等等。虽然数据流中的数据的基本单位还是关系模型中的元组， 但是与传统数据库中的数据不同，这类数掘不再是永久的关系形式，而 是源源不断的到来、时间有序、瞬时变化的。 由于数据流中的数据是连续不断到来的，并且数据产生的速度是惊 人的，数量是无限的。因此，在有限的存储空间中无法保存数据流的全 部数据。同时，数据流上查询的实时性要求也决定了数据不能保存下来 进行处理。因此传统的数据库技术无法对数据流中的数掘进行有效的管 理，越来越多的研究人员丌始进行数掘流查询处理新技术的研究。 1 1 1 数据流模型 在数据流模型【m 1 中，处理的数据不再是从磁盘和内存中随机访问读 取的数据，而是一个或多个连续的、无穷的数据项组成的序列。数据流 与存储在数据库中数据的区别在于： 1 数据流中的数据是实时到来的：而数据库中的数据是存储在磁盘 中、。 2 数据流中的数据是按序流过的，对数据只能进行顺序的访问；而 黑龙江大学硕士学位论文 磁盘中的数据可以随机访问。 3 数据流中的数据是无限的；而数据库中的数据是有限的。 4 由于在有限的存储空间内无法存储无限数据流的全部数据，因此 数据流中大部分的数据在处理后被丢弃了，数据流上的查询多数 只能得到近似的查询结果；而数据库上的查询则可以得到精确的 查询结果。 5 系统只能保存数据流全部数据的一个有限子集或统计数据，并随 着数据流上新数据的到来进行更新，这种更新的频度取决于数掘 流中数据到来的速度。一般来说，数据流的更新频度要远远高于 数据库中数据更新的频度。 目前，数据流的数据模型主要有基于关系和基于对象定义方式。基 于关系的数据流模型将每个数据源产生的数据流看作是虚拟的关系，数 据流中的每个数据项看作是一个元组。基于对象的数据流模型将数据源 及其产生的数据项看作足具有层次关系的数据类型，数据源与数据项之 i 日j 通过方法进行联系。本文使用的数据流的数掘模型是基f 关系的定义 方式。 1 1 2 数据流上查询的特征及语义 数据流上的查询【1 4 】与传统数据库中的查询类型基本上相似，但有一 个明显的区别：数据库中的查询主要是一次查询，而数据流上的查询则 更多的是连续查询。如果一个查询提交后，系统根据当前数据集合的快 照给出查询的结果，则称这样的查询为一次查询；如果查询随着新数据 的到来而不断的返回查询结果，则称这样的查询为连续查询。连续查询 注册到系统中后，除非用户明确的撤销该查询，否则随着数据流上新数 据的到来，查询将不断的返回查询结果。相对于一次查询连续查询具 第l 章引言 有长期运行的特点。连续查询处理的结构如图1 所示。 数据源r l 二二二 数据瀛r 2 二= = 数据流r 3 。 二二二 图1数据流连续查询处理的结构 数据流上的查询还可以分为预定义查询和a dh o c 查询两种查询形 式。预定义查询注册到系统后，主要钊。对数据流后续到来的数据计算查 询结果；丽a dh o c 查询是针对数据流中流过的数掘进行查询，即对历史 、 数掘进行查询。由于系统无法保存数据流流过的所有数据系统只能通 过提取和组织流过数掘的概要信息来支持a dh o c 查嘲，因此a dh o c 查 询一般只能得到近似的查洵结果。 在一个只有插入操作的数据库中，所有查询均是单调的。因为当一 个元组加入后，这个元组或者满足查询，或者不满足查询，查询的结果 随时间表现为递增。数据流上的大部分连续查询均具有单调性。文献l 2 1 讨论了数据流上单调的和非单调的连续查询语义。将时问表示成自然 数的集合，在每个整数时刻，连续查询计算一次查询结果。设爿( q f ) 是 连续查询q 在t 时刻的查询结果， r 表示当前时刻，0 表示查询的开始 时刻，则查询q 在r 时刻的查询结果集表示为： 黑龙江大学硕士学位论文 r 爿( q ，r ) = u ( ( q ，t ) 一爿( q ，一1 ) ) u 爿( q ，0 ) ，= 1 也就是说，单调的连续查询可以采用增量式的计算方式，即前一次 计算的查询结果加上新到来的数据中满足查询条件的那部分元组为当前 查询的结果。相反，对于非单调的连续查询，查询必须每次访问过去的 数据计算查询结果，其查询结果集表示为： r a ( q r ) = u 1 4 ( q t ) 1 = 0 1 1 3 数据流上的查询操作算法 因为数据流中的数据具有无限、瞬时、无法全部保存下来进行处理 的特点，所以数据流上的查询操作算法【1 与传统数据库中的查询操作算 法相比有它自身的特点。 阻塞操作 在关系系统中，若个操作在得到结架前，需要访问关系的全部数 掘，则称这个操作是阻塞的。排序以及聚集函数c o u n t 、s u m 、a v g 、 m a x 、m i n 等诈：多的操作均足m 塞的。如果使用传统的查询操作树米执 行数据流上的连续查询，那么若查询操作树中有一个阻塞的操作，则这 个查询不会有输出结果。因为阻塞操作需要扫描数据流上的全部数据， 而数据流是无限的，阻塞操作永远得不到输出结果。显然，阻塞操作不 适用于数据流的查询处理。然而，许多包含阻塞操作的查询，如聚集查 询又是数据流应用中一种常用的查询类型完全放弃阻塞操作也是不现 实的。 有些操作既有阻塞的实现算法，也有非阻塞的实现算法。例如连接 操作中，循环嵌套连接算法和s o r t - m e r g e 算法是阻塞的连接实现算 4 第1 章引言 法，而s y m m e t r i ch a s hj o i n 算法则是非阻塞的连接算法。s y m m e t r i ch a s h j o i n 算法在内存中分别为参加连接的两个关系a 、b 创建h a s h 表。当a 或b 中有一个新的元组到来时，首先将其插入到该关系对应的h a s h 表中， 然后用这个元组去探测另一个关系在内存中的h a s h 表，将匹配的连接结 果输出。当这些操作应用到数据流上时，显然只能选择其非阻塞的实现 算法。 解决阻塞操作河题的一个通用的方法是在数据流上定义窗口，将无 限的数据流限制在一个有限的范围内。窗口查询是数据流上的一种非常 重要的查询类型。 近似算法 在数据流的查询处理中，由于数据流无限性的特点以及系统存储空 间的限制，许多查询无法得到精确的查询结果。在这种情况下，高质量 的近似查询结果是唯一的选择。数据流查询处理的近似算法是一个非常 活跃的研究领域，已经有很多的研究成果。 抽样技术是处理大数据集上的查询时常用的近似方法，在抽样的样 本上计算查询的结果，同时给出查询结果的误差度。利用样本数据支持 查询时，。蝗查询可以给出明确的误茇度，而彳些查i f i j 则无法给! j 】确 的误差度，例如计算最大值的查询或者是大部分包含连接的查询等等。 系统统计并保存数据流的概要信息，利用概要信息来支持数据流上 的查询是另一种近似查询处理的方法。一般来说，存储数据流概要信息 的空间大小与查询结果的准确性密切相关，存储的概要信息越多，查询 结果的近似程度就越高。目前主要有s k e t c h 、直方图1 和h a s h 表等几 种概要信息的组织方式。 利用小波变换的系数来保存数据的特征信息1 5 l ，以此来支持数据流 上的聚集查询也是一种有效的近似方法。 黑龙江大掌硕士学位论文 滑动窗口 滑动窗1 3 是数据流上应用比较多的一种特殊的数据抽样方法【6 1 。滑 动窗1 3 是指在数据流上设定一个区间，该区间只包括数据流中最近到来 的那部分数掘。随着新数据的到来，窗口向前移动，用最新的数据替换 最旧的数据。与其它抽样方法相比，滑动窗口的优点在于其语义明确。 更重要的是，在许多应用中，例如传感器网络，用户关心的只是数据流 中新近到来的那部分数据。此时，滑动窗口是一种十分理想的抽样方法。 通过滑动窗口对连续查询的范围限定，包括两种限定方式1 0 l ：一种是窗 口中包含最近到来的7 个元组，称为基于顺序( s e q u e n c e ) 或基于计数 ( c o u n t ) 限定的滑动窗口。另一种是窗口中包含最近f 个时间单元内到来的 元组，称为基于时间( t i m e s t a m p ) 限定的滑动窗1 3 。数据流上连续查询处 理的执行方式有两类：一类是立即执行方式：一类是周期执行方式。立 即执行是指数据流上每个新数据到来，均触发执行一次查询：而周期执 行是指每隔固定的时问问隔触发执行一次查询。由刁：连续查询的执行方 式不同，所以滑动窗l j 的滑动方式也随之不同。当连续查询是立即执行 方式时，窗口的滑动是以元组为单位的，即每到一个新的元组，窗1 3 就 向| j i 滑动i | 算查询结果；当连续查询是周期执行方式时，窗l j 的滑动 是以固定个数的元组或固定的时问间隔为单位向前滑动，计算查询结果。 不同执行方式的连续查询中的滑动窗口如图2 所示。 一一 l = - ttb 捌 曲甜靠的錾耀辩叶的蝴口铡戳炳韵遛蜒辩时啪黼口 图2 不同执行方式的连续查陶中的滑动窗口 第1 章引言 目前，基于滑动窗口的查询操作算法都是适用于立即执行的连续查 询。但是在实际应用中，立即执行的连续查询操作算法有时是不适用的。 例如在监测互联网运行状态时，网络管理人员需要统计分析网络在两个 整点时刻内的运行情况。于是，两个整点时刻之间到来的数据不到整点 时刻不能加入到滑动窗口，执行查询处理，计算查询结果。同样，在电信 业和股票交易中也有类似的需求。表1 列出了互联网中主干网上的i p 数 据包组成的数据流a 及与主干网相连的一个分支网的i p 数据包组成的数 据流嚣中的部分数据。 表ii p 数据包组成的数据流a 、b 的部分数据 主干网i p 包数据流爿分支网i p 包数据流口 源i p目的i p时间戳源l p目的l p时自j 戳 2 0 2 1 1 8 2 2 4 2l o 1 0 1 0 19 ：3 52 0 2 1 l8 2 2 4 31 0 1 0 1 0 39 ：4 0 2 0 2 1 1 8 2 2 4 3l o 1 0 1 0 39 ：4 12 0 2 1 1 8 2 2 4 21 0 1 0 1 0 39 ：4 5 2 0 2 1 1 8 2 2 4 2 51 9 2 1 6 8 1 49 ：5 02 0 2 1 l8 2 2 4 21 0 1 0 1 0 1 01 0 ：0 1 2 0 2 1 1 8 2 2 4 2l o 1 0 1 0 1 01 0 ：0 2 在l o ：0 5 分，网络管理员提交了下面的滑动窗口台询统计在过去的 9 ：0 0 1 0 ：0 0 一个小时内，主干网a 的l p 数据包i ，水源于分支链路口的 比例。即： ( s e l e c tc o u n t ( ) f r o ma 【l a s tlh o u r 】，b 1 a s t1h o u r w h e r ea s r c = b s r ca n da d e s t = b d e s t ) ( s e l e c tc o u n t ( 1 f r o ma 1 a s tlh o u r ) ； 由表l 中的数据可知，用户期望的正确查询结果应该是1 3 。但如果滑 动窗口采用立即执行方式的查询操作算法，那么由于在t 0 ：0 2 分和1 0 ：0 1 分数据流a 、b 各有一个元组插入到其滑动窗口中，得到的查询结果是 黑龙江大学硕士学位论文 1 2 ，这个查询结果显然是错误的。因此在这类应用中，滑动窗口的查询 操作算法需要采用适合于周期执行的连续查询操作算法，即每隔固定的 时问问隔计算查询结果。 本文研究了基于周期执行的滑动窗口上的连续查询操作算法。 1 2 国内外的研究现状 数据流的查询处理是一个新的研究领域。近几年来，国外许多数据 库研究者开始从事数据流查询处理技术的研究，并取得了一些研究成果。 目前已经有了许多研究项目。比较有代表性的项目包括s t r e a m 、 t e l e g r a p h 和a u r o r a 。s t r e a m 是斯坦福大学数据库研究组的一个项目， 其目标是实现一个通用的数据流管理系统，研究内容涵盖了数据流查询 处理的各个方面，如资源管理、近似查询处理、数据流查询语言的定义 等方面1 8 - 2 8 j 。t e l e g r a p h 是美国加州大学伯克利分校的研究项目，主要是 基于自适应的查询处理技术来处理连续查询，其中的t u p l er o u t i n g 和 g r o u pf i l t e r 技术可以实现多查询操作算子的共享，有效的降低了查询处 理的内存丌销2 9 讲i 。a u r o r a 是柑朗大学、布兰代斯大学和麻省理- 1 ：学院 三校联合研究的传感器网络中的数掘流的查询处理问题。a u r o r a 采用操 作符一队列的执行方式，主要研究查询操作的调度策略、负载脱落技术 以及查询结果的q o s 等方面的问题1 3 8 - - 4 2 1 。 在传统的数据库中，查询类型主要是一次查询：而在数据流系统中， 查询类型更多的是连续查询。连续查询需要在新数据到来后不断的计算 查询结果。由于连续查询对处理速度提出了很高的要求，因而连续查询 的处理算法均是内存算法。但是由于数据流是瞬时的、无限的，所以在 有限的内存中不可能计算出全部的查询结果。为了在有限的内存中解决 无限流的连续查询处理问题，必须采用近似的查询处理算法。滑动窗口 第1 罩引言 是数据流查询处理中最常用的一种近似技术。文献 4 3 1 给出了维持滑动窗 1 ：3 上的统计信息的近似算法。文献【4 4 】讨论了滑动窗口中的数据抽样算 法。一般基于滑动窗口的数据流查询处理是在内存中为每个数据流维持 一个滑动窗口结构，使所有窗口的大小都适合内存。在任一时刻，通过 查询处理算法，得到近似的查询结果。 数据流上的连续查询中，连接查询是比较重要的一类查询。在数据 流应用中，经常需要对不同数据源的数据进行连接查询。例如，在一个 大厦中，监测温度的传感器产生数据流胄，监测烟浓度的传感器产生数 据流r 数据流包括属性( 1 0 c a t i o n ，t i m e ，t e m p e r a t u r e ) ，s 数据流包括 属性( 1 0 c a t i o n ，t i m e ，s t r e n g t h ) 。如果某个房间的温度达到了4 0 度以上 并且烟的浓度大于0 6 ，则需要启动自动救火装置。我们可以使用下面的 连接查询： s e l e c tl o c a t i o n f r o m r ，s w h e r er 1 0 c a t i o n = s 1 0 c a t i o na n dr t i m e = s t i m ea n dr t e m p e r a t u r e 4 0a n ds s t r e n g t h o 6 ： 来找到这样的房问。山1 二r 和s 两个数据流的数据是无穷的，上面的查 询在有限的内存中无法计算出全部的连接结果。因此，数据流上的连接 查询只能采取近似的方法。一种方法是提取数据流的概要信息 ( s y n o p s e s ) ，在概要信息上进行连接查询4 引。另一种方法是采用滑动窗口 的连接( s t i d i n gw i n d o w sj o i n ) 4 6 1 1 47 1 。对传统的数据模式进行连接操作可以 采用阻塞( b l o c k i n g ) 的查询操作算法，但是山于数据流的特点，阻塞的操 作算法显然不合适。文献【4 8 】提出了一种基于流水线( p i p e l i n e ) 的对称散列 连接( s y m m e t r i ch a s hj o i n ) 算法。此算法在内存中分别为参加连接的两个 数据流创建散列表。当两个数据流中有一个新元组到来时，首先将其插 黑龙江大学硕士学位论文 入到该数据流对应的散列表中，然后用其探测另一个数据流在内存中的 散列表，将匹配的元组输出。文献 4 9 1 提出了对称嵌套连接( s y m m e t r i c n e s tl o o pj o i n ) 算法，其思想与对称散列连接算法类似，只是内存中的数 据是顺序存储而不是散列存储。对称散列连接算法和对称嵌套连接算法 均是基于内存的算法。文献【4 7 】将对称散列连接算法和对称嵌套连接算法 应用到数据流上的滑动窗口连接中，并提出了一种适合于数据流的基于 单元时间的连接代价模型，根据参加连接的每个数据流的流速计算每个 连接算法的连接代价，从中选择代价小的连接算法用于查询。文献 4 6 1 给出了在滑动窗口上执行多路连接的算法，并给出了启发式规则来选择 合适的连接执行顺序，降低连接的执行代价。文献 5 0 5 1 给出了基于速 率的连接代价模型，使连接结果的输出数量在最短的时间内达到最大。 数据流的应用中多是监测数据的状态和变化，因而在数据流的查询 中，聚集查询也是一类特别重要的查询类型。在数据流上的聚集查询方 面，目前也取得了许多研究成果。文献1 5 2 】讨论了数据流上相关聚集的计 算问题。文献【5 3 】计算数据流流过数据的统计信息，称之为草图( s k e t c h ) ， 利用草图来计算数据流上复杂聚集查询的近似解。文献【5 4 】提出了一种计 算滑动窗口聚集的方法，将滑动窗口分成若干个小的基本窗口，缚个基 本窗口拥有一个时间戳。系统计算并保存每个基本窗口的概要信息，当 一个基本窗口过期时，它的概要信息随之被删除，同时，系统计算并保 存新的基本窗口的概要信息。基于基本窗口的概要信息，系统可以增量 式的计算滑动窗口上的聚集。 在数据流的诸多应用中，还经常需要对数据流滑动窗口的连接结果 进行聚集查询，我们称这类查询为滑动窗口连接聚集查询。例如： 1 互联网性能监测的应用中，主干网中流动的i p 数据包构成了数 据流爿，与主干网相连的一个分支网中的i p 数据包构成数据流b ， 第1 章引言 一i _ 网络管理人员需要监测在过去的一个小时中，主干网上的l p 数据包 中来自于该分支网的包的个数，则可使用下面的查询： s e l e c t c o u n t ( * ) f r o ma 6 0m i n u t e ，b 6 0m i n u t e w l 妣a s r c = b s r ca n da d e s t = b d e s t ； 2 在一个智能大厦中，监测温度的传感器产生数据流r ，监测烟浓 度的传感器产生数据流足数据流包括属性( 1 0 c a t i o n ，t i m e ， t e m p e r a t u r e ) 。s 数据流包括属性( 1 0 c a t i o n ，t i m e ，s t r e n g t h ) ，数据 流r 、s 不断的向监控中心发送监测数据。如果在过去的1 0 分钟 内，某个房间的温度达到了4 0 度以上并且烟的浓度大于0 6 的情 况连续出现5 次，则需要启动自动救火装置。我们可以使用下面 的查询来找到这样的房间： s e l e c t l o c a t i o n ，c o u n t ( ) f r o mr 0 0m i n u t e ，研10m i n u t e 】 w h e r er 1 0 c a t i o n = & l o c a t i o na n dr t e m p e r a t u r e 4 0a n d s s t r e n g t h o 6 g r o u pb yl o c a t i o n h a v i n gc o u n t ( + ) 5 ； 相对于滑动窗口的连接查询、聚集查询，滑动窗i ：1 的连接聚集查询 使用的更为频繁。目f i i 瞎l 对滑动窗口的连接聚集查啪的操作算法足建立 一个如图3 所示的查询操作树，以流水线连接算法来计算滑动窗口连接， 并将连接结果保存在内存的一个队列中，然后通过扫描保存连接结果的 队列来计算聚集值。设数据流矗新到来一个元组 则计算滑动窗口连接 聚集的步骤如下： 1 将，插入到足的滑动窗口中，删除只、s 两个滑动窗口中的过期 元组 2 用，扫描s 的滑动窗口，将连接的结果插入到连接结果队列中 熏龙江大学硕士掌位论文 3 删除连接结果队列中的过期数据 4 遍历连接结果队列，计算聚集值 这种处理方式需要在内存中保存滑动窗口的连接结果，设数据流胄、s 的滑动窗口中各有1 0 0 0 个元组，连接的选择性为o 1 ，则需要保存l o ， 0 0 0 0 条连接结果，占用了大量的内存资源。而在数据流的查询处理中， 内存是最宝贵的计算资源【1 3 l 。这种方式显然不适用于处理数据流上的查 询。 t 口妇e c a t e 图3 滑动窗口连接聚集的查询操作树 1 3 本文的贡献 本文主要研究的是数据流的查询操作算法。在数据流的查询操作中 由于数据流中的数据是源源不断、时间有序、瞬时变化的。以及系统存 储空间的限制，因此传统的数据库技术不再适用于数据流中数据的管理。 目早日甲 第1 罩引言 一il l - 这种情况下，我们必须采用近似的查询操作算法。 滑动窗口是对数据流进行查询操作、求得近似结果的一种常用的数 据采样技术。数据流上的滑动窗口是指在数据流上设定一个区间，该区 间只包含数据流中最近到来的那部分数据。当新的数据到来时。滑动窗 口向前滑动。用最新的数据替换滑动窗口中最旧的数据。与随机采样等 其它采样技术相比，滑动窗口的近似语义清楚明了。更重要的是，在许 多应用中，用户最感兴趣的往往是数据流中最近到来的那部分数据。因 此滑动窗口是对数据流进行查询处理时使用的一种比较理想的采样技 术。 目前，基于滑动窗口的查询操作算法都是适用于立即执行的连续查 询，也就是说数据流上每个新数据到来时，均立即更新滑动窗口，触发 执行一次查询。但是在实际应用中，连续查询有时采取的是周期执行方 式，即数据流上每个新数据到来时，不立即更新滑动窗口，而是每隔固 定的时间间隔更新滑动窗口，触发执行一次查询。本文提出了适用于周 期执行的连续查询的滑动窗口查询操作算法，即滑动窗口是以基本窗口 为单位周期更新的复合滑动窗口查询操作算法。复合滑动窗口的大小都 足适合内存的。主要研究了三类算法： 1 复合滑动窗口的连接操作算法 2 复合滑动窗口的聚集操作算法 3 复合滑动窗口的连接聚集操作算法 复合滑动窗口是由若干个大小相等的基本窗口组成。当数据流上最 新的基本窗口被填满时，把它插入到复合滑动窗口中，删除复合滑动窗 口中最旧的基本窗口。我们研究的查询操作算法都是基于复合滑动窗口 结构的。 对于滑动窗口连接聚集查询操作的算法，现有的方法是建立一棵查 黑龙江大学硕士学位论文 询操作树，连接的结果保存在内存的一个队列中，然后通过扫描保存连 接结果的队列来计算聚集值。但是出于内存是数据流查询操作中最宝贵 的资源，这种方式显然不合适。因此，我们提出了一个滑动窗口连接聚 集操作，在处理连接的同时计算聚集值，不再保存滑动窗口的连接结果， 从而有效的节省了查询操作的内存开销。 针对每种复合滑动窗口的查询操作算法，我们给出了多个实现算法， 理论分析和试验结果表明这些算法具有很好的时间和空间复杂性。 1 4 论文结构 本文主要分为五个部分。 第1 章引言。介绍了本文的研究背景、国内外的研究现状、本文的 贡献，阐明了本文的研究意义和学术价值。 第2 章复合滑动窗口连接操作算法的研究。阐述了复合滑动窗口的 结构，适用于周期执行的连续查询的复合滑动窗口连接操作算法，以及 算法的性能分析和试验结果。 第3 章复合滑动窗口聚集操作算法的研究。详细叙述了适用于周期 执行的连续查询的复合滑动窗口聚集操作算法，以及算法的性能分析和 试验结果。 第4 章复合滑动窗口连接聚集操作算法的研究。叙述了适用于周期 执行的连续查询的复合滑动窗口连接聚集操作算法，以及算法的性能分 析和试验结果。 最后，给出了本文的结论，不足之处和未来的工作。 第2 章复合滑动窗口连接操作算法的研究 _ i _ 第2 章复合滑动窗口连接操作算法的研究 连接查询是数据流上一种重要的查询类型。本章给出了复合滑动窗 口连接操作算法使用的复合滑动窗1 3 结构。重点阐述了复合滑动窗口的 二路连接操作算法，最后给出了算法的代价分析，并通过试验结果表明 算法的性能。 2 1 复合滑动窗口的结构 数据流上的滑动窗口有两类定义方式：一类是基于顺序定义的滑动 窗口；一类是基于时间定义的滑动窗口。本文的工作是以基于时间定义 的滑动窗口为例来介绍的。不同执行方式的连续查询使用的滑动窗口的 滑动粒度不同。立b i l 执行的连续查询中的滑动窗口的滑动粒度为一个元 组，而周期执行的连续查询中的滑动窗口的滑动粒度为一个时间间隔， 即连续查询执行的周期。复合滑动窗口就是适用于周期执行的连续查询 的滑动窗口结构。下面给出一个如图4 所示的复合滑动窗口结构的严格 定义。 定义l ( 数据流) 一个数据流是一个按照时间递增顺序排列的无穷 时间序列s = s l ，曲，曲， ，毋是时刻f 出现的序列元素。 我们用研f ，：脚表示s 的从时刻r j 到时刻幻的子序列。显然。数据 流s 在任意时刻t 之前的所有元素的子序列是一个有穷时间序列。数据 流上的滑动窗口具有两种定义。由于本文仅关心基于时间的滑动窗口， 下边我们仅给出基于时间的滑动窗口定义。 定义2 ( 滑动窗口) 设r 是一个时间长度，t t 是一个变化的时刻。 我们称研f r ：f 1 为s 的一个时间问隔为丁的滑动窗口，其中t 和r 的单 黑龙江大学硕士学位论文 位相同，并且t 为相对于s 的起始观测时刻的时间距离。 显然，s i f 一扎妇是随着t 的变化而滑动，故称其为滑动窗口。 定义3 ( 基本窗口) 设曰r 是一个时间长度。t ，。t ? 是一个变化的时 刻，令t l - - t ：= b t 。我们称s t l ：t 2 为s 的一个时问间隔为b t 的基本窗口， 其中t ，1 2 ，b t 的单位相同，并且t ，t 2 为相对于s 的起始观测时刻的时 间距离。 定义4 ( 复合滑动窗口) 设龇f 一田jf 为数据流s 在t 时刻的滑 动窗口，b t 是一个基本窗口的时问白j 隔，令s 弘脑l 如果剐，一s nf 仅在每个b t 时间间隔的结束时刻发生改变，并且在第k 个b t 时间问隔 的结束时刻改变为s i t + 柚r s r ：，+ 船刀，则称甜f s r ：t 为复合滑 动窗口，记作曲r e t - - s t ：， 。其中t ，s t ，b t 的单位相同。 其中口7 有两层含义。一是表示周期执行的连续查询的时问周期。二 是指明了算法产生当前复合滑动窗口查询结果的执行时间上界。用户可 以根据应用的具体要求选取口7 1 的值，一般来说，其值应该远小于复合滑 动窗口的大小。 复舍滑动窗口 皿皿皿皿 l _ j l jl _ j 最旧的基本窗口 基本窗口 最新的基本窗口 图4 复合滑动窗口结构 2 2 复合滑动窗口的连接操作算法 已有的数据流上的基于滑动窗口的连接操作算法都是针对立即执行 的连续查询提出的。这些算法均是当数据流新到一个元组立即计算一次 第2 章复合滑动窗口连接操作算法的研究 i i ii i i i i ii i i i _ 连接结果。不适用于周期执行的连续查询。本节提出的复合滑动窗口连 接操作算法c s w s n l j ( s y m m e t r i cn e s tl o o pj o i nw i t hc o m p o u n ds l i d i n g w i n d o w l 算法和c s w s n h j ( s y m m e t r i cn e s th a s hj o i nw i t hc o m p o u n d s l i d i n gw i n d o w ) 算法是针对周期执行的连续查询提出的。理论分析和试 验结果证明c s w s n h j 算法具有更好的性能。为了方便叙述，我们先引 入一些符号，如表2 所示： 表2术语定义 符号含义 死。数据流r 的复合滑动窗口大小 瓦。数据流s 的复合滑动窗口大小 乃。 数据流r ，s 的基本窗口大小 ， j数据流r 到达的速度，数据流s 到达的速度 口“出f 但)数据流r 的复合滑动窗口中的h a s h 桶数 b u c k e t ( s )数据流s 的复合滑动窗口中的h a s h 桶数 g h a s h 算法中存取一个元组的代价 c 。n e s tl o o p 算法中存取一个元组的代价 复合滑动窗e l 连接操作的算法是一种流水线( p i p e l i n e ) 连接算法。算 法的基本思想如图5 所示。连接操作分为三个阶段： 1 插入：将参加连接操作的数据流胄和s 中到来的元组插入到对应 的最新的基本窗口中。当最新的基本窗口被填满时，将最 新的基本窗口插入到复合滑动窗口中。 2 删除：删除复合滑动窗口中最旧的基本窗口。 3 探测：用胄的最新的基本窗口中的元组依次与s 的复合滑动窗口 中的元组进行连接，用s 的最新盼基本窗口中的元组依次 1 7 黑龙江大学硕士学位论文 与r 的复合滑动密口中的元组进行连接，输出连接结果。 输出 基本窗口 口 数据滚rs 数据淀 图5 复合滑动窗口连接操作模型 本窗口 复合滑动窗口的数据结构。在c s w s n l j ( s y m m e t r i cn e s tl o o p j o i nw i t hc o m p o u n ds l i d i n gw i n d o w ) 算法中复备滑动窗口的数据 结构为链队列。队列分为7 0 7 h 块儿。每一块儿是一个基本窗口结构。 不同基本窗口之闻仍用链表连接起来。如图6 所示。由于基本窗口是按 照时间顺序到来，所以复合滑动窗口是按时间有序 第2 章复合滑动窗口连接操作算法的研究 基本窗口基本窗口基本窗口基南亩1 2 ：i 图6c s w s n l j 算法的复合滑动窗口结构 基本窗口的数据结构。由于数据流的流速是不断变化的，基本窗口 占用内存的大小也是不断变化的。因此c s w s n l j 算法采用动态分配内 存的方式管理基本窗口，基本窑口的数据结构为链表。其数据结构与图 6 中的基本窗口的结构一致。当有新的元组到来时，申请一个新结点， 并将其插入到链表的尾部。基本窗口结构中存放一个头结点，头结点中 存放着本