（计算机软件与理论专业论文）dwarf结构的存储策略及查询处理的研究与实现.pdf

东北大学硕士学位论文摘要 d w a r f 结构存储策略及查询处理的研究与实现 摘要 o l a p 技术是决策支持系统中的一种重要技术，用于管理入员决策分析，可 以用来分析海量数据。为了提高响应速度，需要对数据立方进行预计算。数据屯 方的预计算在数据仓库中是非常必要而且代价很大的操作。减小数据立方计算和 存储的开销成为研究的焦点之一。 d w a r 促一种语义压缩算法，它通过在数据立方计算过程中消除数据立方中 的语义冗余来达到数据压缩的目的。相对于其它几种语义压缩方法，d w a r 暝有 更高的压缩比，但出于自身结构的缘故，d w a r f 同时又具有查询性能不高、更新 困难的弱点。本文在分析了d w a r f n 身特点以及o l a p 查询特点的基础上，提出了 有利于d w a r 隋询的聚簇算法一一针对点查询的递归聚簇算法和针对范围查询的 层次聚簇算法。实验证明，这两种聚簇方法能够比较好地加速所针对性的查询方 式，但是不能加速对方所擅长的查询方式。 同时，本文在分析了w i n d o w sn t 的磁盘系统特点的基础上，设计了基于自 定义缓冲区的d w a r f 查询系统。这是由于d w a r f 查询的完全随机特性使得 w i n d o w sn t 操作系统的磁盘高速缓存和智能预读功能同时趋向于失效。与 w i n d o w sn t 操作系统内存管理类似，本文提出的自定义缓冲区采用页式结构， 所不同的是本文采用了基于页面访问频数的页面置换策略进行页面置换。本文通 过实验证明，应用自定义缓冲区以及采用基于页面访问频数的页面置换策略能够 综合本文提出的两种聚簇方法的优势，提高了聚簇算法的查询适应性以及查询性 能。 关键字：c u b e ，o l a p ，d w a r f ，递归聚簇，层次聚簇，自定义缓冲区。 i i 东北大学硕士学位论文 s t u d ya n di m p l e m e n t a t i o no ft h es t o r a g es t r a t e g ya n dt h e q u e r yp r o c e s sb a s e do nd w a r fs t r u c t u r e a b s t r a c t t h et e c h n o l o g yo fo l a pi sv e r yi m p o r t a n ti nd e c i s i o ns u p p o r ts y s t e m ，w h i c hi s u s e dt oa i dk n o w l e d g ew o r k e r s d e c i s i o na n da n a l y s i s ，a n dw h i c hi su s e dt oa n a l y z e h u g ea m o u n to f d a t a i no r d e rt or e d u c et h eq u e r yr e s p o n s et i m e ，w eo u g h tt oc o m p u t e t h ec u b ei na d v a n c e t h ec o m p u t a t i o no fd a t ac u b ei sn e c e s s a r yb u tc o s t l yi nd a t a w a r e h o u s e i ti sb e c o m i n go n eo ft h er e s e a r c hf o c u s e st or e d u c et h ec o s to fc o m p u t i n g a n ds t o r i n gd a t ac u b e d w a r fi sav e r ye f f e c t i v ea l g o r i t h m ，w h i c hc o m p r e s s e st h ec u b eb ye l i m i n a t i n gt h e s e m a n t i cr e d u n d a n c yw h i l ec o m p u t i n gad a t ac u b e c o m p a r e dw i t hs o m eo t h e r s e m a n t i cc o m p r e s s i n ga l g o r i t h m ，d w a r fh a sh i g hc o m p r e s s i o nr a t i o ，b u tb e c a u s eo fi t s s t r u c t u r ec h a r a c t e r i s t i c ，d w a r fi ss l o w e ri nq u e r y i n ga n dm o r ed i f f i c u l ti nu p d a t i n g b a s e do na n a l y z i n gt h ec h a r a c t e r i s t i co fd w a r fs t r u c t u r ea n do l a pq u e r y ，w ed e v i s e t w oc l u s t e ra l g o r i t h m sf o ro l a pq u e r y ：r e c u r s i o nc l u s t e ra l g o r i t h mt h a tc a ns p e e du p p o i n tq u e r ya n dh i e r a r c h yc l u s t e ra l g o r i t h mt h a tc a ns p e e du pr a n g eq u e r y i ti sp r o v e d b yo u re x p e r i m e n t st h a te a c ho ft h et w od i f f e r e n tc l u s t e ra l g o r i t h m sc a ne f f e c t i v e l y s p e e du pi t s i n t e n d e dq u e r yt y p e ，b u th a v en oe f f e c to ns p e e d i n gu po p p o s i t eq u e r y t y p e l a t e r ，a f t e rw ea n a l y z et h ec h a r a c t e r i s t i co ft h ed i s ki os y s t e mi nw i n d o w sn t o p e r a t i n gs y s t e m ，aq u e r ys y s t e mf o rd w a r fa l g o r i t h mi sd e v i s e d ，w h i c hi sb a s e do n u s i n gau s e r d e f i n e dm e m o r yb u f f e r t h et r u er e a s o nt od ot h i si st h a tt h ec o m p l e t e l y r a n d o ma c c e s su p o nd w a r fm a k e sb o t hd i s kc a c h ea n di n t e l l i g e n tp r e r e a d i n gi n w i n d o w sn to si n v a l i d s e e m e dt ot h ef u n c t i o no ft h em a i nm e m o r ym a n a g e m e n ti n w i n d o w sn to s ，o u ru s e r - d e f i n e dm e m o r yb u f f e ra l s ow o r k si nap a g i n gm a n n e r ，b u t d i f f e r e n tf r o mt h er e p l a c es t r a t e g yi nw i n d o w sn to s ，o u ru s e r - d e f i n e dm e m o r y b u f f e rr e p l a c e su s e l e s sp a g eb a s e do nt h ev i s i tc o u n to ft h ep a g et ob er e p l a c e d i ti s a l s o p r o v e db yo u re x p e r i m e n t s t h a tt h eu s e r d e f i n e dm e m o r yb u f f e ra n dt h e v i s i t - c o u n t - b a s e d r e p l a c es t r a t e g y c o m b i n et h e a d v a n t a g e o ft h et w oc l u s t e r a l g o r i t h m s k e y w o r d s ：c u b e ，o l a p , d w a r f , r e c u r s i o nc l u s t e ra l g o r i t h m ，h i e r a r c h y c l u s t e r a l g o r i t h m ，u s e r d e f i n e dm e m o r yb u f f e r i i i 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰 写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位做作者始掀 日 期：胪占，。v 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复 印件和磁盘，允许论文被查阅和借阅。本人授权东北大学可以将学位 论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 学位论文作者签名： 签字日期：毋占i 导师签名： 签字日期： 东北大学硕士学位论文第一章绪论 第一章绪论 1 1 数据仓库技术简介 随着企业的成长，企业积累了大量的、不同格式的内部历史数据。例如技术 的进步使企业的信息管理方式从传统的基于文件的方式，进化到以d b m s 为核心 的信息管理系统；再比如由于企业的发展，企业内部的业务模型和数据模型发生 了变迁，导致了新增或删除了某些字段；再有，由于企业间的兼并，产生了外来 数据。等等这些原因导致了历史数据的异构特性。通常来说这些异构的历史数据 都是海量的，因为这是长时间积累的结果，如果以记录条数来衡量，它们通常都 是百万甚至千万数量级的。这么海量的数据，无疑是企业的信息财富，如果能够 通过一定的手段挖掘出蕴含在这海量数据中的信息，将会对企业的决策产生重大 的帮助。比如说：超市的经营者希望将经常被同时购买的商品放在一起，以增加 销售；保险公司想知道购买保险的客户一般具有哪些特征；医学研究人员希望从 已有的成千上万份病历中找出患某种疾病的病人的共同特征，从而为治愈这种疾 病提供一些帮助。对于以上问题，现有的以d b m s 为核心的信息管理系统中的数 据分析工具无法给出答案。因为无论是查询、统计还是报表，其处理方式都是对 指定的数据进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取。 随着信息管理系统的广泛应用和数据量激增，人们希望能够提供更高层次的数据 分析功能。为此，数据仓库应运而生。 1 1 1 数据仓库的概念及特点 数据仓库概念始于本世纪8 0 年代中期，首次出现是在号称“数据仓库之父” w i l l i a mh i n m o n 的创建数据仓库一书【l 】中。随着人们对大型数据系统研究、 管理、维护等方面的深刻识认和不断完善，在总结、丰富、集中多行企业信息的 经验之后，为数据仓库给出了更为精确的定义，即“数据仓库是在企业管理和决 策中面向主题的、集成的、与时间相关的、只读的数据集合”。在这里对这四个方 面做一简单介绍： ( 1 1 面向主题：数据仓库的分析与设计与关系型数据库有所不同，相对于关系 型数据库的实体- 关系模型，数据仓库是面向主题的，这样更有利于描述 企业内部的业务流程。比如说可以将涉及到客户的数据、实体等等归于客 户主题以方便客户信息的管理和分析；再比如，我们可以把与销售相关的 部分归于销售主题以便于对销售情况进行分析和报表。 东北大学硕士学位论文 第一章绪论 ( 2 ) 数据是集成的：这是数据仓库最核心的特点。前边说过，由于长时间以来， 企业积累了大量不同格式、不同模式的信息，当我们对这些异构的数据进 行综合分析时，异构性会带来难以想象的困难。比如说，随着时间的变迁， 某些主键发生了变化，使得在这些键上的连接不能进行。再比如说，两个 不同的部门都维护各自的客户信息，相同的客户有可能在两个部门对应于 不同的编码，当我们要进行跨部门的查询时就会出问题。为了避免这些问 题，数据仓库中装载的数据需要进行集成和清洗 羽，建立全局的数据模式 和数据格式。 ( 3 ) 只读性：数据仓库中装载的通常都是历史记录，对数据仓库的操作通常都 是查询之类的只读特性的操作。 ( 4 ) 随时间变迁：由于数据仓库中装载的都是历史记录，所以通常隔一定的时 间间隔就要才对仓库进行更新，添加近期的记录。 数据仓库并没有严格的数学理论基础，也没有成熟的基本模式，且更偏向于 工程，具有强烈的工程特性。因此，在技术上人们习惯于从工作过程等方面来分 析，并按其关键技术部分分为数据的抽取、存储与管理以及数据的表现等三个基 本方面【3 】： ( 1 ) 数据的抽取：数据的抽取是数据进入仓库的入1 3 。由于数据仓库是一个独 立的数据环境，它需要通过抽取过程将数据从联机事务处理系统、外部数 据源、脱机的数据存储介质中导入到数据仓库。数据抽取在技术上主要涉 及互连、复制、增量、转换、调度和监控等方面。数据仓库中的数据并不 要求与联机事务处理系统保持实时同步，因此数据抽取可以定时进行，但 多个抽取操作执行的时间、相互的顺序、成败对数据仓库中信息的有效性 则至关重要。 ( 2 ) 存储和管理：数据仓库的真正关键是数据的存储和管理。数据仓库的组织 管理方式决定了它有别于传统数据库，同时也决定了其对外部数据的表现 形式。耍决定采用什么产品和技术来建立数据仓库的核心，则需要从数据 仓库的技术特点着手分析。 ( 3 ) 数据的表现：数据表现实际上相当于数据仓库的门面，其性能主要集中在 多维分析、数理统计和数据挖掘方面。而多维分析又是数据仓库的重要表 现形式，近几年来由于互联网的发展，使得多维分析领域的工具和产品更 加注重提供基于w e b 前端联机分析界面，而不仅仅是在网上发布数据。 1 1 2 数据仓库的数据模型 相对于关系数据库的实体关系模型，数据仓库采用的是多维数据模型【4 1 。一 般的，维是关于个组织想要记录的透视或实体。比如说一个商场的销售记录中 2 东北大学硕士学位论文 第一章绪论 关于顾客信息的记录就可以设置成一个维，其间包含顾客的姓名、性别、年龄、 家庭住址等等信息。每一个维通常有一个表与之相连，称为维表。多维数据模型 是围绕着主题进行组织的，主题用事实表表示，事实是数值度量的。事实表中包 含着度量值以及相关维表的关键字。多维数据模型在存在形式上可以分为星型模 式( s t a rs c h e m a ) 、雪花模式( s n o w f l a k es c h e m a ) 、事实星座模式( f a c tc o n s t e l l a t i o n ) 。 ( 1 ) 星型模式：最常见的模型，由一个包含大量数据、不含冗余的中心表( 事 实表) 和一组小的附属表( 维表) 组成，每维一张维表。 ( 2 ) 雪花模型：雪花模型是星型模型的变种，在这里某些维表是规范化的，维 表中消除了数据冗余。由于查询时需要维表的连接操作，效率较低，应用 中不如星型模型流行。 ( 3 ) 事实星座模型：复杂的应用可能有多个事实表，星座模型可以看作星型模 型通过共享维表而产生的星型模式集合。 1 1 3 数据仓库中的概念层次 现实中的概念是有层次的，也就是我们通常说的概念有大有小。比如说“应 用数学”是一个比较小的概念，因为它是数学概念的一个分支，相对而言“数学” 就是一个大的概念。一个概念层次定义了一个“一对多”的映射序列，降低层次 的概念映射到更一般的高层次概念。图1 1 中表示了两种形式概念层次。 “位置”的概念分层“时间”的概念格 图1 1 概念层次示例 f i g 1 1a ne x a m p l eo fc o n c e p th i e r a r c h y 3 周 度 ， 鄞 月 醵 省 市 髓 东北大学硕士学位论主 第一章绪论 关于顾客情息的记录就可以设置成一个维，其间包含顾客的姓名、性别、年龄、 家庭住址等等信息。每一个维通常有一个表与之相连，称为维表。多维数据模型 是围绕着主题进行组织的，主题用事实表表示，事实是数值度量的。事实表巾包 古着度量值以及相关维表的关键字。多维数据模型在存在形式j 一可以分为星型模 式( s t a rs c h e m a ) 、雪花模式( s n o w f l a k es c h e m a ) 、事实星座模式( f a c tc o n s t e l l a t i o n ) 。 ( 1 ) 星型模式；最常见韵模型，由一个包含大量数据、不台冗余的中心表( 事 实表) 和一组小的附擒表( 维表) 组成，每维一张维表。 ( 2 ) 雪花模型：雪花模型是星型模型的变种，在这里某些维表是规范化的，维 表中消除了数据冗余。由于查询时需要维表的连接操作，效率较低，应用 中不如星型模型流行。 ( 3 ) 事实星座模型：复杂的应用可能有多个事实表，星座模型可以看作星型模 型通过共享维表而产生的星型模式集合。 1 1 3 数据仓库中的概念层次 现实中的概念足有层次的，也就是我们通常说的概念有大有小。比如说“应 用数学”是一个比较小的概念，因为它是数学概念的一个分支，卡u 对而言“数学” 就是一个大的概念。一个概念层次定义了一个对多”的映射序列，降低层次 的概念映射到更一般的高层次概念。图1 1 中表示了两种形式概念层次。 的概念映射到更一般的高层次概念。图1 1 中表示了两种形式概念层次。 “位置”的概念分层“时间”的概念格 图1 1 概念层欢示例 f i g 1 1a ne x a m p l eo f c o n c e p th i e r a r c h y 3 一 阁 度 ， 魏 月 o ，o + o + o 醵 省 市 雠 东北大学硕士学位论文 第一章绪论 1 2 数据仓库中的预计算问题 1 2 1 预计算的原因 前边说过，数据仓库主要是为分析和决策支持服务的，提供这样的支持有。 个时间效率的问题。但是，数据仓库中装载着大量的历史数据，它的数据规模通 常都是百万级的，任何运行在这么多数据量上的操作都可能存在着时间效率低下 的问题。举例来说，对于存储着2 0 年历史数据的数据仓库，数据规模上百万条， 如果我们要查询某一个事实表的前l o 年的度量值均值，这个计算量将会非常大， 会消耗很多的时间。巨大的时问开销对于提供即时的决策支持非常不利，因此要 想办法减小时间的开销”j 。 在计算机历史上，以牺牲空间效率换取时间效率的方法很多，数据仓库中的 预计算也是采用的这样的策略。预计算主要是针对事实表进行的，主要的方法是 对事实表中所有维的所有组合进行g r o u pb y 操作，计算的结果称之为数据立方 ( d a t ac u b e ) ，每一个组合的g r o u pb y 操作产生的结果称为一个c u b i o d 。举例来 说，假设有一个事实表由两个维a ，b 和一个度量值m 组成，对于这张事实表的 预计算将产生四个e u b i o d ，分别是a 、a b 、b 、 ，其中 代表不进行 g r o u pb y 操作。通过这样的方法生成的数据立方成为全立方( c o m p l e t ec u b e ) ， 这样的计算过程称为完全实例化。 当实例化结束以后，刚才说到的那个例子就变得很简单了，用一条很简单的 查询语句就可以实现了，因为在实例化的时候这个均值已经被计算并被存储到数 据立方中了。 1 2 2 预计算的问题以及常用的解决方法 预计算最大的问题是计算时间和存储开销的问题，“维度爆炸”就是这个问题 最直接的结果。所谓的“维度爆炸”是说随着维数量的增多，c u b i o d 数量会以指 数方式迅速增长，计算时间和存储代价非常大，通常都无法完成完全实例化1 6 “。 这里有一个公式可以计算最后生成的数据立方的元组规模： 丁= n ( 上f + 1 ) ( l ；表示第i 维候选值的数量) f = 1 为了克服完全实例化带来的高昂的时间、空间代价，人们在进行实例化的时 候通常采用以下一些技术： ( 1 ) 不进行实例化：这是一种鸵鸟策略，完全避免了冗余，节省了计算和存储 的开销，但是由于查询时需要动态聚集，查询效率很差。 一4 一 东北大学硕士学位论文第一章绪论 ( 2 ) 不完全实例化：针对应用，选择出几个在查询时经常要用到维，在这几个 位上进行完全实例化，它是不实例化和完全实例化的折衷。它的讨算时间 和占用空间都要比完全实例化高效得多，但是一旦查询请求的维没有被实 例化，查询时需要临时计算，开销比较大。 ( 3 ) 数据压缩技术：利用信息论的相关理沦，通过应用数据编码技术，压缩原 始数据的存储空间。常用的方法是小波变换8 】和主要成分分析p 1 。数据压 缩技术虽然压缩了存储空间，但是在应用的过程中要有解压缩的时间丌 销。本文应用的算法d w a r f 也算是一平十数据压缩技术，但是它的出发点不 是采用信息冗余度小的编码技术，而是去除掉完全实例化生成的c u b e 中 的冗余信息( d w a r f 中提到的前缀冗余和后缀冗余，具体内容后文中会有 提及) 。 ( 4 ) 维度约减：前边提到过，完全实例化的计算代价随着维数的增多而呈现指 数级的增长，维度约减技术的出发点就是减少数据仓库中冗余的维。例如， 如果一个维的内容可以通过另一个维的内容计算得到( 有点类似数据库系 统中的函数依赖) ，或者一个维的内容对聚集值计算或者挖掘过程不产生 影响，我们在计算的时候完全可以把这些维去除。维度约减现在总的来说 还不是太成熟，主要问题是确定不相关的维的时间开销过大。【1 0 】谈到过 这项技术。 1 2 3 样板数据 为了方便下文的叙述，现在给出一个比较具有代表性的样板数据源，见表1 1 。 表1 1 样板数据 t a b l e1 1s a m p l ed a t a 该样板数据对应于数据仓库中的一张事实表( f a c tt a b l e ) ，该事实表由三个 维s t o r e 、c u s t o m e r 、p r o d u c t ，以及度量值p r i c e 组成。其中度量值上的运算为求 和运算，度量值的类型是整型。下文对数据立方以及d w a r f 的讨论都是以此事实 表为例，该事实表虽然总共只有4 条记录，但基本已经涵盖了后边所涉及到的所 有问题，因此该样板数据是具有代表性的。根据1 2 的介绍，对这样一张事实表 进行完全实例化，将会产生下边的数据立方，如表1 2 所示。 5 查! ! 垄塑主兰堡垒查 簦二主竺垒 表1 2 样板数据的全立方 t a b l e1 2t h ec o m p l e t ec u b eo f t h es a m p l ed a t a s t o r ec u s t o m e r p r o d u c t p r i c e ( s ) s 1c 2p 2 7 0 s 1c2 7 0 s 1c 3p 14 0 s 1c 340 s 1pl4 0 s lp 27 0 s 11 1 0 s 2c 1p 1 9 0 s 2c 1p 25 0 s 2c 1 1 4 0 s 2p1 9 0 s 2p 2 5 0 s 2 1 4 0 c lp l 9 0 c 1p 2 5 0 c l 1 4 0 c 2p 2 7 0 c 2 7 0 c 3p 14 0 c340 pl 1 3 0 p 2 1 2 0 2 5 0 1 3o l a p 简介 1 3 1o l a p 的概念 联机分析处理( o l a p ) l 的概念最早是由关系数据痒之父e e c o d d 于1 9 9 3 年提出的，他同时提出了关于o l a p 的1 2 条准则。o l a p 的提出引起了很大的反 响，o l a p 作为类产品同联机事务处理( o l t p ) 明显区分开来。当今的数据处 理大致可以分成两大类：联机事务处理o l t 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 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 ) 。o l t p 是传统的关系型数据 6 一 东北大学硕士学位论文 第一章绪论 库的主要应用，主要是基本的、日常的事务处理，例如银行交易。o l a p 是数据 仓库系统的主要应用，支持复杂的分析操作，侧重决策支持，并且提供直观易懂 的查询结果。 1 3 2o l a p 的特点 o l a p 分析的特点可以总结为： ( 1 ) 快速性：用户对o l a p 的快速反映有很高的要求，一般要求能在5 秒内 对分析要求有反映。设计时应考虑：专门的数据存贮格式，大量的事先运算，特 别的硬件设计。 ( 2 ) 可分析性：o l a p 系统应能处理与应用有关的任何逻辑分析和统计分析。 因为事先编程并不能定义所有的应用，所以，在o l a p 分析的过程中，用户无需 编程就可以定义新的计算，将成为分析的一部分，且以用户希望的方式给出报告。 ( 3 ) 多维性：多维性是o l a p 的关键属性，系统能够提供对数据分析的多维 视图和分析，包括对层次维和多重层次维的支持。多维分析是分析企业数据的最 有效的方法，是o l a p 的灵魂。 ( 4 ) 信息性：不论数据量有多大，也不管数据存贮在何处，o l a p 系统应能 及时获得信息，并且管理大容量信息。 ( 5 ) 共享性：在大量用户间实现潜在地共享秘密数据所必需的安全性需求。 1 3 3o l a p 的基本操作 ( 1 ) 切片( s l i c e ) 定义1 1 在多维数据集的某一维上选定某一维成员的动作称为切片。 定义1 ，2 选定多维数据集的一个二维子集的动作叫做切片。 切片的实质：( 1 ) 切片的作用或结果就是舍弃一些观察角度，使人们能在两个 维上集中观察数据：( 2 ) 一个切片最终是由除切片所在平面两个维之外的其他维 的成员值确定的。 ( 2 ) 切块( d i c e ) 定义1 - 3 在多维数据集的某一维上选定某区间的维成员的动作称为切块。 定义1 4 选定多维数据集的一个三维子集的动作称为切块。 实际上，切块操作也可以看成进行多次切片以后，将每次切片操作所得的切 片重叠在一起而形成的。 ( 3 ) 旋转( r o t a t e ) 旋转即改变一个报告或页面显示的维方向。 f 4 1 下钻( d r i l l - d o w n ) 沿概念层次向更低层次的概念进行离散。 7 - 东北犬学硕士学位论文 第一章绪论 ( 5 ) 上卷( r o l l - u p ) 上卷是下钻的逆运算，它是沿着概念层次向更高级别的概念进行聚集 1 3 4o l a p 的实现类型 按照o l a p 中队数据的组织形式，o l a p 主要可分为下边三种类型 ( 1 ) 关系o l a p 模型( r o l a p ) 。将o l a p 所用到的数据以关系的形式存放 在关系型数据库中。由于关系数据库的技术较为成熟，r o l a p 在数据存储容量、 可伸缩性上占有优势，但足由于查询的时候涉及到连接操作，速度比较慢，通常 需要预计算、索引等技术的支持。 ( 2 ) 多维o a l p ( m o l a p ) 。m o l a p 是基于多维数据库( m d d b ) 的o l a p ， 数据按照多维数组的形式存储，通常他的效率比r o l a p 要高，而且数据存取灵 活，但是数据冗余度高，占用的存储空间比较大，查询速度比较慢。1 2 1 谈到如 何快速m o l a p 。 ( 3 ) 混合o l a p ( h o 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 计算迅速的特点。 8 东北大学硕士学位论文 第二章相关工作及问题的提出 第二章相关工作及问题的提出 2 1 数据立方中的数据冗余 通过观察我们的样板数据和由它完全实例化生成的数据立方，可以发现，尽 管原始数据只有4 条，但是最后的数据立方却有2 3 条记录。如果考察度量值，会 发现在原始数据中有4 个不同的度量值，而最后的c u b e 中只有9 个不同的度量值， 而且有几个度量值重复很多次。在这里，肯定会有一部分数据产生了冗余。举例 来说，对于样本数据生成的数据立方中， 矛f l ，它们是通过两种不同的g r o u pb y 操作计算得到的，前者对应的操作是 “g r o u pb ys t o r e ，c u s t o m e r ”，而后者则是“g r o u pb ys t o r e ，p r o d u c t ”，但是他 们有着相同的度量值，原因在于虽然他们的g r o u p b y 操作不同，但是都对应于 相同的原始记录集 一一这就是语义上的冗余。基于语义的o l a p 技术就是通过寻找这样的关系，达到压缩数据立方体积，加速查询的目的。本章 讲述的集中相关技术都是从这样的出发点出发来消除冗余的。 2 2 浓缩数据立方 浓缩数据立方( c o n d e n s e dc u b e ) 是在 1 3 】被提出的。它是基于b s t ( b e s ts i n g l e t u p l e ) 的一种语义压缩方式。所谓的b s t ，就是那些在g r o u pb y 聚集中唯一的 那些基本元组。就像上节提到的冗余的例子那样， 就是一个b s t ， 因为在g r o u pb ys t o r e ，c u s t o m e r 以及g r o u pb ys t o r e ，p r o d u c t 时，它是唯一的 原始记录。c o n d e n s e dc u b e 就是通过寻找这样的b s t ，并同时记录下b s t 对应的 g r o u p b y 记录，来达到数据压缩的目的。 在这里有一个有用的结论：如果一条元组对于某一些维的g r o u pb y 操作是 一个b s t ，那么对于这些维的超集的g r o u pb y 操作，这条元组仍然是b s t 。 以样本数据举例来说，元组 对于g r o u pb yc u s t o m c r 操作显然是 一个b s t ，所以对于g r o u pb yc u s t o m e r ，p r o d u c t 操作它也一定是b s t 。利用这 个特性，可以比较迅速计算出一条b s t 对应的g r o u pb y 集合。这个结论对后 来多种算法也产生了影响。 2 3 商数据立方和q c t r e e 商数据立方( c o n d e n s e dc u b e ) 仅仅保存了b s t 对应的g r o u pb y 操作，它 有着比较好的查询性能，但对于数据立方中的上卷和下钻的信息没有保留，严格 意义上说，这个算法破坏了语义的完整。y a nz h a o 等人在 1 4 提出了商数据立方 9 东北大学硕士学位论文 第二章相关工作及问题的提出 和它的改进形式q c t r e e 两个算法。这两个算法的基本思想类似于浓缩数据立方， 也是通过划分的方法，找出具有相同基本元组的数据立方记录，将这样的一组记 录压缩成一条记录保存。所不同的是，商数据立方更多地考虑了语义( 主要是上 卷和下钻) 的完整，用它压缩后的记录集在逻辑上可以表示成一张有向无环图， 图中的有向边就表示着上卷( 或下钻) 的关系。 商数据立方采用一种自底向上的计算方法进行计算。主要依据是这样的：在 c u b e 计算过程中具有向下钻方向的依赖性。举例来说，g r o u pb ya 可以根据 g r o u pb y a ，b 的计算结果计算出来，而无需重新扫描原始元组，而原始元组对 应着对所有维的g r o u pb y 操作。这样，从最原始的元组开始，通过逐渐减少 g r o u p b y 中的维的数量，就可以计算出所有的c u b i o d 。 q c t r e e t l | 5 1 是对商数据立方的一个改进，它将商数据立方的计算过程和最终的 计算结果反映到q c t r e e 上，并添加了相应的索引结构。 2 4d w a r f d w a r f 是在【1 6 】被提到的。d w a r f 是通过消除前缀冗余和后缀冗余来实现对 c u b e 压缩的目的。在这里简单介绍一下这两种冗余： ( 1 ) 前缀冗余：记录的共同前缀。举例来说，对于两条不同的记录 和 共享相同的前缀 ，在最后的存储中s 1 将通过前缀合并的方式实现共享。 ( 2 ) 后缀冗余：对于两条度量值相等的记录，它们如果有相同的后缀，这个相 同的后缀就称为后缀冗余。例如， 和 ， 它们有着相同的后缀 且度量值均为7 0 ，这种情况实际上就是2 ，1 中提到过的那种数据冗余。后缀冗余是通过后缀合并来消除。 d w a r f 的生成算法实际上就是对前缀冗余和后缀冗余的压缩过程，最后的结 果类似于一棵树。前缀冗余的消除是通过共享树的靠近根的节点来达到，后缀冗 余的消除是通过共享靠近叶子的节点来实现。通过这个算法，我们的样板数据对 应的数据立方将存储成如图2 1 的样式： 整个结构分为3 层，每一层对应于原始数据的一个维度。每一个维由若干节 点( n o d e ) 组成，节点又是由若干个单元( c e l l ) 构成。每一个节点都有一个特殊单元， 途中对应着深色的部分。对于非叶子节点，节点中的单元存储的都是指向下一层 节点的指针以及该单元对应的候选值；对于叶子节点，单元中存储的候选值以及 度量值。从根到叶子的每一条路经都对应着数据立方中的一条记录，例j z l a ，就对应着一条历经( 1 ) 、( 2 ) 、( 3 ) 节点相关单元的路径，最后的度量值7 0 存储在( 3 ) 号节点的p 2 单元中。 1 0 - 东北大学硕士学位论文 第二章相关工作及问题的提出 图2 1 样板数据生成的d w a f t 结构 f i g 2 1 t h ed w a r fs t r u c t u r eo fs a m p l ed a t a 原文中提到，对于稠密数据，前缀冗余将是主要的冗余形式：对稀疏数据， 后缀冗余将是主要的冗余形式。通过实验，d w a r f 有着非常好的压缩结果，非常 适合于存储超大规模的数据，就向原文的题目那样，压缩p e t a ( 1 0 2 4 t ) 级规模 的数据。在这里，有两点需要重点强调一下，因为它们与本文的讨论相关： ( 1 ) 在数据预处理阶段，需要对元组进行排序。一方面要按照候选值的多少， 将各个维降序排列，原因是有助于消除后缀冗余；另一方面每个维要按照 候选值的具体值排序，就像本文的样板数据对应的数据立方那样。 ( 2 ) 对于d w a r f 的聚簇，原文提到要根据c u b i o d 的依赖关系。假设原数据有 a ，b ，c 三个维，它们生成的数据立方的c u b i o d 有如下的依赖关系，如下图 22 ： 图2 2 三维数据立方c u b i o d 依赖关系 f i g 2 2t h ed e p e n d e n tr e l a t i o n s h i po fc u b i o di nt h r e ed i m e n s i o n sc u b e “ 东北大学硕士学位论文 第二章掘关工作及问题的提出 图中的有向箭头表示的就是c u b i o d 之间的计算依赖一一箭尾代表的c u b i o d 的 计算依赖于指向c u b i o d 。这种依赖关系组成一个格1 7 】。按照这样的关系，在 d w a r f 的生成过程中，首先集中执行前缀合并，而后再集中执行后缀合并。在 本文的例子中节点被创建的顺序为( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 6 ) ( 7 ) ( 5 ) ( 8 ) ( 9 ) 。 2 5 层次d w a r f 层次d w a r f 是在 1 8 】中被提出的，主要是针对d w a r f 中无法体现出概念层次 的问题进行了改进，将上卷下钻的操作添加到d w a r f 的树形结构中。以本文的样 板数据做为例子，在c u s t o m e r 维建立概念层次，层次定义如表2 1 。 表2 1 概念层次定义 概念层次 元数据 a l l 十 t y p e c u s t o m e r c l 斗r 1 c 2 _ r 2 c 3 斗r 2 根据这样的概念层次定义，最终生成的带层次的d w a r f 结构如图2 3 。 图2 3 带概念层次的d w a r f f i g 2 3d w a r fs t r u c t u r ew i t hc o n c e p th i e r a r c h y 上图中，c u s t o m e r 维的概念层次是通过( 5 ) 、( 9 ) 、( 1 1 ) 节点体现的，将低层次 节点的a l lc e l l ( 图中的( 2 ) 、( 7 ) 、( 1 0 ) 节点的a l lc e l l ) 作为指向高层次节点的 指针，当对低层次节点的a l lc e l l 执行后缀合并算法的时候生成高层次节点。文 中的节点编号顺序就是节点被创建的顺序。 ，1 2 东北大学硕士学位论文第二章相关工作及问题的提出 2 6 浓缩d w a r f 浓缩d w a r f 在 1 9 】中被提出，它继续压缩了d w a r f 中的冗余。比如说图2 3 中的( 5 ) 号节点，由于只有一个数据单元t 2 ，所以它的a l lc e l l 一定与t 2 单元内 容相等，这这种情况q - ，a l lc e l l 视为冗余可以被省略。这种方法消除的只可以 视为是一种结构冗余而不是语义的冗余。 2 7 问题的提出 本章简单介绍了三大类，总共6 种语义压缩方法。单从压缩效果来看，实验 表明d w a r f 有着最优秀的压缩性能，特别是对于p e t a 级别的超大型数据更是如此。 但是我们知道，数据立方技术起初是为了避免在查询时临时聚集而发明的，是一 种空间换时间的方法一一它最根本的目的是为了加速查询，所以我们的这些语义 压缩方法最后也应该有着比较优秀的查询效率，最起码不应太差，这样才不违背 数据立方技术的初衷。从试验结果来看，除了d w a r f 的3 种外，其他算法都有着 不错的查询效果。究其原因，最要是因为浓缩数据立方和商数据立方的压缩结果 都可以直接存储在数据库中( 因为他们的结果是结构化的) ，依靠数据库系统强大 的索引和经过优化的查询系统而表现出来。d w a r f 的压缩结果类似于树，是非结 构化的，很难存储在数据库中，况且，从d w a r f 的设计思想上来说，更多考虑的 也是压缩比，对于数据的存储和查询的优化没有作过多的讨论，而这两个方面恰 恰是决定最终查询效率的两个最重要的因素。 本文将从d w a r f 的物理存储以及查询两个方向考察，改进d w a r f 的物理聚簇 方法和存储方式。 一1 3 东北大学硕士学位论文 第三章系统分析及设计 第三章系统分析及设计 3 1d w a r f 的结构特点 通过上一章对d w a r f 相关结构的介绍，经过观察和总结，d w a r f 结构总共有 如下一些特点： ( 1 ) 树形的结构。如果忽略后缀合并的因素，整个d w a r f 形状上非常类似于一 棵树。它由一个公共的根出发，按照维度衍生出若干节点。 ( 2 ) d w a r f 可以被认为是一个索弓i 结构，节点的单元中存储的是关于下一维向 关节点的存储信息。 ( 3 ) d w a r f 的节点是非结构化的，节点的长度不统一。 d w a r f 的这些结构特点决定了d w a r f 不能像其他的压缩技术能够把结果存放 在关系型数据库中，因为节点没有固定的格式。当然，我们可以把节点的的存储 形式按照e r 模型进行建模，分解成关系存储在数据库中( d w a r f 和节点、节点 和节点中的单元实际上都对应着”一对多”的关系) 。但是这样做在查询时，读入 每一个节点都会有相应的连接操作，效率不高。 d w a r f 的存储通常都是存储成平面文件的形式，这样做对于建立、查询会带来 较高的性能，但是更新操作比较困难，原因是用户要自己维护文件的物理存储( 而 在关系型数据库中这个工作是d b m s 负责的) 。后文将会具体谈到这个问题并会 给出一个解决这个问题的方案。 3