（计算机软件与理论专业论文）实视图动态选择算法中重叠实视图的处理.pdf

i i 海人学计算帆工程与科学学院工学硕士论文蜜视圈动态选择算法中重叠实视圈的处理 摘要 当采用实视图来提高o l a p 系统效率时，由于实视图往往并不恰巧是一个 完整的格节点，即实视图是多维数据切片( m r f s ) ，所以系统中会出现大量有重 叠数据的实视图，这不仅占用了过多的存储空间，也使得系统根据已有实视图响 应用户提交的多维查询变得复杂。以往的实视图动态选择算法没有考虑这种情况 的处理。 为此，本文提出了实视图进行合并的算法。该算法包括如何判断同一结点的 两个实视图之间是否有重叠数据，在何神情况下，有重叠数据的实视图需要合并， 如何合并，合并后的一些处理等。 本文把实视图合并算法结合到个简化但是完整的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 系统中。提高多维查询语句执行效率，是个十分重 要的问题，实视图是实现该目的的一个常用手段。本文将实视图合并算法和实视 图动态选择算法结合在一起，是对实视图动态算法性能上的种增强，能够提高 多维查询语句执行效率。本文的重点是讨论实视图合并算法，因此选择了目前比 较先进的基于单位空间频率动态实视图选择算法，以此为基础实现了实视图合并 算法，并通过实际数据的运行说明这个算法的有效性和先进性。 关键词：0 l a p ，多维查询切片，实视图，视图缓冲区 卜海大学计算机t 程与科学学院工学硕士论文实视图动态选择算法中重叠实视图的处理 a b s t r a c t w h e nm a t e r i a l i z e dv i e w sa r eu s e dt op r o m o t et h ee f f i c i e n c eo fo l a ps y s t e m a n di nt h ea l g o r i t h m so fd y n a m i cs e l e c t i o nf o rm a t e r i a l i z e dv i e w s ，t h e r ea r et h e p r o b a b i l i t i e st h a tt h eg r a n u l a r i t yo f m a t e r i a l i z e dv i e w si sn o tt h en o d e so fal a t t i c e ，i e m a t e r i a l i z e dv i e w sa r e t h em u l t i d i m e n s i o n a lr a n g ef r a g m e n t s ( m r f s ) a st h e c o n s i d e r a b l er e s u l t ，t h e r ea r ep r o b a b l ym a n ym a t e r i a l i z e dv i e w sw i t ho v e r l a p p e dd a t a - o v e r l a p p e dm a t e r i a l i z e dv i e w sm a y n o to n l yt a k ee x c e s s i v es t o r a g es p a c e ，b u ta l s o i n c r e a s et h ec o m p l e x i t yo fo l a ps y s t e m st oa n s w e rm u l t i d i m e n s i o n a lq u e r i e s t h i s s i t u a t i o nw a sn o tt a k e ni n t oc o n s i d e r a t i o nb e f o r e t h i sp a p e rr e n d e r sa l la l g o r i t h mf o rm e r g i n go v e r l a p p e dm a t e r i a l i z e dv i e w s b a s e do nt h el a t t i c em o d e l ，i n c l u d i n gh o wt od e c i d ew h e t h e rt w om a t e r i a l i z e dv i e w s c o n t a i n i n go v e r l a p p e dd a t ao rn o t ，o nw h i c hc o n d i t i o nw h e na n dh o wt om e r g e o v e r l a p p e dm a t e r i a l i z e dv i e w s ，a n da f t e r w o r k s ，e r e i nt h i sp a p e r , m a t e r i a l i z e dv i e w sm e r g i n ga l g o r i t h m ，t oi m p l e m e n t ，i sc o m b i n e d w i t has i m p l i f i e db u tw h o l l yf u n c t i o n e do l a ps y s t e m t h i sp a p e rd i s c u s s e st h e o l a p sb a s i cc o n c e p t i o n ss u c ha sd i m e n t i o n ，l e v e l ( h i e r a r c h yo fd i m e n t i o n ) ，m e m b e r ( o rp r o p e r t y ) a n dv a l u e s ；g i v e sas i m p l eo l a p sl o g i cm o d e a n dt h ea l g o r i t h mt o c o n v e r ti tt ol a t t i c em o d e l ；p r o v i d eaw a yt op r e s e n tt h em u l t i d i m e n s i o n a lq u e r i e s ；a n d i n t r o d u c e sa no l a ps y s t e m f r a m e w o r k ，d i e u s s e s t h e e x e c u t i n gp r o c e s so f m u l t i d i m e n t i o n a lq u e r i e su n d e rt h i ss y s t e mf r a m e w o r ka n di m p l e m e n t si t t h i sp a p e r a l s od i s c u s s e st h ei n d e x i n ga n dm a n a g e m e n t so fm a t e r i a l i z e dv i e w sw i t ht h eh e l po f l a t t i c em o d e l i nt h ed a t aw a r e h o u s ea n do l a ps y s t e m ，i ti tv e r yi m p o r t a n tt oi m p r o v et h e e f f i c i e n c eo fo l a ps y s t e m sa n s w e r i n gt h em u l t i d i m e n s i o n a l q u e r y a n d m a t e r i a l i z e dv i e w sa r et h ec o n n 1 t l o na p p r o a c ht of u l f i ls u c hg o a l i nt h i sp a p e r , m e r g i n ga l g o r i t h mi sc o m b i n e dw i t hs e l e c t i o na l g r o r i t h r na n dm e r g i n ga l g o r i t h mi s c o n s i d e r e da saw a yt oi m p r o v em a t e r i a l i z e dv i e w s s e l e c t i o na l g o r i t h m t h i s p a p e r l se m p h a s i si sp m t m go nm e r g i n ga l g o r i t h m ，s o ，b a s e do i la ns h a r p e d g i n g d y n a m i cs e l e c t i o na l g o r i t h m ，i ti m p l e m e n t st h em e r g i n ga l g o r i t h ma n dr i s e st e s t d a t at os h o wi t sf e a s i b i l i t y k e y w o r d s ：o l a p , m r f s ( m u l t i d i m e n s i o n a lr a n g ef r a g m e n t s ) ，v i e wp o o l f ：海大学计算机工程与科学学院工学硕士论文 实视图动态选择算法中重叠实视图的处理 表格4 - 1 表格6 1 袭格6 - 2 表格6 3 表格6 - 4 表格6 - 5 表格6 - 6 表格目录 s q l 类型和编程语言类型的映射 t p c h 的估计大小 表p a r t 中的部分字段 表s u p p l i e r 中韵部分字段 表c u s t o m e r 中的部分字段 表o r d e r s 中的部分字段 表l i n e l t e m 中的部分字段一 2 7 4 5 4 6 4 6 4 6 ，4 6 4 7 二海火学计算机工程与科学学院工学硕士论文实视图动态选掸算法中重叠实视图的处理 图片目录 图1 1 数据仓库系统体系结构3 匿2 一、星形模型8 围2 - 2 雹花模型9 嘤2 - 3o l a p 攮型定义的匿形化襄示1 0 围2 - 4 用树作为数据结构表示的o l a p 模型，1 l 圈3 - i简化的系统分屡架构1 2 图3 2 系统的横块划分。一1 3 圈3 - 3 格模型的建立过程一1 4 图3 - 4 查询执行过程1 4 重3 - 5 测试过程( 测试疆块生成 _ j l 试甩多维蠢诲语句) 1 5 图3 - 6 维中的屡次和属性与关系数据库表的对应关系l5 圈3 7 多雏查询验证的示意图1 7 图3 一b 查询优化模块的功能示意图一1 8 围妒 格模型2 i 图4 - 2 时间维的屡次关系，一2 3 蹬 3 创建维向导初始用户界面2 3 躅4 - 4 创建维p a r t 后的用户界面1 2 4 围4 - 5p a r t 缝的定义2 图4 - 6 格模型向导第一步( 选择多维数据立方体的度量值) 2 5 踊4 - 7 格模型向导第二步( 选择多维数据立方体的维) 一、2 6 图4 - 8 格模型向导第三步( 输入多维数据的名称) 2 6 图4 - 9 由向导生成的多维数据立方体2 6 图4 1 1n 一元缒和格节点之间的对应关系2 9 囱4 1 2 格上个结点和它的子结点的关系3 0 圄5 1实视图管理模块的密口3 5 圈5 2 奎询执行过程) 7 图5 - 3 多维查询语句对应l n 格节点的过程一3 8 图5 - 4 对应格节点中的实视图响应多雅查询的三种可能3 9 圈5 - 5s q l 重写中s e l e c t 语句的生成 一4 0 图6 - 2 生成的测试用o l a p 模型4 7 图6 - 3 测试用多维查询语句生成界面4 s 圈6 - 4 对于格结点的统计信息一一4 9 i 二海大学计算机e 程与科学学院工学硕士论义 实视倒动态选择算法中重叠实视目的处璀 图6 - 5 对于多维查询的统计信息， 图6 - 6 程序运行时的界面一 图6 - 7 测试结果 5 0 5 0 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表 或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学 校有权保留论文及送交论文复印件，允许论文被查阅和借阅：学校可 以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 日期： 2 口口3 弓、f 3 l 二海大学计算机工程与科学学院工学硕士论文实视图动态选择算法中重叠实视图的处理 第1 章绪论 1 1 研究背景和研究意义 本文研究的是如何提赢o l a p ( o nl i n ea n a l y t i c a lp r o c e s s i n g ，联机分析处 理) 系统对多维查询语句执行的效率，即如何缩短o l a p 系统对用户提交的多维 查询语句的响应时间。作为本文的研究背景和研究意义，首要的一点就是要对 o l a p 系统( 也可称为数据集市) 有个较为明确的理解。为什么需要o l a p 系 统，o l a p 系统能给我们带来什么，o l a p 系统的重要性是什么? 对这些问题的 认识有助于理解本文研究内容的意义。 快速发展的、充满竞争的商业世界对于及时、准确的信息有着永无止境的需 求，一些i t 专家对此认为其必然结果就是创建o l a p 系统。虽然o l t p ( o nl i n e t r a n s a c t i o n p r o c e s s i n g ，o l t p ) 和遗留系统拥有宝贵的信息，但是可能难以从这 些系统中提取有意义的信息并且速度也较慢。而且这些系统虽然一般可支持预先 定义操作的报表，但却经常无法支持一个组织对于历史的、联合的、“智能的” 或易于访问的信息的需求。因为数据分布在许多跨系统和平台的表中，而且通常 是“脏的”，包含了不致的和无效的值，使得难于分析。 例如，一个索赔支付系统为了尽可能快地支付或拒绝索赔，通常要处理许多 f i j 常或实时的事务。大多数情况下，这些系统都易于查看单一索赔以及通过系统 来加速其处理。然而，这些系统一般没有提供查看组合索赔数据的工具，来用以 响应即席或基于业务的问题，也没有提供工具，用以联合查看索赔信息和在索赔 系统外部的、与之相关的系统中所包含的信息( 如策略所有者或服务提供者的数 据) 。 联机分析处理( o l a p ) 的概念最早是由关系数据库之父e f c o d d 【t l 于1 9 9 3 年提出的。当时，c o d d 认为联机事务处理( o l t p ) 已不能满足终端用户对数据库 查询分析的需要，s q l 对大数据库进行的简单查询也不能满足溻户分析的需求。 用户的决策分析需要对关系数据库进行大量计算才能得到结果，而查询的结果并 不能满足决策者提出的需求。因此c o d d 提出了多维数据库和多维分折的概念， 即o l a p 。 o l a p 系统经过这些年的发展和推广( 这方面有大量的论文，如【2 等) ，已经 有大量的理论研究结果和商业产品，如各大数据库厂商都推出了各自的o l a p 产品。在对o l a p 系统的理论研究之中，提高o l a p 系统对多维查询的执行效 率是其中一个重要的方向。 f 二海火掌计算机工程与科学学院工学硕士论文实视倒动态选择算法中重叠实筏图的处理 实视图是提高o l a p 系统对多维查询执行效率的一个常用和有效的手段。实 视图集合的选择受限于实视图的存储空间( 如硬盘空间) 的大小限制( 空间限制) ， 即o l a p 系统中只能实化数据立方体中的一部分视图。同时，不同的实视图集合 ( 即选择不同的实视图) 对o l a p 系统执行多维查询的效率的效果不一样，因此， 实视图的选择还需要考虑o l a p 系统的对用户的响应时间( 时间限制) 。对于实 视图集合的选择，现在有大量不同的算法，其中一类算法为实视图的动态算法。 本文即针对当前实视图动态选择算法中可能的不足之处，即可能选择的实视图集 合中有大量的重叠数据这个问题，提出了实视图合并算法。 1 2 数据仓库简介 讨论o l a p 系统的时候，需要对数据仓库有一定了解，理解两者之间的区别 和联系。著名的数据仓库专家w h | n m o n 3 l 在其著作中对数据仓库一词给予如下 定义：数据仓库是一个面向主题的、集成的、非易失的，随时间变化的用来支持 管理人员决策的数据集合。对于数据仓库的概念我们可以从两个层次予以理解， 首先，数据仓库用于支持决策，面向分析型数据处理，它不同于企业现有的操作 型数据库；其次，数据仓库是对多个异构的数据源有效集成，集成后按照主题进 行了重组，并包含历史数据，而且存放在数据仓库中的数据一般不再修改。 根据数据仓库概念的含义，数据仓库拥有以下四个特点： l 、面向主题。操作型数据库的数据组织面向事务处理任务，各个业务系统 之间各自分离，而数据仓库中的数据是按照一定的主题域进行组织。主题是个 抽象的概念。是指用户使用数据仓库进行决策时所关心的重点方面，一个主题通 常与多个操作型信息系统相关。 2 、集成的。面向事务处理的操作型数据库通常与某些特定的应用相关，数 据库之间相互独立，并且往往是异构的。而数据仓库中的数据是在对原有分散的 数据库数据抽取、清理的基础上经过系统加工、汇总和整理得到的，必须消除源 数据中的不一致性，以保证数据仓库内的信息是关于整个企业的一致的全局信 息。 3 、非易失的。操作型数据库中的数据通常实时更新，数据根据需要及时发 生变化。数据仓库的数据主要供企业决策分析之用，所涉及的数据操作主要是数 据查询，一旦某个数据进入数据仓库以后，一般情况下将被长期保留，也就是数 据仓库中一般有大量的查询操作，但修改和删除操作很少，通常只需要定期的加 载、刷新。 4 、随时间变化的。操作型数据库主要关心当前菜个时间段内的数据，而数 海大学许算机_ t = 程i 科学学院t 学硕t 论文虫视闰动态选择算法中重叠实视图的处蛙 据仓库中的数据通常包含历史信息，系统记录了企业从过去某一时点( 如开始应 用数据仓库的时点) 到目前的各个阶段的信息，通过这些信息，可以对企业的发 展历程和未来趋势做出定量分析和预测。 企业数据仓库的建设，是以现有企业业务系统和大量业务数据的积累为基 础。数据仓库不是静态的概念，只有把信息及时交给需要这些信息的使用者，供 他们做出改善其业务经营的决策，信息才能发挥作甩，信息才有意义。而把信怠 加以整理归纳和重组，并及时提供给相应的管理决簸人员，是数据仓库的根本任 务。因此，从产业界的角度看，数据仓库建设是一个工程，是一个过程。 整个数据仓库系统是一个包含四个层次的体系结构。具体由下图示。 曰一曰一曰一曰 操作麒 原子，数锯仓库层o l a p 系统前端t 且 固卜1 数据仓库系统体系结构 操作层：是数据仓库系统的基础，是整个系统的数据源泉。通常包括企业内 部信息和外部信息。内部信息包括存放于r d b m s 中的各种业务处理数据和备类 文档数据。外部信息包括各类法律法规、市场信息和竞争对手的信息等等； 原予数据仓库层；是整个数据仓库系统的核心。数据仓库的真正关键是数 据的存储和管理。数据仓库的组织管理方式决定了它有别于传统数据库，同时也 决定了其对外部数据的表现形式。要决定采用什么产品和技术来建立数据仓库的 核心，则需要从数据仓库的技术特点着手分析。针对现有各业务系统的数据，进 行抽取、清理，并有效集成，按照主题进行组织。数据仓库按照数据饮覆盖范 匿可以分为企业级数据仓库和部门级数据仓库( 通常称为数据集市) 。 o l a p 系统：对分析需要的数据进行有效集成，按多维模型予以组织，以便 进行多角度、多层次的分析，并发现趋势。其具体实现可以分为：r o l a p 、m o l a p 和h o l a p 。r o l a p 基本数据和聚合数据均存放在r d b m s 之中；m o l a p 基本 数据和聚合数据均存放于多维数据库中：h o l a p 基本数据存放于r d b m s 之中， 聚合数据存放于多维数据库中。 前端工具：主要包括各种报表王具、查诲工具、数据分析工具。数据挖掘工 具以及各种基于数据仓库或数据集市的应用开发工具。其中数据分析工具主要针 对o l a p 服务器，报表工具、数据挖掘工具主要针对数据仓库。 圭鲞查兰盐苎垫三堡量型掌璺垫工学硕士论文实视圈动态选择算法中重叠实视图的处理 1 3 主要研究内容 实视图是提高o l a p 系统对多维查询响应效率的有效手段。以格模型为基础， 实视图的粒度从开始的比较粗放的整个格节点【4 】，至4 现在格节点的局部 5 “，反 映了研究的逐步深入。在实视图动态选择算法中，当实视图的粒度小于一个格节 点的时候，许多问题也随之而来。论文【4 1 中首次提出了格模型的概论。同此提 出了一个基于格结点的( 比较粗放的) 静态实视图选择算法。论文5 】在论文f 4 1 上的改进，提出了一种基于单位空间访问频率的实视图动态选择算法。论文f 6 1 采用格模型作为实视图管理框架，提出了自己的实视图的动态选择算法。 在o l a p 系统中，用户对多维数据的访问常常表现出空间局部性，这样， o l a p 系统很可能根据实视图动态选择算法在一较小多维区域生成多个小粒度的 有重叠数据的实视图。大量的重叠实视图带来很多不利结果，如占用大量的存储 空间，使得实视图动态选择算法需要频繁调用实视图淘汰算法，保证有空间存储 需要实化的视图。另外，如果对于一条多维查询语句有多个实视图可以响应，那 么如何决定该选择哪个实视图响应昵? 目前，一种方法n 3 是采用块( c h m 出s ) ，它要求基础数据采用块状文件存储， 这在实际使用中受到很大限制；还有一种方法采用格模型作为实视图的索引结 构，这种方法能快速定位实视图，同时不需要基础数据采用块状存储，在实用中 有较大的改进，但是这种方法没有考虑如何处理实视图的重叠数据。 本文试图解决实视图重叠的问题，包括如何判断实视图之间是否有重叠数 据，如何根据多个有重叠数据的实视图生成一个新的实视图。 1 4 本论文的章节安排 本文把实视图台并算法结合到了一个简化但是完整的o l a f 系统，通过该 o l a p 系统实现和验证了实视图合并算法。在文章的章节安排上，围绕o l a p 系 统的实现( 包括实视图合并算法) 展开。 第2 章讨论了o l a p 系统的逻辑模型介绍了当前两种常用的模型；星形模 型和雪花模型，同时说明了在本文中采用的逻辑模型。第3 章介绍了本文实现的 o l a p 系统的系统框架，如系统的分层，对每层的模块划分和系统的动态功能描 述等，对系统的每个模块做了简要的说明。第4 章着重讨论了如何把o l a p 的逻 辑模型转化为o l a p 系统的内部模型( 格模型) 。第5 章讨论了查询的执行和对 实观图的管理对实视图的管理中考虑了两个算法，一个是实视图的动态选择算 法，一个是本文提出的实视图合并算法。实视图的合并算法是本文的重点，因此， 法，一个是本文提出的实视图合并算法。实视图的合并算法是本文的重点，因此， 上海醴计算机工程与科学学院工学硕士论文实视图动态选择算法中重叠实视图的处理 1 3 主要研究内容 实视图是提高o l a p 系统对多维查询响应效率的有效手段。以格模型为基础， 实视图的粒度从开始的比较粗放的整个格节点 4 1 ，到现在格节点的局部 5 。6 1 ，。反 映了研究的逐步深入。在实视图动态选择算法中，当实视图的粒度小于一个格节 点的时候，许多问题也随之而来。论文【4 中首次提出了格模型的概论，同此提 出了一个基于格结点的( 比较粗放的) 静态实视图选择算法。论文 5 】在论文 4 上的改进，提出了一种基于单位空间访问频率的实视图动态选择算法。论文【6 采用格模型作为实视图管理框架，提出了自己的实视图的动态选择算法。 在o l a p 系统中，用户对多维数据的访问常常表现出空间局部性，这样， o l a p 系统很可能根据实视图动态选择算法在一较小多维区域生成多个小粒度的 有重叠数据的实视图。大量的重叠实视图带来很多不利结果，如占用大量的存储 空间，使得实视图动态选择算法需要频繁调用实视图淘汰算法，保证有空间存储 需要实化的视图。另外，如果对于一条多维查询语句有多个实视图可以响应，那 么如何决定该选择哪个实视图响应呢? 目前， 一种方法【7 1 是采用块( c h u n k s ) ，它要求基础数据采用块状文件存储， 这在实际使用中受到很大限制；还有一种方法1 6 】采用格模型作为实视图的索引结 构，这种方法能快速定位实视图，同时不需要基础数据采用块状存储，在实用中 有较大的改进，但是这种方法没有考虑如何处理实视图的重叠数据。 本文试图解决实视图重叠的问题，包括如何判断实视图之间是否有重叠数 据，如何根据多个有重叠数据的实视图生成一个新的实视图。 1 4 本论文的章节安排 本文把实视图合并算法结合到了一个简化但是完燕的o l a p 系统，通过该 o l a p 系统实现和验证了实视图合并算法。在文章的章节安排上，围绕o l a p 系 统的实现( 包括实视图合并算法) 展开。 第2 章讨论了o l a p 系统的逻辑模型，介绍了当前两种常用的模型：星形模 型和雪花模型，同时说明了在本文中采用的逻辑模型。第3 章介绍了本文实现的 o l a p 系统的系统框架，如系统的分层，对每层的模块划分和系统的动态功能描 述等，对系统的每个模块做了简要的说明。第4 章着重讨论了如何把o l a p 的逻 辑模型转化为o l a p 系统的内部模型( 格模型) 。第5 章讨论了查询的执行和对 实视图的管理，对实视图的管理中考虑了两个算法，一个是实视图的动态选择算 法，一个是本文提出的实视图合并算法。实视图的合并算法是本文的重点，因此， 垡坠茎兰盐墨垫三堡皇型竺兰堕三堂堡! 堕塞 塞塑鬯垫查望塑整鋈! 蔓墨壅塑堕竺丝型 也给予了较多的说明介绍。第6 章是测试，即对实视图的合并算法进行验证，通 过比较得出其性能的评价。第7 章是总结和展望，对已有的工作作出评价，同时 介绍本文研究还需的进一步的工作。 堂丛生墨墨三塑兰型兰兰堕三堂堡圭堡茎 壅塑鬯垫查垫堂茎兰! 重塞壅塑堕箜丝些 第2 章o l a p 的建模 2 1 o l a p 的核心要求 e r i kt h o m s e n 在书i s 中，提出了o l a p 的核心逻辑要求和核心物理要求。 这些核心的、根本的、必需的或者说是最低要求在逻辑层面包括对于多维、层次、 维度公式的支持，以及数据结构和表现形式的分离，在物理层面主要就是对于任 意查询的高速响应。任何语言或者产品，如果不能满足这些要求，那严格说来就 不是o l a p 。 o l a p 的核心逻辑要求 1 带有层次引用的丰富维结构 我们生活的现实世界就是由一组彼此交互的高维子系统组成的，每个子系统 含有多层次的数据、细节、事实、抽象。o l a p 工具的一个基本贡献就是能够有 效的对这种复杂性系统建模。我们熟悉的一些层次，时间方面如年、月、日，地 理方面如洲、国家、省( 州) 、市等。 2 对于维和计算的有效定义 分析工作不仅仅是简单数字汇总，工f 确地对大量数据的汇总和平均自然是重 要的但是最重要的信息是来自对于各种比率的比较、随时间变化趋势的推断和 其它方面。也就是说，在分析过程中进行查询很大一部分是比较深入的分析。 3 灵活性 灵活性又一个非常重要的o l a p 功能。这里灵活性包含了多个方面的含义： 灵活的视图、灵活的定义、灵活的分析、灵活的界面。作为一个系统必须在所有 这些方面都具有灵活性。 4 结构和形式的分离 对于数据进行各种形式的浏览，这个在很大程度上就是数据结构和表现形式 分离的功能体现。具有这种分离的功能意味当前用户对视图调整的时候不会改变 任何数据的结构。如果需要对数据进行重构来支持一个新视图的话，那这个视图 很可能就不会创建了( 当然包括任意查询的方式) 。缺乏结构和形式的分离：是 数据电子表的一个缺陷。 o l a p 的核心物理要求 1 快速获取 数据是o l a p 一个至关重要的组成部分，速度是为了跟上思维的速度。o l a p 需要支持任意的查询，其中的一些需要根据要求来即时计算。例如，个人可能 卜海人学计算机工程与科学学院工学硕士论文 实视图动态选择算法中重叠实视图的处理 会从查询上个季度整体产品在欧洲的利润情况来开始他的分析。当看到利润小于 预计值的时候，他可能会深入到各个国家查看整体产品利润情况。这里，他可能 发现有些国家的利润明显低于其它国家，于是他自然就会查看这些国家中不同产 品组的利润情况，总的目标就是寻找一些比较异常的数据来解释这个现象。第 眼查看的时候可能不会发现什么问题。产品销售的区域完全没有问题，回报和生 成成本也是如此。但是经过一番观察之后，就会发现非直接成本在这些国家明显 偏高。进一步对这些非直接成本分析可以发现对于某些产品的赋税明显增加( 可 能是一些贸易谈判的结果) ，从而明显影响了最总的利润，因为产品价格除非由 于市场竞争的缘故，否则通常是不会发生变化的。 在这个思考过程中的每一步都会有一个查询。每个查询在上一个查询的基础 上进行的，从这个意义上讲它是交互的。对于个进行这种分析的人都希望能保 持这种势头。如果对于每个查询的平均响应时间是按天、小时、甚至是用分钟来 计算的话，那么就很难进行这种分析活动。一个经常提到的o l a p 系统的目标就 是提供平均响应时间在5 秒以内，而不管查询的类别或者数据库的大小。 2 多用户支持 企业是一个互相合作的环境。随着权利的下放和分散化，需要有读写据测分 析数据权利的员工数量正处在不断增长中。 2 2 o i a p 的建模 2 2 1 o l a p 中的关键概念 在o l a p 系统中，维、层次、属性等是关键概念，而在不同的文章和商业 o l a p 系统中对这些概念有着不同的解释州。本文根据相关网站【1 0 1 对这些术语作 出定义。 1 )维( d 蹦e n s l o n ) 维是由一列在用户看来具有相同数据类型的属性组成的构成数据立方体的 结构属性。例如，所有的月、季度、年等构成了一个时间维度：同样，所有的城 市、地区、国家等构成了一个地理维度。维的作用是用来确定1 一个多维数组的值 的指针。如果确定了一个维中一个属性，那么剩余的维中的全部或者几个属性定 义了一个维度较低的数据立方体。如果除了两个维外的其它维度都选定了一个属 性，那么这两个维度构成了一个表格( 或者叫“切片”、“页”) 。如果所有的维都 选定了一个属性那么则确定了一个单位立方体。维提供了对用于查询、浏览和 分析目的的数据的一种管理和选择的非常确切和直观的途径。 i ：海人学计算机工程与科学学院工学硕士论文实视酗动态选择算法中熏叠实视圈的处理 2 ) 层次( l e v e l ， h i e r a r c h i c a l ) 在维的层次结构中，如果属性到其后代的路径中最大节点数相同，则这些属 性属于同一层次。例如，对于一个由总帐系统组成的帐目维度，所有的细节帐目 都处于层次0 ，较高的帐目处于层次1 ，再高的则处于层次2 等。可能出现一个 父属性由两个或者多个处于不同层次的属性，则父属性的层次根据子属性中层次 级别最高的一个定义。 3 ) 属性( m e m b e r ，d i m e n s i o n ) 维度的属性是指在一个维度中确定个数据项的位置和描述的具体名称或 者标识符。例如，“j a n u a r y1 9 8 9 ”或“1 q t r 9 3 ”是时间维度中属性的典型例子。 “批发”，“零售”等则是销售渠道维度中属性的典型例子。 2 2 2 星形模型 大多数数据仓库采用星形模型】来建模多维数据。在数据库中有一张事实表 ( f a c tt a b l e ) ，并且每一维有一张维表。事实表中的每一个元组包含指向维表的 指针( 外键，通常为了方便使用序列号) ，并保存这些坐标的度量值。每个维表 中包含这个维的属性。下图显示了一个星形模型的例子。 o r d e r f a c tt a b l e o r d e r n o 0 r d e r d a t e o r d e r n 0 c u s t o m e r n o c u s t o m e r s a l e s d c r s o n i d c u s t o m e r n o p r o d n o c u s t o m e r n a m e d a t e k e y c u s t o m e r a d d r e s s q 垃燃 c i t y q u a n t i t y s a l e p e r s o n t b t a i p t i c e s a l c v e r s o n i d s a l e p e r s o n n a m c c i t y q u o t a 图2 1 星形模型 - 8 p r o d u c t 卜懈大学计算机工程与科学学院工学硕士论文实视图动态选择算法中重叠实视图的处理 2 2 3 雪花模型 星形模型不支持属性间的层次性。雪花模型l ”1 通过规范化维表( 即消除维表 中的部分依赖和传递依赖等，通常要求达到数据设计的第三范式或者b c n f 范 式) 来支持属性问的层次关系。这样有利于维表的维护。但是非规范化维表的结 构更能方便维的浏览。 o r d e r f a c tt a b l ep r o d u c tc a t e g o r y p r o d n o 1 c a t e g o r y n a m e p r o d n a m e p r o d d e s c r c a t e g o r y 2 3 o l a p 模型 圈2 - 2 雪花模型 m o n t h e y e 盯 在o l a p 理论研究中，o l a p 模型1 1 2 】更有着重要的地位，因此理论界出现了 很多o l a p 模型。例如，李琪、自英彩等提出了一种采用用层次树表示的o l a p 模型。本文给出一个形式更简单、维具有层次结构1 1 4 1 的o l a p 模型。该模裂限 制一个维的一个层次对应一张规范化的维表( 每个维中的a l l 属性，表示在对 事实表汇总时，对该维对应的属性值全部汇总) ，这种对应关系是一对应的( 除 每个维的a l l 属性、细节属性都和事实表对应外) 。下面给出该模型的形式化定 义。 定义一个o l a p 模型仅表示一个数据立方体，是一棵具有如下特征的树： 小，；，l 卜海大学计算机工程与科学学院工学硕_ ：论文 实视圈动态选择算法中重叠实视嘲的处理 ( 1 )以a l l 为根结点： ( 2 ) 根结点的所有子结点表示数据立方体的维度，称为维结点。如 果数据立方体有r l 维，则根结点必须有n 个子结点。 ( 3 )每个维结点的子结点是表示层次的层次结点，同一维结点下的 层次结点按从左到右编号，第一个层次结点表示该维层次关系中的第l 级， 第：个结点表示第2 级等。除第一结点外，层次结点和数据立方体中该维 的维表逐一对应，即第二个结点对应该维中的最后一个维表，第三个结点 对应该维的倒数第二个维表，以此类推。( 这种对应关系反映了浏览多维数 据立方体的d r i l l d o w n 操作，即汇总级别越高的维表对应越靠前的层次结 点。每个维汇总的最高级别就是a l l 。) ( 4 ) 层次结点对应的规范化维表应该具有如下关系：第i + 1 结点对 应的维表的主键应该是第i 结点对应维表中的非关键字段。 ( 5 )层次结点下的结点表示维的属性。第1 级的层次结点只能且必 须有一个属性，即该维的a l l 属性。其余级的层次结点下的属性为该层次 结点对应的维表中的非关键字段 该模型是以雪花模型为基础的，要求对维表作出规范化处理( 满足b c n f 范 式) 。该模型的局限性表现在如只考虑一个数据立方体，层次和维表的对应关系 为一一对应( 每个维的第1 级和最末级除外) 等。该模型相对较为直观，实现也 比较容易，并且能满足本文对o l a p 模型的要求。 下图是对上述定义的一个直观的图形化表示。 a l l 7 弋、 维l维2维3 卜卜 第i 级第2 级 i 产 维1 a l l属性1属性2 圈2 3o l a p 模型定义的图形化表示 f 面给出一个例子。对于上节所示的雪花模型根据本文中定义的o l a p 模型。可以表现为： l ：海人学汁算机工程与科学学院工学硕士论文实视图动态选择算法中重叠实视蚓的处理 圈2 4 用树作为数据结构表示的o l a p 模型 逐步细化 几州 总 卜海人学汁算机工程与科学学院 ：学硕士论文实视图动态选择算法中重叠实视图的处理 3 1 分层体系 第3 章系统框架 o l a p 系统是一种复杂的数据库系统。为了能很好的控制系统复杂性，提高 查询响应的整体效率，对系统进行分层设计并在每层中进行模块划分是两个比较 有效的方法。o l a p 的应用需要实现快速的交互式查询，且这些查询面对的数据 量又异常庞大。所以如何有效地管理这些数据，并且保证足够高的查询响应速度， 是建立o l a p 系统时需要解决的关键问题。而o l a p 系统体系结构的好坏在很 大程度上对该问题的解决起着决定作用。 本文只是利用o l a p 系统对本文提出的算法进行性能验证，而不是提供1 。个 功能完备的o l a p 系统。从这个要求出发，这罩对o l a p 系统做了简化处理。 开放的，功能完备的o l a p 系统可以参见相应文献i l5 。1 6 。下面是本文中使用的 简化的分层架构。 用户输入和系统输出 用户层厂 彳卜 一妙一u l 查询优化、执行。管理实视图等。l 功能层：r 二天一 数据层妙u j 数据源( 关系数据库或者其它)j 圈3 - 1简化的系统分屠架枸 用户层：主要提供用户接口，如用户输入和系统输出。对于用户输入，提供 图形化的窗口界面，方便用户直接输入多维查询，或者由多维查询向导帮助用户 生成多维查询语句。对于查询结果的输出，本着数据和数据显示分离的原则，该 层只提供对查询结果的图形或者文本的显示。 功能层：为系统的核心层，功能包括对用户提交的查询的分析、优化和执行， 以及返回查询的结果。同时为了提高查询的效率，管理和维护一个实视图集合。 数据层：该成由关系数据层实现。 j 海火学计算帆工程与科学学院工学硕j ：论文 实视图动态选择算法中重叠实视图的处理 3 2 系统的模块划分 图3 - 2 系统的模块划分 这里所说的系统模块划分是指从静态的角度根据功能对系统进行的模块划 分。在用户层，主要是提供用户输入和系统输出的功能。用户输入包括通过模型 向导输入多维数据模型和通过用户输入模块输入查询语句( 可以为多维查询语句 和s q l 语句) 。系统执行结果则通过输出模块展现给用户，本文只提供简单的文 本输出和表格形式的输出，而对数据不