（计算机应用技术专业论文）数据流联机分析处理技术的研究.pdf

中文摘要 中文摘要 近些年，数据流逐渐成为越来越重要的数据类型。数据流终的数据 不同于传统的数据库中的数据，因此数据流中的数据处理和管理方面的 技术需要重新被考虑；这开拓了一个崭新的研究方向。另外，随着多年 的o l a p 技术的研究和发展，o l a p 已经起到越发重要的作用。现有的 o l a p 技术只是基于有限的、静态的、持久稳同的、历史的数据：而数 据流联机分析处理是基于无限的、连续的、快速变化的流数据。那么数 据流联机分析处理技术的研究将是一项具有挑战性的任务。 本文主要研究了数据流联机分析处理技术。首先，本文研究了数据 流的滑动窗口大小控制方法和窗口更新技术。它们很好地适应了数据流 的多样流速情况。本文提出了一种基于静态滑动窗l _ _ i 的数据流聚集技术。 它能够有效地实现细节性数据流上的近似查询。第二，本文研究了时间 序列数据流的回归分析技术。该项研究包括以f j l 方面：( 1 ) 时问序列 数据流的一元线性回归模型的创建技术和回归模型的应用：( 2 ) 多个线 性回归方程的聚集技术。本文的实验分析展示该技术能够有效地产“：时 可序列数据流的回归模型，快速地完成数据流的叫归分析。第二t ，本文 提出了多粒度时间维的设计思想，定义了两个关键子模型，并阐述r 基 于先验路径的钻取技术。基于上述三项研究，本文研究了一种数据流上 部分物化多维数据模型的设计与实现。性能分析表明该设汁能够有效地 利用了有限的存储资源。最后，基于以上算法，本文提出了一个数据流 联机分析处理原型系统的总体设计，并给出了实验结果。 关键词：数据流联机分析处理滑动窗口线性回归多维数据模型 外文摘要 a b s t r a c t i nr e c e n ty e a r s ，d a t as t r e a m sa r eb e c o m i n ga ni n c r e a s i n g l yi m p o r t a n t c l a s so fd a t a t y p e s t r e a mo fd a t ai t e m sd i f f e rf r o mr e c o r d ss t o r e di n t r a d i t i o n a ld b m si n m a n yw a y s ，t h e r e f o r e ，s e v e r a la s p e c t s o fd a t a p r o c e s s i n ga n dm a n a g e m e n t sn e e d t ob er e c o n s i d e r e di nt h ep r e s e n c eo fd a t a s t r e a m s ，o f f e r i n gan e w r e s e a r c hd i r e c t i o n m o r e o v e gw i t hy e a r so fr e s e a r c h a n d d e v e l o p m e n t o fo l a pt e c h n o l o g y ，o l a p p l a y s am o r ea n dm o r e i m p o r t a n tr o l e t h ee x i s t i n gt e c h n o l o g yo fo l a pi sm e r e l yb a s e d o nt h e f i n i t e ，s t a t i c ，p e r s i s t e n t ，h i s t o r i c a l d a t a h o w e v e r ，o n l i n e a n a l y t i c a l p r o c e s s i n g o nd a t as t r e a m si sb a s e do nt h e i n f i n i t e ，c o n t i n u o u s ，r a p i d c h a n g i n gs t r e a mi t e m s t h e nt h es t u d yo f t h et e c h n o l o g yo fo n l i n ea n a l y t i c a l p r o c e s s i n gb a s e d o nd a t as t r e a m si sa c h a l l e n g i n g t a s k t h i s p a p e rm a i n l y s t u d i e st h e t e c h n o l o g i e s o fo n l i n e a n a l y t i c a l p r o c e s s i n g o fd a t a s t r e a m s ，f i r s t ，t h i sp a p e ri n v e s t i g a t e s t h e c o n t r o l l i n g m e h o do ft h es i z ea n du p d a t i n gt e c h n o l o g yo ft h es l i d i n gw i n d o w so v e rd a t a s t r e a m s t h e ya d a p tw e l lt ot h es i t u a t i o nt h a td a t as t r e a m st ob ep r o c e s s e d a r r i v ea tt h em u l t i p l er a t et h i sp a p e rp u t sf o r w a r dan o v e lt e c h n i q u et o a g g r e g a t e ad a t as t r e a m so v e r s l i d i n g w i n d o w s t h e t e c h n i q u e c o u l d e f f e c t i v e l yi m p l e m e n ta p p r o x i m a t eq u e r yo fd e t a i ld a t as t r e a m s s e c o n d ，t h i s p a p e ri n v e s t i g a t e sm e t h o d sf o rr e g r e s s i o na n a l y s i so f t i m e s e r i e sd a t as t r e a m s t h i sr e s e a r c h i n c l u d e ss e v e r a l f o l l o w i n ga s p e c t s ：( 1 ) at e c h n o l o g y o f b u i l d i n g l i n e a r r e g r e s s i o n m o d e lo ft i m e s e r i e sd a t as t r e a m sa n dt h e a p p l i c a t i o n so f t h el i n e a rr e g r e s s i o nm o d e l ( 2 ) a t e c h n o l o g yf o ra g g r e g a t i n g t h e m u l t i p l e l i n e a r r e g r e s s i o ne q u a t i o n o ft i m e - s e r i e sd a t as t r e a m s ，o u r e x p e r i m e n t ss h o wt h em e t h o d sc a ne f f e c t i v e l yc o m ei n t ob e i n gr e g r e s s i o n m o d e lo ft i m e s e r i e sd a t as t r e a m s ，a n dr a p i d l yf u l f i l lt h er e g r e s s i o na n a l y s i s i i 外文摘要 o fs u c hd a t a t h i r d ，t h i sp a p e rp r o p o s e st h et i m ed i m e n s i o nw i t hm u l t i p l e l e v e l so f g r a n u l a r i t y t h i sp a p e r d e f i n e sac r i t i c a ls u b m o d e l ，a n ds e t sf o r t ha r t a p r i o r i t y b a s e dd r i l l i n ga p p r o a c h b a s e do nt h er e s u l t s ，t h i sp a p e rp r e s e n t sa p a r t i a l l ym a t e r i a l i z e dm u l t i d i m e n s i o n a ld a t am o d e lo f d a t as t r e a n l s ，w h i c hi s b a s e do nt h ec r i t i c a ls u b m o d e l si t s p e r f o r m a n c es h o w s t h em o d e lc a n e f f e c t i v e l ym a k eu s eo fc o s t l ys t o r a g er e s o u r c e i nt h ee n d ，b a s e do nt h e a b o v e a l g o r i t h m s ，t h ep a p e rp r o p o s e s a g e n e r a ld e s i g n o fa n o n l i n e a n a l y t i c a lp r o c e s s i n gb a s e do n d a t as t r e a m s ，a n dg i v e se x p e r i m e n tr e s u l t s k e y w o r d s ：d a t as t r e a m s ，o n _ l i n ea n a l y t i c a lp r o c e s s i n g ，s l i d i n gw i n d o w s l i n e a rr e g r e s s i o n ，m u l t i d i m e n s i o nd a t am o d e l - l i i 第1 章引言 1 1 研究背景 第1 章引言 随着人类文明向信息时代的迈进，我们生活在一个充满数据的世界 中。世界各地的不同组织拥有着大量的数据库系统。数据库系统跟踪r 个组织运作的整个过程；系统存储着和这些组织的商业运作有关的各 种信息和数据。随着新的“互联网经济”不断地增长，它需要满足各种 组织的更深入需求：数据库系统作为一个强大的信息资源，它使得组织 既能够提高处理用户事务的效率，又能够明确市场发展趋势并抓住市场 机遇。，如果个组织对于自己现状的优劣一无所知的话它在面向瞬息 力变的市场时候就会束手无策。如何从数据源中及时快捷地提取出对公 司决策分析有用的信息，是公司决策管理人员所面对的一个难题。对于 许多组织而- k ，每天都会产生大量的商业数据；完全通过单纯的手工来 解决问题是非常繁重的、重复的和近乎不可能完成的工作! 即使组织拥 有令人难以置信的计算能力，获得有效的管理报告仍然需要花费几个星 期甚至是几个月的时间! 所以，如何从源自于多个地点的多个数据源的 大量数据中抽取那些能够有效地改善资金运作、提高自身效益和利润的 有价值信息，这是数据库分析任务中最具挑战意义的一项工作。 在数据库领域中，o l t p 已经不能满足终端用户对数据库查询分析的 需要，s q l 对数据库进行的简单查询也不能满足用户分析的需求。从而， 多维数据库和多维分析的概念( 即o l a p 一0 n _ l i n ea n a l y t i c a l p r o c e s s i n g ，也称为联机分析处理) 就应运而生。o l a p 能够利用存储在 数据库或数据仓库中的数据完成各种分析操作，并以直观易懂的形式将 分析结果返回给决策分析人员。多年来，o l a p 理论方面的研究有了很 黑龙江大学硕士学位论文 大的进步，出现了很多研究成果：同时，这些成果被成功地应用在实际 应用领域中。在数据分析和决策支持中，o l a p 起着同趋重要的作用! 另外，在实际应用中，许多实时监视系统和其他动态环境经常产生 一种巨大数量的数据，我们称之为数据流( d a t as 仃e a m ) 。数据流是一种新 的数据类型；在该类型中，数据不再是那种传统的永久性的关系形式， 而是大量的、连续的、快速的、随着时间变化的流数据形式。数据流出 现在许多实际应用领域中，比如：股市交易，网络检测，电话通信，动 态监控以及传感器网络等等。基于数据流的特点，数据流系统中的数据 处理工作和传统的关系数据库系统有着很大的差异；数据流不能够在磁 甜上实现存储，而且数据流中的数据一旦流过就不能再次访问，数据流 处理过程也只能做一趟扫描数据。伴随着网络技术的飞速发展，数据流 处理逐渐成为当前计算机研究领域中一个新的热点研究。目前，数据流 的研究领域出现了一些数据流原型系统；数据流操作方面也进行了许多 研究工作；然而，数据流联机分析处理的研究工作做的较少。有效的数 据流联机分析处理能够实现向用户提供那些对决策者有着重要价值的 “隐藏性”信息。考虑到联机分析处理越来越重要的作用以及数据流在 实际应用中逐渐广泛的出现及其潜在的研究价值，数据流联机分析处理 的研究是非常必要的。这项研究工作必将会引起更多的重视! 无论是在学术研究领域上，还是在实际应用领域中，这项研究都有 着十分重要的研究意义和巨大的研究价值，有着广阔的研究和应用前景1 1 2 国内外的研究现状 随着网络技术的飞速发展，数据流处理逐渐成为当前数据库领域新 的研究热点 2 3 1 。数据流是一种新型的数据类型。数据流中的数据是无限 的、流动的、快速的流数据形式。它大量地出现在动态应用领域中。对 第1 章引言 于这些领域来说，数据流的研究有着相当重要的意义，如数据流的查询、 分析和挖掘等等：这些研究必将会带来巨大的应用价值。 国际上，最近几年国外研究组织发表了大量的数据流研究方面的论 文。目前，从事这项研究的较有代表性的研究组织有斯坦福大学、加州 大学的伯克利分校以及布朗大学等。最近出现了一些数据流的原型系统， 例如，斯坦福大学的s t r e a m 系统1 2 9 , 5 3 、加州大学的伯克利分校的 t e l e g r a p h c q 系统】和布朗大学的a u r o r a 原型系统【2 7 h 等。s t r e a m 原型系 统是一个数据流管理系统( d s m s d a t as t r e a mm a n a g e rs y s t e m ) ，它着 重处理在内存有限的条件下计算查洵的近似结果情况。t e l e g r a p h c q 是一 个自适应的数据流系统，它用自适应的查询执行引擎来处理各种情况卜 的数据流。a u r o r a 系统是一个数据流的监视系统，它允许用户定义多个 触发器形成触发器网，并且在运行时会对触发器网进行优化。由于数据 流中的所有数据不可能存储在传统的关系数据库中：而且，数据流系统 中的数据处理技术和传统关系数据库的有着差异；现有的许多成熟数据 处理技术不再适用于数据流处理。为了能够有效地实现数据流处理过程， 我们必须研究出适用于数据流处理的方法和技术。最近，许多数据流处 理的研究工作耿得了成果，比如：数据流的查询处理方面出现了随机抽 样( s a m p l i n g y 3 7 1 14 5 1 ，数据写生( s k e t c h i n g ) m ，直方图( h i s t o g r a m ) 附2 ”， 小波( w a v e l e t ) 变换帅“1 滑动窗口( s l i d i n gw i n d o w s ) 5 4 - 5 6 等近似技术。 但是，现有的研究工作有许多局限性，大部分算法和机制存在着过多的 假设性和较大的局限性。要待数据流处理技术的成熟和成型数据流系统 创建技术的完善，还有相当长的研究道路要走。 在国内，这方面研究工作还处于起步阶段。近几年，哈尔滨工业大 学、北京大学等单位对数据流的关键技术进行了一些创建性研究工作。 然而，国内的有关数据流研究工作现在做的还是很少的，这方面的研究 黑龙江大学硕士学位论文 论文也很少。随着数据流应用领域的迅速扩大，必将会有越来越多的研 究人员开始进行数据流处理技术的研究。 1 3 本文的贡献 本文研究的内容是数据流联机分析处理技术。由于联机分析处理技 术的主要目标是及时地、快捷地响应用户所提出的多维分析处理要求， 并以一种直观易懂的形式将查询结果提供给用户；所以联机分析处理技 术的基本问题是综合性数据的形成和获取，多维数据模型的建立和显示， 查询响应的及时性等等。经过多年的相关研究和发展，出现了许多成熟 的联机分析处理技术。现有的o l a p 技术是基于有限的、静态的、持久 稳固的、历史的数据。数据流有着流动性、快速变化性和无限性等特点； 基于这些特点，数据流联机分析处理技术区别于现有的联机分析处理处 理技术。数据流有着流动性、快速变化性和无限性等特点：因此，对于 数据流联机分析处理来晓，许多联机分析处理技术需要重新被考虑。数 据流联机分析处理技术的研究是一项具有挑战性的任务。 本文将进行以下几方面的研究：( 1 ) 数据流的聚集算法研究；( 2 ) 数据流的回归分析研究与实现：( 3 ) 数据流联机分析处理的多维数据模 型研究与实现；( 4 ) 数据流联机分析处理的原型系统设计。 本文的主要贡献如下： 第一，本文研究了数据流聚集技术。首先，本文研究了基于数据流 的滑动窗口技术。由于数据流的流速是随机变化的，而现有的滑动窗1 5 技术大多建立在一定的假设条件之下的，比如：数据流的流速是匀速， 滑动窗口的大小固定：以及己有的滑动窗口技术很少涉及到的窗口更新 周期问题等。为了使得滑动窗口技术能够更好地适应于数据流的流速随 机变化的情况，本文研究了关于数据流的滑动窗1 2 1 大小控制方法和窗口 第1 章引言 更新技术。本文提出了一种基于静态滑动窗口的树型数据流聚集技术。 它能够有效地实现细节性数据流的近似查询。 第二，本文研究了数掘流的回归分析技术。本文研究了时间序列数 据流一元线性回归模型的创建技术与应用问题。通过本文所提出的理论 和算法获得时间序列数据流一元线性回归模型；根据已有的模型，实现 因变量和自变量之间的预测和控制。本文还研究了数据流多个一元线性 回归方程的聚集技术。该技术能够有效地产生时间序列数据流的匣f 归模 型，快速地完成数据流的回归分析。 第三，本文研究了基于数据流的多维数据模型的创建技术。由于数 据流的特点，以往的多维数据模型创建技术不再适用于数据流：本文提 出r 数据流上的部分物化多维数据模型创建技术。该技术大大降低了数 掘存储代价，减少了多维分析的响应时间。 最后，在综合了以上研究成果，本文设训+ 了一个数据流联机分析处 理原型系统，并给出了实验结果。其中，针对现有的多维数据浏览界面 不足之处，本文提出了一种新的多维表设计技术，并将其应用到本文的 数据流联机分析处理原型系统的实现过程中。 1 4 论文结构 本文主要分为七个部分。 第一章引言。本章介绍了本文的研究背景、国内外的研究现状、本 文的贡献，阐明本文的研究意义和学术价值。 第二章预备知识。本章主要包括两方面的内容：( 1 ) 联机分析处理 技术。本文重点介绍了联机分析处理的定义、特点、和联机事务处理的 比较及其实现技术。( 2 ) 数据流处理技术。本文简要地介绍了数据流中 的数据和传统数据库中的数据比较、数据流中数据模型的定义方式以及 数据查询、数据流聚集算法的实现以及现有的数据流管理系统。 黑龙江大学硕士学位论文 第三章数据流聚集算法的研究。本章研究了三方面的内容：( 1 ) 滑 动窗口技术的主要思想和研究现状：( 2 ) 数据流上自适应式滑动窗口技 术；( 3 ) 基于静态滑动窗口的树型数据流聚集算法。 第四章数据流一元线性回归分析的研究与实现。本章简述了回归分 析的理论基础，阐述了时间序列数据流的一元线性回归分析模型的创建 与实现，研究了回归模型的应用问题。本章研究了时间序列数据流的多 个“元回归分析方程的聚集技术。 第五章数据流联机分析处理的多维数据模型的研究。本章介绍了多 粒度时间维的设计思想，定义了关键子模型，提出了基于先验路径的钻 取技术。依据以上研究结果，本章研究并实现了数据流上的部分物化多 维数据模型创建技术。 第六章数据流联机分析处理的原型系统设计与实现。本章描述了一 种新的多维数据集的浏览界面设计技术，简述了一个基于数据流联机分 析处理的原型系统和各部分的功能，设计了基于数据流的联机分析处理 前台整体界面，并给出了数据流联机分析处理原型系统的实验结果。 最后，给出了本文的结论，不足之处和未来的工作。， 第2 章预备知识 第2 章预备知识 2 1 联机分析处理技术 山于企业( 公司) 经营规模的扩大，产生的数据量变得非常巨大： 另外，用户的查询要求也变得越来越复杂，查询处理过程对象从张关 系表或表中的一条或几条记录的数据扩展到多张表或千万条记录的数 据，并且需要数据的分析和信息的综合。传统的数据库系统是针对操作 型应用设计的；在性能上，它难以适应分析型应用的要求。传统的关系 数据库系统已不能够扮演完全地满足这样的需求。近年来，新的。门软 件技术应运而生，我们称之为联机分析处理( o l a p o nl i n e a n a l y t i c a l p r o c e s s i n g ) 。本节将简要地阐述联机分析处理的基本知识，其中包括 o l a p 的定义及其特点，o l a p 与o l t p 的比较和o l a p 的实现技术等。 2 1 1o l a p 的定义及其特点 联机分析处理( o l a p ) 的概念最早是由关系数据库之父e f c o d d 于 1 9 9 3 年提出的；它专门设计用于支持复杂的分析操作，侧重对决策人员 和高层管理人员的决策支持，可以应分析人员要求快速、灵活地进行大 数掘量的复杂查询处理，并且以一种直观易懂的形式将查询结果提供给 决策人员，以便他们准确掌握企业( 公司) 的经营状况，了解市场需求， 制定f 确方案，增加效益。联机分析处理是针对特定问题的联机数据访 问和分析；它通过对信息的很多种可能的观察形求进行快速、稳定一致 和交互性的存取，允许管理决筑人员对数据进行深入观察。 9 0 年代初期，e f c o d d 给出了o l a p 产品评价的十二条基本准则】。 黑龙江大学硕士学位论文 根据o i 。a p 的概念以及用户对o l a p 产品的十二条评价准则，o l a p 特 点大致有以下几方面内容： ( 1 ) 快速性。快速性是指o l a p 的快速反应能力。用户对o l a p 的这种能力有着很高的要求。对于大量的数据分析要达到这个速度并不 容易，需要一些技术上的支持，如专门的数据存储格式、大量的事先运 算、特别的硬件设计等。 ( 2 ) 可分析性。可分析性是指o l a p 系统应能处理与应用有关的任 何逻辑分析和统计分析。尽管系统需要事先编程；但是，这并不意味着 系统定义了所有应用。用户无需编程即可定义新的专门计算，将其作为 分析的一部分，并以用户满意的方式给出报告。 ( 3 ) 多维性。多维性是指系统提供对数据的多维视图和多维分析， 包括对层次维和多重层次维的完全支持。多维性是o l a p 的关键属性。 其中，多维分析是o l a p 的灵魂。多维分析是指对以多维形式组织起来的 数据采取各种分析动作，以求剖析数据，使最终用户能从多角度、多侧 面来观察数据，从而深入地了解包含在数据中的信息及其内涵。多维分 析的基本动作有：切片、切块、上钻、下钻和旋转等：这些分析动作使 得o l a p 系统可以提供给用户强大的统计、分析及报表处理功能。 ( 4 ) 信息性。信息性是指不论数据量有多大或者数据存储在何处， o l a p 系统应能及时获得信息，管理大量信息。这里有许多因素需要考 虑，如：数据的可复制性、可利用的磁盘空问，o l a p 产品的性能等。 2 1 2o l t p 与o l a p 的比较 联机事务处理o l t p ( o n _ l i n et r a n s a c t i o n p r o c e s s i n g ) 、联机分析处 理o l a p ( o n l i n ea n a l y t i c a lp r o c e s s i n g ) 是两类数据处理方式。o l t p 是传统的关系型数据库的主要应用，它主要是基本的、日常的事务处理。 第2 章预备知识 0 l a p 是数据仓库系统的主要应用，它支持复杂的分析操作，侧重决策 支持，并且提供直观易懂的查询结果。表2 1 列举了o l t p 与o l a p 之 间的比较。 o l t p 数据0 l a p 数据 原始数据导出数据 细节性数据综合性或提炼性数据 当前值数据历史数据 可更新不可更新，但周期性刷新 次处理的数据量小一次处理的数据量大 面向应用，事务驱动面向分析，分析驱动 面向操作人员，支持同常操作面向决策人员，支持管理需要 表2 1o l t p 与o l a p 的比较表 2 1 3o l a p 的实现技术 通常情况下，o l a p 的实现采用的是种三层客户n 务器结构【6 4 l 。 o l a p 实施的关键有两点：其一，如何组织来自多个不同数据源或数据 仓库中的数据，即o l a p 服务器的设计；其二，o l a p 服务器与前端软 件的沟通。多维数据分析是o l a p 服务器与前端软件的桥梁；也就是说， o l a p 服务器必须以多维方式进行构建。因此，o l a p 服务器的设计重 点在于：如何组织数据仓库中的综合性数据以及如何满足前端用户的多 维数据分析需要。 根据o l a p 服务器端的不同数据组织形式，将o l a p 的实现技术分 为三种形式：基于多维数据库的o l a p ( m o l a p ) ，基于关系数据库的 ( ) l a p ( r o l a p ) 和混合的0 l a p ( h o l a p ) 。它们的技术特点如下： 黑龙江大学硕士学位论文 1 、基于多维数据库的o l a p ( m o l a p ) m o l a p 是利用一个专用的多维数据库来存储o l a p 所需的数据， 数据以多维方式存储，并以多维视图方式来显示。m o l a p 对分散在各 个o l t p 数据库中的数据进行提取、净化和转换等过程之后提交给多 维数据库。这些数据在被存入到多维数据库时，将根据它们所属于的 维进行一系列的预处理操作，并把结果按照一定的层次结构存入多维 数据库中。用户通过客户端的应用软件的界面递交分析要求给o l a p 服务器，再由0 l a p 服务器检索多维数据库来获取分析结果；并通过 可视化友好界面返回给用户。 m o l a p 结构的主要优点在于它能够迅速地响应决策分析人员的 分析要求并快速地将分析结果返回给用户，这得益于它的独特多维数 据库结构以及存储在其中的预处理程度很高的数据。然而，在m o l a p 结构中，o l a p 服务器主要是通过读取预处理过的数据来完成分析操 作，这些预处理操作是预先定义的，这将影响m o l a p 结构的灵活性。 2 、基于关系数据库o l a p ( r o l a p ) r o l a p 是以关系型数据库为底层数据库。它的功能类似于m o l a p ， 用户通过客户端工具提交多维分析请求给o l a p 服务器，服务器将请求 动态地转换成s q l 语句执行，分析结果被转化成多维视图返回给用户。 关系型结构能较好地适应多维数据的表示和存储。关系数据库将多维数 据库中的多维结构划分为两类表，一类是事实表，另一类是维表。该结 构有时被称之为“星型模式”。对于维内层次复杂的维，用一张维表来描 述会带来过多的冗余数据。为了避免冗余数据占用空间过大，可以用多 张表来描述一个复杂维。比如，产品维可以进一步划分为类型表、颜色 表、商标表等。这种星型模型被称之为“雪片模式”。r o l a p 的维表和 事实表都是用二维关系表的方式存放的；事实的提取需要通过将维表和 第2 章预备知识 事实表的连接操作来完成。注意到，因为对每个维都需要进行一次连接 操作，所以系统的性能就成了基于关系数据库的o l a p 实现的最大的 个问题；当维数增加和事实表增大时，必须采用有效的查询优化技术( 特 别是表连接策略) ，利用各种索引技术来提高系统的性能。 r o l a p 的主要特点在于灵活性强，用户可以动态定义统计或计算方 式；但是，它对用户的分析请求处理时间要长于m o l a p 。r o l a p 和 m o i 。a p 相比较，一方面，m o l a p 实现的性能要超过r o l a p 技术。另 方面，m o l a p 在可伸缩性方面存在着问题；而r o l a p 实现的可伸缩 性更强。对于客户来说，r o l a p 往往更具有吸引力，这是因为r o l a p 可以充分利用现有的关系型数据库技术。 3 、混合型o l a p ( h o l a p ) 迄今为止，h o l a p 还没有一个f 式的定义。h o l a p 是将m o l a p 和r o l a p 两种结构的优点有机地结合起来，满足复杂的分析请求。 实现h o l a p 的方法一般有以下几种： 同时提供多维数据库和关系型数据库，让开发人员来选择。 在运行时，把对关系型数据库的查询结果存入多维数据库。 h o l a p 系统按照定的先后顺序使用多维数据库和关系型数据库。 h o l a p 系统利用个静态结构的多维模型暂存运行时检索出来的数据。 利用一个多维数据库存储高级别的综合数据：同时，用关系型数据库存 储细节性数据。这种方法是实现h o l a p 结构较为理想的方法，它结合 了m o l a p 和r o l a p 的优点。 2 2 数据流处理技术 近些年，一种新的数据类型已经越来越被人们所广泛的认知；它经 常出现在许多应用领域中。这些应用领域包括金融界应用、网络安全性 黑龙江大学硕士学位论文 监控、电话通信数据管理、w e b 应用领域、传感器网络、股票交易等等， 以及其他动态环境，如电力供给公司、天气预报等。我们把这种数据类 型称为数据流( d a t as t r e a m ) 。数据流中的每个数据项可以是关系型元 组形式，例如传感器网络中流动的监测信号、电信公司的通话记录、w e b 服务器上的用户登录记录、互联网中流过的i p 数据包、股票交易信息等。 但是数据流具有崭新的特征：连续性、随时间变化性、无限性、快速性 等。这些特点引起了许多崭新的数据研究方向。随着网络技术与信息产 业的飞速发展，在许多领域中数据流得到了广泛地应用。目前，数据流 模型已经引起了数据库领域的广泛关注，许多数掘库研究人员丌始从事 数据流相关技术的研究。数据流研究领域出现了很多的研究成果。本节 将概括性地介绍数据流的相关知识，主要包括：数据流中的数据与传统 数据库中数据的比较、数据流中数据模型的定义方式及数据查询、数据 流操作算法的实现、现有的数据流管理系统。 2 2 1 数据流中的数据与传统数据库中数据的比较 数据流可以被看成一个连续的、无穷的数据项组成的序列；它不同 于以往的存储在数据库中的数据形式。数据流中的数据与传统数据库中 数据的主要区别在于： l 、数据流中的数据具有瞬时性；而传统数据库中的数据具有持久稳 固性。 2 、数据流中的数据是无限的，数据无法完全地存储在有限的储存空 间中；而传统数据库中的数据是有限的，数据是存储在磁盘中的。 3 、数据流中数据的存取形式是顺序性存取，数据库中数据的存取 形式是随机访问。 4 、数据流中数据支持的典型查询是连续性查询，且查询多数只能得 第2 覃预备知识 到近似结果：而数据库中的数据支持的典型查询是一次性查询，且查询 可以获得精确的查询结果。 5 、数据流中的数据更新特点是多路性、大数据量性、快速性；数据 流的更新频率要远远高于数据库中数据更新的频率。而数据库中的数据 具有相对低的更新速率。 6 、数据流中的数据存储是主动性存储；而数据库中的数据存储是被 动性存储。 7 、数据流中的数据是按序到达的，数据流中的数据一一旦流过就不能 再次访问，对该类型的数据一次性访闯且只能进行顺序的访问：两传统 数据库中的数据可以被随机地以及多次地访问。 8 、数据流中的数据服务是实时性服务；而数据库中的数据往往不具 有实时服务能力。 2 2 2 数据流中数据模型的定义方式以及数据查询 ( 1 ) 数据流的数据模型 目前，数据流的数据模型主要有两种定义方式，它们分别是基于对 象的数据流模型和基于关系的数据流模型。其中，基于对象的数据流模 型是将数据源及其产生的数据项看作是具有层次关系的数据类型，数掘 源与数掘项之间通过一定的方法实现相互之间的联系。基于关系的数掘 流模型是将每个数据源产生的数据流看作是一个虚拟的关系；其中，数 据流中的每个数据项看作是一个元组。 ( 2 ) 数据流的数据查询 + 数据流的查询类型 数据流上的查询与传统数据库中的查询类型基本上相似；但是，它 们之间存在着一个明显的区别：数据库中的查询主要是一次性查询，而 黑龙江大学硕士学位论文 数据流上的查询更多的是连续性查询。一次性查询是指如果一个查询提 交后，系统根据当前数据集的快照返回查询结果。连续性查询是指如果 查询随着新数据的到达而不断地返回查询结果。除非用户明确的撤销该 查询，连续性查询一旦注册到系统内，它将会随着数铡流上新数据的到 来，查询不断地返回查询结果。 连续性查询的执行方式主要有两种：( a ) 基于队列的查询计划执行 策略。在已有的几种数据流管理系统中，a u r o r a 和s t r e a m 系统的查询 计划执行策略是基于队列的。( b ) 自适应的查询执行方式。在连续性查 询的执行期间，数据流的流速、操作符的选择性、系统的资源都会发生 变化，因此需要系统能够根据这些因素动态地调整操作执行策略，以便 获得更好的查询执行性能。b e r k e l e y 的c a c q 是一个自适应式的数据流 查询处理部件。相对于基于队列的连续查询执行方式，c a c q 能够更好 地适应环境的变化。但是基于元组的调度方式对其核心部件e d d y 的处 理能力有着很高的要求。 数据流上的查询形式 数据流上的查询形式可以分成以下两种形式：预定义查询和a d h o c 套询。预定义查询主要是针对数据流后续到达的数据来获取查询结果； 而a dh o c 查询是针对数据流中已经流过的数据进行查询，即对历史数据 进行查询。由于无法保存数据流中所有流过的数据，系统只能通过提取 和组织那些流过数据的概要性信息来支持a dh o e 查询，因此a dh o c 查 询一般只能得到近似的查询结果。 + 数据流的查询语言 数据流上的查询语言主要有两种类型：基于关系的数据流查询语言 和基于对象的数据流查询语言。其中 ( a ) 基于关系的数据流查询语言。目前，典型的基于关系的数据流 第2 覃预备知识 查询语言主要有两种：一种是斯坦福大学的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 l z 6 2 1 ，另一种是伯克利分校的 t e l e g r a p h c q 系统中使用的s t r e a q u e l 。其中，c q l 是在s q l 基础上扩展 而柬的，而且它的基本查询语义也与s q l 相同。c q l 提供了以下两种映 射方法，( 1 ) 将数据流映劓为关系的方法；( 2 ) 将关系映射为数据流的 方法。前者是通过在数据流上定义窗口来实现，后者可以由以下三种操 作柬实现：i s t r e a m 、d s t r e a m 和r s t r e a m 。在c q l 语法中，只支持对滑 动窗口的定义，目前还不支持其他窗口的定义。c q l 中的滑动窗口有如 下i 种定义方式：基于时间的滑动窗口、基于元组的滑动窗口以及按照 属性划分的滑动窗口。s t r e a q u e l 是t e l e g r a p h c q 系统的查询语言，它提 供了窗 1 定义的功能：它要求每个查询定义都包括f o r 循环结构；循环控 制变量t 为时削变量。该循环包括w i n d o w i s 语句指定窗口的类型和尺寸。 ( b ) 基于对象的数据流查询语言。将数据流转化为面向对象的流模 型的方法有以下两种。一个方法是根据类型等级分类数据流内容。这个 方法应用于t r i b e c a 网络监测系统，它用i n t e r n e t 协议层作为数据分类的 等级1 6 3 1 。另一个方法是将数据源用抽象的数据类型来表示，比如：管理 传感器数据的c o u g a r 系统1 4 7 j 。 2 2 3 数据流操作算法的实现 在这一节中，我们将介绍数掘流模型中的操作算法的实现，包括阻 塞操作和近似算法2 部分内容。 ( 1 ) 阻塞操作。所谓阻塞操作是指在关系型系统中，一个操作动作 需要访问关系的全部数据，才能够得到操作结果。阻塞操作包括排序以 及典型的聚集函数等许多操作。当数据流上的连续查询使用传统的查询 操作捌来执行的时候，如果操作树中含有一个阻塞操作，那么这个查询 黑龙江大掌硕士学位论文 将不会产生结果。因为该操作需要扫描数据流上的全部数据，而数据流 是无限的，阻塞操作将永远不会有结果输出。所以传统的期塞操作不再 适用于数据流的查询处理。通过阻塞操作来实现数据流查询处理的一个 通用方法是在数据流上定义窗口。将数据流限制在一个有限的范围内。 窗口查询是数据流上的一种重要的查询类型。另一种解决方法是在数据 流中插入一类特殊的数据项，用其标识在数据流后续的数据中，不能或 只能出现某些值的数据，这类数据项被称为标点( p u n c t u a t i o n ) 。 ( 2 ) 近似算法。由于系统存储空间的限制以及数据流的无限性特点， 许多数据流查询处理无法得到精确的查询结果。高质量的近似查询结果 是唯一的选择。目前，数据流查询处理的近似算法是一个非常热门的研 究领域，现今出现了许多研究成果。近似查询方法的几个主要研究有以 下几种：采样( s a m p l i n g ) 、直方图( h i s t o g r a m s ) 4 9 , 5 7 - 5 9 、数据写生 ( s k e t c h i n g ) 、小波变换( w a v e l e t r e p r e s e n t a t i o n ) 7 , 2 8 , 5 6 1 、滑动窗口( s l i d i n g w i n d o w s ) 3 2 , 3 7 , 3 a i 等。下面简要地介绍下它们的技术特点： ( a ) 采样技术是处理大数据集上的查询时常用的近似方法。在抽样 的样本上计算查询结果的时候，需要同时给出查询结果的误差度。带有 误差保证的抽样算法是数据流研究领域的一个热点方向。 ( b ) 数据写生和直方图技术是指系统统计并保存数据流的概要性信 息，利用这种信息来近似响应数据流上查询。一般来说，存储数据流概 括信息的空间大小与查询结果的准确性密切相关；在存储的概要性信息 越多的时候，查询结果的近似程度就会越高。这种近似查询技术的核心 研究问题是概要性信息的提取和组织。 ( c ) 小波变换技术是指利用小波变换的系数来保存数据的特征信 息；以此柬支持数据流上的聚集查询是一种有效的近似方法。 ( d ) 滑动窗口技术是指在数据流上设定的一个区间，该区问只包括 第2 章预备知识 数据流最近的部分数据。随着新数据源源不断地到来，窗口“向前”移 动，用“新”数据替换“旧”数据。滑动窗口有基于顺序( s e q u e n c e b a s e d w i n d o w ) 和基于时间( t i m e s t a m p b a s e dw i n d o w ) 两种定义方式。前一种滑 动窗口是指窗口内保存最近到来的k 个元组，它的大小是固定的。后一 种滑动窗r 丁是指窗r q 内存储的是最近t 时间内到达的元组，它的大小是 可变的。由于用户经常对最近到达的数据感兴趣，所以滑动窗l _ _ l 查询处 理算法足数据流研究领域的一个热点问题。目前的研究工作主要包括滑 动窗口聚集13 7 - 3 9 ，、滑动窗口连接q 以及多滑动窗口查询优化等方面。 2 2 4 现有的数据流管理系统 近年来，国内外的数据库研究人员针对于数据流开展了大量的研究 工作，并有了一些数据流管理系统出现。主要有以下几个系统： l 、s t r e a m f 2 9 , 5 3 ：它是斯坦福大学研制的通用数据流管理系统，该 系统是基于关系模型提出，主要研究包括内存管理和近似查询处理技术。 2 、t e l e g r a p h c q i 圳：它是伯克利大学提出的连续查询处理系统，主 要特点是自适应的查询处理技术以及物理操作符的共享。 3 、a u r o r a l 2 7 , 4 4 1 ：它提供了一个面向工作流的查询处理框架，用户可 以组织操作符来创建查询计划，并提供了q o s 管理器监控系统的性能。 4 、c o u g a r l 4 6 4 7 1 ：它是基于对象模型的传感器数据库