收稿日期 2001-06-26基金项目 黑龙江省教育厅科学技术研究项目(9551104)。

文章编号:1005-3751(2002)01-0029-03关于数据仓库若干关键技术的研究Study on critical techniques of Data Warehouse周丽娟1,柳池2,刘大昕1(1.哈尔滨工程大学计算机科学技术学院,黑龙江哈尔滨150001;2.哈尔滨理工大学计算机与控制学院,黑龙江哈尔滨150080)Z H O U Li j uan1,LI U Chi2,LI U Da x in1(1.College of Computer Science and Technology,Harbi n Engineering U niv., Harbin HLJ.150001;puter&Control College,Harbi n Univ.of Science and Technology,Harbin HLJ150080,China)摘要:介绍数据仓库系统的基本结构,讨论了建立数据仓库的几个关键技术和实现方法,并比较了各种方法的优缺点,以便在数据仓库的实施中选择高效的技术方案。

关键词:数据仓库;实视图;联机分析处理ABS TRACT:Introduces structure of data w arehouse system and discusses som e critical techniques and methods of i m plement in data w arehouse.These methods are compared so that w e choose efficient technical s oluti on.KEYWO RDS:Data Warehouse;M aterilized View;On_li ne Ana lytical Processing中图分类号:T P311.13文献标识码:A1引言随着数据库技术的成熟和广泛应用,人们积累了大量的数据,利用这些数据可以进行分析和推理,辅助企业的决策,使企业获得最大的效益。

当今企业面临着一个激烈竞争的环境,自动快速获得有用的决策信息是企业获得最大效益的重要环节。

因此有必要建立企业的决策支持系统(DSS)。

但随着数据量的迅速增大以及查询要求的复杂化,建立在联机事务处理(OL T P)的数据库上的DSS,暴露出许多难以克服的问题:数据分散、没有统一的标准,缺乏组织性;只存储当前数据,难以满足决策分析对所需的历史数据的分析;数据访问效率低下。

为了弥补数据库系统存在的不足,数据仓库(DW)的思想逐步形成。

数据仓库是一个用以更好的支持企业或组织的决策分析处理的、面向主题的、集成的、稳定的、随时间不断变化的数据集合。

数据仓库系统不同于数据库系统,作为一个新兴的研究领域,数据仓库发展很快。

本文侧重讨论数据仓库所需解决的主要问题和可采用的技术。

2数据仓库系统的基本结构数据仓库系统由数据仓库、仓库管理工具和分析工具三部分组成,如图1。

图1数据仓库系统的结构数据仓库的数据来源于多个不同的数据源,它可以是通常的数据库系统,但也可以是非传统的数据,如文件、HT M L和SGM L文件、知识库等。

数据仓库管理包括:在确定了数据仓库的信息需求后,首先进行数据建模,然后确定从数据源到数据仓库的数据抽取、清理和转换过程,最后确定数据仓库的存储方法。

元数据是数据仓库的核心,它是对数据库中各个对象的描述,它遍及数据仓库的所有方面。

数据仓库管理包括对数据的安全、归档、维护、备份、恢复等工作,这些工作需要数据库管理系统的支持。

数据仓库是面向分析的,所以分析工具是数据仓库系统的一个重要组成部分。

分析工具包括用于完成决策问题所需的各种查询工具、检索工具、OL AP分析工具和数据挖掘工具等,以实现决策支持系统的各种要求。

292002年第1期微机发展3数据仓库若干关键技术数据仓库中数据量十分庞大,其实现是一项复杂的任务,要考虑相应的技术支持,如索引优化、视图的一致性维护、实视图的选择、并行处理技术、数据集成、存储与管理、多维数据组织、查询优化等。

3.1索引优化不论是数据库还是数据仓库,索引建立的好坏直接影响访问效率。

索引查找是优化查询响应时间的重要方法,因而它在数据仓库中得以系统的应用以提高数据仓库的处理能力。

在数据仓库中存在复杂的查询类型、海量数据和频繁的读操作,这些因素使在OL T P 系统中的查询处理/优化技术不适合数据仓库环境。

传统的B-T REE索引在数据库系统中作为外部索引已经被广泛应用,它对查询响应时间和空间提供了有效的结构。

它非常适合于查找并取回少量记录的情况。

但对于数据仓库的复杂交互查询,存在三个缺点:(1)B-T R EE只在索引是高基数(基数是一个表列中不同值的个数与整个表中的行数的比值)的时候才有价值;(2)B-T R EE索引在数据仓库中构造和维护的代价高;(3)B-T R EE索引对于简单查询比较有效,而在数据仓库的复杂查询中,往往是无能为力的。

因此,在数据仓库中采用位图索引(Bit-M ap)技术,它可使查询处理和索引存取的效率提高许多倍。

位图索引突破B-T REE索引的一些限制,它可以非常有效的对低基数数据进行索引。

位图索引就是使用0或1来表明在元组中的属性值是否和一特定值相等。

在位串中一位的状态表明了表中元组的状态。

索引的主要任务就是通过缩小搜索空间的范围来加速查询过程。

无论是B-T REE还是位图索引都可以达到此目的。

但是,在查询中给出两个或更多选择条件,比如A=a i和B=b j,在属性A和B上分别建立的B-T REE索引,它们不能有效的综合,共同完成查询。

