1.1 课题研究背景及意义
随着数据库技术的不断发展，大数据量的，尤其是海量数据的系统越来越多。人们对数据库的要求，已不再满足于简单的数据查询、数据统计，而是希望数据库能对原始数据进行深层次加工，从中挖掘出有用信息，支持决策分析。如何有效利用已有的数据成为人们关注的问题，也正是在这样的背景下数据仓库[1]应运而生。
数据仓库一经面世就以其巨大的应用价值和可操作的技术方案得到了国内外商业界、企业界和学术界的高度重视。数据仓库技术是公认的有利于信息利用的最佳解决方案，它不仅能从容解决信息技术人员面临的问题，同时也为商业用户提供了很好的商业契机。数据仓库已成为现代部门决策支持系统建立的重要技术手段。数据仓库的集成技术就是将分布的、异构的、的信息源中有用的数据抽取出来,经过转换和传输并最终集成到目的数据库系统中,最终给用户提供一个统一的数据视图,随之而来的数据挖掘技术、数据分析技术很好的应用在数据仓库之上使人们从海量数据中获得有效的信息成为了可能。与一般数据库中的简单数据查询不同，在数据仓库和联机分析处理等决策支持系统中，相对于明细数据来说，经过求和、计数、求平均值等聚集运算的数据更具有分析价值。因此，聚集运算是决策分析中主要的、也是关键的查询计算。聚集查询相对于普通查询，其运算量通常都很大，查询开销更为昂贵。如何有效地降低查询代价，快速地响应用户查询，是数据仓库和联机分析处理面临的重要问题，响应时间越短，给出的数据越准确是众多数据仓库专家研究的目标，在这个目标的驱动下Oracle首先提出了物化视图的概念， 此后MS SQL SERVER，DB2等大型的数据库管理系统(DBMS)也相继提出了这样的理念并付诸实践。
物化视图(Materialized Views )，被广泛应用于数据仓库和联机分析处理等各项应用。在数据仓库的海量数据的背景下，一个复杂的查询可能需要数分钟，甚至数小时，无法满足及时响应即席查询和联机分析处理等应用中的用户查询的要求。物化视图针对可能的复杂查询，对数据仓库中的原始数据进行投影、连接、分组等预处理，并将结果存储到数据仓库中。在数据仓库中预先进行多少SPJ运算，并将其结果存储到仓库中，这即是数据仓库中的物化视图选择问题。相对数据量庞大的原始数据，物化视图通过预计算，大大减少了数据量，所以能够快速地响应复杂查询。物化视图，成为影响决策分析系统性能的重要问题。然而，由于数据仓库的时变性，当数据源发生变化以后，物化视图会与数据源出现不一致，导致物化视图失效。因此，物化视图需要根据数据源的变化，不断进行调整维护，重新进行运算，刷新其数据，保持与数据源的一致。这就是物化视图的维护问题。物化视图的有效维护直接关系到数据仓库和联机分析处理的系统效率，因此，物化视图选择和维护问题是数据仓库中的重要研究内容。
物化视图技术的出现使得”信息孤岛”现象成为过去，给数据挖掘技术提供了展示的平台，帮助企事业单位充分利用过去积累的事务系统中的数据，为将来的发展进步提供潜在的信息。本课题依托北京市教育委员会科技发展计划项目《面向CIMS数据仓库体系结构及物化视图技术的研究》(合同编号：KM200810028016)完成。
1.2 国内外研究现状
数据仓库技术自产生之日起就引起了学术界和工业界的广泛关注，作为数据仓库中一项重要技术和数据仓库仲优化查询的解决方案，物化视图技术已经成为众多专家研究的对象，Stanford大学、Wisconsin大学、IBM Almaden研究中心等很多机构都成立了专门的研究小组，从事这方面的研究。在国内，国防科技大学、东南大学、中国人民大学、复旦大学以及科技大学等院校这方面的研究也较为活跃。但是如何选择适当的物化视图集并进行及时的更新，以充分地发挥它提高决策支持查询性能的作用，却是一个迫切需要解决的关键性技术问题。IBM, HP, Oracle等纷纷推出了自己的数据仓库产品和解决方案，一些小企业也在该领域找到了商机，推出了一些有用的数据仓库工具，这些产品为大型零售业、制造业等企业所采用，已有不少成功案例。
自90年代初 W.H.Inmon给出数据仓库的定义后，数据仓库技术就成为研究的热点［５］。许多专家开始研究数据仓库及其关键技术。很多大型企业利用已有数据跟踪市场需求、预测企业发展趋势，也利用数据仓库的先进技术，研究和实现数据仓库的方案。工业界大都考虑数据仓库的实现问题，学术界一般考虑数据仓库的关键技术的实现。作为一个新兴的研究领域，数据仓库和联机分析处理发展很快，许多大学和公司都正在这个领域进行着广泛而深入的研究，如探讨数据仓库的建立、维护等方面，研究物化视图技术等。斯坦福大学正在进行一个名为“WHPS”的科研项目，提出了一个基本的数据仓库模型和一些高效的算法，威斯康辛大学和AT&T也在研究物化视图、OLAP数据组织等方面的问题。传统上，视图是数据库中一个或多个基本表导出的表，其记录没有存储在数据库中，而是在需要时根据视图定义计算出来。而物化视图(materialized view)是物理上存储视图定义的数据，在数据仓库中，它是一张实实在在的表。数据仓库可以简单看成一系列异质复制的关系表和需要周期性进行维护的物化视图。对于大规模的数据集，分析用户希望能够迅速得到查询结果。在查询频率很高，而且视图很复杂的情况下，每次对查询重新计算视图是不可能的。一个很有效的方法就是利用数据仓库中存放的大量的物化视图，在用户进行查询处理时，无须实施计算复杂视图，而是利用这些物化视图就可以快速得到查询结果，比普通的查询修改方法快的多。目前，物化视图技术的研究是数据仓库研究的一个热点问题［８］。物化视图技术己经在数据仓库中得到广泛的应用。
国内外专家学者对物化视图的研究主要分为两大部分：一是物化视图选择问题；二是物化视图维护问题；物化视图选择的研究，集中在如何在众多的视图中选择出相对最优的视图集进行物化，以最大程度地缩短查询时间、减少扫描空间，从而达到优化查询满足用户需求的目的。在物化视图选择问题上，国内外提出、借鉴并改进了一些经典的算法，例如，遗传算法(GA)，它模拟了生物界的优胜劣汰的思想，从众多的候选视图中循环淘汰收益较低的视图，直至最后得到满足条件的视图，并将它们作为最终物化的视图集；贪心算法(Greedy)，Greedy算法也是循环选择物化收益最大的视图作为物化对象；以上两种算法是静态的选择算法，也即是查询和视图集都事先规定好，但是实际的应用中可能会出现查询频繁的变化的情况，并且静态算法的时间复杂度偏高，不适合在线运行，无法根据查询分布的变化对物化集做出即时的调整，为此一些研究人员针对这个问题，通过改造静态算法使之具有一定的动态调整能力[16]，从而可以用于用户需求变化不是很快的情况，一定程度上减少了管理员的工作量，在这种情况下就提出了动态选择算法FPUS[17]。
在数据仓库中，随着基础数据源的更新，物化视图必须及时更新以保证和数据源同步，因此，物化视图维护也是数据仓库中一项很重要的技术，得到了广泛的讨论[19]。视图维护最直接的方法是根据视图的定义重新计算生成，这种方法算法非常简单，无需一直保持数据源和数据仓库的连接，但算法的时间和空间代价很大，即使数据源出现很小的变动，都要对整个视图进行重新计算，其效率很低，除非一些特殊情况或别无选择，一般情况下很少采用。比较实用的方法是采用增量维护[19]的方法，它根据数据源的更新信息，只计算视图的变化部分，从而很好地刷新物化视图，虽然算法较复杂，但维护效率大大提高了，显著地降低算法的开销。增量维护算法中一个必须解决的问题是，在视图和数据源一致性维护中出现的“更新异常”[20][21]时怎么来处理，为此Y.zhuge等人首先针对单一数据源，提出了ECA算法[20]，该算法采用补偿查询来解决更新问题，文[33]在补偿思想的基础上，引入应答机制和版本控制来协调数据库和数据仓库之间的更新操作，以达到保证数据一致的目的。聚集或外联算子下的补偿维护讨论较少，相关研究亟待加强，其后，Y.Zhuge又提出了strobe算法[21-23]用以进行多数据源的数据仓库一致性维护，为了实现维护，算法需在数据仓库和数据源之间来回地多次传送查询和结果，时间开销很大，于是Agrawal提出的Sweep算法[24]，没有采用查询补偿机制，而利用临时查询结果解决了视图一致性维护中出现的“更新异常”问题，克服了ECA和Strobe算法中补偿查询算法的不足，以上算法在网络拥塞时，都会引起性能的显著下降。因此为了降低更新算法的网络开销和提高算法的效率，研究人员在增量维护的基础上又提出了自维护的概念[25]。它充分利用了中间辅助视图或是视图表达式所含的信息，以及部分数据源的备份，使视图的维护可以无需或者很少访问源数据即可实现。
1.3 论文组织结构
本文主要研究数据仓库中物化视图技术，全文总共分三大部分，第一部分包括第一二两章，主要阐述了数据仓库、物化视图等预备知识，第二部分主要包括第三、四章，重点讨论物化视图选择模型及相关算法设计，第三部分主要包括第五、六章，阐述了物化视图维护算法相关问题。各章节具体安排如下：
第一章为绪论，介绍了物化视图技术研究背景和意义，详细概述了物化视图选择及维护问题的研究现状，指出了现存的算法存在的不足，以便下文进行改进、完善。
第二章为数据仓库和物化视图的概述，这一章主要介绍了数据仓库产生的背景以及数据仓库定义，分析了数据仓库体系结构，并且着重介绍了数据仓库中物化视图的概念，进一步介绍了物化视图在数据仓库中所起的重要作用。
第三章为物化视图选择技术，本章介绍了代价计算模型，并且在代价模型基础上对经典Greedy算法进行改进，提出了BGIA算法，并且通过实验证明了BGIA算法较Greedy算法更适于物化选择。
第四章为物化视图选择代价模型和算法设计，这一章充分考虑了多种因素，提出了新的代价模型，在代价模型基础上设计了物化视图选择-BCMA算法，并且用实验证明了BCMA算法较BGIA算法性能优越。由于，BCMA和BGIA都是静态选择算法，有许多缺陷，最重要的是不适合在线运行，正是出于这一点考虑，本章提出了动态物化视图选择算法-SWAP-VSA算法，并且通过实验证明了SWAP-VSA算法比静态算法更适于物化选择，并且能在线动态运行，适宜于不断变化的查询。
第五章为物化视图维护相关问题的研究，分析了物化视图维护的体系结构，在此基础上进行改进，分析了经典ECA和Storbe算法存在的问题，并且针对这些问题提出了一种改进的物化视图增量维-护模型MVIM-Model，以便第六章进行算法设计。
第六章为物化视图维护算法设计，基于第五章提出的增量维护模型MVIM-Model，本章设计了物化视图增量维护算法-DMMVIM，通过实验证明了DMMVIM算法较Strobe和重计算策略在性能上优越。为了减轻网络的传输负担，本章还介绍了物化视图自维护算法，给出一物化视图自维护解决方案SMVSM-Project，通过一例子分析了改方案的可行性。
第二章 数据仓库以及物化视图概述
2.1 数据仓库定义
1988年IBM爱尔兰公司第一次提出了“信息仓库”的概念，这也是数据仓库的雏形。
1992年美国著名的信息工程学家William H.Inmon在《Building the Data Warehouse》（《建立数据仓库》）一书中首先系统的阐述了数据仓库的思想和理论，他将数据仓库的描述为：“数据仓库是面向主题的、集成的、随时间变化的、非易失的数据集合，用以支持经营管理中的决策制定过程。”[7]数据仓库的四大重要特征主要表现如下：
面向主题性（Subject-Oriented）：数据仓库围绕一些主题组织数据，并且它关注决策者的数据建模与分析，而不是像OLTP系统那样，集中于组织机构的日常操作和事务处理，因此，数据仓库是一种分析驱动/面向主题的数据处理技术，而不是传统的事务驱动/面向应用的数据处理方式。它是在较高层次上将企业信息系统中的数据结合、归类并进行分析利用的抽象。
集成性（Integrated）：通常，数据仓库是将多个异种数据源，如关系数据库、一般文件和联机事务处理记录集成在一起。由于数据仓库的数据是从原有分散的数据库数据中抽取来的，存在有许多不一致或综合性不够的地方，因此在数据进入数据仓库之前，必然要经过统一与综合，如一致的命名规则、一致的度量单位、一致的编码规则、一致的数据物理属性等，同时进行数据综合和计算，以保证了数据的可靠性与一致性。
随时间变化性（Time-Variant）：数据仓库的数据从历史的角度（例如过去 5-10 年）提供信息。数据仓库的数据反映的是一段相当长的时间内历史数据的内容，是不同时点的数据快照的集合，以及基于这些快照进行统计、综合和重组的导出数据，而不是联机处理的数据。数据库中进行联机处理的数据经过抽取、转换、加载到数据仓库中，一旦数据仓库存放的数据已超过数据仓库的数据存储期限，这些数据将从当前的数据仓库中删去。
非易失性（Nonvolatile）：数据仓库总是物理的分离存放数据；这些数据源自操作环境下的应用数据。数据仓库中的数据只在初始建立和更新的时候修改，其它时间数据仓库只提供数据的只读访问。其更新也是定时的。数据仓库是一种语义上一致的数据存储，它充当决策支持数据模型的物理实现，并存放企业战略决策所需信息。数据仓库也常常被看作一种体系结构，通过将异种数据源中的数据集成在一起，支持结构化的和专门的查询、分析报告和决策制定。数据仓库能够很好的支持决策支持系统和联机分析系统，这与传统的数据库系统在功能和性能要求上完全不同，数据仓库技术的发展对于数据库管理系统提出了许多特殊的要求。简单地讲，数据仓库就是企业内部一个专门的、大型统一的数据存储，支持更快速、更灵活、更有效的分析型数据查询。数据仓库是进行分析决策的基础，但还必须有强有力的工具进行分析和决策，这一工具就是联机分析处理系统。数据仓库是数据库技术的一种新的应用，而且到目前为止，数据仓库一般还是应用数据库管理系统来管理其中的数据。当前数据仓库的核心仍是关系型数据库管理系统管理下的一个数据库系统但数据仓库不同于操作型数据库系统，它提供的是综合的、经过提炼的信息，并且要保存历史数据以分析未来的发展趋势。
传统的数据库系统应用中，联机事务处理系统一直是应用的主流。在过去的几年，数据仓库技术经历了突飞猛进的发展，在大量的行业中得到了应用，包括零售业、金融服务业、交通、电信、公用事业等。同时数据仓库的研究也有了迅速的发展，表现在数据仓库数据模型、数据仓库设计、数据仓库体系结构、数据仓库管理、主动数据仓库、数据仓库中的数据操作，尤其是查询优化方面，在这方面主要集中在对物化视图技术的研究，用物化视图来提高查询的效率。
2.2数据仓库的优点
数据仓库是在数据量巨大、信息匮乏的大背景下产生的一门技术，自从出现之日起就产生了巨大的效果，总体来说可以分为以下8个方面来概述：
1、及时获取生产管理综合信息，为决策者提供科学分析依据；
2、改善管理能力，可以得到凭直觉无法得到的结论；
3、对转瞬即逝的机会快速作出反应，提高竞争能力；
4、既能够管理宏观信息也能够管理微观数据，可以追朔历史；
5、建立企业内部各部门之间的合作关系。
6、提供了面向主题的信息架构，存取数据方便，业务用户也能方便的取用这些数据。
7、开拓了进一步探索和研究的广阔空间
数据仓库支持进一步的探究，以发现数据所形成的趋势、构成的模式及其间的关系，这可引导用户改进现行的业务处理过程或作出正确的决策。
8、改善客户关系管理，让客户能获得更多的好处。
正是基于以上优点，数据仓库技术才得以蓬勃发展，为商业智能的发展奠定了良好的基础。
2.3 数据仓库体系结构
数据仓库从多个异构数据源中获取原始数据，整理加工后，存储在数据仓库的内部数据库中，这样，用户端就能通过前端工具对数据仓库进行访问，数据仓库收到用户端提交的查询请求后，在仓库中进行一系列的扫描然后将最终结果返回给用户。除了响应用户的查询外，数据仓库还能和数据挖掘很好的集成，给用户提供潜在的信息，从而进行决策支持。数据仓库体系结构见图1。
图1 数据仓库体系结构
从数据仓库体系结构图中可以看出数据仓库主要由三大部分组成：
1. 数据源：为数据仓库提供源数据，如各种生产系统数据库、联机事务处理（OLTP）系统中操作型数据、外部数据源(例如xls文件、csv文件、平面文件等)以及ERP系统等都可以作为数据仓库的数据源，通常,一个企业级数据仓库的数据源种类很复杂。
2．ETL(Extraction Transformation Loading)过程：ETL过程也即是抽取、转换以及加载的过程，根据已经设计好的数据仓库模型从数据源中提取数据，因为数据源种类繁杂，所以在抽取数据的过程中需要对数据的正确性、完整性、一致性、完备性、有效性、时效性以及可获取性进行有效性检查，根据数据仓库的设计要求,对数据进行重新组织、转换，然后装载到数据仓库的目标数据库中,并且可以周期性地刷新数据仓库以反映源的变化。SQL Server2000中的DTS就是和ETL原理相似，在SQL Server2005中SSIS也能完成ETL功能，专业的ETL工具主要有：
OWB(Oracle Warehouse Building),Datastage,Informatica,国产的Beeloader等。虽然这些工具都能完成ETL过程但是为了保证效率和灵活性，一般我们都是使用工具和脚本程序段相互配合使用来完成数据的抽取转换加载整个过程，整个ETL过程将占据数据仓库构建60%-70%的时间，数据抽取的成功与否对数据仓库中信息是否能够得到有效利用有着至关重要的影响，可见ETL过程是相当重要而且繁琐的工作。
图2
3．元数据存储：用于存储数据模型和元数据，其中元数据就是数据的数据，它描述了数据仓库中源数据和目标数据本身的信息。元数据包括技术元数据和业务元数据，技术元数据是存储关于数据仓库系统技术细节的数据，常见的有库表结构、数据映射、汇总算法等，业务元数据从业务角度描述了数据仓库中的数据，使得不懂计算机技术的业务人员也能够“读懂”数据仓库中的数据。业务元数据具体包括以下信息：企业概念模型、指标定义、代码标准化、用户访问报表的规则、权限等。
2.4 物化视图概念
视图是从一个或几个基本表或视图导出的表，视图和基本表不同，视图是一个虚表，即数据库中只将视图的定义存储在数据字典中,而不存放其所对应的数据。
1993年，关系数据库之父 E.F.Codd 提出了OLAP(On-Line Analytical Processing)，也即是联机分析处理的概念，OLAP是相对于OLTP(On-line Transaction Processing)联机事务处理而言的，如果说传统联机事务处理强调的是更新数据库——向数据库中添加信息，那么联机分析处理就是要从业务数据库中获取信息、利用这些信息进行决策分析，其中On-Line体现了OLAP一个非常重要的特性，即快速性。对于大量的数据分析要达到用户需求的速度，不是一件容易的事情，物化视图就是为了使 OLAP 系统能够在尽可能短的时间内回答用户查询而被广泛使用的策略之一。所谓物化视图就是一些经过简单的数据预处理，例如，联接、投影、选择操作等生成的存储在数据仓库中的实实在在的表。
2.5 物化视图在数据仓库中的作用
数据仓库中物化视图存储的数据是由底层数据库或其它数据源中的数据经过清洗、转换、加载而成的。为了加快查询速度，通常将查询频率高的视图内容保存在数据仓库中，这样便可以直接访问物化视图获取数据而无须再访问底层的数据库，与数据库中的视图相对比，物化视图不仅仅存储视图的定义,也存储视图所对应的实际内容。
物化视图对数据库系统，特别是大型数据库系统的查询性能有很大的提高作用。物化视图是以空间换时间的一种有效手段，可以实现更少的物理读和写，更少的CPU计算时间，更快的响应速度。数据库，数据仓库中的物化视图主要用于预先计算并保存表连接或聚集等耗时较多的操作的结果，这样，在执行查询时，就可以避免进行这些耗时的操作，从而快速的得到结果。在数据仓库中，还经常使用查询重写（query rewrite）机制，这样不需要修改原有的查询语句，例如Oracle数据库就会自动选择合适的物化视图进行重写查询，完全对应用透明。
物化视图的作用主要表现在下面四个方面[6]：
1） 降低网络负担
2） 创建大规模配置环境
3） 可以实现数据的子集化
4） 可以实现不连接计算
2.6 本章小结
本章介绍了数据仓库和物化视图技术方面问题，主要讲解了数据仓库定义、数据仓库优点、数据仓库体系结构，并且重点介绍了物化视图概念以及物化视图在数据仓库中的作用，从而为下面章节研究物化视图技术奠定了良好的基础下载本文
