（计算机软件与理论专业论文）数据仓库与联机分析处理技术研究.pdf

华中科技大学博士学位论文 摘要 数据库的广泛使用积累了大量历史数据，人们已不再满足于仅仅用数据库对业 务数据进行简单的处理，而渴望对这些历史数据进行各种分析，以辅助决策。传统 的数据库在事务处理方面的应用获得了巨大的成功，但它对分析处理的支持一直不 能令人满意，于是出现了数据仓库与联机分析处理新技术。数据仓库与联机分析处 理技术的应用范围十分广泛，包括金融、保险和政府部门等各行各业，可用于客户 关系管理和企业资源计划等多方面的决策分析。数据仓库能集成大量的异构数据， 而联机分析处理则分析数据中的趋势。，w 由于要对数据仓库中的大量数据进行分析，查询效率是一个关键问题。为此， 作者主要围绕数据仓库与联机分析处理中的稀疏数据立方计算和利用实化视图响 应查询两个关键技术进行了全面而深入的研究，并基于数据库管理系统d m 3 ，设计 和实现了一个数据仓库原型系统。具体研究内容表现在以下几个方面： 通过分析稀疏数据立方计算的一般方法和常用优化手段，提出了带约束关系的 稀疏数据立方计算问题，即当数据立方的各维之间存在函数依赖关系时数据立方的 高效计算问题。为了满足利用维之间存在的依赖关系快速计算的要求，提出了算法 c f d 。c f d 算法根据维的基数和维之间的函数依赖关系共同确定维的划分顺序，使 有依赖关系的维的划分顺序相邻，它们的编码满足单调映射关系，从而有效减少有 依赖关系的维的划分次数；c f d 算法还把自底向上的划分与自顶向下的聚集计算有 机结合起来，即从最细划分的聚集结果逐步累加得到较粗划分的聚集结果，进一步 加速了稀疏数据立方的计算。 分析研究了部分数据立方的计算问题，提出了p c c 算法。它通过动态调整部分 数据立方中各个g r o u pb y 的计算路径，即优先计算单元组出现概率大的g r o u p b y ，再减少其它g r o u pb y 计算时的划分次数，并结合裁减不必要的划分以及避 免不必要的聚集计算，充分利用了单元组优化和共享划分技术。p c c 算法可用于计 算基于数据立方的视图选择所得到的视图集合，以及符合s q l - 9 9 标准的 g r o u p i n gs e t s 算子。实验结果表明，对部分数据立方的计算，p c c 是一个高效 的算法。 研究了快速利用实化视图响应查询的问题，为了避免顺序扫描整个视图集合以 华中科技大学博士学位论文 找到所有可能响应查询的视图，先按使重写查询和初始查询保持等价的要求确定了 利用实化视图替代查询的条件，由此设计了一个内存索引一层次索引以尽快找出可 能用来响应查询的候选视图集合，层次索引的每一层由不同的视图替代条件组成， 其中的每个结点被标明它所在的层次号，并按先序遍历的方式被存储和加载，从而 避免每次系统启动时重构该索引，有效减少了系统启动时间；然后，提出了一个简 单的代价模型，并结合该模型提出了能更快找出较优重写查询的启发式算法h e u ， h c u 算法的时间复杂度是查询涉及关系数的平方；接着，提出了利用视图合并方法 以有效减少整个实化视图的数量，从而减少层次索引所需的内存空间、搜索时间以 及搜索得到的候选视图集合的大小，并且设计了一个内存索引一归并树和利用该树 的视图合并算法v m 来加快视图合并。少 设计了一个三层客户服务器结构的数据仓库原型系统d md w ，将稀疏数据立 方计算和利用实化视图响应查询等功能放在中间层的应用服务器中，并单独管理数 据仓库的元数据。 关键词：数据仓库：联机分析处理；数据立方；视图替代；层次索引；视图合并 华中科技大学博士学位论文 a b s t r a c t t h ea p p l i c a t i o no fd a t a b a s e sa c c u m u l a t e sl a r g ea m o u r so fh i s t o r i c a ld a t a p e o p l en o t o n l yn e e d d a t a b a s e st od os i m p l ed a t ao p e r a t i o n sb u ta l s on e e d a n a l y s e so f h i s t o r i c a ld a t a t os u p p o r td e c i s i o n d a t a b a s e sh a v ea c h i e v e dg r e a ts u c c e s si nt r a n s a c t i o n a lp r o c e s s i n g ， b u tt h en e d df o rd e c i s i o ns u p p o r th a sn o tb e e ns a t i s f i e d , s od a t aw a r e h o u s ea n do n l i n e a n a l y t i c a lp r o c e s s i n ga p p e a r e da sn e wt e c h n o l o g i e st 0s u p p o r td e c i s i o n d a t aw a r e h o u s e a n do n l i n ea n a l y t i c a lp r o c e s s i n gc a r lb eu s e di nf i n a n c e ，i n s u r a n c e ，g o v e r n m e n ta n ds oo n t od oc u s t o m e rr e l a t i o nm a n a g e m e n t ，e n t e r p r i s el s o u r c ep r o j e c t ，e t c d a t aw a r e h o u s e i n t e g r a t e sl a r g ea m o u n t so f h e t e r o g e n e o u sd a t aa n d o n l i n ea n a l y t i c a lp r o c e s s i n ga n a l y z e s t r e n d sf r o ms u c hd a t a b e c a u s ea n a l y s e sa r eo r i e n t e dt oam a s so fd a t ai nd a t aw a r e h o u s e ，t h ee f f i c i e n c yi sa k e yp r o b l e m s ot w ok e yt e c h n i q u e so f d a t aw a r e h o u s ea n do n l i n ea n a l y t i c a lp r o c e s s i n g ， i e c o m p u t a t i o no fs p a r s ed a t a c u b e sa n du s i n gm a t e r i a l i z e dv i e w st oa n s w e r q u e r i e s ，a r e s t u d i e d e x t e n d e d l y a n d d e e p l y a d a t aw a r e h o u s ep r o t o t y p ei sa l s o d e s i g n e d a n d d e v e l o p e d ，b a s e d o nn a t i o n a ld b m sd m 3 t h e p r i m a r y c o n t e n t sa r ea sf o l l o w s ： b y t h ea n a l y s i so fg e n e r a la p p r o a c h e sa n do p t i m i z a t i o n sf o rc o m p u t i n gd a t ac u b e s ，a p r o b l e mo fc o m p u t a t i o no fs p a r s ed a t ac u b e s w i t hc o n s t r a i n t si sp r o p o s e d t h ep r o b l e m i sw h e nt h e r ea r ef u n c t i o n a ld e p e n d e n c i e sb e t w e e nd i m e n s i o n s ，h o wt ou s et h e mt o e x p e d i a t et h ec o m p u t a t i o n an e wa l g o r i t h mc f d i sp r e s e n t e dt os a t i s f yt h i sd e m a n d c f dd e t e r m i n e st h ep a r t i t i o n i n go r d e rb yc o n s i d e r i n gt h ec a r d i n a l i t i e so fd i m e n s i o n sa n d t h ef u n c t i o n a ld e p e n c i e sb e t w e e nd i m e s i o n st o g e t h e r , a n dm a k e sd i m e s i o n s w i t h f u n c t i o n a l d e p e n d e n c i e sa d j a e e u t i nt h e p a r t i t i o n i n g o r d e ra n dt h ec o d e so fs u c h d i m e n s i o n ss a t i s f yt h em o n o t o n i cm a p p i n g ，t h u sr e d u c et h ep a r t i t i o n i n gt i m e so fs u c h d i m e n s i o n s c f da l s oc o m b i n e st h ep a r t i t i o n i n gf r o mb o t t o mt ou pa n dt h ea g g r e g a t e c o m p u t a t i o n f r o mt o pt ob o t t o m ，i e c o m p u t e sc o a r s e rp a t i t i o n sf r o mt h et h i n n e s t p a r t i t i o n s ，s oe x p e d i a t e t h ec o m p u t a t i o n o f s p a r s ed a t a c u b e sf u r t h e r c o m p u t a t i o no fp a r t i a ld a t ac u b e si ss t u d i e da n dt h ea l g o r i t h mp c c i sp r e s e n t e d i n o r d e rt ou s e s u f f i c i e n t l y t h e a p p r o a c h e s o fs i n g l e - t u p l e o p t i m i z a t i o n a n d s h a r i n g p a r t i t i o n s ，p c cd y n a m i c a l l ya d j u s t st h ep a r t i t i o n i n gp a t h o fg r o u p b y s ，i e c o m p u t e s 华中科技大学博士学位论文 t h o s eg r o u pb y sw i t h s i n g l e - t u p l eo p t i m i z a t i o nf i r s ta n dt h e nc o m p u t e so t h e rg r o u p b y s b yr e d u c i n gt h ep a r t i t i o n i n gt i m e s p c ca l s op r u n e st h o s eu r m e s s a r y p a r t i t i o n sa n d a v o i d su n n e s s a r yc o m p u t a t i o n s p c cc a l lb eu s e dt o c o m p u t e 趾s q ls t a t e m e n to f g r o u p i n gs e t st h a ts a t i s f i e st h es t a n d a r do fs q l 9 9o rt h o e sm a t e r i a l i z e dv i e w s s e l e c t e db a s e do nad a t a c u b e e x p e r i m e n t sh a v es h o w n 也a tp c ci s a ne f f i c i e n t a l g o r i t h mt oc o m p u t e a p a r t i a ld a t a c u b e i no r d e rt ou s em a t e r i a l i z e dv i e w st oa n s w e raq u e r yf a s ta n da v o i ds e q u e n t i a l l ys c a n 也ew h o l ev i e ws e tt of m dm a t c h e dv i e w sf o rs u b s t i t u t e ，am e m o r y i n d e x ，i e 1 e v e li n d e x ， i sp r e s e n t e dt of a s tn a r r o wt h es e a r c hs p a c eo f p o t e n t i a lu s e f u lv i e w s e v e r yl e v e lo f s u c h a ni n d e xi sc o m p o s e do fd i f f e r e n ts u b s t i t u t ec o n d i t i o n s ，a n de v e r yn o d ei sm a r k e dw i m t h en u m b e ro ft h el e v e l l e v e li n d e xc a n nb es t o r e da n d1 0 a d e d s od o e sn o tn e e dt ob e r e c o n s t r u c t e dw h e nt h es y s t e ms t a r t sn e x tt i m e t h e nas i m p l ec o s tm o d e li sp r e s e n t e d a n dah e u r i s t i ca l g o r i t h mu s i n gt h a tm o d e l ，h e u , i s p r o p o s e d t oc h o o s eab e t t e r - r e w r i t t e n q u e r y f a s t t h et i m e c o m p l e x i t yo fh e ui s t h e s q u a r e o ft h en u m b e ro fr e l a t i o n s r e f e r e n c e db yt h eq u e r y a na p p r o a c ho fm e r g i n gv i e w si sa l s op r e s e n t e dt oe f f i c i e n t l y r e d u c et h ew h o l en u m b e ro fv i e w s ，s oa st or e d u c et h em e m o r yn e e d e d ，t h es e a r c h i n g t i m en e e d e da n dt h ec a n d i d a t ev i e ws e tg o tb yt h el e v e li n d e x i no r d e rt oe x p e d i a t ev i e w m e r g i n g ，am e m o r yi n d e x ，i e m e r g i n gt r e e ，i sd e s i g n e da n d a na l g o r i t h mv m u s i n gt h a t t r e ef o rv i e w m e r g i n g i sp r e s e n t e d ad a t aw a r e h o u s ep r o t o t y p en a m e dd md w i nt h r e e - t i e rc l i e n t s e r v e ra r c h i t e c t u r ei s p r o p o s e d t h ec o m p u t a t i o no fs p a r s ed a t ac u b e sa n du s i n gm a t e r i a l i z e dv i e w s t oa n s w e r q u e r i e sa r ei n t e g r a t e dt ot h em i d d l et i e r , t h ea p p l i c a t i o ns e r v e r t h em e t a - d a t ao f d a t a w a r e h o u s ei sm a n a g e ds e p a r a t e l y k e y w o r d s ：d a t aw a r e h o u s e ；o n l i n ea n a l y t i c a lp r o c e s s i n g ；d a t ac u b e ；v i e ws u b s t i t u t e ； l e v e li n d e x ；v i e wm e r g i n g - 华中科技大学博士学位论文 1 1 研究背景、目的和意义 1 绪论 早在上个世纪6 0 年代，人们为了收集、存储和处理大量业务数据而开发了数 据库管理系统( d b m s ) ，数据库系统的开发和应用为企业处理各种业务数据提供了 强大的工具和极大的便利。也正是因为这样，在过去几十年中，数据库系统得到了 迅速地发展和应用。传统的信息处理是以数据库为中心，进行事务处理、批处理到 决策分析等各种类型的数据处理工作。 在信息化时代来临、i n t c m e t 高速发展的今天，信息资源的经济价值和社会价值 越来越明显，人们需要对大量的信息处理进行各种复杂的分析。另外，随着数据库 存储的数据越来越多，人们已经不再满足于仅仅用数据库系统来保存业务数据和对 数据进行简单的处理，还要求对企业活动的历史数据进行各种分析，如多维分析、 长期趋势分析和数据挖掘等，以发现企业的业务趋势并辅助决策。传统的数据库在 事务处理方面的应用获得了巨大的成功，但它对分析处理的支持一直不能令人满 意，在这种情况下，数据仓库与联机分析处理技术应运而生。 1 1 1 数据仓库与联机分析处理 联机事务处理( o n l i n et r a n s a c t i o n a lp r o c e s s i n g ，o l t p ) 是为企业发生的业务进行 记录而设计的数据处理系统，它的特征是许多并发用户动态地添加和修改数据。 o l t 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 a p ) 系统，用于对企业的业务数据进行各种分析。 o l a p 的概念最早是由关系数据库之父e f c o d d 针对决策分析提出的，他还提 出了o l a p 的1 2 条规则【”。根据人们对o 乙心产品的实际需求，o l a p 可以简单地 定义为共享多维信息的快速分析 2 1 。o l a p 系统进行数据组织和提供查询工具，目 的是发现影响企业发展的关键因素。一般来说，o l a p 系统具有快速、可分析和多 华中科技大学博士学位论文 维等特点。 当以业务处理为主的联机事务处理应用与以决策支持为主的联机分析处理应 用共存于同一个数据库系统时，这两种类型的处理发生了明显的冲突。人们逐渐对 数据处理的这种多层次性有了清晰的认识，把数据处理分为两大类：操作型处理和 分析型处理，并开发了数据仓库技术支持分析处理。数据仓库的经典概念由w h i _ r l y l l o n 提出 3 1 ：“数据仓库是9 0 年代信息技术构架的新焦点，它提供集成化和历史 化的数据，它集成种类不同的应用系统，它从事物发展和历史的角度来组织和存储 数据，以供分析处理之用。”数据仓库具有以下四个最基本的特点： 1 面向主题( s u b j e c t - o r i e n t e d ) ：即它是面向企业的主题，如客户、产品等，而 不是传统的面向过程。 2 集成性( i n t e g r a t e d ) ：数据从面向应用的操作环境中提取到数据仓库中都要经 过集成化，如一致的数据属性、一致的编码结构等。 3 时间变异性( t m a e v a r i a n t ) ：在数据仓库中，数据记录总含有一个时间属性， 记录了数据随时间变化的历史。 4 稳定性( n o n - v o l a t i l e ) ：数据仓库只有装载数据和访问数据两种基本操作，因 此数据是相对稳定的，其修改和重组由管理员定期后台实现。 当前绝大多数企业内的应用和数据都是分散的，而数据库是一种单一的数据资 源，难以将异构数据有效集成。要提高决策分析的效率和有效性，必须把数据从事 务处理环境中提取到数据仓库，按照分析处理的需要进行重新组织，建立单独的分 析型环境。数据仓库的数据来源于业务数据库和其它数据源，如e x c e l 文件、遗留 系统( 1 e g a c ys y s t e m ) j f l lw e b 站点等。数据仓库中的数据比企业数据库中的数据更多、 更复杂。 数据库环境不适宣决策分析应用的原因主要有四点 1 - 9 1 ： 1 事务处理和分析处理的性能特性不同。在事务处理环境下，用户的行为特点 是数据的存取操作频率高而每次操作处理的时间短：在分析处理环境下，用户通常 对大量的数据进行查询和聚集，因此将两种截然不同的应用放在同一环境中显然是 不合适的。 2 数据集成问题。由于业务处理的分散，当前绝大多数企业内的数据是分散而 非集成的，为了决策分析的完整和可靠，数据仓库要尽量收集来自不同方面的数据。 3 历史数据问题。事务处理一般只需要当前数据，在数据库中通常也是存储短 一 2 华中科技大学博士学位论文 期数据，保留历史数据会影响数据库的性能，而数据仓库则需要保存历史数据，并 对它们进行分析。 4 数据的综合问题。事务处理一般针对细节数据，而数据仓库要对细节数据进 行不同程度的综合，并允许有冗余的存在。 将数据库系统直接用于决策分析，会产生很多问题。通过数据仓库技术重新组 织数据，可以克服数据库系统所存在的问题，采用数据仓库进行决策分析的优点有： 1 可以将异构数据源中的数据组合成一种单一的同类结构。 2 采用有效的结构组织数据，目的是提高分析查询的效率，而不是事务处理。 3 提供代表业务历史记录的稳定数据。 由于数据仓库的数据量非常大，而人们的决策分析往往是面向一个主题的，即 对数据仓库的一个子集进行分析，这就是数据集市。数据集市与o l a p 服务器对应， 它常把多维数据看成数据立方a t ac u b e ) v 以直观支持复杂多维分析，数据立方的每 个小方可看作一个带聚集函数的视图。o l a p 查询涉及在大量数据上的复杂查询， 而响应时间又要快，因此查询效率十分关键。提高效率的一个常用的和有力的方法 是将这些小方部分或全部加以实化，而不是每次都从原始数据计算它们。一个完整 的数据立方可能很大，它的保存受到计算机存储空间的限制，因此我们常预先计算 部分小方，即一些维上的聚集，以便在回答有关查询时，可以直接使用这些聚集数 据，从而提高查询响应速度。对于基于大规模数据集的数据立方而言，预先选择一 些关键聚集进行实化，对于o l a p 性能改善具有重要的作用。 1 1 2 研究的目的和意义 数据仓库与联机分析处理技术是信息领域中近年来迅速发展起来的数据库新 技术。数据仓库的建立能充分利用已有的数据资源，把数据转化为信息，进行分析 处理，从中挖掘出知识，辅助决策，最终创造出效益。随着人们对决策支持系统日 益增长的需求，数据分折市场在过去的几年中成长迅速，吸引了众多的数据库厂商 投身其中，一些著名的数据厂商纷纷在传统的数据库上增加了数据仓库功能，推出 了它们的联机分析处理服务器，如m ss q ls e r v e r2 0 0 0 的o l a ps e r v e r ，i b m d b 2 的o l a fs e r v e r7 2 和o r a c l e9 i 的e x p r e s ss e r v e r 等。但这一具有广阔前景 的新一代决策支持系统，在我国的应用尚处于起步阶段，面对国内越来越大的数据 华中科技大学博士学位论文 分析市场，对于我们的国产关系数据库管理系统d m 3 来说，开发数据仓库功能和 联机分析处理工具是十分必要的。 数据仓库的应用范围十分广泛，包括金融、保险和政府部门等各行各业，可用 于客户关系管理和企业资源计划等方面的决策分析。其中，建立电子化政府，推动 电子政务的发展，是电子信息技术应用到政府管理的必然趋势，实践经验表明，政 府部门的决策越来越依赖于对数据的科学分析。发展电子政务，建立决策支持系统， 利用电子政务综合数据库中存储的大量数据，通过建立正确的决策体系和决策支持 模型，可以为各级政府的决策提供科学的依据，从而提高各项政策制定的科学性和 合理性，以达到提高政府办公效率、促进经济发展的目的。因此在政府决策支持方 面，需要不断吸纳新的信息处理技术，而数据仓库与联机分析处理正是实现政府决 策支持的核心技术，以此为依托的建立的政府决策支持系统，将发挥重要的作用。 在华中科技大学数据库与多媒体技术研究所承担的科技部电子政务工程中，科 技部信息数据仓库需要提供整个科技部内的面向主题的、集成的、稳定的的数据集 合，搭建面向决策支持的数据环境，并支持决策分析。因此，本文的主要研究目标 是跟踪国外发展动向，为研发基于国产数据库d m 3 的数据仓库系统d m _ d w 进行 相关的技术研究，构造一个通用的决策支持平台，提高电子政务系统的分析效率。 1 2 国内外研究概况 数据仓库与联机分析处理涉及了数据库、决策分析、结果展现等多方面的理论 和技术，本文主要围绕数据仓库与联机分析处理的两个关键技术，即稀疏数据立方 计算和利用实化视图响应查询进行了研究，因此重点介绍它们的研究情况。 1 2 1 数据立方计算 自从j i mg r a y 等人于1 9 9 6 年提出c u b e 算子【1 0 】概念以来，高效的数据立方 计算方法一直是一个研究的重点 1 l - s 2 j ， 数据立方中的数据存储有多维型 ( m m t i d i i n e l l s i o i l a l ) 和关系型( r e l a t i o i l a l ) 两种不同的方法，相应地。我们可以将数据 立方计算方法分为多维数据立方计算方法和关系数据立方计算方法两类。 j i mg r a y 在给出c u b e 算子的同时，还给出了一个多维数据立方计算方法 m e m a r r a y c u b e ，a r r a y c u b e 算法i l l 】是第一个比较实用的多维数据立方计算方法，它 一一 华中科技大学博士学位论文 采用了多维数组的分块机制和复杂的主存管理机制，大大减少了对于主存的容量要 求，另外m u t o 等人还对a r r a y c u b e 算法进行了改进【也】。尽管多维数据立方计算方 法采取了种种措施来减少主存需求和提高计算速度，但是如果数据立方很稀疏，使 得每一个块中非空单元太少，将导致计算效率过低，不能满足实际的需要。 i b ma l m a d e n 研究中心和w i s c o n s i n m a d i s o n 大学的研究人员总结了数据立方 计算的各种可能的优化技术【”4 5 1 ，提出了p i p e s o r t 算法、p i p e h a s h 算法和o v e r l a p 算法。其中，p i p e s o r t 算法是第一个使用立方格图描述数据立方计算问题的算法， 基于立方格图描述数据立方计算的问题被后来的数据立方计算算法所广泛接受。 p i p e s o r t 算法是基于代价和排序的流水线型算法，它主要结合了“最小父母”、“缓 存结果”和“批处理”三种优化方法。 p i p e h a s h 算法基于代价、散列( h a s h ) 和划分的思想计算数据立方，它主要结 合了“最小父母”、“缓存结果”、“批处理”和“共享划分”四种优化方法。在p i p e h a s h 算法中，基于属性划分立方格图的技术被首次采用。o v e r l a p 算法是一个基于排序 的流水线型算法，该算法主要结合了“共享划分”和“共享排序”两种优化技术。 o v e r l a p 算法是第一个固定立方格图中维顺序的数据立方计算方法。 p a r t i t i o n e dc u b e 算法【】6 】是一个分而治之，基于代价的流水线型算法，它主要结 合了“共享排序”、“共享划分”和“缓存结果”三种优化技术，是第一个适合于计 算稀疏数据立方的算法。b u c 算法【1 7 】是一个基于排序和划分，自底向上计算的数 据立方计算方法。b u c 算法自底向上地计算各个g r o u p b y 首先计算一个维上的 g r o u pb y ，然后计算两个维上的g r o u pb y ，如此等等。b u c 算法是第一个自 底向上计算数据立方的算法，自底向上的计算使得b u c 算法可以采用共享划分的 优化技术，并结合了特别适合于稀疏数据立方计算的单元组优化方法。 数据立方计算是一个复杂的操作，需要消耗大量的计算机资源，并行则是提高 数据立方计算的效率和对付不断增长的数据立方尺寸的有效方法【1 9 。2 ”。每一种立方 计算方法都有相应的并行算法，如并行a r r a y c u b e 算法1 2 0 和并行b u c 算法1 2 1 等。 在稀疏数据立方计算方面，作者提出了一个带约束条件的稀疏数据立方计算问 题，并且提出了相应的高效计算方法c f d 【l ”。 对于大规模数据立方，它所需要的存储空间非常大，因此还有一部分数据立方 计算方法着重于压缩数据立方的尺寸 2 4 m 】。有些算法通过不同的压缩形式来近似 个数据立方，如小波f 2 7 】，多变量多项式 2 8 1 ，采样1 2 9 3 0 1 ，以及数据概率分布【3 1 】等。 5 华中科技大学博士学位论文 另一些算法则压缩和保存完整的数据立方，w a n g 和f e n g 等人首先提出了压缩的数 据立方c o n d e n s e dc u b e 及算法m i n i c u b e l 2 4 1 ，d w a r f 算法【2 5 】提出了一个用于计算、 存储和查询的高度压缩的数据结构，q u o t i e n tc u b e 侧重于在压缩时保持数据立方格 原有的语义酬，b a r b a r a 等人则提出用线性模型压缩数据立方【3 2 1 。但是，数据立方 压缩后的范围查询仍是一个需要研究的问题。 自从c o d d 等人提出了联机分析处理以来，联机分析处理模型也一直受到人们 的重视【3 3 - 4 2 1 ，c h e n 等人较早提出了汇总数据管理的模型和存取方法1 3 3 】，l i 等人提 出了一个联机分析的模型p 4 】，g y s s e n s 等人以及a g a r w a l 等人研究了多维数据库的 模型和查询【3 5 ，3 6 】，l i b k i n 等人提出了一种多维数组的查询语言1 3 7 ，d a t t a 等人、 p o u r a b b a s 等人以及z i r k e l 还研究了c u b e 算子的代数表示和运算 3 8 - 4 0 】。另外， v a s s i l i a d i s 等人总结了现有的联机分析模型【4 ”。在国内，李建中等人以偏序和映射 为基础，提出了一种新的多维数据模型，该数据模型能够充分表达数据仓库的复杂 数据结构和语义，并提供一个以o l a p 操作为核心的操作代数，支持层次结构间的 复杂聚集操作序列1 4 a 。 为了加快数据立方的查询，r o u s s o p o u l o s 等人提出了c u b e t r e e 这一经典的索引 结构用于索引数据立方【4 3 1 ，j o h n s o n 等人提出了数据立方索引的一些方法【“，4 5 1 。数 据挖掘是目前研究的热门问题i “”】，s a r a w a g i 等人以及( o i l 等人研究了基于数据立 方，结合经典的数据挖掘方法如何进行多维分析【4 8 。”】，提出了数据立方梯度的概念。 1 2 2 利用实化视图响应查询 在联机事物处理( o l t p ) 系统中，查询具有高度的选择性，并且此类查询通常不 需要扫描大量的数据。与此相反，数据仓库的查询是典型的聚集查询，通常要扫描 大量的数据，并且这些查询还经常包含重复的成分，如果所有的查询都从原始数据 进行计算，那么响应速度会很慢，而人们通常所能忍受的晦应时间是非常短的，因 此必须对查询进行优化。r a l p hk i m b a l l 指出【4 j 。“影响一个大型数据仓库性能的唯 一的戏剧性的方法是提供一组适当的聚集实化视图。”i n m o n 也提出警告【9 】，“聚集数 据的问题在于它也许不能为分析提供适当级别的粒度。”实化视图技术是解决该问题 的有效手段，它把查询结果保存起来，以供多次使用，从而提高总体的查询效率1 5 粥”。 实化视图是相对于普通视图( 即虚视图) 而言的，它是存储了实际数据的视图。 - 6 华中科技大学博士学位论文 实化视图有两个主要的应用领域：一是在数据库中可以加快查询的处理速度； 二是在数据仓库中用于回答决策查询，尤其是需要处理大量数据的聚集查询，国外 的数据库和数据仓库系统都在研究如何利用实化视图提高查询处理的效率【5 2 “】。决 定什么时候和怎样利用实化视图来处理一个给定的查询是一件困难的工作。目前己 提出的利用实化视图响应查询算法的不同点在于：能支持的查询和实化视图的种类， 替代表达式的种类，怎样处理多个替代表达式，是否考虑重复元组等。有些算法考 虑了实化视图比查询有多余表的情a t 5 2 - 5 5 1 ，而有些则要求视图响应查询时，它们有 相同的表集 5 6 5 8 】；有些算法将利用视图响应查询结合到查询优化中5 6 1 ，而有些只 考虑了如何找出重写查询口7 科】。 利用实化视图来加速决策支持查询的处理是一个很早以前就有的想法胪9 j 。但只 到最近几年才在数据仓库系统中采用这一思想。最近的t p c - r 基准测试和实际的用 户经验表明，正确使用实化视图可以使查询处理时间改进几个数量级。为了实现实 化视图的潜在好处，需要关于以下三个问题的有效解决方案： 1 视图利用：有效地使用实化视图来加速查询处理。 2 视图选择：决定实化哪些视图，包括如何存储和索引它们。 3 视图维护：当基表发生变化时，有效地维护实化视图。 要想利用视图响应查询，首先应解决视图替代问题。视图替代( 匹配) 就是利 用实化视图代替查询的某个子表达式，它可以看作查询优化中的个转换规则。目 前文献中提出的解决视图替代问题的算法在如下几个方面有所差别： 1 所考虑的查询表达式的类型。 2 所支持的实化视图类型。 3 所考虑的替代表达式类型。 4 是否和怎样处理多个替代表达式。 5 基于包语义还是集语义。 6 是否利用了某种约束。 但是视图替代算法只解决了优化问题的一部分，这个算法必须集成到整个的优 化处理之中，以便生成所有利用视图的合法重写，并且和没有利用视图的原始查询 按相同的方法进行代价估算。有些利用视图优化查询的文章完全忽略了这方面的问 题，有些则只考虑了找出所有合法的重写，有些则提出了利用启发式规则来选择一 个最好的重写。 华中科技大学博士学位论文 l a r g o n 和y a n g 首次描述了关于s p j 查询与s p j 视图的视图匹配算法【铷，他们假设 了集语义，考虑了单个表的替代，而没有考虑约束。在文献【6 0 】中，l a r s o n 和y a n g 将他们的算法扩展到考虑由多个视图的连接构成的替代，但没有讨论怎样选出最好 的重写。s r i v a s m v a 等人提出了一个关于s p j g 查询与视图的视图匹配算法【5 引，他们考 虑了包语义但没有考虑约束，他们考虑了选择谓词的包含，但没有详细描述如何进 行比较，除了单视图替代( s i n g l e - v i e ws u b s t i t u t e s ) ，他们还考虑了由视图的联合所构 成的替代( 仅对s p j 视图) ，但他们要求视图和被替代的表达式引用相同的表，也没 有讨论怎样在多个重写中进行选择。c h a n g 和l e e 认识到即使一个视图包含了多余的 表，它仍有可能用于重写查询睁”。 l e v y 、m d e l z 和s a g i 研究了利用视图重写s p j 查询的算法复杂性问题【6 7 l ，并 且证明许多相关问题是n p - e o m p l e t e l b 7 题，即使是对一个最简单的问题，如确定一个 不含嵌入谓词( b u i l t - i np r e d i e a t e s ) l 拘连接查询( c o n j u n c t i v eq u e r y ，o p w h e r e 子句仅由列 等价谓词和一个列等于一个常量的谓词组成) 是否存在一个重写。g u p t a 等人介绍了 一个一般化的投影操作符【5 刀，它可以把消去重复( d u p l i c a t ee l i m i n a t i o n ) 、聚集、分组 和重复保t l ( d u p l i c a t e - p r e s e r v i n g ) 等操作放在一个统一的架构下，但他们没有考虑分 组表达式和选择谓词( b p w h e r e 条件) 。 一个查询的分组列必须是一个视图的分组列的子集，这一条件是充分的但不是 必要的。y a h 和l a r s o n i 正明视图的分组列函数地决定查询的分组列是充分的l 叫，这一 特点在o l a f 环境下是重要的，因为在一个维层次下较低层函数地决定维的较高层。 p a r k 、k i m 和l e e 利用这些函数依赖关系定义了o l a p 查询和视图之间的偏序关系 ( p a n i a lo r d 盯) ，印格( 1 a n i c e ) ，从中观察到的一个关键点在于：一个视图可能是有用 的，只有当它和查询在格的同一层或比查询的层次低，他们的算法可能会生成包括 联合与连接的替代( s u b s t i t u t e ) ，他们利用启发式规则来选择最好的重写，但没有报告 实验结果i 。 c h a u d h u r i 等人首次提出把实化视图的使用结合到查询优化中1 5 6 】处理基于集语 义的s p j 查询和视图，由于采用穷举的方法寻找最佳替代，因此查询优化的时间迅速 而且增长，他们的匹配算法没有考虑选择谓词和约束。 o r a c l e 是第一个支持实化视图的商用数据库系统【5 孤，视图包含了连接和聚集， 但没有选择条件，算法考虑了利用一个实化视图替代一个p s j g 查询的部分或全部， 并且也考虑了通过基数保持( c a r d h m u t yp r e s c r v i n g ) 连接了多余表的视图以及维层次 ；穗虢5 华中科技大学博士学位论文 之间的函数依赖关系，并用启发式方法选择最优执行代价的重写查询。z a h a r i o u d a k i s 等人描述了在i b md b 2u d b a 执行的视图替代算法掷j ，i , a r s o n 等人描述了在 m i c r o s o f ts q ls e r v e r 上利用实化视图响应查询的算法【s 4 j 。 利用实化视图响应查询的技术还可以用在其它的查询处理上。例如，查询结果 可以缓冲起来用来响应后面的查询【6 9 7 2 】，这些被缓冲的结果可以看作临时的实化视 图；在数据集成环境下，也可以利用实化视图来处理查询 7 3 , 7 5 】。 利用实化视图响应查询时，还需要用到查询优化的相关技术。在查询优化的策 略方