（计算机应用技术专业论文）多维数据存储及聚集优化策略的研究.pdf

硕士学位论文 摘要 摘要 数据仓库以传统的数据库为主要信息源，为联机分析处理( o l a p ) 、 决策支持( d s s ) 和信息挖掘( d m ) 提供了一个集成的数据环境，高效地组 织和管理数据是实现数据仓库技术的关键之一。本文从数据仓库的多维 数据概念模型和o l a p 实现两个方面对这个问题进行了深入的研究。 多维数据模型是数据仓库研究的核心问题。本文首先对现有的多维 数据模型进行了总结，并分析了其优缺点，然后利用分类的方法提出了 一个多维数据模型，并对数据立方体的相关概念进行了定义，该模型能 够充分表达数据仓库的复杂数据结构，这为多维数据的存储及聚集优化 策略奠定了理论基础。 多维数据的逻辑组织方式是o l a p 实现的关键之一。本文对这个问 题进行了深入的研究，总结了多维数据的两种组织方式一关系方式和数 组方式，重点研究了在数组方式中多维数据的存储结构、多维数组的建 立方法、稀疏数组的压缩方法、数组分块的原则和分块数组访问方法， 并在以上的理论分析的基础上实现了一个数组方式存储的实例。 在数据仓库中高效计算多维聚集是提高o l a p 性能的手段之一。本 文总结了聚集计算的主要优化方法，对相关的概念进行了形式化定义， 着重研究了数组聚集计算的优化策略，并给出了一个数组方式下的聚集 算法p a n c u b e 算法，该算法运用了最小父亲、阶段扫描以及缓存结果 的优化策略，基于搜索格建立不完全方体的最小跨度树，当内存不足时， p a r t c u b e 将数组进行划分并分别计算，计算完所有的划分后再把中间结 果合并成完整的聚集结果。分析表明该算法能充分利用内存空间、减少 i o 次数，具有较高的计算效率。 论文最后对研究工作进行了总结，并对进一步的研究工作进行了展 望。 关键词数据仓库，o l a p ，多维数据模型，多维数据存储，聚集计算 优化策略 硕士学位论文摘要 a b s t r a c t t h e 删i t i o n a id a _ t a b a s e sa d e 吐l em a l ni n f o 肋a t i o ns o u r c e so fd a t a 础o u s e s ；d a t a 鼬o u s 船p r o 、r i d ea 1 1 幻白e g r a t e dd a t ae n v 蛐e n t 细 o l l l i n ea n a l 舛c a lp r o c e s s i l 培( o l a p ) ，d e c i s i o ns u p p o r ts y s t e m s s ) a n d d a t am i i l i i l g ( d m ) o r g a n i 洳g 锄dm 锄l g i l l gm ed a t ae f f i c i e n u yi so n eo f n l ek e y so fi i i l p l e m e n t 啦d a t aw a r e h o l l s e s 1 1 1 i sm e s i s 咖d i e shd e 印l y0 n t h ea s p e c t so f w a r e h o u s e s c o n c 印tm o d e la n do l a p i i l l p l e m e n t a t i o n m u l t i d i i i l e n s i o 越ld a ：t am o d e li sab 硒i c 邪p e c ti i lm er e s e a r c h6 e l do f d a t aw a r e h 肌s e s a r e rs u 啦m a r 协ga n da n a l y s i n gt l l ee ) 【i s t i l 唱加m o d e l s ， ad a t aw a r e h 烈j s e s m u l t i d i m e n s i 伽谢m o d e li s p r o p o s e du s 岖 c l 船s i f i c a t i o nm e t h o da n dn l ec o m l a t i v ec o n c e p t so fd a t ac l l b ea r ed e f - m e di i l 吐l i s n _ 幢s i s ，l en 1 0 d e l i s p o v 旧l 彻即o u 曲矗”r n o d e l i n gc o m p l e xd a t a s n l l c t u r eo f ( 1 a t a 、) i 撇h o u s e w h i c he s t a b l i s h e sn l e o r e t i c a lf o u n d a t i o n - o rm e s t o r a g e 锄d 雄g r e g a t i o no p t i m i z i n gm e t l l o d so f m u l t i d i m e n s i o n a ld a t a n e 1 0 9 i co 玛a n 砌i o nm o d eo f m u l t i d i m 朗s i o l l a ld a t ai s 衄eo f t h ek e y s o fo l a p i m p l e m e n t a t i o n ，m i s 也e s i s 乳吼m 撕z e sm e t w oo 玛a i l i z i i l gw a y so f m u l t i d i m e r i s i o n a l 妇一r e l a t i 蚰a lm o d ea n da r r a ym o d em o r o u 曲l ma n d p l a c e se m p t 粥e so n l er e s e a r c h e so fa r r a yr n o d e ，m c l u d i i l gm es t o r a g e s t n j d u r eo fm u l t i d i m e n s i o n a ld a 饥t l l ec o n s t n j c t i o nm e m o d so f m u l t i d i m e n s i o n a la r r a y s ，廿l ec o m p r e s s m gm e t h o d so fs p a r s ca r r a y s ，t h e p r i f l c i p l e so fd i v i d 协ga r r a y si i l _ t oc h u n l 【s 锄dt l l ea c c e s sm e 廿l o d so fc h u n k a r r a y s ，a n da l s om i st i l e s i sr e a l i z e sas t o m g ei n s t a n c eo fa r r a ym o d e b a s e do n t l l ea l o 、r e 协e i ) r e t i c a la n a l y s e s 0 l i l em e 孤so fi i l l p r o v i n g l ep e r f o n n a l l c eo fo 【a pi st oc o r n p u t e 枷l t i d i m e n s i o n a la g 嗍a t i o i l se f f i c i e n t i y n i s 恤s i ss u m m a r i z e sm em a i n o p t 皿i z m gm e t h o d so fc 伽叩m m ga g g r e g a t i o 船，o nw h i c ht l l e c 0 佗l a t i v e c c 印t s a r e f o m a l l yd e f m e d 如r d l e n n o r e ，t l l i st 1 1 e s i s 锄p h a s i z e s n l e r e s e a r c ho fo p t i m i z i l 玛m e m o d so f a r r a ym o d ea n dp r 叩o s e sa n 延；g r e g a t i o n a l g o r i m m p a n c u b ea l g o r i 衄，i tm a k e sl l s e o fo p t i m i z i n gm e m o d s i n c l u d i i l gs m a l l _ p a 崩止a r n o f t i z e - s c a n s 柚dc a c h e - r e s u l t s ，a n d a l s o t e s t a _ b l i s h e sm em i n i m u ms p 釉i i l gn e eb a s e do ns e a r c h 晰i c e i fm e m o 搿i s i l i s u m c i e l l p a r t c u b ed i v i d e sa m y i i l t op a r 捃a n dc o m p u t 郎e a c hs e p 撒t e l y ， 堡兰焦堡塞 塑墨 a 舭ra l lp a n sh a v eb e e na c c o m p l i s h e d p a n c u b em e r g e st t l ei i l t e 姗e d i a t e r e s u l 拓如t oi l l t e 掣a t e da g g r e g a t i o 璐t h e 柚a l y s i ss h o w sm a tm i sa l g o r i t h m c 锄m a l ( et 1 1 eb e s tu s eo fm e m o r ya i l dr e d u c e 狄) t i m e s ，s oi t h 嬲h i g h e m c l c ymc o 叫) m m ga g 洲i o i l s a tt h ee n do fm i st h e s i s ，m er e s e a r c h e sa r es u m m a r i z e da n dm e 缸u r e w o r ki sp r e s e n t e d k e yw o i s d a t a 、v a f e h o u s e ，o l a p ，m u l t i d i i n e n s i o n a ld a t am o d e l ， m u l i t i d i r n e n s i o n a ld a t as t o r a g e ，a g g e g a t i o no p t i m i z i n gm e t h o d i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 j 作者签名：埤日期：2 1 呈咀月三乒日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者躲级年导师签躯眺竺衅旦月型日 硕士学位论文 第一章绪论 第一章绪论 1 1 数据仓库及0 l a p 技术产生的背景 随着社会的信息化程度的提高，相应数据量也急剧增长，从上世纪8 0 年代的兆 ( m ) 及千兆( g ) 字节发展到现在的兆兆( r ) 字节和千兆兆口) 字节，而传统的联机事务处 理( o l l p ，0 i t l i 鹏t f a n 鼢c t i p r 船s i | l g ) 系统的应用长期以来一直停留在查询、检 索、统计等几个方面，远远没有发挥数据库中数据的作用和价值，并且用户不再仅 仅满足于简单的事务性数据查询，而是需要利用这些数据提供相关的决策信息。这 就必须对大量的业务数据包括历史数据等进行分析，以获取需要的决策信息，这种 基于决策分析的应用称为联机分析处理( 0 l a p 【1 】【3 】，o i l l i n e a n a l 如c a lp m c e s s i n g ) 。 o i 。a p 是以海量数据为基础的复杂分析技术，它支持各级管理决策人员从不同 的角度、快速灵活地对数据仓库中的数据进行复杂查询和多维分析处理，并且能以 直观易懂的形式将查询和分析结果提供给决策人员，这种应用在0 u p 系统中实现 起来是非常困难的，主要原因有以下几点： 分析操作需要大量的数据，因此将长时间访问数据，这在0 u p 系统中是不 可接受的； 分析操作需要多方面的、集成的信息，而这些信息常分散在多个0 u p 系统 或外部数据源中； 历史数据中隐含着企业发展和变化的模式，分析操作需要长时间的历史数 据，而在o l l p 系统中保存的是较短时间的数据，长时间的数据通常备份而 与系统脱离。 操作性系统的设计目的是为了提高事务处理的性能，而决策分析需要的是企业 全方位的视图，在传统的操作性系统上建立和维护这些视图是低效的，这将极大降 低操作性系统的性能，其决策分析处理的速度也不能满足o b 快速性的要求。因 此，需要为分析类的应用提供一个平台，建立一个体系结构来容纳来自o u m 系统 或异构的外部数据源、脱机的历史业务数据和元数据等，为统计分析和决策支持提 供联机分析服务所需的数据，这个体系结构就是数据仓库( d w 翻，d a t aw 疵h o u ) 。 数据仓库集成了多个数据源的数据，形成了一个可靠的、一致的、不断更新的 数据集合在数据仓库的o l a p 应用中，会涉及到大面积的数据查询与聚集操作， 如何有效地组织和管理数据仓库中的数据，实现快速的o “心查询和多维分析，是 数据仓库技术研究的核心问题之一，也是本论文要研究的内容。 硕士学位论文第一章绪论 1 2 国内外研究现状 由于数据仓库中存储的是海量数据量，且0 l a p 查询非常复杂，为了实现o l a p 的快速性，高效组织和管理数据仓库的中的数据是整个系统成功的关键。 在数据仓库系统中，通常把数据的逻辑模型称为o l a p 的实现途径。由于o u 心 系统必须提供对数据分析的多维概念视图，包括对维的层次结构的完全支持，因此 在实现o l a p 时常把数据仓库中的数据组织成多维形式。按照底层数据存储方式的 不同，o l a p 的实现途径主要有r o l a p 、m o l a p 和h o l a _ p 三种。r o l a j p 是基于 关系数据库的【4 ”，通常采用星型模式和雪花模式进行数据存储，在数据的存储容量、 适应性上占优，但是数据的存取较m o l a p 复杂，查询响应速度较慢；m o l a p 是基 于多维数组的【4 2 j ，其访问速度快，存储效率高，它存在着数据稀疏和各个维的访问 不对称两个缺陷，目前对m o l a p 的研究才开始起步，如何实现其存储结构，使之 适合o l a p 的需要是一个实现m o l a p 的关键；h o l a p 是r o l a p 和m o l a p 的混 合存储模式【4 3 】，一般的方法是将细节数据存在关系数据库中，而将综合数据存在 m o l a p 服务器中，既利用了r o l a p 扩展性好的优点，也利用了m o l a p 计算速度 快的优势。 数据仓库技术另一个重要的方面是对数据进行多维分析，其核心是要有效地计 算多个维集合上的聚集，因此，数据仓库系统应该支持高效的数据立方体聚集计算 技术。在n 维数据立方体中子方体的总数是2 n ，如何高效计算这些方体? 一个最直 接的方法就是分别计算这2 n 个子方体，这样将对数据集进行2 n 次访问，很显然这不 是一个高效的方法，一条有效途径是利用这2 “予方体的相互依赖性，同时计算多个 聚集，减少i ，o 访问的次数，从而提高计算效率。目前已有多篇文献对此进行了研 究，其中大部分研究工作集中在关系方式c u b e 计算上，对多维数组方式c u i 疆计 算的讨论相对较少；如何在多维数据仓库系统中实现这些优化方法，并利用数组中 数据已有序的特点来加快聚集计算的速度，是在多维数据仓库中实现多维分析一个 非常重要的方面。 1 3 本论文的研究内容 在数据仓库系统中，如何对多维数据进行组织，设计多维数据层数据的存储结 构，并在多维数据集上进行高效的立方体聚集计算，这是本论文研究的思路。 o l a p 的实现需要多维数据模型作为理论基础，数据立方体聚集计算需要基于 多维数据模型的结构。本文首先对现有的多维数据模型进行了总结，并分析了其优 缺点，然后结合分类的方法提出了一个多维数据模型，并对数据立方体的相关概念 硕士学位论文 第一章绪论 进行了定义，该模型能够充分表达数据仓库的复杂数据结构，这为多维数据的存储 及聚集优化策略奠定了理论基础。 在o u 心系统中，多维数据层的功能是负责组织和管理聚集节点中的维数据和 度量数据，以往研究的重点是应用广泛的r o l a p ，r o l a p 用关系表存储数据，然 后用星型模式( s t a rs c h e i m ) 或雪花模式( s w n a k es c h e m a ) 口l 把数据组织成多维形式。 相对r 0 k 心而言，对m o l a p 的探讨较少本论文研究了把数据从其它数据源转 移到多维数组中的方法，设计了m o l a p 多维数据层维数据和度量数据的管理模式； 针对多维数组中数据稀疏问题，本文详细讨论了适合多维数组的压缩方法，并对它 们的效率进行了分析；在本文中还重点讨论了对数组进行分块的划分以及访问方法， 从而有效解决数组各维访问不对称的问题。 c u b e 聚集计算的具体实现依赖于多维数据存储方式。本论文中首先总结了关 系方式聚集优化方法，然后讨论了如何在数组方式应用这些优化措施。在数组方式 中，聚集计算时的内存需要量往往会超过物理内存，本文详细讨论并给出了一个最 小内存需要量的聚集优化算法一p a n c u b e 算法，该算法通过对数组的一次扫描能够 同时计算所有方体；同时，当只需要计算立方体的部分子集时，可对子集中所有的 方体进行优化选择，通过对数组的一次扫描同时计算子集中的所有方体。分析表明， 该算法能有效减少l 访问，具有较高的计算效率。 1 4 本论文的结构 论文全文分五章 第一章为绪论，主要介绍了数据仓库及o l a p 技术产生的相关背景及其概念，并 总结了o l a p 实现及立方体聚集优化策略的研究现状。 第二章对数据仓库系统进行了概述，在总结现有的多维数据模型的基础上，结 合分类的方法提出了一个新的多维数据模型，并对数据立方体的相关概念进行了定 义。 第三章研究了数据仓库中多维数据层的实现方式，对关系和数组两种多维数据 组织方式的比较，重点深入研究了多维数据在数组中的表示方法，多维数组的压缩 方法及数组的访问方法。 第四章研究了多维聚集优化的策略，总结了关系方式下的聚集优化的方法，重 点研究了数组聚集的优化策略。 第五章对本文的工作进行了总结，并对进一步的研究工作进行了展望。 硕士学位论文 第二章数据仓库及多维数据模氆 2 1 数据仓库 第二章数据仓库及多维数据模型 2 1 1 数据仓库的定义解释 数据仓库是在上个世纪8 0 年代发展起来的，数据仓库之父w h i 衄o n 在他 的著作b u i l d i i i gt 量掂d a t aw 础。啪e 提出了数据仓库的基本框架及其定义：数 据仓库是一个面向主题的、集成的、时变的、非易失的数据集合，用以支持管理 部门的决策过程。 r o bm a t i s i o n 在他的著作d a t a 砒啪h o u 中对数据仓库是这样定义的：一 个据仓库是由i 脚o n h a c k t h o m 按照当今实际应用所完成的基本工作的一个组 合。一个数据仓库是这样一个数据库：其数据能被组织用作一个中性存储区的， 由数据挖掘和其它应用来使用的，使用这些数据满足一组预定义的商业评测。 还有很多其它对数据仓库的定义，把数据仓库作为数据的存储和加工地，主 要是面向复杂的数据分析和高层决策等。 综上所述，数据仓库系统由以下几个部分构成： 历史数据集合 数据库管理系统( d b m s ) o l a p 技术 d a 【a m i 疵n g 2 1 2 数据仓库的特征 1 面向主题 在数据仓库中，问题将被集中在某一领域进行分析，如顾客、产品等。数据 仓库关注决策者的数据建模与分析，因此将排除对于决策无用的数据，提供特定 主题的简明视图。 2 集成性 数据仓库是将不同平台的数据使用数据清理和集成技术，合成到一个平台 上，为决策和分析作准备。 3 时间性 通常d b s 只保留近期的应用数据，而与数据仓库所要求的历史数据，如近 五年或者更长时间的历史数据无关。正是由于数据仓库这一特征，给分析历史数 4 硕士学位论文第二章数据仓库及多维数据模型 据、将历史数据作为快照并且带来了数据的未来发展趋势。 4 数据的一致性 由于数据仓库是将不同d b s 、分散的数据集成在一个公共的平台上，所以， 在这系统一开始就需考虑将不同格式的数据进行一致化、标准化的问题。例如： 。名字”、“性别”、“地区”等的表示，进行一致化处理后，应存入一个中性 存储区中，供数据仓库使用。比如象：“性别”这类属性，有的d b s 习惯于用“男” “女”表示；有的采用“蚴”和“w o m c i l ”；有的用“m a l e ”和“f c m a l e ”表示。 而d w 系统中，将两类不同性质事物的表示，采用二进制的“l ”和“o ”表示， 即，“l ”代表男，“o ”代表“女”这就使得“性别”在( 任何一个系统) 计算 机内部与外部都是一致的。可见，数据仓库为处理多平台的数据提供了可靠的标 准。 t 2 1 3 数据仓库的体系结构 数据仓库的系统结构可用图2 1 来表示，分别由数据源，数据抽取与集成工 具、历史数据及元数据库、前端数据挖掘展现系统组成 元数据痒 异构教据源 图2 1 数据仓库系统结构 数据仓库系统独立于操作型数据库系统，是对数据进行再组织。在上面的系 统结构图中，各种异构的数据源是数据仓库系统数据的来源，包括各种外部数据 及操作型数据库中的数据。数据源的数据经过抽取、集成等工具装入数据仓库， 并在运行的过程中要进行更新、维护等。数据仓库中的数据包括细节数据和综合 数据，细节数据即为数据源中转换过来的，基本与数据源相对应。综合数据即为 数据立方体，是对细节数据进行综合计算后产生的数据集，包括数据层次维表和 事实数据，主要是为了能从多个角度对数据进行分析，提高系统的响应速度。数 据市场是为了各种特定需要从细节数据导出的数据表，是面向某个部门( 主题) 而 在逻辑上或物理上划分出来的数据仓库中的数据子集，当要使用这一子集时，不 需要到数据仓库中的巨量数据中检索，因此可提高系统的效率和速度。元数据库 5 硕士学位论文第二章数据仓库及多维数据模型 是用来存储数据仓库中的元数据，元数据是描述数据的数据，它描述了数据的存 取维护和管理等信息。数据仓库中的元数据包括以下两类：第一类是为了从操作 型数据库环境向数据仓库环境转换而建立的元数据，它包括所有数据项的名称， 属性及其转化。第二类元数据是用来与最终用户的多维商业模型和前端 o l 枷m 工具之间建立映射的，这种数据称为决策支持系统( d s s ) 元数据，它 包括：数据仓库信息的种类、存储位置、存储格式；信息之间的关系、信息和业 务的关系等；数据模型、数据模型和数据仓库的关系等方面。前端分析工具是为 决策者或分析者提供数据展示：应用工具，包括0 l a p d m ，应用( 查询) 工具等。 2 2 多维数据模型的研究 2 2 1 多维数据模型简介 模型是人们对客观世界的认识和理解，是对客观世界的近似描述，数据模型 是对现实世界的抽象，抽象程度的不同就形成不同抽象级别层次上的数据模型。 在把现实世界种的客观事物抽象为数据仓库中数据的过程中，可以分为现实世 界、信息世界和机器世界三个阶段，相应数据仓库数据模型的设计可分成三个不 同的级别：概念模型、逻辑模型和物理模型。在数据仓库的设计中，概念模型是 现实世界到机器世界的一个中间层，人们首先将现实世界抽象为信息世界，然后 再将信息世界转化为机器世界；逻辑模型处于概念模型和机器模型之间，是对概 念模型的的细分和逻辑实现，物理模型是逻辑模型在数据仓库中的实现，如数据 存储方式、存储结构、存放位置等。 1 9 9 3 年e f c o d d 提出了1 2 条准则来描述o l a p 系统【”，其中明确地指出 o l a p 操作具有多维性，从此多维数据模型引起了学术界的重视，数据仓库概念 模型设计的首选模型是多维数据模型。 在多维数据模型中，通常用一系列属性集来描述某一主题，如商品销售这个 主题可用时间、地点、商品和销售量等属性来描述，有些用来描述人们观察主题 的角度，如时间、地点和商品，这些属性可以形成多维空间，因此称作维，而这 些多维空间的单元包含了该主题剩下属性的值，如销售量、销售额等；维属性往 往有具有层次结构，度量数据的值就放在这样一些有层次结构的维构成的多维空 间中，这个多维空间就称作数据立方体，如图2 2 所示。 6 硕士学位论文第二章数据仓库及多维数据模型 1 9 蚺1 9 9 9 攫 t j w “) 钢铸敷搦褒方律 鲁詈参 p r ，d 眦t 瓣l o c h t i 锄臻t i 聃缎 b ) 撑接坎赫拇 图2 2 销售数据立方体及维结构图 近年来，人们提出了多种典型的多维数据模型【5 】【6 】【1 2 】1 m ，这些模型都把数 据分为两类：维和度量下面对其中具有代表性的模型进行介绍，这些模型可分 为简单的立方体模型、统计对象模型和结构化的立方体模型。 1 简单多维数据模型 1 9 9 5 年，j i mg m y 等在微软公司技术报告中第一次引入了c u b e 操作符嘲， c u b e 操作符是s q l 中对g r o u p b y 字句的扩展，它把n 个聚集属性当作n 一维空 间的n 个维，在对应着这n 个维属性值构成的n 维向量的每一个具体取值的度 量的集合上聚集，结果构成了n 维空间的一个点。所有这些点构成一个n c u b e ， 进一步低维空间聚集可得到( n 1 ) 础e ，o c t l b e 。所有这些c u b e 集合构成一 个n - 维数据立方体。j i m g r a y 引入了关键字a l l 来表示属性上所有取值的集合， 表示聚集操作中没有参与的属性，从而使操作结果数据立方体a t a c u b e ) 可以用 关系表来表示。这种数据立方体模型具有多维性的特点，能给报表生成分析工具 常用的操作：制直方图( h i s t o g r a m ) 、交叉表( c r o s s 砒) 、小计( s u b 粕t a l ) 提供有效的 帮助，但每一维智能由一个属性组成，不能表示维的层次结构，对数据立方体复 杂的操作也没有进行深入的讨论，只是扩充了s q l 语言。 1 9 9 7 年m a r c c b s s 饥s 和l a l 【s v s l a k s h n 姗趾提出了另一种简单立方体模型 1 4 】。他们把模型的结构和内容区分开来，提出了n - 维表模式( n - d i m c n s i o n a lt a b l e s c j l e m a ) 和实例( i i l s t a l i c e ) 的概念，通过引入“关系模式的关系值关于其对应的多 维数据模式的完全表示”( 也ec 伽叩i 嘶o no fa 佗l 撕晰t h s p e c tt 0 a n d i i n s i 伽i a ls c h 锄a ) 的概念，在多维表模式的实例和对应的关系模式的关系值 之间建立了一一对应关系，从面把在多维数据表的代数操作用对应的关系上的代 数操作来定义，定义简单而清晰，具有较强的表达能力，能有效地表示c u b e 操 作符g y s s e 璐等提出的这个模型在数据立方体上前进了一步，每一维可包含多 个属性，支持维属性和度量属性的对称性，但是不支持维属性的层次结构，并且 对定义在多维数数据表上的操作缺乏有效的实现方法。 7 硕士学位论文第二章数据仓库及多维数据模型 而删y ad a t t a ，h e l e n1 协m 勰则给出了一个形式化的简单立方体多维数 据模【l ”，他们把数据立方体( d a t ac u b e ) 定义成一个四元组 d ，m a 伊，其中d 代 表维名的集合，m 为度量名的集合，d 和m 的交集为空，a 为所有属性的集合， f 为d 到a 的一到多的映射。立方体实例( c u b ei n ：吐锄c e ) 定义为一个六元组 ，其中d ，m ，a ，f 是来自于。父”立方体，v 是用来实例化立 方体的值集合，其中的元素可用一个k 元组表示q l ，螗，“表示第i 个度量属 性的取值，g 是从立方体各维构成的空间到v 的映射。该多维数据模式本质上同 m a r cg y s s c 璐和l a l 【sv s l a b h m a i l a i l 提出的多维数据模型相同，每一维可包含 多个属性，支持维属性和度量属性的对称性，不支持维属性的层次结构，不同之 处在于直接给出了模型上的代数操作：选择( 回，取集似) ，笛卡乐积( ) ，连接q ) ， 并( u ) ，差( 一) ，拉p i i l i ( 西) ，推p 璐h ( v ) ，分区p a n m o n 0 ) 的定义，但是对推、拉 的定义不够完善，对所有操作符如何实现没有进行讨论。 在国内，北京大学的裴健、柴玮、赵畅、唐世渭、杨冬青在1 9 9 9 年针对多 维模型缺乏形式化理论支持的状况，用形式化的方法定义了一个立方体模型【1 2 】， 并定义了一套立方体操作代数：指标维转换m d ( a 慨，m i ) ，维指标转换 d m ( c u b c ，d - ) ，指标退化操作d e g ( c u b c ，m i ) ，基于聚集的退化操作d e g ( c u b c ，d 。) ， 选择函数o 。( c u b e ) ，具有相同特征的数据立方体的集合运算c u b c lu c u b e 2 ， c u b e l n c u b e 2 ，c u b e l c u b e 2 ，数据立方体的积c u b c l c u b e 2 ，数据立方体关于谓词一 的连接c u b e l 司0 c u b e 2 。 总之，这些简单的多维数据模型本质上把数据当作n - 维立方体，数据通常被 分为维和度量，每一维由一定数量的属性组成，它们可以在l e c t 查询的机鹏 子句和g r o u pb y 子句中作为条件，但是这种模型不能支持维属性之间的层次结构 关系，任何一个属性只能属于某一个维，对现实世界的多维数据表达能力极为有 限。 2 统计对象模型 二十世纪八十年代，很多学者对数据聚集建模相关的问题很有兴趣。因为聚 集数据是在基本数据的基础上使用统计聚集或分析函数得来的，因此这类数据库 通常也叫统计数据库，统计数据库中存储的数据项通常是具有复杂的数据结构， 如向量、关系，时间序列等，这些数据项被叫做统计对象一s t a t i s t i c a l o b j e c t ( s o ) 【1 0 1 。 s o 被定义为一个四元组心i ，c ，s ，佥，其中： n 是s o 的名字，c 是分类属性( 维属性) 的集合；每一分类属性都有一个相 关的域( d o 肌i i l l ) 和一个域的基数( d o m a i nc a r d i 豫l i 劝和一个计量单位( u 血o f m 船s u r e ) ，s 代表与s o 相关的唯一的一个聚集属性( 度量属性) 。这个聚集属性也 8 硕士学位论文第二章数据仓库及多维数据模型 有一个相关的域，一个域的基数，一个计量单位，另加一个聚集类型。 f 为分类属性的值的笛卡尔积到聚集属性的值的映射。 也可以采取以下形式描述一个统计对象： n ( c l ，c 1 2 l ，c n ：s ) 其中n 是s o 的名字，c ( i ) 是来自于c 的一个分类属性，函数f 用“：”表 示。 例如，下面是对有关在美国的不同的产品销售量的统计对象的s t o r m 表 示。 p r o d u c ts a l e s ( r r p e ，p r o d u c t ，y e a r ，c n y ，s 伽，r e g i o n ； a m o u 阿n m 肌r i z i o 凡虹a n e l l i ，a f i es h o s h a n i 在研究统计数据库的统计对象的结 构和语义属性的基础上发现上述表示方法不能表示分类属性之间的关系和结构 语义，进而提出了一种统计对象模型s t o r m ( as t a l i s t i c a lo b j e c t 代p r e s 饥t 砒i o n m o d c n 【埘。 在s t o 剐h 模型中，s o 使用一棵有向树来表示。树的节点分为三类：s 型、 c 型、a 型，s 型节点表示聚集属性，c 型节点表示分类属性，a 型节点表示对 指向它的所有的节点的聚集，它们满足下列条件： ( 1 ) 只有一个s 型节点，这个节点就是树的根。 ( 2 ) 一个唯一的a 型节点指向s 型节点。 ( 3 ) 可以有多个c 型节点或多个a 节点指向一个a 型节点 ( 4 ) 只有唯一的一个c 型节点或a 型节点指向一个c 型节点。 如果一个s o 中所有指向c 型节点的映射都是单值映射，而指向同一个a 型节点的所有节点之间的映射为多值映射，则这个s o 为。格式好的” ( w b l l 勘珊e d ) s o 。一个s o 是可聚集的不仅要求它是一个格式好的s o ，而且还 要满足以下的条件： 1 ) 所有的单值映射是“完全的” l l i d 。 2 ) s 0 必须是“完整的”( c o m p l e 哟，即对应的聚集数据没有丢失。 s t o r m 模型考虑了分类属性( 维属性) 之间的映射关系和统计对象的可聚集 性，这种表示统计对象的方法能有效表示分类属性的层次关系、聚集路径和聚集 语义，对后来的结构化多维数据模型具有重要的参考价值。 3 结构化多维数据模型 1 9 9 7 年，鼬b s ha g 哪v a l ，a s i l i s hg u p t a 和s 岫i 诅s a r 州a g i 提出了一种结构 化多维数据模型1 4 1 ，该多维数据模型把立方体的元素当做是从各维的域的笛卡 尔积到 o ，l 的映射，或是到n 个度量属性构成的n 元组的映射，通过定义两个 9 硕士学位论文第二章数据仓库及多维数据模璎 操作符p u s h 、p i i l l 把维属性改变为度量属性，把度量属性改变为维属性以支持维 和度量的对称处理，并且提出函数映射的方式使每个维能支持多个层次结构。当 某一维只有一个取值时，可用操作符d e s 仃o y 把该维消除。利用蒯c t 操作符 可以取某一维的以值进行限制，选择出需要的元素组成新的立方体。j o i n 操作符 则把两个立方体在维上面通过些函数映射构成对应的新的维成新的立方体，而对 应的两个立方体的元素同样通过函数映射的方式形成新的立方体的元素，该操作 符可以支持迪卡尔积( c 眦e s i m 龇哟，自然连接恤舳r a l j o m ) ，并( u n i o n ) ，归并 ( m e 曜e ) ，关联( 鹤c i g t e ) 。 而l u c ac a b i b b 0 和m c c a r d ot o d o 北提出的多维数据模型则由维层次结构和 事实表构成嗍，维层次结构表示为一个三元组( l ，r u p ) ，l 表示所有层次 的集合，表示维层次问的偏序关系，r u p 表示有偏序关系的层次之间层次属 性之间的包含关系。事实表的形式为：f l a l ：l l ，a n ：l n 】：1 0 ，其中f 为事 实表的名字，a i 为事实表的属姓名，而l i 是一个维的层次，1 0 为度量。多维数 据模式定义为一个二元组；f ) ，其中d 维为层次结构的有限集，f 为事实表的 有限集。多维数据模式的实例为从层次属性域的笛卡尔积到度量属性值域的函数 映射。然后给出了一套基于域的谓词演算的查询语言。该模型能支持维的层次结 构，允许同一维中存在不同的层次结构。 1 9 9 9 年，h v j a g a d i s h ，l a k sv s l a k s h m 肌锄，d i v e s h s r i v 蝴引入有向图， 提出了一种s q l ( 哪多维数据模型【1 6 1 ，这种模型中把有向图，维层次属性，有向 图节点到维层次属性集合( 该集合必须包括该维最基本的属性) 的映射结合起来 反映维的层次结构，数据仓库模式则由维模式及由各维的基本属性和度量属性构 成的事实表的集合组成。s q l 语言被扩展成s q l o ) 语言使之能直接支持维的层 次结构，该语言增加了d i m e n s l 0 n s 子句和在维基本属性上的层次操作符= ， 、 、 = 、，- ，它具有如下形式： s e l e c t d o m e x p l k ；t ，a g g l i 鲢 d i m e n s i o n sd i m l i s t f r o m6 【n l i s t w h e r ew h e r e c o n d i 缸o i l s g r o u p b y 掣0 1 j p b y l i s t h a v n g h a _ 、，i n g c o n d i d o i l s 其中d o m e x p l i s t 表示维表d i m l i s t 和事实表舶m l i s t 的属性列表，而，a g 吐i s t 表示在舶m l i s t 的属性上的聚集函数。该语言允许用户直接对维的层次进行操 作，能用较简单的形式表达复杂的o l 廿查询。这种模型能允许同一维有不同 的层次结构同一层次属性可包含异构的节点，但是要求用户对维层次构成的细 l o 硕士学位论文第二章数据仓库及多维数据模型 节进行了解。 在国内，李建中、高宏以偏序和映射为基础提出了一种新的多维数据模型 旧，该数据模型同一维能支持多个不同的层次结构，引进了层次结构的聚集约 束概念以提供表达聚集约束的机制，它允许在多维数据集合的任一维的同一个层 次链上使用不同的聚集函数执行维数据结构和语义，并提出一个以o l a p 操作 为核心的操作代数。 李琪、白英彩在2 0 0 2 年提出一个基于关系数据库的s q l ( d ) 的多维数据模型 圆，该模型的层次链、层次树、维的定义支持不平衡、异构的维层次结构，并在 此基础上对s q l 作了相应的扩充以支持维的定义、维层次比较、维的引用和维 聚集层次的指定，使得原先冗长、复杂的0 l a p 查询表达工变得简洁、易于理 解。 总之，上述的结构化多维数据模型在明确表示维的层次结构、同维中能表示 多个层次结构和维层次间的聚集语义三个方面都有不同程度的支持。下面将首先 提出一个结构化的多维数据模型，然后对其结构进行研究。 2 2 2 多维数据模型 分类对统计分析起着非常重要的作用，是减少问题复杂度和对领域知识的建 模的有效途径，一个对象集合上的分类就是定义了一组具有相同特征的对象( 等 价类) ，对象的分类是根据一定的分类规则进行划分的。一个复杂的分类还包括 多个分类层次，如可以根据地区对城市进行分类、也可以根据国家对城市进行分 类，因此一个分类层次也就表示了一个分类规则。在本文的建模过程中，把分类 模式作为维模式的一部分，这样能满足数据仓库多方面的应用需求 定义2 1 ( 分类层次) 分类层次d 是域d o m ( d ) 中的一个有限对象集合，其中的一 个对象x d 0 m ( d ) 称为层次d 的一个分类节点。 分类层次的一个节点通常通过一组描述属性表示。在本文多维数据建模的方 法中，要求一个分类层次的所有节点具有相同的描述属性，并且每个节点都具有 唯一标识，因此可直接通过标识引用节点。 定义2 2 【分类模式) 一个分类模式可定义为一个二元组 ，其中d ； d i d 2 一，d n ，是包含了n 个不同分类层次的集合；d d ，它表达了不同分类层 次间的分类关系，是d ( d ) 上的偏序关系。 硕士学位论文第二章数据仓库及多维数据模璎 定义2 3 ( 域的扩充) 域d 的扩充域d7 = d u a l l ，并且v d d 有d a l l ； 维是由一定数量的分类层次构成，且实际应用中这些分类层次形成的偏序关 系一定存在全下界。例如时间维可由分类层次y e 盯，m o n t l l ，w e e k 和d a y 组成， 则d a y 就是时间维的全下界，因此扩展域后的维结构都构成有界格。 定义2 4 ( 维模式) 设有分类模式 ，定义五= ，其中d j ，呜 d d i 也，o 日= ( a g 鲷，a g g r 2 ，a g g r m ) ，a g g r k 是对第k 个度量属性的