（计算机应用技术专业论文）并行数据仓库paraware系统的多维数据管理技术.pdf

并行数据仓库p a r a w a r e 系统的多维数据管理技术：摘要 摘要 本文论述我们自行研究开发的一个并行数据仓库系统p a r a w a r e 的核心技术多 维数据的存储、查询和维护技术的理论研究和系统实现。 本文共分四个部分。第喑b 分介绍了数据仓库和联机分析技术的产生与发展，介绍 p a r a w a r e 系统研制的背景和它的整体系统结构，给出了本文的研究内容和创新点。 本文第二部分主要介绍p a r a w a r e 的多维数据存储和索引策略。常用的多维数据存储 方式有两种：关系表方式( r o l a p ) 或多维数组方式( m o l a p ) 。r o l a p 在数据的存储容量、 适应性上占有优势，但其数据存取较m o l a p 复杂。m o l a p 存储效率高、访问速度快。但 是，它存在着数据稀疏和各个维访问速度不对称两个致命问题。p a r a w a r e 系统采用了将 r o l a p 和m o l a p 两种存储方式相结合的混合存储模式，借助于一种分层编码的b i t m a p 索引，充分利用了二者的优点、克服了它们的缺点，在节约存储空间的同时，提高了查 询的效率。 最近兴起的语义数据方体存储技术将具有相同性质的数据元素压缩存放在一起，大 大缩减了数据方体的存储空间，但是它只适合于存储分布型和代数型聚集函数，而对于 整体型聚集函数例如m e dj a n ，如果采用这种存储方式存储的话，维护的时候需要存储所 有的历史数据并对他们进行排序，代价昂贵。因此，p a r a w a r e 针对整体型聚集函数，提 出了一种新的数据存储方法一a d d s e t 语义存储方法。该方法不但进一步缩减了数据方体 的存储空间，同时提高了整体型聚集函数的维护效率。 本文的第三部分介绍p a r a w a r e 的查询处理和优化子系统。根据数据仓库中数据的多 维性特点，p a r a w a r e 采用微软定义的多维表达式( m d x ) 作为系统的查询语言。相对于 o l t p 应用来说，o l a p 分析型应用的查询要复杂许多。为了得到真正的联机处理性能， p a r a w a r e 采用了针对分析型应用的的如下查询处理技术：( 1 ) 将一个m d x 查询分解为多 个子查询，每个子查询对应一个底层实体化视图：( 2 ) 对每个子查询进行单独处理，选 择合适的实体化视图对它进行回答；( 3 ) 将各个子查询的查询结果进行组装后返回给前 端用户。 由于数据仓库系统中数据组织( 如采用多维存储) 和查询类型( 如采用m d x 查询语 言、在不同维不同层上进行聚集操作) 的特殊性，传统的关系数据库查询优化技术不能 在o l a p 环境中直接加以应用。为保证分析型应用的联机高性能，p a r a w a r e 采用了如卜| 查询优化技术：( 1 ) 基于实体化视图的多查询优化；( 2 ) 识别和提取公共子查询；( 3 ) 基于语义数据块的查询结果缓存和基于知识的缓存数据淘汰技术。 第四部分介绍p a r a w a r e 的增量维护子系统。主要针对语义存储结构，借助传统的 g a l o i s 格理论，捕捉了不同类型等价类的特征并提出了确切的维护策略。针对分布型和 代数型聚集函数，提出了两种有效的增量维护算法，一种是单元组增加的方法，另一种 是批量增加的方法。针对整体型聚集函数，提出了一种滑动窗口技术，该技术和a d d s e t 中国科学院博士学位论文一并行数据仓库p a r a w a r e 系统的多维数据管理技术 语义存储结构相结合，有效地缩减了维护整体型聚集函数所需要的运行时问。 关键词：并行数据仓库，多维数据存储，查询处理和优化，多维表达式，增量维护，滑 动窗口 并行数据仓库p a r a w a r e 系统的多维数摧管理技术：h b s t r a c t t e c h n i q u e so fm u l t i d i m e n s i o n a ld a t as t o r a g e ，q u e r ya n d m a i n t e n a n c ei np a r a w a r es y s t e m l i c u i p i n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rw a n gs h a n t h i sd i s s e r t a t i o na d d r e s s e st e c h n i q u e so fm u l t i d i m e n s i o n a ld a t as t o r a g e ， q u e r ya n dm a i n t e n a n c ei nap a r a l l e ld a t aw a r e h o u s es y s t e mn a m e dp a r a w a r e ，w h i c h i sd e s i g n e da n di m p l e m e n t e dc o m p l e t e l yb yo u r s e l v e s ， t h i sd i s s e r t a t i o ni sc o m p o s e do ff o u rp a r t s i n p a r to n e ，t h e t e c h n i c a l d e v e l o p m e n t o f d a t aw a r e h o u s ea n do l a pi s i n t r o d u c e d t h e nt h eo v e r a l la s p e c t so fp a r a w a r e 。w h i c hi n c t u d ei t sr e s e a r c h b a c k g r o u n da n di t ss y s t e ma r c h i t e c t u r e ，a r es u r v e y e d ，f i n a l l y ，t h e m a i nc o n t e n t s a n dt h er e n o v a t i o n so ft h ed i s s e r t a t i o na r ep r o p o s e d i n p a r tt w o ，t h em u l t i d i m e n s i o n a td a t as t o r a g ea n di n d e xs t r a t e g i e s o f p a r a w a r ea r ei n t r o d u c e d t h e r ea r et w oc o m m o nw a y st os t o r em u t t i d i m e n s i o n a l d a t a ：u s i n gr e l a t i o nt a b l e s ( r o l a p ) o ru s i n gm u l t i d i m e n s i o n a la r r a y s ( m o l a p ) r o l a ph a st h ea d v a n t a g e st h a ti tc a ns t o r em o r ed a d aa n dh a sm o r ef l e x i b i l i t y b u tt oa c c e s st h ed a t ai nr o l a pi sc o m p li c a t e d 。o nt h eo t h e rh a n d ，t h es t o r a g e e f f i c i e n c yo fm o l a pi sh i g h 。b u ti th a s t w od i s a d v a n t a g e s ：t h ed a t ai ni tm a y b et o os p a r s ea n dd i f f e r e n td i m e n s i o n so f i tm a yh a v ed i f f e r e n td a t a a c c e s sr a t e s p a r a w a r ep r o p o s e dam i x e ds t o r a g em e t h o dt h a tc o m b i n e sr o l a pa n dm o l a p w i t h t h eh e l po fat r e ee n c o d i n gb i t m a pi n d e x ，t h i sm i x e ds t o r a g em e t h o dn o to n i y s p a r e st h es t o r a g es p a c eb u ta l s oi n c r e a s e s t h eq u e r ys p e e d r e c e n t yp r o p o s e ds e m a n t i cd a t ac u b es t o r a g et e c h n i q u eg r o u p s t h o s ec e ll s t h a ta g g r e g a t e df r o mt h es a m es e to fb a s er e l a t i o nt u p l e s t h i sm e t h o dg r e a t l y r e d u c e st h es t o r a g es p a c eo fad a t ac u b e 。b u ti ti so n l ya p p r o p r i a t ef o rs t o r i n g t h ed i s t r i b u t i v ea n da l g e b r a i ca g g r e g a t i o nf u n c t i o n s f o rh o li s t i ca g g r e g a t i o n f u n c t i o r ss u c ha sm e d i a n a 1 1h i s t o r yd a t an e e d st ob es t o r e da n ds o r t e dw h e n t h ed a t ac u b ei sm a i n t a i n e d 。t h em a i n t e n a n c ec o s to ft h i ss e m a n t i cs t o r a g em e t h o d i sv e r ye x p e n s i v e 。w ep r o p o s e dan e ws e m a n t i cs t o r a g em e t h o di np a r a w a r es y s t e m f o rh o l i s t i ca g g r e g a t i o nf u n c t i o n s t h i sm e t h o dn o to n l yr e d u c e st h es t o r a g e s p a c em o r eb u t a 1s oi n c r e a s e st h em a i n t e n a n c ee f f i c i e n e y i np a r tt h r e e ，t h eq u e r yp r o c e s sa n do p t i m i z a t i o ns t r a t e g i e so fp a r a w a r e a r e i n t r o d u c e d 。p a r a w a r eu s e sm d xt h a tw a sd e d i n e db ym i c r o s o f tc o m p a n ya s i t s m u l t i d i m e n s i o n a lq u e r yl a n g u a g e c o m p a r e dt oo l t pa p p l i c a t i o n ，o l a pa n a l y s i s a p p l i c a t i o ni sm o r ec o m p l i c a t e d i no r d e rt oo b t a i nr e a l o n i i n ep e r f o r m a n c e ， i 菇 中国科学院搏十学位论文一并行数据仓库p a r a w a r e 系统的多维数据管理技术 p a r a w a r ep r o p o s e dt h ef o l l o w i n gq u e r yp r o c e s st e c h n i q u e s ：( 1 ) s p l i tam d xq u e r y i n t om o r es u b q u e r i e s e a c hs u b q u e r yi sm a p p e dt oam o r ed e t a i l e dm a t e r i a l i z e d v i e w ( 2 ) e a c hs u b q u e r yi sp r o c e s s e ds e p a r a t e l y a c c o r d i n gt oac o s tm o d e l a p p r o p r i a t em a t e r i a l i z e dv i e wi ss e l e c t e dt oa n s w e rt h es u b q u e r y ( 3 ) a s s e m b l e t h er e s u l t so fe a c hs u b q u e r i e sa n dr e t u r n e di tt oe n du s e r s f o rt h e s p e c i a l d a t a o r g a n i z a t i o n a n d q u e r yt y p e s ，q u e r yo p t i m i z a t i o n t e c h n i q u e si nt y p i c a lr e l a t i o n a ld a t a b a s ec a n n o tb eu s e di no l a pe n v i r o n m e n t t h e f o l l o w i n gq u e r yo p t i m i z a t i o nt e c h n i q u e s a r e p r o p o s e d i np a r a w a r e ：( i ) m u l t i q u e r yo p t i m i z a t i o nt e c h n i q u e b a s e do nm a t e r i a l i z e dv i e w s ：( 2 ) p u b l i c s u b q u e r yr e c o g n i z a t i o na n dp i c k u pt e c h n i q u e ( 3 ) q u e r yr e s u l t sc a c h et e c h n i q u e b a s e ds e m a n t i cc h u n k sa n dc a c h e dd a t ar e p l a c e m e n tp o t i c yb a s e do nk n o w l e d g e i n p a r tf o u r ，t h e i n c r e m e n t a lm a i n t e n a n c e s t r a t e g i e s o fp a r a w a r ea r e i n t r o d u c e d t h ef o c u si so ns e m a n t i cs t o r a g es t r u c t u r e w i t ht h eh e l po ft y p i c a l g a l o i sl a t t i c et h e o r y ，w ec a p t u r e dt h ec h a r a c t e r is t i c so fd i f f e r e n te q u v a n l e n c e c l a s s e sa n dp r o p o s e dt h ee x a c tm a i n t a i ns t r a t e g i e s f o rt h ed i s t r i b u t i r ea n d a l g e b r a i ca g g r e g a t i o nf u n c t i o n s ，w ep r o p o s e d t w oe f f i c i e n ti n c r e m e n t a l m a i n t e n a n c ea l g o r i t h m s o n ei sf o rs i n g l et u p l ei n s e r t a t i o n ，a n da n o t h e ri sf o r b a t c ht u p l e si n s e r t a t i o n f o rt h eh 0 1 i s t i ca g g r e g a t e df u n c t i o n ss u c ha sm e d i a n ， w ep r o p o s e das l i d i n gw i n d o wt e c h n i q u et h a te f f i e i e n t l yr e d u c e st h ec o s to f m e d ja nm a in t e n a n c e k e y w o r d s ：p a r a l l e ld a t a w a r e h o u s e ，m u l t i - d i m e n s i o n a ld a t as t o r a g e ，q u e r yp r o c e s s a n d o p t i m i z a t i o n ，m u l t 卜d i m e n s i o n a e x p r e s s i o n 。i n c r e m e n t a l m a i n t e n a n c e ， s l i d i n gw i n d o w 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：李珲午日期：1 。一，c 争，f 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 作者签名：耋罕爷 导师签名：7 侈日 日期：”c 专。f 哆 第一章弓f 奇 第一部分数据仓库和o l a p 系统总论 l ，1 数据仓库和o l a p 的产生与发展 第一章引言 信息作为现代企业的宝贵资源，占据着越来越重要的地位，己经成为现代企业科学 管理的基础和正确决策的前提。能否拥有及时、准确、全面的信息已经成为衡量一个企 业是否具有发展潜力的一个重要指标。数据仓库利用大量高质量的数据源构建信息系统 旨在为企业进行全局范围的战略决策和长期趋势分析等提供有效的支持。越来越多的研 究表明，采用数据仓库所带来的好处是实质性的和可度量的。i d c1 9 9 7 年曾进行了一项 研究，在调查了6 2 家各种规模的采用了数据仓库的公司之后，得出的结果表明：他们的平 均r o i ( 投资回报率) 超过4 0 0 ；而一些采用了较小型的部门级数据仓库( 有时也被称为数 据集市( d a t am a r t ) ) 的公司，其平均r o i 甚至超过了6 0 0 。 数据仓库是面向联机分析处理( o n l i n ea n a l y s i sp r o c e s s i n g ，简称o l a p ) 的系统， 而数据库主要用于事务处理，是面向联机事务处理( o n l 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 ) 的。关系数据库之父e f c o d d 于1 9 9 3 年最早提出了o l a p 的概念。当时， c o d d 认为o l t p 已不能满足终端用户对数据库查询分析的需要，s q l 对大数据库进行的 简单查询也不能满足用户分析的需求。用户的决策分析需要对关系数据库进行大量计算 才能得到结果，而查询的结果并不能满足决策者提出的需求。因此c o d d 提出了多维分 析的撅念，即0 l a p 。 o l a p 用于管理人员的决策分析，决策支持过程要求系统保存大量的历史数据，以支 持长期趋势分析；集成全局范围的数据，以支持宏观及综合分析的能力；具有对大量数 据进行复杂分析的能力；对复杂的决策检索过程具有快速响应的能力等。而o l t p 则是 指对数据库联机的日常操作，通常是对一个或一组记录的查询和修改，主要是为企业的 特定应用服务的，人们关心的是响应时问，数据的安全性和完整性。 概括来说，一个o l a p 系统应具有以下特征： 快速响应o l a p 系统的设计目标是以最快的速度( 通常不超过5 秒) 对用户查询 作出响应。但是，当数据量很大的时候，实现快速响应很难( 尤其对于o n - t h e f l y 或a dh o c 查询来说) 。为此，人们求助于很多技术，如采用特定的存储格式， 采用预计算技术，借助于硬件的力量等。 灵活分析系统应提供对各种商业和统计逻辑的分析功能并以清晰易懂的方式提 交给最终用户。尽管系统可以提供编程接口给用户来实现某些分析功能，但是 中国科学院博士学位论文一并行数据仓库p a r a w a r e 系统的多维数据管理技术 这种方式太复杂，难以被用户接受。应该允许最终用户以更直观一些的方式来 进行分析，比如提供货币转换，目标搜索，数据挖掘等功能。 安全共享系统应能够提供安全性保证。如果允许多个用户同时写的话，应该在 适当的层次上提供并发控制锁。系统应该提供能够同时对数据进行安全修改的 方法。很多o l a p 产品在安全性控制方面都比较弱，他们都假定o l a p 应用是只 读的。即使有的产品有安全机制，也比较简单。 多维性多维性是o l a p 的最关键特征。要从不同的角度分析商业数据，系统必 须能够提供数据的多维视图，包括多个层( 1 e v e l ) 和多个层次( h ie r a r c h y ) 。 海量存储该特征用来衡量o l a p 系统处理数据的能力。不同的o l a p 产品处理数 据的能力不同，处理的数据量可能相差上千倍。 o l a p 通常以数据仓库为支撑，数据仓库为o l a p 服务器提供丰富的数据基础。图1 一l 是一个典型的数据仓库和o l a p 共同协作的体系结构图。 操作型数据源 图1 - 1 数据仓库和o l a p 体系结构 前台丁具 从上图可以看出，该系统总体上来讲分为以下几个部分：数据仓库的后台工具、数 据仓库服务器、o l a p 服务器和前台工具。 数据仓库的后台工其，包括数据抽取、清洗、转换、装载和维护工具。它们负责把 企业或组织中各部门的操作型数据进行转换，装载到数据仓库系统中，同时维护数据仓 库和操作型数据源数据的一致性。 数据仓库服务器一般是关系d b 嬲或扩展的关系d b m s 。o l a p 服务器透明地为用户提 供多维数据，用户不必关心数据到底存储在什么地方。但物理上必须考虑数据存储问题。 数据仓库服务器和o l a p 服务器之问的功能划分没有严格的界限，根据数据存储方式 的不同有如下几种实现方式： 专r o l a p 结构：这种结构采用关系d b m s 或扩展的关系d b m $ 来存储和管理数据，用 2 第一章嘻l 言 o l a p 服务嚣做其他剩余的事情，例如聚集计算，镬询优化等。m i c r o s t r a t e g y 公司豹d s s 黻务爨秘i n f o m i x 戆m e t a c u b e 均莱惩r o l a p 绩魏。器秘粒疫熬数据 均以关系袭的形式存储程数据仓库中。 m o l a p 结构：这种结构采用多维数组米存储数据，a r b o r 公司的e s s b a s e 采用的 就是l a p 结构。多维数缀存储的优点是可以对数撼进幸亍直接定能，不需要索引， 毽在数据耩筑瓣清凝翥要进行数据疆缩。 h o l a p 结构；这种结构将r o l a p 和m o l a p 结合起来，既稍用了r o l a p 可扩展性好 的优点，也利用了m o l a p 计算速度快的优点。例如，可以将细节数据存在关系数 据痒中，聪姆综合数据存在m o l a p 服务器中。微软的s q ls e r v e r7 0 采用斡就 是这耱结构。 特殊s q l 服务器：为了满足日益增长的o l a p 处理的需求，一些关系数据库或数 据仓库厂商( 如r e d b r i c k ) 对原来的系统进行了扩展，为只读环境下在星型域 雪冀摸型蘩懿上送行s q l 查询疆供支持。 前台工其包括凌询报表、多维分析和数攒挖掘等凡类，蠲于向数据仓库管理系统发 出请求，并把返回的结果通过备种可视化方式展现给用户。 建立数据仓库系统的目的主要是为企业提供决策支持。在过去的几年中，数据仓库 蠢o l a p 技术霉裂了逐速蓑震，它裁凌避痰愆翔素造、零懿、令：藏羧务、交逶、电信、 保险等多个行业。现阶段，以数据仓库为中心，建立一个企业或组织的体系化数据环境， 并在这个数据环境上建立企业决策支持应用，已经成为目前我国企业信息化建设的现实 嚣求。箍且，随羲我雹绩惠化建设的不断深入，这静嚣求逐会迅猛增长。 1 2 并行数据仓麾p a r a w a r e 系统简介 i 2 。i 。p a 融皲跹瓣磺劐鹜景 由于数据仓库系统是面向分析型的应用，所以历史的综合的数据对宦来说非常重要。 随蓿时间的推移，数据仓库中存储了大量的数据，经常达刹t 级。如何肖散地存储和管 理这麓数据是令鬻复杂夔闼熬。瓣置疆羲众蝗鼗摇筵瑾经验馥投黍，涉及大数据爨豹 分析需求与目俱增，企业管理者需要使用大嫩的数据进行备种复杂的分析( 如趋势分析 和数搬挖掘等) ，这需要相当长的计算时间，常常超出了用户能够忍受的极限。由于单 枫系统能够提供韵资源有艰，使髑现有的数攒仓痒技术如：预综合数攒，特殊的聚集攥 蕈魏c u b e 操俸籍，特殊静索孳 缭梭鲡b i t m a p 等等，只熊程菜种程度土瓣离数据仓瘁系 统的性能。 躜想为大数据嫩的数据仓库提供数据存储和管理、提搿各种联机分析处理的性能， 必须将数据仓痒系统程并零亍鼓零结合越来。势晕亍技术在著行数摆瘁系统中靛应爱已缀翼 趋成熟，可以为并行数据仓库的研究提供借撩，但传统的并行数据库系统的一些基本方 法，| j i ；j 手没有考虑数据仓库系统中数据组织( 如采用多维数组存储) 和谢询类型( 如采 土 中嚣辩学院磷生掌短论文势苻数据仑瘴p a r a w a r e 系统鲢多罐数据管理技术 用m d x 焱询语言、在不间维不同层上进行聚集操作) 的特殊性，不能直接加以应用，必 须对其遴 子适应洼穆蒗，将它帮褒鸯魏数据仓露技术绪台慈塞一超镬矮。 基于这种思路，我们研制开发了基于网络环境的面向分析的并行数据仓库系统 p a r a w a r e 。它的设计目标是要在国产的数据库管理系统p h a s e 的基础上，实现对数据仓 库管理功能的扩展，完善国产数据艨的整个产品体系，以满足企业从事务处理到决策支 蒋懿各麟次豹应焉要袋。本顼垂获缮了国家蠡然耱学基金静支特，蒡已予2 0 0 2 年褒竞 成了一个初步的原型系统。 1 2 。2 。p a p , a w a r e 的特色 近年”柬数据仓库和o l a p 技术成为个十分活跃的研究领域，各国大学和研究机构纷 纷展开了对数据仓库的研究，例如作为专业数据库厂商的i b mv i s u mw a r e h o u s e 产品， 露隽菲专渡数据库厂巍的s a sd a t aw a r e h o u s e 产熬，班及掺麓教育科研搬稳戆囊坦描 大学( s t a n f o r du n i v e r s i t y ) 开展的数掘仓库硪隧黼i p s 。圆内晗尔滨工娥大学李建中 教授领头研制了并行数据仓库系统p d w m s 。 和现商的并行数据仓库系统相比，p a r e w a r e 舆有以下特甑： 支持超太数撂豢存德p a r a w a r e 暴瑁了灵滔多群魏多缀数据玺织方法。薅关系存 储和多维存储相结合：首先，将一个数攒方体划分成多个数据块。蔟次，对不同 的数据块，根据数据稀疏程度的不同，或者采用多维数组直接存储，或者采用一 秘特殊的关系袭进季亍存储。这群，既利用了多维存储访闷速度快豹傥点，又列用 了关系存储节约空闻静优点。溺孵，本文瓣出了一静耨瓣语义数援存德方法，送 一步缩减了数据方体的存储空间，为数据仓库环境下越犬数据量的数据存储奠定 了壑实的基础。 支持m d x 多维囊逶语言微软发布的“o l ed bf o ro l a p ”标准中定义了雳予访翊 多维数据源的多维表达式( m d x ) ，它提供了语义丰富的镬询多维数据的语句，自 缴布以来逐渐成为工业界的攀实标准。因此，p a r e w a r e 采用m d x 作为查询语言 其囊非常现实的意义。 鬟鸯毫套圣氅楚瓒性能襁对予o l t p 应强来说，o l a p 分攒鳘应用懿套谗要复杂诲 多。为了得到嶷正的联机处理效果，p a r e w a r e 采用了专门针对分析型应用的新 的优化技术：( 1 ) 在将一个m d x 查询分解为多个子查询的基础上进行查询优化； ( 2 ) 基于实体优视图的多淼谗优位：( 3 ) 多层有效的索弓| 方法；( 4 ) 利用已有 蠢诲结栗重写耨查诲。 鼹有高可靠性商可靠性是新代数据库技术追求的目标之一，也鼹让国产数据 库软件走向市场的关键。农分析型应用中，为提高性能会预计算一魑导出数据， 这些鬏诗算蕊爨熬嚣强滋较妖，掌誊嚣要尼天躲靖闽，懿莱出瑷蔽瓣，熨兹功尽 弈，为此，p a r e w a r e 提供了断点续算功能，保证在系统出现故障黥情况下可戳 从断点处继续避行，而不用从头开始。另外，由于导出数据来之不搦，p a r e w a r e 4 第一章引言 对其进行备份。 具有高安全性由于数据仓库中的数据常用于决策支持，非常宝贵，对国家信息 安全有很大影响，因此，p a r e w a r e 针对分析型应用环境，采取了用户级、数据 方体级、层级等多层数据控制措施，保证数据仓库中数据的安全。 1 2 3 p a r a w a r e 的体系结构 p a r e w a r e 是基于大型网络环境( 包括企业内部的i n t r a n e t 和企业外部的i n t e r n e t ) 的面向分析的并行数据仓库系统，它采用三层体系结构，如图卜2 所示。 最底层为数据库服务器 p b a s e - o l a p ，p b a s e o l a p 以我们 已经研制完成的并行数据库服务 器p b a s e 为基础，针对分析型应用 的特征进行了改造、扩充和重写。 它的主要任务是负责数据仓库中 数据的存储和管理，为查询的高效 实现提供基础。数据库服务器中的 数据可以在数据加载过程中由异 构数据源进行数据集成而得。 中间为数据仓库中间件o l a p 服务器，为o l a p 分析提供直接支 持。它主要负责查询的整体分析、 优化，并通过对各个后台并行数据 库服务器的协调工作来完成查询， 获取查询结果。o l a p 服务器起到 一个中心和枢纽的作用。客户端的 4 m r n n ，i n t r ! ! 夕一。“ o l a p - p b a s e 数据库服务器io l a p p b a s e 数据库服务器1 1 o 纛? w 图卜2p a r a w a r e 的体系结构 请求必须通过o l a p 服务器才能与后台数据库服务器打交道。系统初次启动时，o l a p 服 务器将源数据加载到各个后台数据库服务器上，在加载的过程中，对细节数据根据典型 的用户查询模式进行一些预综合，然后存储到数据库服务器。同时为了查询的方便，数 据仓库中的维数据也存储在o l a p 服务器上。在数据库服务器中存储的是细节数据和预 综合数据。 最上层为客户展现层，接收网络用户查询和展现查询分析结果。它主要负责提交用 户的查询请求，并将返回的查询结果展现给用户。 在p a r e w a r e 中，客户端为w i n d o w s 操作系统，o l a p 服务器和数据库服务器端为u n i x 操作系统不同的处理机之间通过消息机制进行通讯，系统使用s o c k e t 作为协议与数 据的传输方式。 瀣霸 介妙= 唑 隧 中国科学院博士学位论文一并行数据仓库p a r a w a r e 系统的多维数据管理技术 1 3 本文的研究目标和内容 本文的研究目标是并行数据仓库系统的核心技术，即多维数据的存储、查询和维护 技术。数据仓库是一个更好地支持企业或组织的决策分析处理的、面向主题的、集成的、 不可更新的、随时间不断变化的数据集台 王9 8 。决策分析着重于分析数据间的关联关 系或发展趋势，因此数据仓库中包含了大量的历史数据，随着时间的推移，数据仓库中 的数据会越来越多，同时在数据仓库上的查询通常是一些需要多表连接并具有聚集操作 的复杂查询。数据仓库中的大量数据和在其上进行的查询的复杂性会导致查询的响应时 间过长，如前面所述，这通常是不能被人们所接受的。如何有效地组织、存储海量数据， 提供海量数据上高效率的查询操作和维护操作一直是该研究领域的热点问题。 1 3 1 多维数据存储的研究内容 多维数据存储的任务主要在于为上层的数据查询以及数据载入提供高效可靠并易于 扩充的数据处理机制。到目前为止，常用的多维数据存储方式有两种：关系表方式 ( r o l a p ) 或多维数组方式( m o l a p ) 。 基于关系表的数据存储是使用维表和事实表来表达多维的概念。由于关系数据库的 技术较为成熟，r o l a p 在数据的存储容量、适应性上占有优势，但其数据存取较m o l a p 复杂。在大型数据仓库中，通常需要预计算出来一些实体化视图和索引来提高查询速度， 但是当考虑如何生成这些合适的视图以及它们的索引时，我们会发现直接使用关系模式 和b 一树索引来实体化这些视图将造成空间的极大浪费，而查询速度和增量维护速度也是 难以接受的。 r k r 9 7 和 k r 9 8 提出c u b e 一树作为r o l a p 视图的存储和索引组织结构。 c u b e 一树是一组经过打包压缩的r 一树。与传统的o l a p 实体化视图的存储组织结构相比， c u b e 树最好可以使存储缩减2 倍，查询性能提高l o 倍，批量维护速度提高i 0 0 倍。 多维数组存储和关系表相比存储效率高、访问速度快。但是，多维数组存储方式存 在着两个致命的问题：( 1 ) 数据稀疏问题：( 2 ) 各个维访问速度不对称。虽然可以采用 压缩技术来解决数据稀疏问题，但是一般来说，对压缩后存储的数据进行查询时，都需 要将被压缩的数据先解压到多维数组中，这样当维的数目和规模很大时，查询效率非常 低。如果能找到一种方法直接在压缩的数据上进行查询，而不用事先解压，这个问题将 得到解决。 l r s 9 9 中提出了一种可以直接在压缩的多维数组上进行查询的方法，但在 计算的过程中也有数据展开的过程，只不过不是一次将全部数据展开，而是对单个数据， 由压缩后的逻辑位置计算它在非压缩多维数组中的物理位置。 r o l a p 和m o l a p 都是以视图( 或c u b o i d ) 为单位进行存储的，最近出现了一种新的 根据数据元素的语义信息进行存储的方法，它将具有相同特征的数据元素压缩存储在一 起，具有代表性的如d w a r f 结构、c o n d e n s e d 结构和q u o t l e n t 结构等。 设计多维数据的存储结构时的主要困难在于很难协调存储空间和查询以及维护时间 之间的矛盾问题。目前，人们主要从如下两个方面分别进行努力： 6 第一章芍 言 1 数据缩减：为了缩减数据仓库庞大的存储空间，人们通常采用数据压缩的技术 来节省磁嶷空阗。焦怒基于在查谗彝维护戆嚣援爨要矮压缭，影稠了查谗执行 和维护的效率。尽管数据仓库上的数据压缩一般不采用整个数销块压缩静方法， 而是针对单个元组或元组中的每个字段分别压缩，这样当对数据进行查询和维 护时，只要将相关的数据解压丽无须艇块解压数据，但查询效率和维护效率仍 然受裂影响。掰爨这秘方法稳当予戳辩霆换取空瓣。 2 冗余存储：数据仓库中通常使用冗余的数据( 实体化视图) 柬提高查询性能， 即预计算一些常用的焱询，并把结果保存下来，邋样在真正处理查询时，就不 需要查询多个基表劳遴褥连接或聚集操作，两直接查询该实体化视图即可。但 是这种方法需要大量躬存德空淘寒存储实体像撬黼，褶当于激空闯换取对嗣。 当数据赞很大( 达到t 级) 的时候，由于存储空间的限制，很难实体化太多的 视图存放程数据仓库中。 可竣番爨，上述嚣秘方法怒稳互矛磊豹。要么墟牲时瓣换取空翅，癸么旗鹱空耀换 取时闯。如果单纯考虑其中的任何一个舀标非常简单，憾上述两个方酾楚相辅相成的， 在节省存储空间的同时必须考虑查询效率和维护效率的损失有多大。遮将使多维存储结 构的设计变得异常复杂。 1 3 。2 多维查询娥理与优化的研究内容 多维查询处理与优化豹耳括建充分利用系统中的资源尽可能赢效地处理各种套谶。 在关系数据库中，箱户查诲静瓣象是关系，箕缮栗氇是关袭；在多维数糖痒中，查谗熬 对蒙楚数据方体，焱询的结果也是数据方体。对于关系数据库的查询我们采用标准的s q l 语句，对于多维数据的访问，微软发布的“o l ed bf o ro i 。a p ”标准中定义了一组语义 丰蜜熬语句，穆之必多维表达式( m o x ) ，它螽发毒班来，逐灏成为工数赛豹事实标准， 为鼗，p a r a w a r e 将它作为鸯己髂多维查询添畜。 多维查询处理的主要功能怒用来对用户的查询请求( m d x 语句) 谶行分析处理，并 通过访闷并行数据仓库服务器中的多维数据邋回查询结果。它除了支持普通的切片，切 块，旋转，r o l t - u p ，d r i l l - d o w n 查谗癸，逐支耪复杂囊谗翅r a n g e 褒落，w h a t if 查 询，诞似查询等。多维查询优化的主要功能怒为查询执行g i 擎提供优化的查询执行方案 ( 即瞧询执行计划) 。 传统的关系数摆瘴对s o l 的整询处理和优化技术进行了广泛的研究。但由于数据仓 库系统中数器盔绥( 妻拜采露多维数组存储) 酾查询类型( 鳓采瘸m d x 鸯谣语言、在不璃 维不司层上进行聚集操作) 的特殊性，这些方法在o l a p 环境中不能赢接加以应用，为 保证分析型应用的联机高性能，必须研究新的查询处理和优化的方法。 文皴 z d n 9 8 ，l 雕o o ! 善次黠如旃在o l a p 环境下弱露袄速这处理多个查诲麴阏蹶避 行了磷究。文献( z d n 9 8 在骰定数据仓库采掰星型模式的溱础上，透过不简查询之阁共 享网一个星型连接朱优化多个焱询。他们提出了三种用于进行星型连接的共享连接操作 串强辩擎靛蒋 学住豫雯莽行鼗攘仓瘁p a r a w a r e 系统豹多缝数摇管理拄寒 符：( 1 ) 基于哈希的熬享扫描连接，( 2 ) 基于索引的共享扫描连接，( 3 ) 臻于哈希和索 弓| 麴共摹羟接连接。在这些共享掇 錾簿翡基磴上镶髓提窭了三个爰予产生俊豫豹查询执 行计划的启发式算法，郎：两阶段局部优化冀法( t p l o ) ，扩展的两阶段简部贪婪算法 ( e t p l g ) ，全局贪婪算法( g g ) 。文献 l o y 0 0 掇出了另外两个近似优化的算法和一个确 切的算滋来为多个查询生成全局最优的执行计划。 多缀查逶楚瑾稻饶纯在 曼嚣对存在羞蠡下困难： 1 个m d x 查询往往同时涉及多个不同的视豳，如何对原始的m d x 查询进行分解鼹 一个非常复杂的问题。查询分解得太粗成太细都有可能导致查询代价过大。而且 在查询分解的孵侯必须缳存些乐始倍感，以方便曰聪查询结果熬汇总。 2 镑对一个子套询，当萁对疲馥实俸琵援黼不存在静霹镞，如俺选择簸倪的底屡实 体化视图来实时计算它也怒个棘手的问题。由于一个m d x 查询可以分解成多个 子查询，单个套询的响应时间快并不等于系统的整体囊询效率高。所以必须对多 个子查询慰对翔潋考虑，避行多查谗优缘，方玎戳援巍系统熬整镕瞧戆。 3 各个子查询的凌询结莱最终必须组装成一个完整的数据集并以多缳形式呈现在 用户面前。所以必须进行焱询结果的组装和转换操作。既要方便用户的浏览，又 璎满足速度快的要求，必须袋取有效的焱询结果缓存策略。 1 3 3 增量维护的研究内容 当数据潦的数摄发生变纯时，辫簧对数据方传( 采用各张疆缩方法缩减怎的数