（计算机软件与理论专业论文）面向数据仓库的多表连接与聚集算法研究.pdf

中文摘要 数据仓库和商业智能的作用在于为业务人员提供定制操作性和战略性业务决策 所需的信息和工具，联机分析处理( 0 l a p ) 是数据仓库的主要应用之一。r o l a p 是联 机分析处理( o l a p ) 中使用最广泛的一种类型，其主要功能是管理决策所需要的总结 数据。总结数据一般都涉及多表连接和分组聚集操作，提高这些操作的性能成为提 高o l a p 操作响应速度的关键。本文主要围绕r o l a p 的海量数据聚集查询技术展 开研究，对提高r o l a p 聚集查询效率具有重要意义。主要研究工作如下： ( 1 ) 给出一种改进的分组序号聚集算法i m u g a 。该算法充分利用时间维表的特 殊性，通过对事实表关键字直接获得分组属性值，减少了多表连接中时间维度的连 接次数，提高了联机分析处理查询效率。实验结果表明，该算法是有效的。 ( 2 ) 给出了一种基于层次有序维的分组聚集算法。该算法在偏序和映射的基础 上，通过定义层次有序维，利用维属性之间的聚集关系，通过约束层次链中的元素 次序，实现了分组聚集计算中多表连接转换为维范围的查询，提高了连接和聚集效 率。最后，实验验证了该算法的正确性和有效性。 关键字：数据仓库；联机分析处理：聚集查询；多表连接；层次有序维 a b s t r a c t d a t aw 2 l r e h o u s ea n db u s i n e s si n t e l l i g e n c ei st op r o v i d ei n f o r m a t i o na n d t o o l st h a tc u s t o m i z e do p e r a t i o n a la n ds t r a t e g i cb u s i n e s sd e c i s i o n sn e e df o r b u s i n e s sp e r s o n n e l t h eo 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 ) i so n eo ft h e m a i na p p l i c a t i o n so fd a t aw a r e h o u s e s r o l a pi s ak i n do fo l a p ( o n l i n e a n a l y t i c a lp r o c e s s i n g ) a n di s m o s tw i d e l yu s e d i t sm a j o rf u n c t i o nl st o m a n a g ea g g r e g a t ed a t aw h i c hi sn e e d e di nt h ed e c i s i o n 。m a k i n g a g g r e g a t e d a t ai sg e n e r a l l yi n v o l v e di nm u l t i t a b l ejo i n i n ga n da g g r e g a t i n gt h eq u e r y d a t a e n h a n c i n gt h ep e r f o r m a n c eo ft h e s eo p e r a t i o n s b e c o m e st h ek e yt o i m p r o v eo p e r a t i o n a lr e s p o n s ee f f i c i e n c y o fo l a p i nt h i sp a p e r , r o l a p q u e r yt e c h n o l o g i e s a r es t u d i e df o rt h eh u g ea m o u n to fd a t a t h em a i n r e s e a r c hw o r k sa r ea sf o l l o w s ： ( 1 ) a ni m p r o v e da g g r e g a t i o na l g o r i t h mi m u g a b a s e do ng r o u pn u m b e r i sp r e s e n t e d t h ea l g o r i t h mt a k e sf u l la d v a n t a g eo f t h et i m ed i m e n s i o nt a b l e s p a r t i c u l a r i t y , d i r e c t l yg e tt h eg r o u pa t t r i b u t e v a l u e st h r o u g ht h ef a c tt a b l e ， g r e a t l vr e d u c eq u e r yt i m e so nt i m ed i m e n s i o n a lt a b l ei nm u l t i t a b l ej o i na n d i m p r o v et h ee f f i c i e n c yo fo l a pq u e r y e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e a l g o r i t h m i se f f e c t i v e ( 2 ) a na g g r e g a t i o na l g o r i t h m i s p r e s e n t e db yu s i n g h i e r a r c h i c a l s e q u e n c ed i m e n s i o n sb a s e do nt h ec o n c e p t so fp a r t i a lo r d e ra n dm a p p i n g u s i n g t h ea g g r e g a t i o nr e l a t i o n s h i pb e t w e e nd i m e n s i o n a la t t r i b u t e s ，t h e a l g o r i t h mt r a n s f o r m sm u l t i - t a b l ej o i n i n gi n t od i m e n s i o n a lq u e r yr a n g e sm t h e a g g r e g a t i o nc o m p u t i n gb a s e do ng r o u pn u m b e rb yr e s t r i c t i n gt h e o r d e ro f e l e m e n t si nh i e r a r c h i c a lc h a i n ，a n di m p r o v e st h ee f f i c i e n c yo f m u l t i - t a b l ejo i n a n da g g r e g a t i o n t h ee x p e r i m e n t a lr e s u l t s v a l i d a t et h ev a l i d i t ya n dt h e c o r r e c t n e s so ft h ea l g o r i t h m k e yw o r d s ：d a t aw a r e h o u s e ；o l a p ；a g g r e g a t eq u e r y ；m u l t i t a b l ej o i n ； i i i h i e r a r c h i c a ls e q u e n c ed i m e n s i o n i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名： 垃! 磊日期：兰! 翌堑星兰望 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名：塑! 丕 日期：2 翌兰卑型皇 导师签名：写避l 日期：一 第一章绪论 第一章绪论 k 1 1 月l j 舌 随着i n t e m e t 的进一步普及与计算机硬件的不断革新，数据量急剧膨胀，数据仓 库( d a t aw a r e h o u s e ) 经为商务运作提供结构与工具，对系统的组织、理解和使用数 据进行战略决策做出巨大的贡献。在当今这个充满竞争和快速发展的世界，人们已 经不再满足于简单的数据操作，产生了进一步使用现有数据的需求，也就是利用积 累的历史的数据，进行数据分析和推理，从而为决策提供必要的依据。大量的组织 机构已经发现数据仓库是一个非常有价值的工具，如许多政府、公司、研究机构花 费巨资构建他们的数据仓库。数据仓库系统允许将各种各样的应用系统集成起来， 为统一的历史数据分析提供坚实的平台。i i l m o n 将数据仓库明确地定义为一个面向主 题的、集成的、时变的、非易失的数据集合，支持管理部门的决策过程【l 】。这个定义 阐明了数据仓库具有以下四个主要特征：面向主题的、集成的、时变的、非易失的。 面向主题的( s u b j e c t o r i e n t e d ) ：什么是主题? 主题是一个抽象概念，是指用户使 用数据仓库进行决策时所关心的重点方面，每个主题对应一个客观分析领域，如顾 客、供应商、产品和销售组织。数据仓库中的数据与操作型数据库中的数据不同， 是按一定的主题域进行组织的。主题域是独立和完备的，适用于分析型的应用。而 基于应用的数据组织是客观世界既定的，对数据内容的划分不一定能够满足分析需 求。基于主题组织的数据可以划分为各自独立的领域，各个领域的逻辑内涵互不相 交。 集成的( i n t e g r a t e d ) ：在数据进入数据仓库之前，必须经过加工与集成。操作型数 据库系统通常与某些特定的应用领域相关联，数据库之间总是相互独立，并且通常 是异构的。而数据仓库中的数据则是对分散的各个原始数据库进行了数据抽取、清 理后，通过系统加工、汇总和整理得到的，必须消除原始数据中的不一致性，以保 证数据仓库中的信息是关于整个部门的一致的全局信息。 时变的( t i m e v a r i a n t ) ：数据仓库中包含了大量的历史数据，经集成后进入数据 仓库的数据并不是实时更新的，但也要随时间的变化不断地更新、增删和重新汇总。 数据仓库中数据的时限为5 年至1 0 年，主要用于时间趋势分析。操作型数据库系统关 注于当前某一个时间段内的业务数据，而数据仓库中的数据通常是业务数据积累而 来的历史信息，系统地记录了企业部门从过去某一时点开始到目前的各个阶段的信 息，这些信息使得决策人员可以对企业部门的发展历程和未来趋势做出必要的定量 1 面向数据仓库的多表连接与聚集算法研究 分析和预测。 非易失的( n o n v o l a t i l e ) ：数据仓库中的数据主要用于决策分析，涉及的操作主要 是数据查询，一般不进行修改操作，不需要并发读写控制机制。一旦某些数据进入 了数据仓库，一般情况下不做修改将被长期保留，也就是说数据仓库通常进行大量 的查询操作，但修改和删除操作非常少，通常只需要定期地进行数据加载与刷新。 从概念来看，数据仓库是一个静态的概念，有人也许会把数据仓库简单地理解 为一个大型的数据存储管理机制。事实上，只有把信息及时交给需要这些信息的用 户，帮助他们做出改善业务经营管理的决策，信息才能真正发挥作用，信息才有意 义。而把信息进行整理和归纳，并及时提供分析数据给相应的管理决策人员是数据 仓库的根本任务。因此，数据仓库并非静态的，而是一个工程的、动态的概念。应 该说，数据仓库是一种体系结构的基础，而不仅仅是一个大型的数据库管理系统。 联机分析处理0 l a p ( o n l i n ea n a l y s i sp r o c e s s i n g ) 是用来对数据仓库中的数 据进行联机分析的一种新技术【2 1 ，其主要功能是管理决策支持所需要的总结数据( 总 结数据一般以实视图的形式出现在数据仓库中【3 1 ，其中实视图也是一张表) ，满足用 户进行即席( a dh o c ) 查询，及时向用户提供分析处理数据的结果，以辅助决策，这类 数据是从原始数据转化而来的，并以用户容易理解的方式反映真实状况【3 。8 】。实时的 联机分析处理对查询响应速度提出了更高的要求，但由于数据仓库存储着不同粒度、 容量巨大的数据记录，于是如何有效地执行联机分析处理查询操作，尤其是多表连 接和聚集操作成为数据仓库领域的核心问题。 1 2 数据仓库与联机分析处理 1 2 1 数据仓库 ( 一) 数据仓库的数据模式 典型的数据仓库具有为数据分析而设计的模式，使用o l a p 工具进行联机分析处 理。因此，存储的数据通常是多维数据，一般包括维属性和度量属性。包含多维数 据的表称作事实表，通常远远大于维表。它将直接影响到前端工具、数据库的设计 和o l a p 的查询引擎。以下为常用到的多维模型的相关概念。 事实表( f a c t ) ：多维数据模型一般围绕中心主题进行组织，该主题常用事实表表 示，事实是数值的度量，一般包括事实的名称或度量以及各个相关维的关键字。对 于企业中动态发生的事件，如产量、销售额等。 度量( m e a s u r e ) ：度量属性是决策者所关心的具有实际意义的数量。例如：商品 2 第一章绪论 的销售量、仓库中物品的库存量等等。这些属性测量了某个值，可以对他们进行统 计、聚集操作等。 维( d i m e n s i o n ) ：维是人们观察度量属性和度量属性汇总的特定角度。例如，企 业部门经常关心产品销售数据随着时间的推移而产生的变化情况，这时是从时间的 角度来观察产品的销售，所以时间就是一个维( 称时间维) 。维决定决策过程中事 实实例可能的聚合方式。维可以是离散属性，例如“地域”维，它对应的维属性都 是离散的，例如“国家”与“城市 等；维也可以是连续属性，例如轧制速度可以 作为分析维，它的取值是实数。 维表用于描述事实表，大多是文字描述、种类、地域、时间、产品等类型的数 据。在数据仓库中，维表有自己的主键，并通过主键实现与事实表的链接。事实数 据倾向于在整个时间段上保持稳定，而维数据随着业务的变化及用户需求分析的变 化而变化。 概念分层( c o n c e p th i e r a r c h y ) ：观察数据的某个特定角度( 某个维) 还可以在细 节程度不同的多个描述方面，称这多个描述的方面为维的概念分层。它定义了一组 由低层概念集到高层概念集的映射，并且允许在各种抽象的级别上处理数据，从而 在多个抽象层上发现知识。概念分层结构可以是一般的格或偏序。如图1 1 是关于时 间维的典型概念分层。 图l l 概念分层的格结构 f i g u r e1 - 1t h es 仃u c t i l r eo fc o n c e p th i e r a r c h y 最为流行的数据仓库模型是多维数据模型。它由实体的集合和实体之间的关系 组成，分为星型模式、雪花模式和事实星座模式。 星型模式( s t a rs c h e m a ) 星型模式是数据仓库采用最多的一种模式。简单的星型模式是由个事实表以 3 面向数据仓库的多表连接与聚集算法研究 及若干个维表组合而成的，一个复杂的星型模式包含数百个事实表和维表，它反映 了观察对象的角度。星型模式使数据仓库成为一个集成的系统，为最终用户提供报 表服务和分析服务对象。其主体是事实表，事实表中存放着大量的事实数据，这些 数据量通常都很大，而且非规范化的程度很高，有关维的细节信息则描述在维表内， 从而达到简化事实表的目的。通过事实表将多个维表关联起来，建立了各个维度之 间的对象关系( 如下图1 2 所示) 。 图1 - 2 星型模式 f i g u r e1 - 2s t a rs c h e m a s 星型模式的优点为能够提供星连接，即维表给出取值条件后，从事实表中获得 查询值的结果。用户非常容易通过分析维度表中的信息获取维度关键字，以便连接 到中心事实表进行查询，可以减少在事实表中扫描的数据量。因此，此模式非常适 合于数据分析和统计。 雪花模式( s n o w f l a k es c h e m a ) 雪花模式是对星型模式的扩展，由于模式图形呈现为雪花状而得名，其中每个 维表都可以向外连接到多个详细类别表。它对星型模式的维表进一步标准化并最大 限度地减少数据存储量，增加了应用程序的灵活性，也更有利于数据分析与决策， 它反映了对对象的观察角度和深度。图1 3 所示的模式即为雪花模式的例子，是对图 1 2 中星型模式的扩充。相比同样内容的星型模式和雪花模式，不难看出雪花模式增 加了用户必须处理的表的数量，增加了某些查询的复杂性。 4 第一章绪论 图1 - 3 雪花模式 f i g u r el - 3s n o w f l a k es c h e m a s 事实星座( f a c tc o n s t e l l a t i o n ) 更为复杂的应用中，可能出现一个维表被多个事实表共享的情况，这种模式看作 事实星座模式。事实星座模式是星型模式的直接扩充，为了表示多个事实间的某种 关联，可以通过共享维将多个星型模式连接起来( 如图1 4 所示) 。数据仓库收集关 于整个组织的主题域( 如资产、销售、顾客、商品和人员) 信息，它们都是企业范 围的。由于要对多个相关主题建模，数据仓库通常采用事实星座模式。数据集市是 数据仓库的一个部门子集，它有针对性地选定主题，是部门范围的。数据集市通常 选用星型或雪花模式，都适合于单个主题建模。 图1 - 4 事买星座模式 f i g u r e1 - 4f a c tc o n s t e l l a t i o ns c h e m a s ( - - ) 数据仓库的体系结构 数据仓库是面向计算机应用的信息系统，用来支持在各领域的决策分析。数据 仓库作为一个集成了许多数据源的中央数据库系统，从许多不同的联机事务处理数 据源收集和提取数据，并通过一系列汇总计算将数据组织成易于分析的形式，从而 为企业提供了一个信息集成平台，为管理人员和决策者迅速地提取信息并回答有关 业务运作的问题提供支持，包括从数据到信息，从信息到知识，最终到商业智能。 气 面向数据仓库的多表连接与聚集算法研究 整个数据仓库系统的体系结构【9 】包含了四个层次，如图1 5 所示。 存储与管理：数据仓库的组织管理方式使得它明显的区别于传统数据库，同时 这种组织方式也决定了其对外部数据的表现形式。它是整个数据仓库系统的核心。 在数据仓库中最为关键的是数据的存储方式和管理模式。如何决定建立数据仓库采 用的产品和技术，则需要从数据仓库的技术特点着手分析。 数据源数据仓库服务器 0 l ”服务器 前端工具 图1 5 数据仓库体系结构 f i g u r e1 - 5t h ed a t aw a r e h o u s ea r c h i t e c t u r e 针对目前现有的各业务数据库系统的数据，按照某个主题进行e t l 转换后重新组织。 数据仓库按照其覆盖范围大小可以分为企业级数据仓库和部门级数据仓库( 也称数 据集市) 。 数据源：是整个系统的数据源泉，是数据仓库系统的基础。一般包括企业内部 信息和外部数据信息。内部信息主要是存放于关系数据库管理系统中的各种业务处 理数据和各类文档数据。外部信息主要为各类市场信息、法律法规和竞争对手的相 关数据等。 联机分析处理服务器：对有关数据进行集成，按多维模型进行组织，使得可以 进行多角度、多层次的分析处理和发现某种规律。 前端工具：主要包含一些查询工具、报表工具、数据挖掘工具、数据分析工具 6 第一章绪论 以及各种基于数据仓库或数据集市的应用开发工具。其中数据分析工具主要针对联 机分析处理服务器，报表工具、数据挖掘工具主要针对数据仓库。 ( 三) 数据仓库的应用 数据仓库已经广泛应用于银行、证券、金融服务、税务、保险、消费物品零售 批发部门，以及诸如基于需求的产品生产过程中。客户关系在各种交易中所起的作 用已经越来越重要，重要的及时的信息往往可以决定企业的成败，甚至可以决定企 业的优胜劣汰。目前已经有非常多的行业及大企业都建设了自己数据仓库系统作为 企业决策机构的参谋和智囊。如我们平时所说的移动用户信息管理系统、铁路售票 系统、民航订票系统、证券交易系统、银行a t m 系统与服务系统等就是建立在大型 数据库之上的数据仓库。 1 2 2 联机分析处理 随着数据库技术的不断发展和广泛的应用，数据库存储容量从上个世纪8 0 年代的m b 及g b 过渡到现在的t b 和p b ，用户提交的查询更为复杂，涉及面已经 不是查询或操纵一张关系表中的一条或几条记录，而是需要对数百张表、成千 上万的记录集数据进行分析处理和信息汇总，关系数据库系统已经很难满足现 代超大规模数据分析处理需求。在性能上操作型数据库的应用和分析型数据仓 库应用二者难以两全，数据分析人员通常在r d b m s 中放宽了对数据冗余的限 制，利用统计方法汇总数据，但这些汇总的数据的应用逻辑是非系统化的、分 散而杂乱的，因此其分析功能通常非常有限，极不灵活，维护更新困难。在国 外，已经有很多的软件开发商利用最新发展的前端产品来弥补r d b m s 对分析处 理支持的不足，这些开发商为自己开发专门的数据汇总引擎，以及更加直观易 于理解数据访问界面，将业务数据按需求加以整合，在短期内满足非数据处理 专业人员的复杂查询要求。因此，联机分析处理这一概念产生了。 ( 一) o l a p 的概念 联机分析处理( o l a p ) 的概念最早是由关系数据库之父e f c o d d 7 】于1 9 9 3 年 提出的，他同时提出了关于o l a f 的1 2 条准则。o l a f 的提出使得联机分析处理 作为一类数据分析处理产品同联机事务处理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 ) 明显区别开来。 n i g e lp e n d s e l l l 】对e f c o d d 的定义进行了补充，并且提出o l a p 应具有的1 8 种特 性，将o l a p 定义简化为：多维共享信息的快速分析( f a s ta n a l y s i so fs h a r e d m u l t i d i m e n s i o n a li n f o r m a t i o n 简称f a s m i ) 。对此定义的介绍如下： 7 面向数据仓库的多表连接与聚集算法研究 快速( f a s t ) ：意味着能够快速地响应查询，对于大部分用户查询请求反应时间应 该要短于5 秒，很少查询超过2 0 秒： 分析( a n a l y s i s ) - 要求系统有分析建模的机制，能够处理大部分与用户和应用有 关的逻辑和统计分析，有交互式的查询和统计分析的功能； 共享( s h a r e d ) ：主要要求系统提供足够的安全机制，使多个用户的并发读写成为 可能； 多维( m u l t i d i m e n s i o n a l ) ：这是o l a p 的最基本要求，要求能够对数据提供多维视 图，视图独立于数据存储的具体形式，能够提供多层的层次机制； 信息( i n f o r m a t i o n ) ：不管数据量有多么大，也不管数据存储在什么地方，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 6 所示。 分析人品 图1 - 6o l a p 结构图 f i g u r el - 6o l a p s t r u c t u r e o l a p 系统按照其数据存储格式可以分为关系o l a p ( r e l a t i o n a lo l a p ，简 称r o l a p ) 、多维o l a p ( m u l t i d i m e n s i o n a lo l a p ，简称m o l a p ) 和混合型 o l a p ( h y b r i do l a p ，简称h o l a p ) 三种类型【1 2 1 。 1 r o l a p r o l a p 是利用关系数据库进行存储的多维数据，根据实际应用的需求有选 8 第一章绪论 择地定义一批实体化视图作为快速访问的表也存储在关系数据库中。一般情况 下将使用频率较高、覆盖面相对较广、计算量较大的查询作为实视图。针对向 o l a p 服务器提交的查询，最先使用已经在数据库中存储好的实视图来生成查 询结果，可以快速的得出查询结果。关系数据库管理系统也对o l a p 的查询功 能作出了很大的优化措施，例如并行化的数据管理、位图及连接索引、并行存 储及高速缓存、并行查询及查询优化、s q l 的o l a p 扩展( 具有c u b e ，r o l l u p 功能) 等多种重要技术优化o l a p 。 2 m o l a p m o l a p 是利用多维数组的形式存放o l a p 多维数据的，这样似乎形成了 一个“立方体”的结构。这样的有点是m o l a p 具有高的响应速度，能够对预聚 集计算得到的汇总数据进行快速的索引，但这种方式主要适合于密集型数据集， 对于稀疏数据集，存储上的利用率可能受极大的影响，随着数据规模的增大其 存储成本也大大增加。 3 h o l a p h o l a p 是对m o l a p 和r o l a p 的结合。分析人员将r o l a p 与m o l a p 两者的特性( r o l a p 的可伸缩性与m o l a p 的快速计算) 结合在一起，从而设 计了h o l a p ( 混合型o l a p ) 。 1 2 3 国内外研究现状 在应用需求背景的推动下，学术界和工业界一起开始对决策支持及其相关技术 进行研究和开发。针对数据仓库及其应用的不同特点，从提高数据仓库和联机分析 处理角度出发，学术界所进行的研究主要包括新的索引技术、实物化视图技术、多 维存储技术、新的查询处理和查询优化技术等等。 ( 一) 新索引技术【1 3 。1 7 】 索引是一种加快数据库中数据的加载和定位的内部结构。数据库的索引类似于 书籍的索引，不必遍历整个数据库就可以快速地找到表中的相关数据，因此通过创 建索引可以大大提高系统的性能，特别是对于以海量数据存储为特点的数据仓库来 说，正确地创建索引更是意义重大。对于以建立客户统一视图、存放历史数据为主 的数据仓库来说，数据查询是其最主要功能之一。然而，从数据仓库系统的数据组 织结构观察，不难看出此类系统查询的复杂性是普通的业务系统望尘莫及的：它经 常会涉及到多表的连接、分类、排序、累计等操作，同时查询时载入和返回的数据 9 面向数据仓库的多表连接与聚集算法研究 量一般都很大，系统资源耗费巨大。基于这些因素的考虑，相应的数据仓库索引技 术就应运而生了。文献 1 3 】中介绍了除b + 树以外的一些新的索引技术，如位图索引， 连接索引，多维索引等，并通过实验将其做了比较分析。实验表明新的索引技术确 实能够提高查询的性能。文献 1 7 】利用维的层次属性对维进行编码，利用生成的编码 代替原关键字，以实现关键字的压缩。 ( 二) 实视图技术【1 8 2 1 】 实视图是存储了实际数据的视图。在响应查询时，若能直接采用实视图技术， 则可以避免相应的重新计算，从而提高查询处理的性能。o l a p 查询分析是一个非常 耗时的过程，它通常涉及大量的数据，且要对数据进行投影、连接、分组等复杂处 理。o l a p 要求它的查询能够快速地给予响应，因此数据仓库则对经常可能提交的查 询建立许多“实视图”，它是含有数据查询结果的实际存在的表。通过这种预先计算 出来的数据结果并保存在数据库中，o l a p 无需每次提交查询都读取原始数据，而只 需比原始数据量小很多的实视图进行简单地计算便可以完成复杂的查询。目前存在 的实视图响应查询算法大部分采用顺序搜索的方法，以寻找可能响应查询的实视图 2 2 - 2 5 】。文献 2 6 中，g o l d s t e i n 等人提出了利用过滤树( f i l t e rt r e e ) 来减少可能响应 查询的实化视图的搜索空间，但所给出树的构造条件较为宽松，搜索得到的候选视 图集合仍然较大，而且当整个视图数量很大时，过滤树所需的内存空间也相应增加。 另外，过滤树的存储也未给予考虑，如果在每次系统启动时重新构造过滤树，将会 明显增加系统的启动时间。文献 2 0 1 首次提出在视图选择时先进行视图合并，但采用 的是顺序比较的合并方法。 实视图为系统解决快速响应用户需求的同时，但也带来了新问题。数据仓库中 的数据是由异构的传统数据库进行e t l 转化而来的，并随时间的推移不断增长，因 此如何使得数据仓库中的实视图与更新后的数据仓库仍能保持同步，即实视图的维 护，便成为一个关键技术。文献【2 7 首先提出了实视图选择的框架理论，在空间的限 制下，使查询响应时间和视图维护代价总和最小的实视图选择代价模型，它检查小 部分状态空间，使实视图满足空间的条件限制，达到时间要求。此外，其他学者也 对实视图的选择进行了一定的探讨2 8 。0 1 。 ( 三) 立方体计算( c u b e ) 数据立方体是多维数据库的一种形象描述方法，数据在多维数据仓库中是以数 据立方体( d a t ac u b e ) 的形式存储的【3 l 】。为了提高查询效率，常常采用预聚集技术将 1 0 第一章绪论 d a t ac u b e 中的数据进行聚集处理，然后将处理后的数据保存到数据立方体视图( d a t a c u b ev i e w ) 中【3 2 】。j i mg r a y 等人提出了“c u b e ”操作符，“c u b e 将数据由原来的二 维关系表组成多维立方体【3 1 1 ，在其上进行旋转、切片、切块、下钻( d r i l l i n g d o w n ) 和上翻( r o l l i n g u p ) 等操作，从而提高了s q l 对多维数据的支持。如何对立方体进 行多维计算及优化也是o l a p 实施的关键技术，在数据库领域，专家学者先后在数 据仓库中的c u b e 计算【3 3 3 4 1 、c u b e 预聚集处理【3 2 3 5 1 、c u b e 压缩存储陋3 9 1 、语义 c u b e 4 0 。4 1 1 、c u b e 更新【4 1 4 2 l 等方面取得了一些研究成果，提高了c u b e 的性能。 ( 四) 查询优化与并行处理技术1 4 3 j 为了提高查询速度，采用查询优化及并行处理技术，对d b m s 加以改进，充分 支持具有多处理器的s m p 和m p p 系统。并行处理主要包含数据装载时的并行、同 一查询执行时的并行、执行查询与数据装载的并行以及查询和与查询之间的并行。 对于r o l a p 进行查询时，经常要进行多个表之间的连接，在传统d b m s 中，一般 只支持两个表之间的连接，多表连接将被分成两表之间的连接一步一步去做。这就 有个连接次序问题，要选择最佳连接次序。由于f a c t 表非常庞大，因此进行多表连 接开销很大，为解决这一问题，在f a c t 表上建立连接索引( j o i ni n d e x ) 。与普通索 引不同，连接索引的属性不是f a c t 表的属性，而是维表中相应的属性，这样在多表 连接时利用连接索引，不进行真正的连接运算，就能找到符合查询条件的记录，从 而大大提高效率。 ( 五) 分组聚集技术【4 4 。4 6 】 在数据仓库中，o l a p 往往需在大量历史数据上进行复杂的分组聚集查询，这些 查询中通常包含多表连接和分组聚集操作，因此提高这些操作的性能成为提高o l a p 查询响应速度的关键问题之一。为了提高o l a p 的查询效率，减少i o 操作，胡孔法 等人提出了一种基于维层次编码的新型预分组聚集算法d h e p g a l 4 7 ，以及黄震华等 人提出一种降低连接和聚集操作的新算法j a c m d h 4 8 1 ，利用复杂多维层次的特点， 在位图索引的基础上，采用层次联合代理和预先分组排序，使得连接和聚集操作转 化为事实表上的区域查询，从而提高了效率。 1 3 论文研究内容与组织 1 3 1 论文的主要研究内容 本文主要围绕r o l a p 的海量数据聚集查询技术展开研究，对提高r o l a p 聚集 查询效率具有重要意义。主要研究工作如下： 面向数据仓库的多表连接与聚集算法研究 ( 1 ) 提出一种改进的分组序号聚集算法i m u g a 。该算法充分利用时间维表特殊 性，通过对事实表关键字直接获得分组属性值，减少了多表连接中时间维度的连接 次数，提高了联机分析处理查询效率。实验结果表明，该算法是有效的。 ( 2 ) 在联机分析处理( o l a p ) 中，有效地维度模型对海量数据的即席复杂分组 聚集查询起着关键的作用。在偏序和映射的基础上，通过定义层次有序维，提出了 一种基于层次有序维的分组聚集算法。该算法利用维属性之间的聚集关系，通过约 束层次链中的元素次序，实现了分组聚集计算中多表连接转换为维范围的查询，提 高了连接和聚集效率。最后，实验验证了该算法的正确性和有效性。 1 3 2 本文的组织 本文以数据仓库和o l a p 为研究背景，从提高数据仓库和o l a p 系统性能的角度 出发，讨论了基于关系存储的0 l a p 查询处理算法，包括多表连接算法和分组聚集算 法。为了提高数据查询的速度，研究了数据仓库的维度模型并且面向应用，参与设 计并实现了基于数据仓库平台的联机分析处理查询算法原型系统，取得了很好的效 果。 本论文由五章组成，具体安排如下： 第一章绪论中讨论了数据仓库和联机分析处理的相关概念和理论，以及本文研 究工作的意义和国内外研究现状，并简要介绍了本文的主要研究内容。 第二章分析研究了各种聚集计算方法，分析了这些算法的优缺点及可改进之处。 第三章给出一种改进的分组序号聚集算法的研究，并实现了算法。充分利用时 间维表特殊性，通过对事实表关键字直接获得分组属性值，减少了多表连接中时间 维度的连接次数，提高了联机分析处理查询效率。实验结果表明，该算法是有效的。 第四章给出一种基于层次有序维的分组聚集算法。该算法在偏序和映射的基础 上定义层次有序维，并利用维属性之间的聚集关系，通过约束层次链中的元素次序， 实现了分组聚集计算中多表连接转换为维范围的查询，提高了连接和聚集效率。实 验结果验证了该算法的有效性。 第五章总结与展望。总结己取得的研究成果，并分析有待继续深入研究的问题 和进一步拓展的方向。 1 2 第二章数据仓库的聚集计算技术 第二章数据仓库的聚集计算技术 2 1 引言 在已有的数据仓库环境中，许多决策支持应用需要在海量数据上进行复杂的查 询，由于大数据量以及查询的复杂性使得一个查询的执行需要很长的时间，查询速 度依然是数据仓库应用的主要瓶颈。到目前为止，聚集计算方法主要有基于排序和 基于哈希两种【4 9 1 ，现在的分组聚集查询一般都要求结果记录分组有序，采用基于排 序的方法将避免再次排序的过程。另外排序过程中结合预先分组，某些情况下能够 减少归并段的大小，从而减少磁盘存取，提高聚集查询性能。排序方法的研究有许 多新的成果，例如缓存优化的排序算法【5 0 】等，都可以用于基于排序的聚集算法。相 对排序方法，基于哈希的聚集算法性能相对较优，但是相差很少，基于哈希方法需 要解决数据偏斜等一系列困难问题，所以算法较为复杂。在大多数的企业数据库系 统中大都采用了基于排序的聚集计算方法。文章【4 5 】提到一种基于排序的分组聚集方 法m u s a ，对排序过程面向星型结构进行优化。文章【4 6 j 又提出一种基于分组序号的聚 集算法m u g a 。该方法使用各维内部的分组序号组合得到分组聚集的分组序号，然后 根据这个分组序号直接进行分组聚集计算。这样m u g a 算法就减少了m u s a 中开销极 大的排序操作，从而提高分组聚集的算法的性能。 2 2 基于排序的分组聚集算法 m u s a 算法【4 5 】的核心思想：首先，对各个维表进行处理，从而得到维表中每条记 录由分组字段而对应的分组序号；然后，进行多表连接操作，并采用各个维表内部 的分组序号组合成的分组排序关键字进行排序；最后，进行聚集计算。由于分组序 号组成的关键字较短，也就相当于对分组字段组成的排序关键字进行了数据压缩， 这样不但能提高排序的速度，而且小于关键字长度变短，还可以在必要时采用基数 排序方法来代替原来使用的快速排序方法，进一步提高排序的性能。另外，分组关 键字长度变短，也能够显著减少外存归并排序时由于暂存中间结果而带来的磁盘存 取开销。 下面以第三章中的实验用维表s h t i m e s 为例来说明m u s a 是如何进行预处理的， m u s a 算法在查询处理时，需要使用各分组字段在各个维表中对应的分组序号。首先 获得维表s h t i m e s 分组字段c a l e n d a ry e a r 的所有取值，并按字段c a l e n d a ry e a r 的值进 行排序，给出每个取值的分组序号。假设结果如下表2 1 所示： 1 3 面向数据仓库的多表连接与聚集算法研究 在得到每个分组字段值对应的分组序号以后，就可以相应给出维表s h t i m e s 每条 记录对应的分组序号g r o u p n o 。此外对于维表s h t i m e s j 丕可以得到按字段 9 2 1 维s h t i m e s 中年分组字段 t a b l e2 - 1g r o u pf i e l dy e a ri nd i m e n s i o n a ls h t i m e s v e r r g r o u p n o 1 9 9 80 1 9 9 91 2 0 0 02 c a l e n d a r j e a r 进行分组的分组数目g r o u p s y 。盯，表示分组数g r o u p s y e 盯的最小二进制位 数g r o u p s b i t y 。盯，以及分解组合关键字时需要的位运算掩 l - q g r o u p s m a s k y e 觚，对应于给 定的s h t i m e s 表实例这三个值分别为g r o u p s y c 打= 3 ，g r o u p s b i t y 。扩2 ， g r o u p s m a s k y 。矿3 。对于其它的维表也同样处理。进行多表连接时，对应于事实表 s h s a l e s 的每条记录，可以通过连接字段查找内存中的有序表，然后分别得到连接后 记录在每个维表中的分组序号，例女1 1 g r o u p n o y 。盯，u p n 0 删唧，将这些分组序号 组合起来就可以得到进行分组聚集计算的排序关键字。计算方法如下： k e y = 0 ： k e y = ( ( ( k e y l g r o u p n o ”d q o u p b i t c o 。n t r y ) l g r o u p n o 岫时使用上述方法计算得到 的分组排序关键字k e y 相比直接将分组字段组合成的分组关键字显然长度要短得多， 并由此显著提高聚集算法的性能。 算法流程： s t e p l 将查询q 分解为针对相应维表的单表查询； s t e p 2 分别提交每个单表查询得到维表记录，并得到每条记录对应的分组序号， 和分组字段个数g r o u p s i 、占用位数g r o u p s b i t i 、和位掩码g r o u p m a s k i 的值； s t e p 3 顺序扫描事实表的每条记录，通过上述k e y 值的计算方法得到事实表每条 记录的关键字组合值，并与聚集字段a 组合成记录r ( k e y ，a ) 放入排序缓冲区，缓冲 区满则转存至磁盘； s t e p 4 将s t e p 3 生成的若干有序记录序列归并成一个完全有序的记录序列； s t e p 5 进行聚集计算，将r ( k e y ，a ) 中k e y 相同的进行累加，最后将合并后i 拘k e y 反 算出相应维的分组字段，将所有分组字段和聚集结果s u m a 作为分组聚集结果放入磁 盘。 1 4 第二章数据仓库的聚集计算技术 2 3 基于分组序号的聚集算法 m u g a 算法f 4 6 j 是对m u s a 的一个改进算法，该方法使用各维内的分组序号组合得 到分组聚集的分组序号，然后根据这个分组序号直接进行分组聚集计算，这样相比 m u s a 算法避免了开销很大的排序操作，从而提高聚集计算的性能。 各个维表内部的分组序号采取了与2 - 3 1 节中m u s a 算法相同的方法，这里假设时 间、地区和产品维的内部分组序号分别为：g r o u p n o y 。矿g r o u