（计算机软件与理论专业论文）数据仓库中物化视图的选择与调整.pdf

摘要 数据仓库是一个面向主题的、集成的数据集合，用来支持管理人员的决策。 它维护着海量的数据并且支持形式复杂的查询，如何高效的管理如此之多的数据 并提供高效的查询是数据仓库面临的其中一个难题，而物化视图是解决这个问题 的重要手段，但是它需要额外的系统空间来存储，并且需要牺牲系统的代价来维 护，因此，物化视图的选择是一个重要的研究课题。传统物化视图的静态选择算 法是基于查询分布概率已经由用户提供，或这些查询在综合数据上是均匀分布的 前提下。但实际应用中，用户查询均匀分布或用户提供查询概率的假设常常不能 成立，因此提出一种既有静态选择能力，又有动态调整能力的视图选择算法就显 得相当有实际与研究意义。 本文从静态和动态两方面深入研究物化视图的选择问题，基于s p j ( s e l e c t - p r o j e c t - j o i n ) 视图假设的数据仓库模型，以m v p p 为搜索空间，综合考 虑存储空间、视图维护及查询性能，提出了一种新的物化视图选择和调整算法一 v s a a ( v i e w ss e l e c t i o na n da d j u s t m e n ta l g o r i t h m ) 。从数学模型和关键参数两个方 面研究了v s a a 的理论模型，针对v s a a 实时性差的缺陷提出了d v m v ( d y n a m i c v i r t u a lm a t e r i a l i z e dv i e w s ) 算法作为v s a a 算法的补充，以理论分析为指导实现 了v s a a 的算法并和各种经典算法进行了对比分析，利用t p c h 基准数据生成 1 g 数据，并导入到o r a c l e 数据库中作为实验数据，通过理论及实验证明了v s a a 算法的有效性和优越性。 关键字：数据仓库：物化视图；静态选择；动态调整 a b s t r a c t ad a t aw a r e h o u s ei s ，b yd e f i n i t i o n , as u b j e c t - o r i e n t e d ，i n t e g r a t e dc o l l e c t i o no f d a t aw h i c hs u p p o r tm a n a g e r st om a k ec o r r e c td e c i s i o n i te n a b l e sc o m p l e xq u e r i e s o nd a t aw a r e h o u s e s ，w h i c hc o n t a i n sl a r g ea m o u n t so fd a t a h o w e v e r , h o wt o m a n a g es om u c hd a t ae f f i c i e n t l ya n dp r o v i d eh i g he f f i c i e n tq u e r yi so n eo ft h e p r o b l e m sf a c e db yd a t aw a r e h o u s e a n dm a t e r i a l i z e dv i e wi sai m p o r t a n tm e t h o d t o s o l v et h a t ，b u ti tn e e d se x t r as y s t e ms p a c et os t o r ea n da l s on e e d st ob em a i n t a i n e da t t h ep r i c eo fs y s t e mi m m o l a t i o n t h e r e f o r e ，t h es e l e c t i o no fm a t e r i a l i z e dv i e wi sa n i m p o r t a n tr e s e a r c hs u b j e c t t h es t a t i cs e l e c t i o na l g o r i t h mo ft r a d i t i o n a lm a t e r i a l i z e d v i e wi sb a s e do nt h ea s s u m p t i o nt h a tp r o b a b i l i t yd i s t r i b u t i o no fq u e r i e sh a sb e e n p r o v i d e db yt h eu s e r , o rt h e s eq u e r i e si nt h ei n t e g r a t e dd a t aa r eu n i f o r m l yd i s t r i b u t e d b u tt h e s ea s s u m p t i o n sa l w a y sc a l ln o tb er e a l i z e di n p r a c t i c a lu s e s oav i e w s e l e c t i o na l g o r i t h mw i t ht h e c a p a c i t yo fb o t hs t a t i c s e l e c t i o na n dd y n a m i c a l a d j u s t m e n ti sq u i t ep r a c t i c a la n dr e s e a r c h a b l e t h i sp a p e rl u c u b r a t et h es e l e c t i o no fm a t e r i a l i z e dv i e wf r o ms t a t i ca n dd y n a m i c a s p e c t sa n dp r e s e n t san e wm a t e r i a l i z e dv i e ws e l e c t i o na n da d j u s t m e n ta l g o r i t h m v s a a ( v i e w ss e l e c t i o na n da d j u s t m e n ta l g o r i t h m ) w h i c hb a s e do nt h es p j ( s e l e c t - p r o j e c t - j o i n ) v i e wa s s u m p t i o nd a t aw a r e h o u s em o d e l t h i sa l g o r i t h mt a k e m v p p ( m u l t i - v i e wp r o c e s s i n gp l a n ) a st h es e a r c hs p a c ea n di n t e g r a t e l yc o n s i d e rt h e f a c t o r so fs t o r a g es p a c e ，v i e wm a i n t e n a n c ea n dq u e r yc a p a b i l i t y a f t e rh a v i n g r e s e a r c h e dt h ev s a at h e o r e t i c a lm o d ef r o mm a t h e m a t i cm o d e la n dk e yp a r a m e t e r a s p e c t s ，t h i sp a p e rp u tf o r w a r dd v m v ( d y n a m i cv i r t u a lm a t e r i a l i z e dv i e w s ) a l g o r i t h ma sas u p p l e m e n t a r yo fv s a aa l g o r i t h ms p e c i f i ct ot h er e a l t i m ed e f e c to f v s a a a n dt a k et h et h e o r e t i c a la n a l y s i sa sg u i d a n c et or e a l i z et h ev s a aa l g o r i t h m a sw e l la sc o n t r a s t i v ea n a l y s i st oo t h e rc l a s s i c sa l g o r i t h m s f i n a l l y , iu s et p c h b e n c h m a r kd a t at og e n e r a t e1gd a t ai n t oo r a c l ed a t a b a s ea st h ee x p e r i m e n t a ld a t a , a n dp r o v e dt h ee f f e c t i v e n e s sa n ds u p e r i o r i t yo ft h ea l g o r i t h mv s a a t h r o u g ht h e o r i e s a n de x p e r i m e n t s k e yw o r d s ：d a t aw a r e h o u s e ；m a t e r i a l i z e dv i e w ；s t a t i cs e l e c t i o n ；d y n a m i c a d j u s t m e n t 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的资助， 在() 实验室完成。( 请在以上括号内填写课题或课题 组负责人或实验室名称，未有此项声明内容的，可以不作特别声明。) 声明人( 签名) ：互互u ( 一 年月日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书馆 及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国博 士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘 要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文，于 年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“”或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签名) ：互色0 乙 年月日 绪论 1 1 引言 第一章绪论 在过去的三十多年里，数据库系统作为数据管理手段主要用于事物处理。这 些数据库已经存放了大量的日常业务数据。尤其到了二十世纪末，信息技术发展 迅速，数据量加倍的时间越来越短。从大量的数据中得到有价值的，支持决策制 定的信息是信息系统用户的新需求。因此，数据仓库技术应运而生。 经过近几年的发展，数据仓库技术已经日臻完善，大多数大型数据库供应商 都已在其产品中集成了数据仓库的功能。例如o r a c l e 、i b md b 2 、s y b a s e 、s q l s e r v e r 等都已经向用户提供了比较成熟的数据仓库产品，并且在实际应用中取得 了显著的效果。数据仓库中数据的大量积累、用户数量的增加、查询的复杂化， 使得数据仓库必须满足更高的性能要求。虽然数据仓库没有o l t p 那么苛刻的响 应时间要求( 通常少于3 秒) ，然而如果响应时间过长用户是不能接受的。 物化视图技术是数据仓库系统中提高性能的关键性技术之一，它是一种将视 图所对应数据加以实际物理存储的技术。其目的是通过预计算来加快数据仓库系 统对用户查询的响应速度。然而视图的物理化既需要占用可观的磁盘空间，又需 要耗费大量的系统资源以对其进行维护。所以如何选择一组合适的视图集合加以 物理化，使系统能够利用有限的资源最大限度的提高数据仓库系统对用户查询的 响应速度，是一个极为重要的问题。本文主要研究数据仓库中的物化视图选择问 题，此课题具有一定的理论意义和实用价值。 1 2 联机分析处理概述 数据仓库把来自多个数据源的数据集成起来，形成一个可靠的、一致的和不 断更新的历史信息集合。数据仓库是进行分析决策的基础，但还必须有强有力的 工具进行分析和辅助决策。基于数据仓库的一个重要分析工具联机分析处理 ( o l a p ) 的概念最早是由关系数据库之父e e c o d d 于1 9 9 3 年提出的。当时，c o d d 认为联机事务处理( o n l i n et r a n s a c t i o np r o c e s s i n g ，简称o l t p ) 尸, 不能满足终端 数据仓库中物化视图的选择与调整 用户对数据库查询分析的需要，并且s q l 对大数据库进行的简单查询也不能满 足用户分析的需求。用户的决策分析往往需要对关系数据库进行大量的计算才能 得到结果，而查询的结果并不能满足决策者提出的需求。因此，c o d d 提出了多 维数据库和多维分析的概念，即o l a p 。o l a p 与o l t p 各有其特征，对二者的 比较见下表1 1 。 表1 - 1o l a p 与o l t p 特点对照表 0 l t p 数据0 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 常常包括对数据的相互查询，这项 活动发生在经过多种途径的一系列分析，如对底层细节的进一步挖掘之后。用户 对这种多维数据模型的操作比对其他数据模型的操作要容易和直观。例如，用户 2 绪论 可以在模型中切片、切块或者旋转等。 1 2 1o l a p 的功能特征 联机分析处理是一种数据分析技术，在著作【1 】中，列出了以下它需要具有的 功能特征： 给出数据仓库中数据的多维逻辑视图，其视图应独立于数据储存的具体 形式。 一般应包括交互式的查询和对数据的分析。交互式的查询通常有多种方 式，如查看较低粒度的详细数据或统览较高粒度的概括性和聚集性的数据。 提供分析的建模功能，包括可以产生比率、变量等的计算引擎，有关度 量或跨多维的数字数据。 生成概括数据、聚集和层次，并在每一维的交叉点上对聚集和概括级别 进行审计。 支持功能模型进行预测、趋势分析和统计分析。 检索并显示多维表格、图表和图形中的数据，并且能够容易地变换基准 轴。这一点很重要，因为用户需要从不同角度分析数据，并且在分析一个侧面的 数据时产生的问题可能需要在另外一个侧面中检验。 快速响应查询，以避免分析过程被中断，或查询信息是过时的。 具有多维数据存储引擎，按阵列存储数据，这些阵列是各应用维的逻辑 表示。 1 2 2o 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 的实现方法，根据存储数据的方式不同可以分为r o l a p 、m o l a p 、h o l a p 三种。 数据仓库中物化视图的选择与调整 r o l a p ( r e l a t i o n a lo l a p ) 是基于关系数据库的o l a p 实现。其以关系数 据库为核心，以关系型结构进行多维数据的表示和存储。r o l a p 将多维数据库 的多维结构划分为两类表：一类是事实表，用来存储数据和维关键字；另一类是 维表，每个维至少使用一个表来存放维的层次、成员类别等维的描述信息。维表 和事实表通过主关键字和外关键字联系在一起，从而形成星型模型、星座模型或 雪花模型。r o l a p 的最大好处是可以实时地从源数据中获得最新数据更新，以 保持数据实时性，而且，由于r o l a p 是基于传统的关系数据库，可以利用原来 就已经成熟的存储、索引和查询技术。其缺陷则在于运算效率比较低，用户等待 响应时间比较长。 m o l a p ( m u l t i d i m e n s i o n a lo l a p ) 是基于多维数据库的o l a p 实现。其以 多维数据组织方式为核心，使用多维数组存储数据。多维数据在存储中将形成类 似“数据立方体( c u b e ) ”的结构。事实上，多维数据库是由许多经过压缩的， 类似于数组的对象构成，这种对象通常带有高度压缩的索引及指针结构。每个对 象由聚集成组的单元组成，每个单元块都按类似于多维数组的结构存储，并通过 偏移计算进行存取。由于索引只需要一个较小的数来标志单元块，因此多维数据 库的索引一般较小，只占很小一部分数据空间，容易装进内存。因此，此结构在 得到高度优化后，可以最大程度地提高查询性能。随着源数据的更改，m o l a p 存储中的对象必须定期处理以合并这些更改。两次处理之问的时间将构成滞后时 间，在此期间，o l a p 对象中的数据可能无法与当前源数据相匹配。维护人员可 以对m o l a p 存储中的对象进行不中断的增量更新。m o l a p 的优势在于由于经 过了数据多维预处理，分析中数据运算效率高。其主要的缺陷在于数据更新有一 定延滞，此外，多维存储必须具有高效的稀疏数据处理能力，能略过零值、缺失 的值和重复数据，否则存储存在大量的冗余。 表1 - 2r o l a p 与m o l a p 性能对比表 r o l a pm o l a p 优势 没有大小限制；性能好、响应速度 可用沿用现有的关系数据库的技术；快； 可以通过s q l 实现详细数据与概要 专为o l a p 所设计； 数据的存储； 支持高性能的决策 4 绪论 现有关系型数据库已经对r o l a p 做 支持计算，如：复杂的跨 了很多优化，包括并行存储、并行查询、 维计算；多用户的读写操 并行数据管理、基于成本的查询优化、位作；行级的计算 图索引、s q l 的o l a p 扩展( c u b e ，r o l l u p ) 等大大提高r o a l p 的速度 缺点一般比m d d 响应速度慢；增加系统复杂度，增 不支持有关预计算的读写操作：加系统培训与维护费用； s q l 无法完成部分计算； 受操作系统平台中 无法完成多行的计算文件大小的限制，难以达 到t b 级( 只能1 0 - - 2 0 g ) h o l a p ( h y b r i do l a p ) 是基于混合数据组织的o l a p 实现。用户可以根 据自己的业务需求，选择哪些模型采用r o l a p ，哪些采用m o l a p 。一般来说， 会将非经常使用或需要灵活定义的分析使用r o l a p 方式，而常用、常规模型采 用m o l a p 实现。 1 3 物化视图概述 1 3 1 物化视图的概念 o l a p 必须支持各种可能的查询，相当一部分查询是复杂的，通常要涉及大 量的数据，并且需要对数据进行选择、投影、连接等处理，这是一个非常耗时的 过程，然而一个决策支持系统要求它的查询能够被快速响应。解决这一矛盾通常 采用的一个有效的方法是：数据仓库针对o l a p 可能的查询对原始数据进行选 择、投影、连接等预处理，并将得到的综合数据存储在数据仓库中。这种综合数 据就是物化视图( m a t e r i a l i z e dv i e w ) 。物化视图不同于视图的概念，视图只是一个 虚表，是一个定义，查询的时候需要重新计算；而物化视图就是用户常用的查询 或最可能的查询模式计算出来的结果的物理存储。有了物化视图，o l a p 基本上 不再需要对原始数据进行处理，而只需要在物化视图的基础上进行一些简单的计 算便可以完成复杂的查询。因此，物化视图是提高数据仓库的查询响应能力，有 效支持决策分析的重要手段。 5 数据仓库中物化视图的选择与调整 对物化视图的探讨是目前数据仓库设计方面研究的热门课题，物化视图技术 已经用于很多领域。在查询优化和数据库设计中，由于物化视图对查询的部分计 算已经完成，因此用物化视图来计算查询能够提高查询处理的速度；在数据集成 系统中，通过建立物化视图使用户查询不需要访问底层的各种数据源，而直接访 问数据集成系统中的中介层( m e d i a t e ds c h e m a ) ，所有的与数据源的访问关系都是 由中介层的物化视图来完成；为了维护物理数据的独立性，有一些作者考虑用视 图作为描述数据存储的机制，特别是现在一些应用中，如将x m l 数据存储到关 系数据库中。半结构数据的存储，更是需要考虑物理数据的独立存储机制。 1 3 2 物化视图的主要管理任务 数据仓库中的物化视图主要用于预先计算并保存表连接或聚集等耗时较多 的操作结果。这样，在执行查询时，就可以避免进行这些耗时的操作，而从快速 的得到结果。而在数据仓库中使用物化视图，主要需要解决五个问题，也称为物 化视图的五个主要管理任务：视图维护，视图使用，视图选择，视图同步，视图 调整。如下图1 1 所示。 6 绪论 用户 i 匮笼融曼 i固 e 画i薹：糍皇_ 步习f 税豳溯整 千 图i - i 物化视图的五个主要管理任务 视图维护在源数据改变时保持视图与数据源的一致性；视图同步在源模式改 变时重写视图定义，保持视图定义与源模式的一致性；视图调整在视图定义重写 以后，增量调整视图内容；使用视图是指回答用户查询时，基于视图重写用户查 询；视图选择主要是指根据一定条件( 比如大小限制) ，预先选择一批符合条件 的视图进行物化操作，从而最大化提高用户查询效率。 视图维护 由于数据仓库中的数据是来源于其它独立的操作型数据库，当这些数据库中 的数据发生变化时，数据仓库中的数据也会随着改变。因此，由数据仓库中的基 表预计算得到的物化视图也必须与原始数据的变化保持同步，以保证数据的一致 性。这种同步更新物化视图的操作即物化视图的维护。 7 数据仓库中物化视图的选择与调整 目前已有的物化视图维护方法主要有以下几种： 重新计算：直接访问基表，重新计算视图，实现对物化视图的维护。这 种方法简单、直接，是当前许多现行商用数据仓库普遍采用的方法，但是其维护 代价过大，并且使得数据仓库长时间处于不可访问的状态，在某些应用中是不可 容忍的。 增量维护：通过访问底层数据的增量和物化视图的定义，计算物化视图 的增量，然后修改相应的物化视图。该方法效率高、维护代价小，尤其当基表更 新的比例较小时，增量更新比重新计算的性能更好。目前有许多增量维护算法致 力于提高增量维护的效率，文献【2 ，3 1 是用于集中式环境下的增量维护。文献【4 1 采 用增量表达式，并使用算法查找最优增量表达式来降低更新时间。文献【5 叫都提 出了各自的物化视图的增量维护算法。 通过添加辅助的视图来减少物化视图维护的复杂性和减小维护的代价 【1 0 1 ： 自维护技术【1 1 1 ，通过添加辅助关系使得对物化视图的维护不需要对底层 数据源进行访问。 此外，就广义的物化视图的维护而言，对物化视图的动态调整也属于物化视 图维护的一种，这是对物化视图集本身为适应新的查询分布情况的维护。 目前的物化视图的增量维护算法一般可以归为两类： 1 ) 规则系统型算法 根据视图和源数据的变化，规则系统型算法生成用来维护视图的一段由演绎 规则或s q l 语句构成的程序。文献第一次提出了这种策略，他们提出的有限 差分算法，基于功能数据模型实现了视图的增量维护。该算法生成的视图维护程 序代码通过插入到源数据的更新事务中，从而实现视图的同步更新。文献【1 3 1 提出 通过自动派生出生成规则实现视图的维护。文章假设视图需要所有基表的集合语 义，并且包含至少一个键。文酬1 4 1 基于包的语义提出记数维护算法。插入变化量 记为正数，删除变化量记为负数。如果一个视图的元组记数值变为0 ，则将该元 组从视图中删除。 规则系统型算法很难证明算法的正确性，尤其是不同数据库对s q l 语言扩 展后，无法保证算法在所有环境中都仍然有效。并且，由算法生成的维护程序难 以优化。为此，一些学者提出了代数型算法。 8 绪论 2 ) 代数型算法 文献【1 5 】中提出的算法为每种操作都预定义了一组基本变化传递规则。通过递 归调用这些基本规则，为视图查询树中每个代数运算传递变化，从而构造出视图 维护计划。而生成的视图维护计划，可以基于查询开销进行优化。因为代数型算 法是基于代数的，所以其不受任何特有查询语言扩展的影响。 目前，这方面的研究主要集中于通过建立代数维护框架，如何支持更多类型 的操作和不同的数据模型。文献旧研究了基于集合语义的含有连接操作的视图维 护。文献【1 5 1 把研究扩展到包代数( b a ga l g e b r a ) 。文献【坛1 刀研究了聚集操作和外连 接操作。文献【1 8 】还研究了维护模式s q l 视图中的高序操作。在关系数据模型之 外，基于代数的维护工作也有很多的研究，比如基于x m l 代数维护x m l 视图 1 9 1 。所有这些对代数维护框架的扩展，都有一个前提条件：每个代数操作的变化 传播与其具体应用环境无关。因此，我们可以重用这些变化传播规则，构造出更 为复杂的操作，解决复杂的问题。 视图同步 在许多实际应用中，因为业务需求快速变化，或者新的数据类型或者约束的 加入，不仅数据源的数据会发生变化，数据源的模式也不可避免地会改变。比如 数据集成时的模式设计变化，或者x m l 模型和关系模型映射的物理模型结构设 计变化。随着数据模式的日益复杂，数据模式的变化也变得越来越频繁，视图同 步的问题变得日益重要。 影响视图定义的源模式变化，可以归纳为两种基本类型： 重命名型变化：数据源的部分属性或关系被重命名。 删除型变化：数据源的部分属性或关系被删除。 维护重命名型变化，我们可以简单地通过使用新的名字修改视图定义中相关 部分来实现；而对于删除型变化，基表思想就是在数据源中找到其他的源，来代 替被删除的数据。文献【2 0 t2 1 1 将视图同步问题引入到了更为复杂的半结构化数据 中。这两篇文献考虑到了源模式变化更多的基本类型。比如：在半结构化数据中， 除了增加或删除元素外，我们还可以增加或删除约束，或者重构模式。值得注意 的是，视图维护处理并不要求重写的视图与原来的视图完全等价。这一点对于大 9 数据仓库中物化视图的选择与调整 规模的、动态数据源的信息集成显得尤为重要。当重写的视图与原视图不是完全 等价时，下一步的视图调整就很必要了。 视图调整 重写视图定义有两个原因：1 ) 用户想要隐式更新视图定义；2 ) 就是上文提 到的源模式的变化。 视图调整研究是基于视图同步工作的。在文献【2 2 】中，作者提出由于源模式的 变化可以导致视图定义失效，所以视图定义不得不随之调整。基于文献所提出 的方法，文献【2 4 1 一文作者提出一种视图调整技术：为基本类型的模式变化定义一 组调整规则，任何复杂的模式变化都可以转换为一组基本类型的模式变化。 从理论上来说，视图调整是视图维护问题的一种变化。不同的是：视图维护 是在源表变化以后维护视图的数据；而视图调整则是维护视图的定义。同时，视 图调整与使用视图回答查询也有密切关系。这是因为每个基本调整规则的导出， 都相当于视图重写。打个直观的比方：给定原视图和新视图，视图调整可以视为： 如何使用原视图回答新视图。 视图使用 一旦物化视图被创建并得到维护以后，下面的问题就是如何利用这些视图去 回答用户查询。视图使用就是说找出有效的方法，利用预定义的视图重写查询， 代替访问基表。 视图使用的核心由两部分技术组成：查询内容和查询重写。查询内容阶段， 检查视图是否包含足够的信息回答查询要求。查询重写，就是利用基于对查询信 息内容的检查所选出的视图，重写查询。 这两项技术在不同查询语言中，都得到了广泛的研究，比如s p j 查询2 5 1 、算 术比较预测查询2 6 1 、聚集查询【2 8 1 和最近的x p a t h 查询【2 9 】。查询重写技术还被研 究用于关联查询2 7 1 、多块查询【3 0 1 、半结构化数据查训3 、重构查询( 比如 s c h e m a s q l 3 3 1 ) 以及x m l 查询( 比如x q u e r y 3 2 】) 。 目前，关于使用视图回答查询的研究可以分为两大类： 第一类，主要是关于查询优化和维护物理数据的独立性。这类研究为了确保 l o 绪论 查询计划的正确性，只考虑等价查询重写。 第二类，主要是为了在一个更加松耦合的环境里进行信息集成。因此，这类 研究不仅考虑等价查询重写，也考虑包含查询重写。 视图选择 视图选择问题，就是在给定查询负载的情况下，选择一组视图进行物化操作， 从而达到最好的查询效率。通常，视图选择都会遵循一定的条件约束，比如：存 储空间的限制，或者维护开销的限制。 与视图使用问题需要处理即席查询不同，对于视图选择，查询是已知的。因 此，大部分视图选择算法都是从提炼众多查询中的公共表达式开始的。在视图选 择阶段，需要考虑许多可能的、相互制约的因素，比如空间、查询效率、更新效 率，等等。这增大了视图选择问题的难度。视图选择的另一大难题是，视图选择 是一个典型的静态过程。一旦查询负载改变，先前选择的视图，对于查询效率来 说，有可能不再是最佳的选择。因此，对于动态环境，增量视图选择算法和适应 性视图选择算法非常有必要。 1 4 国内外研究现状 1 4 1 物化视图静态选择算法 1 9 9 6 年，d r 。j i mg r a y 等人提出了数据立方模型和数据立方计算【m j 的概念， 从此，o l a p 服务器开始用数据立方体来组织多维数据集。基于数据立方的视图 选择算法也应运而生，它的特点是约束条件很强，更容易实现。g u p t a 把数据立 方体中的索引和视图选择结合起来考虑【3 5 1 。后来g u p t a 又介绍了视图选择问题的 一个理论上的框架，提出了一些算法和启发机制【3 6 3 7 1 。h a r i n a r a y a n 等人提出一 种多项式贪婪算法b p u s 3 8 】，它用数据立方格来表示视图间的依赖关系，以单位 空间收益作为判断的依据，按照单位空间收益的降序来选择视图。a m i ts h u k l a 等人提出了一种既简单又快速的选择方法p b s 3 9 】，同样用数据立方格来表示视 图间的依赖关系，依照聚合视图大小的升序来进行视图选择。j o s e p h 等人将遗传 算法的获取最优解的能力应用于最优物化视图集的选取m “，并在降低算法复 数据仓库中物化视图的选择与调整 杂度方面进行了研究。此外，还有c o h e n 等人提出的基于单位空间上查询频率的 算法f p u s 4 2 1 。以上这些算法都是在给定预计存储空间大小的限制下，选择一组 物化视图，最小化系统查询响应时间。然而，在实际应用中，仅仅从视图所占空 间大小这一限制条件着眼是不够的。随着数据存储技术的飞速发展，物化视图的 维护等其他方面的开销己逐渐代替存储空间，成为限制数据仓库不能物化所有视 图的主要因素。 基于上述考虑，文献【4 3 】提出了以物化视图总维护时间为约束条件的贪心算法 i t g a 。文献3 刀则结合与或图，贪心算法以及a 宰启发式算法探讨该问题的求解方 法。文献【4 4 】提出的代价模型考虑了使用不同视图维护策略而产生的最小维护代 价，然而，在该代价模型中，没有考虑这些视图的查询代价。r o s s 、s t r i v a s t a v a 和s u d a r s h a n ，b a r a l i s 、p a r a b o s c h i 和t e n i e n t e 等，t h e o d o r a t o s 和s e l l s 等，h a r i n a r a y a n 和r a j a r a m a n 等，y a n g 、k a r l a p a l e r m 和“等提出了几种视图选择的框架和启发 式算法【4 9 1 ，优化查询响应时间和视图维护时间。文献【删基于根据查询之间的 依赖关系构造的网络框架【2 】提出了一种结合遗传算法和模拟退火算法的混合算 法。在这些算法都使用穷举法进行搜索视图。其中，y a n g 和k a r l a p a l e m 提出构 造m v p p ( m u l t i v i e wp r o c e s s i n gp l a n ) 作为视图选择的搜索空间以获得最优解【4 j ； 文献【4 9 】在m v p p 的基础上，应用遗传算法求解；以上算法，都同时考虑了查询 代价和维护代价，但都将目光集中在获取最小代价的多查询最优化，而忽略了物 化视图维护策略的优化对这个问题的影响。 n a h a a 。r 。y o u s r i 和k h a l i lm 。a h m e d 同时考虑多查询优化和视图维护优 化这两个问题，提出了i r v s a 算法和i m d v s a 算澍删，但这两个算法都忽略存 储空间的约束。此外，i m d v s a 算法从物化视图的维护代价着眼，且只考虑使 用增量更新策略的情况；而i r v s a 算法虽然同时考虑两种维护策略，但其与 b p u s 算法主要缺陷相同：首先，其每一步选择都要重新计算所有待选择视图的 收益，算法的计算开销大；其次，其每一步选择的视图都将作为将来要物化的视 图，没有考虑每选择出一个新的视图后，已选视图的收益将出现衰减，而这一变 化可能会导致其应该从已选视图中删除。 1 2 绪论 1 4 2 物化视图的动态调整 由于数据仓库的时变性，特别是决策支持系统中存在较大成分的随机访问， 使得系统的查询分布情况难以预测，导致最初选择出来的物化视图集在系统运行 过程中逐渐失去时效性。因此，需要及时发现查询模式的变化，选择适当的时机 对物化视图进行动态调整，以确保系统的查询响应时问能满足用户的要求，使系 统性能保持最优。物化视图的动态调整涉及两个问题：如何选择进行物化视图动 态调整的最佳时机以及如何调整。 文献【5 1 ，5 2 1 都采用定期对物化视图集进行动态调整的策略，文酬5 3 1 通过对样 本空间内查询代价的数学期望和方差进行分析，判断用户查询分部情况的变化， 选择调整物化视图的时机，进行调整。这些方法都需要一定的统计周期，无法及 时地反映查询分布的变化。对此，f p u s 算法采用了实时调整的策略【4 2 】，能及时 地按照查询的变化或随机访问对物化视图集进行针对性的调整，但这样的策略， 在每次查询之后，都要对所有物化视图进行物化效益的比较，运行开销大，尤其 对于查询密度很高的情况下不适用。此外，采用实时调整的策略可能导致部分视 图出现频繁的“抖动”，使得物化视图集缺乏稳定性，也将使很多经过优化的查 询方案和优化路径不能重复利用，反而在一定程度上增加了查询开销，从而使该 算法失去真正的实用价值。 1 5 存在的问题 1 5 1 物化视图选择的负面因素 物化视图的数量越多，使用物化视图能够回答的查询就越多，从而越有利于 缩短系统响应查询的时间，提高效率。物化视图选择还要考虑很多负面因素，特 别是对于查询代价，存储代价，维护代价的考虑。因此，物化视图并不是越多越 好，物化所有的视图更是不可行的。不但会占用大量的存储空问，而且会有很大 的维护开销。但是，如果不采用任何物化措施，那么查询响应时间会很长，也不 可取。通常的做法是通过一定的算法，选择出部分的视图进行物化，来寻求一种 效率跟开销之间的平衡。在可以接受的开销内，达到最好的性能。 数据仓库中物化视图的选择与调整 l k l a x s p k t t l 缸c l t 亡n 1 2 ：耳r f n 3 l 、 卜n c l 譬 l t ：n c o n 1 5 2 静态物化视图选择的缺陷 静态物化视图选择算法具有以下共同的特点：在给定的查询下，给定存储空 间的限制下，选择出满足算法目标的视图集进行物化。算法的前提是己知查询， 针对于这个前提做出物化选择。使用静态选择算法选出的物化视图，是在对当前 用户查询非常了解的基础上选出来的，因而能够适应当前的查询，数据仓库对于 当前用户查询能快速响应，达到短期内提高o a l p 或d s s 性能的目的。但是， 静态选择视图集的方法与d s s 或o l a p 的动态本质相悖。 首先，用户查询的模式内容很难预料，对特别查询的支持程度差。例如高级 用户会对数据仓库提交一些难以预料的查询，以从大量历史数据中寻找他感兴趣 的结果。使用静态视图选择方法，很难预料到需要物化这样的查询，而这样的查 询往往都是复杂查询，需要对大量的数据进行运算，从基础数据直接查询会耗费 大量时间及系统资源。 其次当数据和查询模式随着时间发生变化时，物化视图集就过时了。数据仓 库存储大量的与时间相关的历史数据。对于发展迅速的现代社会，处在这样背景 下的企业从理念到业务都会发生r 新月异的变化。业务的变化直接就会导致数据 仓库中的数据发生变化，而且不仅仅是数据的更新操作，还有可能发生数据模式 的改变。多方面影响因素也有可能使得用户对数据仓库中的数据的兴趣点也会有 所转移。很明显，当这样情况发生时，静态算法选出的物化视图集就过时了。为 1 4 绪论 了适应这样改变，数据仓库管理员要监视查询模式并且阶段性地运行一下这些物 化视图选择算法，来重新计算物化视图。这对于一个拥有很多用户的大的数据仓 库来说，是非常复杂也是非常耗时的。而且即便通过这种方式，系统也很难及时 地适应改变。 最后，静态物化视图选择的一个与生俱来的缺点是系统没有办法调整一个错 误的物化选择。例如，物化的视图集不能够回答用户提交的查询。不能自调节， 需要不时的重新校正。因而，静态物化视图选择方法是一种特殊性的方法，它要 求事先明确查询，跟据查询来定制物化视图集。对于随着时问推移而发生的相关 改变不具有适应性。 1 6 本文的工作 本文基于s p j ( s e l e c t p r o j e c t - j o i n ) 视图假设的数据仓库模型，以m v p p 为 搜索空间，综合考虑存储空间、视图维护及查询性能，引入了新的物化视图维护 策略和调整策略，综合考虑视图维护开销，视图维护策略优化及查询性能，提出 一种新的物化视图选择和调整算法一v s a a ( v i e w ss e l e c t i o na n da d j u s t m e n t a l g o r i t h m ) 。在综合考虑动态调整算法中选择物化视图动态调整的最佳时机的不 同方法的优缺点之后，决定采用批量式调整与周期性调整结合的策略作为触发 v s a a 调整算法的方法，并针对该策略无法满足实时性要求较高的场合，本文提 出了d v m v 算法作为v s a a 的补充。 最后，采用t p c h 基准数据，1 g b 的数据构造并填充了一个o r a c l e 数据仓 库，然后经过理论与实验证明了v s a a 算法在视图选择与调整的有效性。 1 7 本文的组织结构 本文是按照下面的结构组织的： 第二章给出当前经典的多维物化视图的选择与调整算法，先是介绍多维物化 视图的收益计算模型，然后分析三个经典算法g r e e d y , y k l 及i m d v s a 的不同特 点。 第三章介绍v s a a 的理论基础，先是通过叙述物化视图选择中存在的负面 因素与及静态物化视图选择的缺陷引出v s a a 产生的意义。之后对v s a a 采用 1 5 数据仓库中物化视图的选择与调整 的数学模型进行介绍。最后，对v s a a 中几个关键参数进行分析。 第四章先是给出v s a a 算法的实现，然后通过理论和实验对v s a a 算法的 优越性进行了验证。 第五章对本文的工作做了一个总结，指出本文的不足，并对下一步的研究工 作进行展望。 1 6 经典物化视图的选择与调整算法 第二章经典物化视图的选择与调整算法 从多维数据集中选择视图进行物化能有效提高决策支持和o l a p 的查询响 应效率。一般有以下三种策略可供选择： 物化所有可能的视图。 显然，这种