（计算机应用技术专业论文）基于olap的数据仓库索引技术研究.pdf

摘要 数据仓库索引技术是基于传统数据库索引技术发展起来的数据 仓库查询优化方法。数据仓库索引技术主要有树形索引和位图索引两 种方法。本文就这两种索引结构的主要特点，应用范围和发展前景作 了一些深入的探讨和研究，为这两种数据仓库索引技术的广泛应用奠 定基础。 树形索引结构是适用于高基数维属性的索引技术，r 一树索引基于 传统b 一树索引技术而发展成为主流的数据仓库多维索引结构，具有 结构简单、易于维护及适用范围广等优点，缺点是索引子空间重叠数 据过多，导致查询路径失效，影响查询性能。四叉树是用超平面的方 法来组织索引结构的一类索引机制，具有查询速度快，插入和删除操 作简单方便的优点。q r 一树索引结合四叉树和r 一树的各自优点，既可 以满足较高的存储效率，又避免太多的无效查找，达到较好的查找性 能。为此，我们在这里特别讨论数据仓库的一种新型多维索引- - q r - 树索引，分析其多维索引结构的特点，给出其插入，删除及查询操作 伪码算法，并与r 一树索引的操作性能进行比较，实验证明，q r 一树索 引是一种比较理想的多维索引结构，将会有良好的发展应用前景。 位图索引是另外一种比较重要的数据仓库索引技术，主要基于二 进制逻辑运算的简化操作来达到查询优化的目的。位图索引的主要特 点是查询效率比较高，实现起来比较简单，具有很强的可操作性。主 流的位图索引技术是分段位图索引，分段索引降低了索引存储的空间 开销，但也增加了扫描位图的个数，为了平衡这两者之间的矛盾，可 以采用二进制逻辑运算的合并简化操作来实现优化查询的目的。本文 就位图索引的成员查询合并简化算法作了一些改进，使得算法的效率 得到了一定程度的提高，实验证明，算法的改进有效地优化了查询过 程，取得了预期的效益。 总的来说，数据仓库的索引技术还是一个比较新的课题，r 一树索 引和位图索引各有所长，综合这两种索引的特点而设计的混合索引也 有比较好的查询性能，是一种适用性很广，很有发展前途的索引技术。 关键词数据仓库，树形索引，位图索引，联机分析处理 a b s t r a c t d a t aw a r e h o u s ei n d e x t e c h n o l o g y i sad a t aw a r e h o u s e q u e r y o p t i m i z a t i o n m e t h o dd e v e l o p i n gf r o mt h et r a d i t i o n a ld a t a b a s ei n d e x t e c h n o l o g y d a t aw a r e h o u s ei n d e xt e c h n o l o g ym a i n l yi n c l u d e st r e ei n d e x a n db i t m a pi n d e xt w om e t h o d s t h i sa r t i c l eh a sd o n es o m ed e e p d i s c u s s i o na n dr e s e a r c hw o r k sa b o u tm a i nf e a t u r e ，a p p l i c a t i o na r e aa n d d e v e l o p m e n tp r o s p e c to ft w oi n d e xs t r u c t u r e st h e o r e t i c a l l yf o u n d i n gt h e w i d ea p p l i c a t i o no ft w oi n d e xt e c h n o l o g i e s t r e ei n d e xs t r u c t u r ei ss u i t a b l ef o rh i g h c a r d i n a l i t yd i m e n s i o n a t t r i b u t e ，r t r e eb e c o m e sm a i n s t r e a md a t aw a r e h o u s em u l t i d i m e n s i o n i n d e x s t r u c t u r e ， a n di t s a d v a n t a g e i n c l u d e s s i m p l es t r u c t u r e ，e a s y m a i n t e n a n c e ，w i d e - a p p l i c a t i o na r e a ，i t sd i s a d v a n t a g ec o v e r st h a ti n d e x s u b s p a c e d a t a s u p e r p o s e sr e d u n d a n c y a n dl e a d st o q u e r yp a t h s i n v a l i d a t i o n ，i n f l u e n c i n gt h eq u e r ye f f i c i e n c y q u a d t r e eo r g a n i z e si n d e x s t r u c t u r eb yt h ew a yo f s u p e r - p l a n e ，a n dp o s e st h ea d v a n t a g eo ff a s tq u e r y s p e e d ，c o n v e n i e n t i n s e r t i o na n dd e l e t i o n e x e c u t i o n q r - t r e ei n d e x c o m b i n e st h ea d v a n t a g eo fq u a d t r e ea n dr - t r e e ，n o to n l ys e r v e st h en e e d o fh i g hs t o r i n ge f f i c i e n c y , b u ta l s oa v o i do fm a n yi n v a l i d a t i o nq u e r y , i n o r d e rt oa c h i e v eg o o dq u e r yc a p a b i l i t y h e n c e ，h e r ew ee s p e c i a l l yd i s c u s s an e wd a t aw a r e h o u s em u l t i - d i m e n s i o nq r - t r e ei n d e x ，a n da n a l y z et h e f e a t u r e so ft h i si n d e x ，o f f e rt h ee x e c u t i o na l g o r i t h m so fi n s e r t i o n ，d e l e t i o n ， q u e r yo p e r a t e ，m a k eac o m p a r i s o nw i t ht h eo p e r a t i o np e r f o r m a n c eo f r - t r e e a c c o r d i n gt oe x p e r i m e n tr e s u l t ，q r t r e ei n d e xi s a ni d e a l m u l t i d i m e n s i o ni n d e xs t r u c t u r ea n dw i l lh a v eag o o d a p p l i c a t i o n p r o s p e c t b i t m a pi n d e xi sa n o t h e ri m p o r t a n td a t aw a r e h o u s ei n d e xt e c h n o l o g y , a n de x e c u t e st h es i m p l i f y i n gb i n a r yl o g i co p e r a t i o ni no r d e rt oo p t i m i z e t h eq u e r y t h em a i nf e a t u r eo fb i t m a pi n d e xi s h i g hq u e r ye f f i c i e n c y , e a s yi m p l e m e n ta n dg o o dm a n i p u l a t e s s e c t i o n - b a s e db i t m a pi n d e x ，a s t h em a i n s t r e a mb i t m a pi n d e xt e c h n o l o g y , l o w e r st h es p a c ep r i c eo fi n d e x s t o r i n g ，b u t a d dt h en u m b e ro fs c a n n i n g i no r d e rt ob a l a n c et h e c o n t r a d i c t i o no ft w on c m r s ，w ec o u l du s et h ec o m b i n a t i o no p e r a t i o no f i i b i n a r yl o g i co p t i m i z i n gc a l c u l a t i o nt oi m p r o v et h eq u e r yo p t i m i z a t i o n t h i sa r t i c l em a k e ss o m ei m p r o v e m e n tt om e m b e r s h i p q u e r yc o m b i n a t i o n s i m p l i f y i n ga l g o r i t h m sa n de n h a n c e st h ea l g o r i t h m se f f i c i e n c yt os o m e e x t e m v e r i f i e db yt h e e x p e r i m e n t t h ei m p r o v e m e n to fa l g o r i t h m s e f f i c i e n t l yo p t i m i z e st h ep r o c e d u r eo fq u e r ya n da c h i e v e st h ee x p e c t e d g o a l o nt h ew h o l e ，t h ei n d e xt e c h n o l o g yo fd a t aw a r e h o u s ei ss t i l lan e w t o p i c ，r - t r e ei n d e x a n d b i t m a pi n d e xh a v er e s p e c t i v ea d v a n t a g e ， c o m p o u n di n d e xc o m b i n i n gt h ef e a t u r eo ft w oi n d e x e sa l s op o s s e sg o o d q u e r yp e r f o r m a n c ea n d i sa p p l i e di nw i d ea r e a s k e yw o r d sd a t aw a r e h o u s e ，t r e ei n d e x ，b i t m a pi n d e x ，o n l i n ea n a l y t i c a lp r o c e s s i n g 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：敏，本毒、日期：2 里盘年本日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名： 硕士学位论文第一章绪论 1 1 课题研究意义 第一章绪论 联机分析处理( 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 l a p ) 是数据仓库技术中的 一个重要分析工具，通过对数据仓库中的多维数据进行多维分析处理，以得到更 为方便有效的信息供企业决策者参考和查询，便于企业决策者更为灵活地操纵本 企业的数据信息，从多方面和多角度以多维的方式来了解企业的状态和变化，并 根据市场情况来做出相应的实时处理，有利于提高企业决策的科学性和可靠性， 为企业全面信息化的系统工程打下良好基础。 数据仓库索引技术是一种应用非常广泛的数据仓库查询优化方法，通过索引 技术来组织和维护数据，可以极大地提高数据仓库o l a p 查询的速度和效率，改 善o l a p 查询操作的性能，使得0 l a p 查询处理有着更好的应用价值，真正成 为数据仓库研究方向中的核心技术。 1 2 课题国内外研究背景及现状 1 2 1 数据仓库的研究背景 数据仓库概念的提出者及相关技术的主要倡导者是美国著名信息工程学家 w i l l i a ni n l n o n 博士。9 0 年代初，i n i n o n 根据数据库技术己趋于成熟化，结合市 场经济发展之需首次提出了数据仓库概念的一个表述。他提出的数据仓库的解释 是【l j ：一个数据仓库通常是一个面向主题的、集成的、不同时间的、稳定的数据 的集合，用以支持经营管理中的决策制定过程。 该定义描述了数据仓库如下几个性质： 1 所谓面向主题，是指数据仓库内的信息是按主题进行组织的，为主题进 行决策的过程提供信息。所谓主题，是指用户使用数据仓库进行决策时所关心的 重点方面，如：销售情况、人事情况、整个企业的利润状况等。 2 所谓集成，是指数据仓库中的信息不是直接从各个业务部门的处理系统 中简单地提取出来的，而是根据需求、经过系统的预处理即加工、汇总和整理， 确保数据仓库内的信息是关于整个企业的全局信息。 3 所谓随时间变化的，是指数据仓库内的信息并不只是关于企业的现行的 数据，而是记录了从过去的某一时间开始至目前各个阶段的信息，通过这些信息， 可以对企业发展的历程和未来趋势做出定量分析和预测。 4 所谓信息的相对稳定性，是指一旦某数据被提取到数据仓库以后，一般 硕士学位论文 第一章绪论 情况下，将被长期保留下来，也就是说数据仓库会有大量的插入与查找操作，而 删除与修改操作却很少，可见数据仓库是一个复杂的处理过程。 在i n m o n 首次提出数据仓库概念的当时，并未马上引起研究者们的注意。但 是，随着网络等技术的发展大大推进了企业组织全球化和国际化趋势的同时，也 给许多大型企业带来了障碍与矛盾，即分散平台的d b s ( d a t a b a s es y s t e m ) 的数 据与需要全局性集成数据( 一致化的数据) 的矛盾等，由于这些因素的影响，导致 了一些大型企业的生产效益下降、商业的销售额下滑、银行的预测和分析人员因 信息滞后的原因而做出的决策失效等等。为了解决上述矛盾，人们在实践中，开 始尝试和研究数据仓库系统有关概念和相关的技术。著名的d b s 和m i s 专家r o b m a t t i s i o n l 2 1 在1 9 9 6 年出版的“d a t aw a r e h o u s e ”一书中也详细地叙述了数据仓库的 定义与解释，他认为：数据仓库是一种新型的数据库，数据仓库被组织用作一个 中性存储区，被d a t am i n i n g 和其它应用程序所使用，使用这些数据将满足一组预 定义的商业评判。 1 2 2o l a p 的研究背景 与数据仓库紧密联系在一起是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 实施提供了理想的环境；而o l a p 作为一种多维查询和分析工具，是数据仓库功 能的自然扩展，也是数据仓库中的大容量数据得到有效利用的保障。 o l a p 的产生是由于传统的决策分析工具在性能和灵活性上己经不能满足 人们对海量的分析需求，客观上要求有另外一种面向分析人员的、灵活的、符合 人们思维习惯的分析工具来替代现有的工具。面向决策分析的数据仓库的产生为 这种工具的出现提供了基础，于是o l a p 技术应运而生。 1 9 9 3 年，e e c o d d 在“p r o v i d i n go l a p ( o nl i n ea n a l y t i cp r o c e s s i n g ) t o u s e r - a n a l y s i s ”一文中提出了有关o l a p 的1 2 条准则【3 1 。其后，部分公司根据各 自对o l a p 的理解也提了一些规则，如表1 1 所示。 2 硕士学位论文第一章绪论 表1 1 关于o l a p 连接的规则 c o d d 的1 2 条规则 g a r m e r g r o u p 的9 条规则 多维概念视图多维数组 透明性o l a p 连接操作 存取能力 数据库管理工具 一致的报告性对象存储 客户机服务器结构子集选择 维的等同性 细节深入 动态的稀疏矩阵处理局部数据支持 多用户支持递增数据库刷新 非受限的踌维操作s q l 接口 直观的数据操作 灵活的报告 不受限的维和聚合层次 1 2 3 索引的研究背景 索引( i n d e x ) 最早出现在文献系统中，从这个意义上讲，索引是指文献集合中 包含的事项或从文献集合中引出的概念的一种系统指南，这些事项或引出的概念 是按已知的或已说明了的可检顺序排列的款目表达出来的。索引系统( i n d e x i n g s y s t e m ) 是指以检索和提供文献为目的，为组织知识记录中的内容而制定的一套方 法。 由于计算机的出现，索引技术在现代得到了迅速的发展，特别是数据库系统 中的索引技术。“索引”在数据库的术语中是指根据某特定域( 或属性) 对数据库中 数据的一种排序，这一特定域( 或属性) 称为关键域或关键属性。对应的索引服务 ( i n d e xs e r v i c e s ) 就是根据索引从数据中提取信息，再对这些信息进行有效的组织、 分析后，提供给用户。 对数据库索引系统的研究长期以来一直都得到高度重视。索引树就是最为常 见的一类索引结构，这类索引树既可以自底向上通过抽象来构造，也可以自顶向 下通过分类来构造。随着数据库应用中出现的对空间数据管理的要求，各种形式 的多维索引树结构也被提出，如r 树、r + 树、q r 一树、k d b 树、t 树等，据统 计，目前这类索引树结构已超过5 0 种。与这种特定的、针对某种数据类型而提 出的索引树形式相比，随着应用领域的扩大，用户不断提出自定义数据类型的要 求，为了能更有效地实现对用户自定义数据类型的操作，人们对可扩展的搜索树 硕士学位论文第一章绪论 结构进行了研究，这些搜索树结构基本上都基于原有的索引结构，如b + 树或者 r _ 树。 当今的数据库技术已不再只是针对常规的事务型( 商业型) 信息处理，已经扩 展到人类社会的各个方面，成为信息处理的重要工具和组成部分，因此索引系统 的应用范围也大大扩展了。由于应用要求的不断提高，数据库索引技术也将接受 新的挑战，数据仓库索引就是最早被重视的领域之一。 1 3 主要内容介绍 数据仓库中典型的查询优化技术有索引技术、视图分割及o l a p 并行查询 等。本文研究的重点方向是数据仓库的索引查询优化技术。数据仓库的索引结构 主要有三种：b 一树索引、r 树索引和位图索引。b 一树索引可以建立多个属性上的 索引，以用于多个属性上的查询，但需要建立属性个数为指数级的b 一树数目， 因此查询效率不高。r 树索引是一种面向多维空间对象的索引结构，适合于动态 数据的查询操作，但其索引结构是基于所有维而建立的，不能很好地满足基于部 分维查询操作的需要，故由基本的r 树出现了很多变种，如：r 树，k d 树等。 位图索引采用二进制值来表示属性值，相应的各种比较、连接、和聚集操作都变 成位算术运算，大大减少了运行时间，对于基数较小的域特别有用，但更新位图 索引的开销要大于传统索引的更新开销，因此位图索引只适合于静态数据，对于 具有高度活动性的动态数据，位图索引并不能有效提高其查询效率。 本论文分为五章，研究的重点内容是树形索引和位图索引。 第一章为绪论。 第二章介绍数据仓库和多维索引的一些基本概念和原理方法，重点内容有数 据库和数据仓库以及各自索引结构的一些特点和区别、数据仓库索引的设计准 则、基本要求等。 第三章是全文的重点，分别介绍了b 树索引、r _ 树索引、四叉树索引的各 自索引结构特点以及插入、删除、查找等相关操作过程。在r - 树索引和四叉树 索引结构的基础上，本文在数据仓库的索引结构中引进了空间索引结构q r - 树索 引，描述了相关的q r 一树索引o l a p 操作伪码算法，并就其操作性能与其它两种 树型索引进行了比较，模拟试验证明q r - 树是一种比较理想的数据仓库索引结 构。 第四章讨论位图索引。基本的位图索引一共有简单位图索引、区域位图索引、 分段位图索引、编码位图索引四种，应用最广泛的是分段位图索引。这一章重点 研究了成员查询的位图索引优化算法，在已有的理论基础上，提出了改进型的矩 阵合并贪婪优化算法，降低了算法的时间复杂度，有效地提高了成员查询的执行 硕士学位论文第一章绪论 性能。 第五章介绍了其它几种比较有特色的数据仓库索引结构，包括反转索引、层 次索引、基于多维数组的索引、散列索引、网格文件，这些索引虽然应用不是很 广泛，但在某些特定场合下，却有较好的查找性能，也是数据仓库索引中不可获 缺的成员。 硕士学位论文第二章数据仓库与多维索b 第二章数据仓库与多维索弓 与传统的数据库管理系统相比，数据仓库涉及对现实世界大量多维数据的处 理。多维数据具有其特殊性，首先，多维数据往往具有不规则的相联规则，且数 据之间的多维关系复杂、存储需求量大；其次，针对多维目标的多维操作，例如 交叉点、邻接物及包含物，计算的代价比起传统的选择或连接操作复杂、运算量 大，这是由于多维对象的不规整性所造成的；最后，多维数据的多维次序难以定 义，无法应用通常的排序技术。随着计算机技术的发展，多维数据仓库应用范围 已经扩展到了计算机辅助设计和地理数据中，一个数据仓库系统需要一种索引机 制，以便帮助它根据数据的多维定位迅速地检索数据项目。 2 1 数据仓库与数据库系统 数据仓库是面向主题的、集成的、稳定的、非易失的不同时间的数据集合， 用于支持经营管理中的决策支持过程。传统的数据库系统主要执行的是联机事务 和查询处理，是为企业特定的应用需求而服务的，用户关心的是响应时间、数据 安全性和完整性1 4 】。 o l t p ( o nl 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 以快速事物响应 和频繁的数据修改为特征，用户利用数据库可快速地处理具体业务，o l t p 应用 程序包含大量相对简单的事物，事物量大且重复率高，因此o l t p 适于处理高度 结构化的信息，特别是在数据信息量不是很大，且没有太多复杂查询的情况下， 能够很好地满足用户各种不同数据访问的要求。o l a p 联机分析处理是数据仓库 中共享多维信息的快速分析，它具有快速性、可分析性、多维性和信息性的典型 特征。o l a p 是一项给数据分析人员以灵活、可用和及时的方式构造、处理和表 示综合数据的技术，主要关于如何理解聚集大量不同的数据，以便决策人员和高 层管理人员对数据仓库进行信息分析处理。 o l a p 和o l t p 是两类适应于不同数据信息的应用技术，它们各自特点分别如 表2 1 所示 6 硕士学位论文第二章数据仓库与多维索日 表2 1o l a p - # o l t p 对比表 o u r po l a p 数据库数据数据仓库数据 细节性数据综合性数据 当前数据、确保更新历史数据、周期性刷新 事务吞吐量小事务吞吐量大 高性能、高可用性高灵活性、高自治性 响应时间要求高响应时间合理 面向操作人员，支持日常操作面向知识工人，支持管理需要 面向应用，事务驱动面向分析，分析驱动 用户数量大 用户数量小 基于e r ，面向应用星型雪花模型，面向主题 短的简单事务 复杂查询 2 2 数据仓库与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 数据库保存的是各种轻度综合的细节数据，而o l a p 数据库 中的汇总数据也被存储在数据仓库中，数据仓库也能容纳细节数据。数据定期从 数据仓库中导入到o l a p 数据库中，由于操作型环境的数据进入到数据仓库时已 被集成，因此o l a p 数据库就不用从操作型环境中抽取与集成数据。 数据仓库与o l a p 数据库的区别【4 i ： 1 数据仓库存有大量的数据，o l a p 数据库中的数据至少要少一个数量级。 2 数据仓库只适于少量的灵活访问，o l a p 数据库适合大量的非预知的访问 和分析。 3 数据库存储很长时间范围内的数据，o l a p 数据库中存储着较短时间范围 内的数据。 4 数据库允许分析人员以受限的形式访问数据，o l a p 数据库允许自由的访 问。 5 数据库侧重于存储和管理面向决策主题的数据，而0 l a p 则侧重于数据仓 库中的数据分析，并将其转换成辅助决策信息。 硕士学位论文 第二章数据仓库与多维索； 此外，o l a p 的一个重要特点是多维数据分析，这与数据仓库的多维数据组 织正好形成相互结合和相互补充的关系。0 l a p 技术中比较典型的应用是对多维 数据的切片和切块、钻取、旋转等，它便于使用者从不同角度提取有关数据。 2 3o l a p 的数据组织 建立0 l a p 的基础是多维数据模型，多维数据模型的存储可以有多种不同的 形式。m o l a p 和r o a l p 是o l a p 的两种数据形式，其中 m o l a p ( m u l t i d i m e n s i o no l a p ) 是基于多维数据库存储方式建立的o l a p ； r o l a p ( r e l a t i o n0 l a p ) 是基于关系数据库存储方式建立的0 l a p 。 r o l a p 中多维数据必须被映射成关系表中的行，具有代表性的是非标准化 的星型模型的设计，基本信息存储在一个单独的事实表中，而有关维的支持信息 则被存储在其他表中。欲处理的结果一般被存放在大量的综合汇总表中，这些汇 总表分别被不同的聚集及组合。它们每个都需要关键字来标识，并且通过索引来 获得高效的访问。r o l a p 数据存储与关系模式一致，数据存储粒度非常大，进 行多维查询时可获得较好的查询性能，同时也具有较好的通用性【5 】。 r o l a p 多维数据库是由许多经压缩的、类似于数组的对象构成，这种对象 通常带有高度压缩的索引及指针结构，是逻辑上的多维数组形式存储，表现为超 立方的结构【6 】。由于多维数据库信息粒度较粗，索引比较小，可以很容易地将整 个索引装进内存，这将极大的提高查询性能。 表2 2m o l a p 与r o l a p 的比较 m o l a p r o l a p 数据集市数据仓库 固定维可变维 维交叉计算数据仓库的多维视图 行级计算超大型数据库 读一写应用维数据变化速度快 2 4 数据仓库的数据存储与o l a p 的多维数据分析 数据仓库不同于数据库。数据仓库存储的数据模型是数据的多维视图，它 将直接影响到前端工具、数据库的设计和o l a p 的查询引擎。多维数据视图是在 多层次的维构成的多维空间，存放着数据测量值，并对一个或多个维进行集合运 算。对于逻辑的多维数据模型，可以使用不同的存储机制和表示模式来实现多维 数据模型。目前，使用的多维数据模型主要有星型模型、雪花模型、星网模型等。 硕士学位论文第二章数据仓库与多维索g 2 4 1 星型模型 大多数的数据仓库都使用星型模型，星型模型是由事实表以及多个维表组 成。事实表中存放大量关于企业的事实数据，这些数据通常都很大而且非规范化 程度很高，维表中存放描叙性数据，维表是围绕事实表建立的较小的表。 图2 1 所示是一个星型模型的实例 车间表 车间号 车间名 主任名 仓位表 仓位号 地址 主任名 产品表 产品号 产品名 单价 客户表 客户号 客户名 联系人 电话 地址 税号 账号 事实表 产品号 车间号 仓位号 客户号 销售员号 入库单号 出库单号 定单号 总数量 总价值 销售惯表 销售员号 姓名 性别 学历 业绩 图2 1 星型模型示例 定单表 定单号 数量 折扣 总价 定单日期 入库单表 入库单号 入库量 入库日期 经手人 出库单表 出库单号 出库量 出库日期 经手人 事实表有大量的记录，维表相对来说有较少的记录。星型模型以潜在的存储 空间代价，使用了大量非规范化来优化速度，限制了事实表的数量属性个数。星 型模型的缺点是数据冗余量很大，不适合于大数据量的情况，且不能解决业务更 新时须增加新维的问题【7 1 。 9 硕士学位论文第二章数据仓库与多维索日 2 4 2 雪花模型 雪花模型是对星型模型的扩展，雪花模型对星型模型的维表进一步层次 化，原来的维表可能被扩展为小的事实表，形成一些小的局部层次区域。它的优 点是最大限度地减少数据存储量，以及把较小的维表联合在一起来改善查询性 能。缺点是增加了用户必须处理的表的数量，使查询操作复杂化，且使系统专业 化和实用化程度较高，降低了系统的专用程度。1 。图2 2 是雪花数据模型的实例。 主任表 主任号 主任名 车间表 车间号 车间名 主任名 仓位表 仓位号 地址 主任名 产品表 产品号 产品名 单价 客户表 客户号 客户名 联系人 电话 地址 税号 账号 2 4 30 l a p 的多维数据分析 事实表 产品号 车间号 仓位号 客户号 销售员号 入库单号 出库单号 定单号 总数量 总价值 型堡巨壅 销售员号 姓名 性别 学历 业绩 图2 2 雪花模型示例 定单表 定单号 数量 折扣 总价 定单日期 入库单表 入库单号 入库量 入库日期 经手人 出库单表 出库单号 出库量 出库日期 经手人 年月表 丘 月 o l a p 的目的是为决策管理人员提供一种灵活的数据分析手段，这是通过多 维数据分析实现的。基本的多维数据分析包括切片、切块、旋转等。切片就是在 某两个维上取一定区间的维成员或全部维成员，而在其余的维上选定一个维成员 的操作。切块可以看成是在切片的基础上，进一步确定各个维成员的区间得到的 0 硕士学位论文 第二章数据仓库与多维索； 片段体，即是由多个切片叠和起来的。钻取有向下钻取( d r i l ld o w n ) 和向上钻取 ( d r i l lu p ) 操作。向下钻取是使用户在多层数据中能通过导航信息而获得更多的细 节性数据，而向上钻取是获得概括性的数据。 2 5 数据仓库索弓 在数据仓库的管理中，为了迅速从庞大的数据仓库信息中找到所需要的数 据，提供了类似地图作用的索引技术。通过在数据仓库中对维表增加索引，可以 大大提高数据的检索速度，改善数据查询性能，这是数据仓库索引的主要作用： 可以加速维表和维表之间的连接，特别是在实现数据的参考完整性方面特别有意 义；通过使用索引，可以在查询的过程中，使用优化器，提高系统的性能。 2 5 1 数据仓库索引概念 索引是数据仓库中的一个重要对象，索引是包含维表中选定字段的信息的对 象，这些信息以某种规律排序，有一个指针指向存放实际数据的记录。索引包括 选定的列值和指向数据位置的指针，当对某个维表按某个列值查找，无索弓l 要扫 描整个表，即读取维表中所有记录的所有列：若所查询的列已被索引，则搜索仅 在索引结构上进行，仅需要查询索引列和其上的数据指针，读取数据较少，且索 引数据已被完整排序。 数据仓库的索引具有顺序号，可保证数据唯一性，用户可建立唯一性索引 ( u n i q u ei n d e x ) 和非唯一性索引( n o n u n i q u ei n d e x ) ，唯一性索引不允许索引数据重 复，非唯一性索引则允许；用户可根据需要针对多个维表列建立复合索引，更好 地组织管理数据；可以使用索引分区，即按索引将整个数据仓库物理分区，索引 分区可以存储在分开的维表空间中，这些维表空间具有各自的存储参数。 2 5 2 数据仓库索引和多维数据库索b 数据仓库与传统的数据库的个主要区别是存储数据包括大量历史数据，并 且需要对这些历史数据进行聚集和汇总处理，然后采用多维数据模型来完成数据 的组织。因此，传统的数据库索引机制b 树并不能很好地满足数据仓库查询优 化的需要，我们在此研究的多维数据索引技术是基于多维时空数据库的索引理 论，这主要由于数据仓库的多维数据模型与多维数据库的太多相似之处 g j o 】： 1 复杂的结构：多维数据库存储的数据是各种各样不同的复杂对象，可能 是一个多维空间的点数据，也有可能是复杂的多边形或多面体，不太可能以关系 数据库的定长元组来存储此类对象，而数据仓库的数据模型可以看作是一个结构 比较简单的多维数据立方体，具有典型空间数据库的特点。 硕士学位论文第二章数据仓库与多维索b 2 动态的数据：数据仓库和多维数据库的插入删除操作都是以更新操作交 叉存储的，都伴随着对数据本身的修改。 3 海量的存储：数据仓库和多维数据库的数据对象都是海量的存储量，要 更多的存储空间。 4 计算代价昂贵：各类操作的代价虽各有不同，但其时空代价与标准的关 系代数运算相比，耗费要大得多。 5 算法与操作的不标准性：由于多维数据库数据对象的复杂性，其空间算 法与各类数据操作都具有典型的非标准化的特点，数据仓库的数据模型也具有多 维数据库的特点，也具有非标准化的特性。 正是由于以上数据仓库与多维数据库的相似之处，数据仓库的索引结构与多 维数据库的索引结构也有许多的共同之处 1 l , 1 2 1 ： 1 动态构造：多维数据的存储通常都以关系数据库为基础，数据可以在数 据库中任意顺序插入或删除，多维数据索引也应该与之保持一致，索引结构也必 须支持动态的插入和删除。 2 二级，三级存储管理：由于多维数据内容的复杂性，索引结构要充分考虑 到二级以及三级的存储管理。 3 支持尽量多的操作：不能以牺牲其他的操作文件而支持某一种特定的操 作。 4 独立于输入数据及插入顺序：支持各种多维数据以及任意的插入顺序， 多维索引的效率不依赖于数据类型及插入顺序。 5 可增长性：索引结构要能够适应数据库大小的增长，满足应用程序发展 的需要。 6 时间的有效性：查找速度必须是快速的。 7 空间的有效性：一个索引结构相对于其原始数据应是比较小的，要保证 一定的空间利用率。 8 最小的影响：多维索引方法与数据库系统的融合对现存系统应产生最小 的影响。 2 5 30 l a p 索引技术的要求 1 对称的局部匹配查询 大多数o l a p 查询在概念上可以表达为与一个立方体的一个或多个维关联的 局部范围的查询。查询的目标是某个范围的聚集，它要求能够高效地检索到所需 的数据。最简单的情况是只查询所有维中的一维，称为点查询。查询的范围可以 是连续的，例如，“时间从1 2 2 0 年1 月到3 月”：也可以是不连续的，例如，“每个 硕士学位论文 第二章数据仓库与多维索日 月的第一个星期”。较理想的做法是扩展这种索引遍历技术使得可以并行搜索一 批键值，而不是一个时刻只能搜索一个键值。查询范围的维数可以是一个也可以 是几个，而且查询谓词运用的对象维集合是灵活多变的。总之，应该能对所有的 维进行对称索引。有时候，可能需要索引维的无量纲属性，而度量属性有时也需 要像维一样看待并进行索引。例如，用户可能只对销售量达到一定程度的产品感 兴趣，如“每类产品最畅销的前3 名”这种形式的查询在o l a p 应用中是很普遍的。 这样的查询可以通过对产品类型和销售量进行联合索引得以优化。 o l t p 查询与o l a p 查询主要区别为：典型的o l t p 查询只针对少量数据， 点查询较为普遍，而在众多属性上同时运用多谓词进行查询则很少见。 2 索引多级别的聚集 大多数o l a p 数据库预先计算与基本立方体中不同级别聚集对应的多个分 组，因此，索引汇总数据( s u m m a r i z e d d a t a ) 非常重要。需要考虑的问题为：是为 不同级别的聚集分别建立索引，还是在每个维中加入特别的值以在底层对汇总数 据进行索引。例如，需要索引“产品一年度”分组的销售量，则可以将销售总量存 储在分组“产品”级别，方法是简单地为年度维添加一个对应于“所有”年度的附加 值，用来存储每种产品的销售总量。 3 多种遍历顺序 b 一树常用于o l t p 系统中对已建立索引的数据进行检索。这是外部排序的一 种比较经济的方法。由于o l a p 数据库需要执行大量的分组计算，所以可以通过 采用索引来排序数据而改善性能。其难点在于如何将这种技术运用到多个属性而 不是一个，或是属性的任意组合。 4 高效的批量更新 o l a p 数据库不像o l t p 数据库那样需要频繁的细节更新，但有必要建立高 效的批量更新。例如分布式环境下，不同国家和地区每天的更新时间不同，因此 不可能每天进行多次数据库更新；另一方面，这些更新都是按地区和时间集中进 行的，由此产生了对更新本地化和高效批量处理的要求。 5 稀疏数据的处理 一般情况下，逻辑o l a p 立方体中只有1 2 b 的数据为非零值。因此，理想 的索引技术应能对数据的稀疏程度具有可伸缩性。 2 5 4 数据仓库索引设计准则 数据仓库索引的创建应该尽量遵循以下的准则【1 3 l ： 1 数据仓库要限制一个维表上的索引数量，一般不要超过1 0 个，尽量限制 在5 个以内，索引会占用数据库空间，索引越多，o l a p 操作的执行速度就越慢。 硕士学位论文 第二章数据仓库与多维索b 2 用户应索引具有一定范围的维表列，索引时有一个大致的原则，如果表 中维表列的值占该维表中行的2 0 以内，这个维表列就可以作为候选索引表列。 3 在经常需要搜索的列上面创建索引。 4 在主键上创建索引，主键能确保维表中数据行之间的唯一性，可以减轻 开发者为了实现唯一性检查，而需要满足各自编程的要求。 5 用在连接的列上创建索引，也就是在外键上面创建索引。 6 在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其 指定的范围是连续的。 7 在经常需要查询、排序的列上创建索引，因为索引已经排序，这样查询 可以利用索引的排序，加快排序查询时间。 8 如果在o l a p 执行中多个表列被一起连续使用，则应该考虑将这些表列一 起放在一个索引内创建复合索引。同时应把最常用到的字段作为前导列( 即第一 列) ，并把要引用的字段都包含到复合索引中，这样可利用优化程序的索引覆盖 功能。 同时，对下列情况不应该创建索引【l 3 l ： 1 不要对那些必须经常修改的列做索引，并设法抑制对具有高插入与删除 操作的表中的任何列做索引。 2 不要对那些总是用于具有函数或操作符的维表列做索引。在这种情况下， 优化程序不使用索引。 3 不要对那些主要用于否定或n u l l 比较的列做索引。 4 不要对那些只有很少值的列增加索引。 4 硕士学位论文第三章数据仓库树形索； 第三章数据仓库树形索弓 数据仓库基本索引技术有树形索引和位图索引两种，基于这两种基本索引技 术的其它索引方法主要有反转索引、分层索引、基于多维数组的索引、基于函数 的索引、网格文件等，本章重点讨论树形索引。 数据仓库树形索引是数据仓库中很重要的一种索引技术，树形索引通过对维 表索引项用各种树形结构来组织数据，可以极大地提高数据仓库多维列表中的数 据检索速度。在本章中，我们将介绍数据仓库的各类树形索引结构特点，对其各 自优缺点进