需要建立在复合关键字上的另外一个B-T REE 索引。

然而,在A和B属性上分别建立的位图索引,它们能共同取回所需的数据,只要在相应的位图向量上实施一个!AN D∀操作即可。

因此,在用户查询中涉及的属性最大有n个,只要建立n个位图索引即可。

选择条件的任何组合都包括n个属性的任意子集,可以通过在相应位图向量上实施逻辑操作即可被计算出来。

但是如果在复合关键字上建立B-T REE索引,为了包含在n个属性上所有可能的选择条件,需要C n1+C n2+#+C n n=2n-1个B-T REE索引。

维护如此多的B-T REE的代价是难以接受的。

在数据仓库环境中,位图索引优于B-T R EE索引:(1)建立和维护位图索引时间和空间代价小;(2)位图索引可以彼此一起工作达到减少搜索空间的目的。

然而,随着关键字的基数增加,建立和维护位图索引的时间和空间复杂度也迅速提高。

在高基数情况下的另外一个问题是位图向量的稀疏。

稀疏度平均是(m -1)/m,其中m是属性的基数。

随着m的增长,空间利用率下降,这时,位图索引的性能迅速下降,可能比B -T REE索引的性能更差。

因此位图索引不适合高基数数据,如对于姓名或地址等可能有数万个选值的数据往往需要取回全部原始数据值才能获得查询结果。

在数据仓库环境下,位图索引优于B-T R EE索引,但随着基数的增加,位图索引存在不可克服的缺点。

如何高效地建立数据仓库的索引,提高查询性能,从整体上使系统得到最优,是需要进一步研究和探讨的问题。

3.2视图的维护数据仓库中存储了大量的从多个、分布、异质数据源中集成的信息,这些信息数据仓库中以视图的形式存在,被称为实视图(M ater ialized View)。

数据仓库主要是为O LAP提供支持。

OLA P查询分析通常需要涉及大量的数据,不可能将查询传送到原始的数据源中去,因为这不仅很复杂,且非常耗时,尤其当数据源很多,而且分布在不同的场地时。

因此在数据仓库中实视图即用作快速查询和分析,它有效的提高了查询速度和响应时间。

但当基础关系表因元素的插入、删除和更新而发生变化时,实视图必须作相应更新以保证查询结果的正确性。

这种对源数据发生变化后,保证视图也是最新的过程叫视图维护(V iew M aintenance)。

保证实视图与源数据一致是数据仓库要解决的关键问题之一。

对视图维护问题的一种解决方法就是每次当原始数据发生改变时,在数据仓库端对实视图频繁的重新计算。

这种方法会导致很大的额外存储和维护代价。

而且这种作法有时也是不可能的,因为数据仓库的空间是有限的。

因此,近几年对视图维护采用增量计算的方法比较多,即当数据源中的数据发生变化时报告给集成器,集成器计算相应的变化,然后将这些变化通告给数据仓库。

Y.Zhuge等人提出了ECA方法(Eager Compensating Alg orithm)。

该算法设计只针对单个数据源的情况,它通过补偿查询来解决更新问题。

30微机发展2002年第1期后来,Y.Zhuge打破了ECA算法中单数据源的限制,提出了Strobe算法。

该算法基于多数据源环境视图一致性维护。

它要求所有基本关系的关键字都包含于视图中。

除了此视图的定义限制外,还要求实视图更新时必须保证信息源是静止的。

对于多数据源的视图维护算法,Agraw al等人提出了SW EEP算法。

和Strobe算法相比,它对视图的定义更灵活,它不要求基本关系的关键字必须保存在视图中。

另外,它不要求视图更新时系统是静止的。

上述三种算法有一个共同的限制即是信息到达视图的顺序和在数据源产生时的顺序相同。

3.3实视图的选择视图维护导致了所谓的视图维护代价。

数据仓库中存储的许多实视图占据着大量的存储空间,而且它们的一致性维护也需要占用大量的CPU时间。

在存储空间有限、用于维护的视图的CPU时间有限,同时又要最大限度缩短O LAP查询时间的情况下,对所有视图都进行实体化是不可能的,选择其中一部分实体化已成为目前数据仓库研究的重要课题。

这个问题被称作视图选择问题(VSP),它直接影响用于决策支持的数据质量和数据仓库的效率和维护代价。

为了解决VSP问题,很多研究人员提出了一些解决方法。

一个最显而易见的算法就是在一系列查询中应用完全搜索算法进行实视图选择。

然而如果搜索空间很大时,这种算法代价很高,是不切实际的。

H.G upta使用Gr eedy算法,它检查一小部分状态空间,使实视图满足空间的条件限制,达到了时间要求,但这种方法性能不是很好的。

Kenneth.A.Rose研究动态视图的修改问题。

J.Y ang给出了一个结构和算法,其基本思想是选择大部分视图可以∃共享%的公共子视图进行实体化。

遗传算法是基于自然选择和基因遗传原理的优化和搜索算法,用它来解决VSP问题也不失为好的选择。

利用遗传算法将视图选择问题的解决方法看成是染色体展现。

每个染色体都由固定数目的二进制串组成(0或1),固定数目是指在A ND-OR图中候选视图的数目。