（计算机应用技术专业论文）多维数据模型和数据立方体技术研究.pdf

摘要 摘要 多维数据模型和数掘立方体技术是联机分析中两项关键技术。目前，联机分析产品 支持的数据模型不能很好的描述一些复杂应用，缺乏理论基础。另外，在原始数据很大、 维数多、有大量维成员的情况下，如何有效的减少数据立方体的体积，快速计算数据立 方体仍然是一个十分重要的研究课题。本文针对这两个问题进行了研究。 本文提出了基于扩展关系模型的多维数据模型e r ( 如。e r ( j o 把维表示成半结构化 数据，路径表达式作为查询语言，使得维可以用做关系模型的域；去掉关系模型中第一 范式的限制，允许属性的值可以是多值；扩展了关系代数。e r ( 卿可以充分利用在关系 模型、面向对象模型以及半结构化数据方面的研究成果，易于在主流的关系对象数据库 系统上实现。 通过把数据立方体中的维分为划分维和非划分维，定义了一个等价关系，使得具有 相同划分维的视图构成了一个等价类。把等价类组织成主流水线，等价类中的视图组织 成次流水线，给出了两层流水线数据立方体串行算法和并行算法，可以充分的利用物理 内存，大大减少读原始数据的次数和处理机之间的通讯开销，缩短了计算时膪j 。 本文提出了星型数据立方体实例化视图选择方法。在星型数据立方体中，对每个等 价类，只计算并保存其中的最大视图( 具有最多的维数) ，其它的视图可以从最大视图实 时计算。星型数据立方体至少可以把数据立方体中的视图个数减少一半，节省了计算和 维护时间。在假定一个分片只需要一次i o 的前提下，星型数据立方体和实例化所有视 图的完整数据立方体的查询响应时间几乎一样。 在数掘立方体中，有很多元组是从基本数据中一组相同的元组经过聚集运算得到 的，对这些元组，只需要存储一个元组，其它的元组可以从这个元组中导出。根据这个 现象，提出了封闭数据立方体的概念，给出了一个快速生成算法。然后，根据线性查询 代价函数对它的查询性能进行了分析，进一步提出了半封闭数据立方体的概念，它很好 的平衡了查询响应时间和存储空间。本文给出了半封闭数据立方体的数学描述并设计了 个贪心算法，可以快速的生成半封闭数据立方体。 关键词：数据仓库，联机分析，多维数据模型，数据立方体 竺壁型 一 r e s e a r c h0 1 1m u l t i d i m e n s i o n a ld a t am o d e la n dd a t a c u b e t e c h n o l o g y l is h e n ge n ( 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 yw a n gs h a h m u l t i d i m e n s i o n a ld a t am o d e la n dd a t ac u b et e c h n o l o g ya r et w ok e yt e c h n i q u e si n o n l i n ea n a l y t i c a lp r o c e s s i n g a tp r e s e n t ，t h ed a t am o d e lu s e db yp r o d u c t so fo l a p c a r l t s u i tf o rs o m ec o m p l e xa p p l i c a t i o n sa n di sl a c ko ft h e o r yb a s i s i nt h ec a s eo fa p p e a r i n gh u g e r a wd a t ao ral o to fd i m e n s i o n so rm a n yd i m e n s i o nm e m b e r s ，h o wt or e d u c et h es i z eo fd a t a c u b ee f f i c i e n t l ya n dc o m p u t ed a t ac u b er a p i d l yi ss t i l la ni m p o r t a n ti s s u e t ot a c k l et h e s e p r o b l e m s ，t h i s t h e s i sc o n t r i b u t e sa sf o l l o w s ： f i r s t l y , p r o p o s e sam u l t i d i m e n s i o n a ld a t am o d e le r ( 翳，w h i c hi sb a s e do ne x p e n d e d r e l a t i o nm o d e l e r ( m o d e l sd i m e n s i o n sa ss e m i - s t r u c t u r ed a t aa n du s e sp a t he x p r e s s i o na s q u e r yl a n g u a g e i ta b s t r a c t sd i m e n s i o n st o a na l g e b r as y s t e m ，s od i m e n s i o n sc a na c ta sa d o m a i no fr e l a t i o nd a t am o d e l i te x p e n d sr e l a t i o nm o d e lb yr e l a x i n gt h ef i r s tn o r m a ln o h n l i m i t a t i o n ，a c c e p t i n gm u l t i - v a l u e si na t t r i b u t ea n de x p e n d i n gr e l a t i o n a la l g e b r a ，i tc a na b s o r b t h er e s e a r c hr e s u l t so fr e l a t i o nm o d e l ，o b j e c t - o r i e n tm o d e la n ds e m i s t r u c t u r ed a t am o d e la n d c a nb ei m p l e m e n t e di nt h em a i n s t r e a mo b j e c t r e l a t i o nd a t ab a s es y s t e me a s i l y s e c o n d l y , b yd i v i d i n g t h ed i m e n s i o n si nd a t ac u b ei n t o p a r t i t i o n d i m e n s i o n sa n d n o n - p a r t i t i o nd i m e n s i o n s ，d e f i n e sa ne q u i v a l e n tr e l a t i o n t h a tm a k e st h ev i e w sw i t hs a m e p a r t i t i o nd i m e n s i o n sc o m p o s ea l le q u i v a l e n tc l a s s 。b yo r g a n i z i n ge q u i v a l e n tc l a s s e si n t o m a j o rp i p e l i n e sa n dt h ev i e w si na ne q u i v a l e n tc l a s si n t om i n o rp i p e l i n e s ，p r e s e n t sas e r i a l a n dp a r a l l e lt w ot i e r sp i p e l i n ea l g o r i t h mf o rc o m p u t i n gd a t ac u b e t h ea l g o r i t h mc a l lm a k e r i s eo f p h y s i c a lm e m o r ye f f i c i e n t l ya n dd r a m a t i c a l l yr e d u c et h et i m e so fr e a d i n g r a wd a t aa n d t h ec o m m u n i c a t i o nc o s tb e t w e e n p r o c e s s o r s ， t h i r d l y , g i v e san e wm e t h o do fm a t e r i a l i z e dv i e ws e l e c t i o n ，c a l l e ds t a rc u b e i ns t a r c u b e ，o n l yc a l c u l a t ea n ds t o r et h em a x i m u mv i e ww h i c hi so fm a x i m a ld i m e n s i o n sa n d c a l c u l a t e 壤eo t h e rv i e w si nac l a s sa tr e a lt i m e 。s t a rc u b ea tm o s tc a l c u l a t e sa n ds t o r e sh a l f o f t h ev i e w si nad a t ac u b e ，s or e d u c e st h ec o m p u t a t i o na n dm a i n t e n a n c et i m e i nc a s eo fa f r a g m e n to n l yn e e do n ei o ，t h eq u e r yr e s p o n s et i m eo fs t a rc u b ei sa l m o s tt h es a m ea s m a t e r i a l i z i n g a l lt h ev i e w si nad a t ac u h e l a s t l y , i nd a t ac u b e ，t h e r ea r em a n yt u p t e sa r ea g g r e g a t e df r o mt h es a m et u p l e ss e ti n b a s ed a t a f o rt h e s et u p l e s ，藩s t o r e do n l yo n et u p l ea n dd e d u c e dt h eo t h e r t u p t e sf r o mt h e s a v e do n e ，s t o r a g es p a c ec a nb er e d u c e d b a s e d0 1 1t h eo b s e r v a t i o n ，p r o p o s e st h ec o n c e p to f c l o s e dd a t ac u b ea n dp r e s e n t sa na l g o r i t h mt h a tc a l lp r o d u c ec l o s e dd a t ac u b ef a s t t h e n ，u s e s al i n e a rq u e r yc o s tm o d e lt oa n a l y z et h ep e r f o r m a n c eo fc l o s e dd a t ac u b ea n dp r o p o s e st h e i d e ao fs e m i m c l o s e dd a t ac u b e ，w h i c ht r a d eo f ft h eq u e r yr e s p o n s et i m ea n ds t o r a g es p a c e a b s t r a c t a f t e rg i v i n gt h em a t h e m a t i c a l d e s c r i p t i o n o fs e m e - c l o s e dd a t a c u b e ，d e s i g n s a g r e e d y a l g o r i t h m t op r o d u c es e m i c l o s e dd a t ac u b er a p i d l y k e y w o r d s ：d a t aw a r e h o u s e ，o l a p , m u l t i d i m e n s i o n a td a t am o d e l ，d a t ac u b e 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：务墩鲤、 日期：工。弓5 3 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 作者签名：专嘞魍，导师签名：碱 日期：3 笫一肇0 i 高 第一肇雩l 富 1 1 数据仓库和联机分祈技术的产生 随着计算机技术的。遮发展和广泛应鲻，很多政府部门和企业都建立了自己的信息 管理系统，处理l j j 常事务，它极大地提高r 事务处理的效窭和水平，并在实际运行过程 中积累了大量的蛭务数露，如产品数据、销售数撰、客户数据及市场数据等。这些数据 是宝贵的资源，其中隐含着丰富的信息和有用的知识，有可能对决策产生麓大影响。如 俺获大量靛数蠢中挖据i 鑫蠢用豹知谈，帮劲入傲在焚纯逐遽竞争激黧魏市场中迅速徽密 正确的决策是人们感兴趣的课题，具有非常重要的现实意义。 鑫予经验和姿盒静壤铡，诲多企韭都楚先在蓑于个蕺门建立管理售惑系统，然螽孬 加以推广。在系统设计时，使用的分析方法是面向业务处理流程的，可以得到很高的事 务处理速痰，但造成了信爨毂分教。恻如，客户关系管理( c r m ) 对“个现代企业是蓦常 重要的，而在一个供电企业，客户的数据往往分散在报装部门、计量部门、线路部门、 监察部门够，很赡彳导到完熬的资料。为了遴行客户分折，在实际中往往采娜从多个系统 中插取相获数据缀建新系统的方法，这是一种治标不治本的做法，结果使得各系统之间 有错综复杂豹关系。人们形象的称之为“蜘蛛网”现象。另外，目前主流的数据库管理 系统是基予关系禳型的，为了克月醚插入异常和更耨弊常，稳出了规范化理论作为设计应 用系统的指南，规范化的主要手段是模式分解，使得相关数据分散在不同的表中。 现有鹃巍弼数据库管蕊系统题谣惫事务处理的，在事务处理鼙虚弱中敬得了成功， 例如，火车售票系统、银行通存通兑系统、税务征收管理系统。这然应用的特点愚每个 臻户请隶只缝理极少量静数据，翔谚改一”f 账户余鼗，要衾穗应遮菠狭，熊阉嚣憝溪缀 多用户请求，对数据的安仝性、完艇性以及事务香吐量要求很高。因此，肖前的数据库 蛰理系统楚舒对予楚理短漆务恧设计兹。像辩数暴送行分撰遮撑韵应秀要袋访遥大壤熬 数据，进行复杂的统计，需要运行很长的时间，是只读的长事务，与事务处理型应用有 不越豹要求。 对信息集成的需求以及目前的数据库管理系统不适合处理像数据分析这样的皮带， 使褥数据仓痒固a t aw a r e h o u s i n g ) 技术应运蕊生。数据仓库之父i n m o n i n m 9 3 把数键仓 库定义为一个面向主题的、集成的、不可煎新的鼠随时问罐i 断变他的数据集合，用米支 持管理人员的决策。 联祝分析处理( o n - l i n ea n a l y t i c a lp r o c e s s i n g ) 楚黻海薰数据为鏊黼的复杂分析技术， 是数据仓库中一一项十分重要的应用。联机分析处理支持器级管理决策人员从不| 司的角 度、俊邃瑟活缝霹数据仓麾中的数箍迸幸亍笈杂查谲鞠多维分析处理，并叠熊以直躐猫懂 的形式将盗询和分析结果提供给决策人员，以方便他们及时掌握企、业内外的情况，辅助 生里楚兰堕坚! ：堂垡堡塞= 兰生墼塑堡型塑整塑生查焦楚! 塑一 各级颥导进行证确决策，提高钍业的竞争力。 数据仓库系统总体 = 由以下几个部分组成：数据会艨的后台工具、数据仓魔服务器、 联机分析服务器和数捅挖掘服务器和前台工其。图1 1 是一个鼹型的数据仓库系统的体 系结构。 囝 外州数槲 话 l l j 联机誊务处理 潜e 王p 鼗瓣海 暂据集m 圈1 ，l 数据仓库体系结构 数撼仓疼中鲍数提来源予多秘不尉熬数据瓣( d a t as 姻r e 舒。它翻可悲是不嗣孚台上 异构数据库中的数据，也可能是外部独立的数据文件( 例如由某些应用产生的文件) 、 w e b 贾强、市场调查警。 数据仓库的后台工其，包括数错抽取( e x t r a c t i n g ) 、清洗( c l e a n i n g ) 、转换 ( t r a n s f o r m a t i o n ) 、加载( l o a d ) 和维护( m a i n t a i n ) 工具。目前许多公司产鼹把后螽 工其简记为e c t l 工鬃或e t lt 其，簿插取、转换帮装载三个英文字头。e t l 把数耨 源中的数据经过加工以后装入数据仓席并建立元数据( m e t a d a t a ) 。 数据仓痒服务器( d a t aw a r e h o u s es e r v e r ) 裾警子数据库系统巾的d b m s ，它受责管理 数据仓库中数据的存储管理和数据存取，并给联机分析服务器和前端工县提供存取接口 ( 掘s q l 查键接掰) 。数据仓簿服务器蟊蓊一般是r d b m s 袋舻震豹r d b m s 。舔崮铸 统数据库厂商对d b m s 加以扩展修改，使得传统的d b m s 支持数据仓库的功能。 联糗势瓠骚务器透爨逢魏藤黎工其鼹琢户提供多缀数擐撬攀。数撬挖撼爨务器蜇螯 挖掘模型、算法和数据的管理。 鸯谗捉表王其、多维分拆王具、数摆挖掘王其襄分捱结果碍援经王具等结合在一起 构成了数掘仓库系统的前台工其层( f r o n t t o o l s ) 。 数据集市( d a t am a r t ) 是部f 1 缓豹数据仓库。数据集赘的组织标准悬多葶孛多榉的，除 了按业务来组级外，也可以按主题或数据的地理分布来组织。数据集市的思想同时提供 了分布式数据仓库的思想。如果我们按照数据的地理分匆来组织数据集市，就彤成了一 个造臻上分布瀚数脊仓库。蒯鳓我们可疆为一个跨函集团的各予公司建立起各自的数掘 集市，然后再在数掘集市的基础上建立集团全髑的数据仓库。 笫一牵引击 联机分析和数据挖掘服务器除了可以从数据仓库中获敬数据外，还可以从数据集市 中获敬数撼f 强1 1 没有标明) 。 许多公司提供了数据仓库相关产品。例如，i n f o r m a t i c a 、a s c e n t i a l 和b u s i n i e s so b j e c t 公司的e t l 工具。n c r 、i b m 和o r a c l e 的t e r a d a t a 、d b 2 和o r a e l e 9 i 数据仓库服务器。 h y p e r i o n 、c o g o n s 和m i c r o s o f t 的e s s b a s e 、p o w e r p l a y 和a n a l y s i s s e r v e ro l a p 服务器。 s i m o nf r a s t e r 大学、i b m 和m i c r o s o f t 的d b m i n e r 、d b 2d a t am i n i n gs e r v e r 和m i c r o s o f t a n a l y s i ss e r v e r d a t am i n i n g 藏务秣。 一些大学也对数据仓库和联机分析技术进行了研究，取得了丰富的成果。例如 s t a n f o r d 熬数摄仓瘁矮嚣w h i p s ，攘拿大d a l h o u s i eu n i v e r s i t y 霸c a r l e t o nu n i v e r s i t y 匏 并行o l a p 项目p a n d a 。国内的中国人民大学、哈尔滨工业大学、南京大学、西北工业 大学等都对数据仓疼技术避牙了磅究，主娶巢孛在数搀仓蓐熬体系缝捣、数握仓瘴拣建 模、数据仓库中数据的组织与存储、数据立方体的计算等方面。 1 2 数据窃库和联梳分析的主要研究内容 数据仓霹中的数据是多个数撵源中的数据经过捆取、过滤、集成盼结鬈，可以稽作 魁对多数据源查询的结果，即实例化视 h m w l + 9 5 1 。涉及到的主要研究内容有实例 纯梭图懿逸择、实嵇l 促麓强爨壤量维护释耩耀实铡佬视图瓣查询熏写。 1 2 1 实体纯视图的选择 鼗耀仓库中寄鹾类数据，一癸跫定义程分布予多个数爨源孛静基本表( b a s et a b l 上 的实例化视 ( b a s ev i e w ) ，另一类是在实例化视图卜定义的综合表( s u m m a r y t a b l e ) ，它 涉及裂了大量麴蒙蔟函数，蠢对瞧骥骰导滋褪整( d e r i v e dv i e 奶。 用r 袋示基本表，v 表示实例化视图和导出视图，q 表示数据仓库要阐答的针对r 静蹇落熬集台，实秘伍蠢阉豹选爨逡遂可戳接述莠：选择组援强m ，m g v ，经褥遴 过查询重霹技术，q 只访问m 中的视图，并且，焱询代价c ( q ) 最少，同时，满足空间 簸键或露蠲隈翻，帮给定常数l 帮l 2 ，s ( m ) l l ，u ( m ) b ，s ( m ) 耩u ( m ) 分翮燕m 占 用的存储空间和维护时间( 代价) 。 【g 泖馘9 7 】穆套诲q 凌示菇一令a n d 。o r 鹜g ，g 中褥两类迭，a n d 透程o r 透。 a n d 边由移条普邋边构成，它们之间的关系是与关系。如v 】一u ，v 2 一u ，v 。一u ， 表示视图u 弓l 爱t 程爱v l ，毪。，h ，震要谤闫繇有这些裰黟彳麓鼹爨毪熬继栗。o r 边 也出多条普通边构成，不过它们之间的关系是或关系。如v i u ，v 2 一u ，表示可以通过 v t 域v 2 可以诗算撼褪图u 。霉中每个节点驸彝访鞫缀率、修改壤率释掺改饯羚垂数，巍 图选择问蹶转换成了找出g 中的节点集合m ，满足c ( q ) 最少，同时满足限制条件s ( m 1 s ，s 是时间限制常数，可以找到m ，u ( m ) 2 s ，使得总的查询代价至少是最 优的0 6 3 。对于a n d o r 图，给出了一个启发式搜索算法a - ，可以得到最优解。 f l h 9 9 利用基因算法解决o r 图的视图选择问题，特点是复杂性与维数成正比，执 行速度快，得到的结果接近于最优解。基因组用0 和l 二进制表示，采用了标准的 c r o s s o v e r 和m u t a t i o n 操作，采用对数，指数和线性函数做适应性函数( f i t n e s sf u n c t i o n ) ， 实验结果表明指数函数比较适用于视图选择问题，初始时有3 0 个基因组，产生4 0 0 代 以后算法终止。 t s 9 7 提出了用m u l f i q u e r y g r a g h 来表示s j 查询，r 中的关系作为图中的节点，q 中的查询选择条件和连接条件作为边，每个边有一个标签，说明是哪个查询的选择条件 和连接条件，并提出了s e l e c te d g ec u t 、j o i ne d g ec u t 和v i e wm e r g i n g 转换规则，将 m u k i q u e r yg r a g h 从一个状态转换到另一个状态，实例化视图的选择被映射到状态空间 搜索。 f a c n 0 0 研究了在s q l 数据库中自动选择实例化视图和索引加快查询速度的问题， 为了减少搜索空间提出了感兴趣子表算法和视图合并算法。视图被限制为只有一个块 ( b l o c k ) 的s q l 查询语句。 y k l 9 7 用m v p p ( m u l t i p l e v i e w p r o c e s s i n gp l a n ) 表示系统中的查询，从图中找出可 以使查询代价和维护代价最少的视图实例化，使用线性代价模型。该文将视图选择问题 映射到了o l 整数规划问题，得到最优解。 以上的文章中提出的解决方法是当知道用户的负载( 查询) 以后，做出的一个针对 这个负载的近似最优解，当用户的负载发生显著变化以后，需要重新计算实例化视图。 另外，当确定实例化一个视图后，是将这个视图的所有元组实例化，而不可以只实例化 其中的一部分。 k r 9 9 1 提出了动态视图管理系统d y n a l v h t ，它根据用户负载的变化自动 调整实例化的视图，实例化的最小单位是f r a g m e n t ，把实例化视图的选择和c a c h e 结合 起来。d y n a m a t 不问断的追踪用户提出的查询，根据用户查询模式的改变，动态的调整 实例化视图，使得系统的查询响应时间总是最优。它还考虑了视图维护对实例化视图选 4 第章引裔 撵的影响。 1 2 2 实体车l ：褫圈酌媾蠢维护 当数攥源中的数据发生了变纯以后，需要将这黧变记反映至l 数据念露申，称为实翻 纯援鬻黪缍妒阉题。一秘方法怒重凝淘系统提交褫瀚豹定义语訇，褥到耨鹣蠢谗缝聚。 鹦一种方法叫增量维护，即用糕本表的变化量计算视图的变亿量，用变化量去修改视图。 一般情况下，增量维护斡代价院鬟新计算溪低，增蘩维护燕数据仓库中瓣一个研究热点。 目前已经发表了缀多增量维护的算法。根据维护的时机可以分为及时维护 f i m m e d i a t e ) 和延迟维护( d e f b r r e d ) 两大类。及时维护是一个事务在提交前，要将对一个表 熬修改( i n s e r t 秘d e l e t e ) 缝聚聂浚到瑟骞弓| 霜渡表豹巍黧中，援强缝护藏为事务靛一 豁分，加重了事务的负掇，但可以缳持视圈与纂零表阉步变刳二。筵迟维护是当月户需要 榄图的嫩新结果时，才去更新视图。但是视图中的数据不能反映璇新情况。另外，每种 算法郡滚热了一骜瓣裂条件，稠翔，可激缍护豹摆醋类型不同：麓s p j 定义懿视毅，罔 s q l 语句定义的视图，用d a t al o g 定义的视图等。使用的环境不一样：集中环境，分 布环境。 强强增爨维护豹基本添理楚：j 尊每一令投强，投壤它豹定义，导凑一个增量绦护表 遴式，然后计算这个表达式得到视图的增璧。 g m s 9 3 1 以d a t al o g 的澎式给出了增量维 护表达式，采用了包( b a g ) 语义。f g l 9 5 掇出了麓予龟语义的代数增蘩维护。【q u a s s 9 6 】 扩展了 g l 9 5 的王 乍，馒得戡处理聚集醋数。 例如，v = r lwr 2 。用r 和v r 分别表示插入到r 和从r 中删除的元组。当r l 中瑟增麓了嚣组r l 对，v = ( r l + a r i ) * r 2 = = r l “r 2 十r l * r 2 。v 豹增量我达式 为r l wr 2 ，鼹撵，当从r l 中删昧元组v r l 封，v 嬲增量表达式为v r lwr 2 。 1 3 t l 8 6 1 最早讨论了在集中数搽库环境下s p j 视图的增量维护问题。摁出了梢关修 羧帮 轻关穆改瀚概念以及一个检溯算法。魏聚鏊本表的修改影潮裰潮的结采，这释懿 修改就是相关修改，否则是不相关修改。提出了维护s e l e c t 、p r o j e c t 、j o i n 和s p j 视图 的维护算法。当一个事务在提交对，需要执行维护算法。 【c w 9 1 讨论了震s q l 谬窝定义懿裰鬻静壤篷缀护逡题，对一个筏嚣定义，捺等窭 一组产生式媲则，当执行i n s e r t ，d e l e t e 和u p d a t e 时，执行这些燃则，达到视图增量维 护的目的。与 b t l 8 6 相磁，【c w 9 1 提出的方法更爱活，为此，该文于2 0 0 0 年获得 v l d b l 0 年谯秀论文奖。 与集中数据库环境不同，数据仓库中的视网是定义在多个数撼源的纂本表上的，由 予数据滚其露鑫涤往，当数据源中懿数据发生交织孵，只憝激游惑静方式通翔数据仓瘁， 数握仓疼稷搀援嚣魏增繁维妒装遮残生成令囊谗，发送到数摄源，数耀滚穆套键绪暴 遐回数据仓库，数据仓席利用谴询结果修改视图。如果数掘源两个变化的间隔足够长， 筏图将稽到正确静维护。否刚瀚话，裁会出现掇入稻翻除笄常，簿致谨误绐采。 z m h w 9 5 r 瞬究了单数撮源的数据仓库环境“f 的视躁增量维护问题，定义了视图维 中国科学院博士学位论文多维数据模型和数描蕺疗体技术研究 护正确性的判断标准：收敛( c o n v e r g e n c e ) ，弱一致性( w e a kc o n s i s t e n c y ) ，一致性 r c o n s i s t e n c y ) ，强一致性( s t r o n gc o n s i s t e n c y ) 和完全( c o m p l e t e n e s s ) ，提出了e c a 、e c a “ 和e c a l 算法。 a a s y 9 7 研究了多数据源的数据仓库视图增量维护问题，提出0 n l i n e e r r o r c o e c t i o n 思想，并据此设计了s w e e p 算法。在多数据源的环境中，一个视图会涉及 到多个数据源中的数据，在数据仓库发出一个增量维护查询到收到结果之前，会收到来 自各个数据源的修改操作，根据查询的执行进度，可以区分出有些修改是不影响查询结 果的，另外，多个增量维护查询可以合并执行。 前面的算法都属于立即维护型，对集中式系统来讲，增加了每个事务的工作，限制 了系统中可以定义的视图的数量。对分布系统而言，增加了通讯量。在某些可以容忍视 图的内容不是最新的应用中可以采用延迟维护的策略。立即维护型算法要求针对基本表 的一个变化构造的增量维护查询在修改发生之前的数据库状态上执行，称为p r e u p d a t e ， 否则，就会得到错误结果，例如，e c a 算法不能保证这个条件，才采取了补偿的办法。 除了基本表的增量以外，延迟维护需要一些辅助数据结构才能保证得到正确的结果。例 如，对基本表维护一个日志( 1 0 9 ) ，对视图维护一个差异表等。 c g l 9 6 研究了延迟维护所需要的辅助数据结构和增量维护表达式，称为三个不变 式。提出了四个过程：m a k e s a f e t 1 为了到达增量维护的目的，一个事务除了本身的工作 外需要做哪些辅助性工作。r e f r e s h 将视图的增量反映到视图中。p a r t i a lr e f r e s h 同r e f r e s h ， 但不能保证视图中的内容是最新的。p r o p a g a t e 根据日志计算出视图的增量。通过引入 多个过程，分摊了增量维护的成本，使得事务可以尽快完成，封锁视图的时间缩短。 c k l m 9 7 给出了在一个系统中，支持多种视图维护的策略：立即维护型，延迟维 护型和快照( s n a p s h o t ) ，以满足不用的应用要求。 【m q m 9 7 研究了数据仓库中综合表的增量维护问题，在 c g l 9 6 和 q u a s s 9 6 的基础 上，提出了s u m m a r y d e t a t a b l e 解决方案。综合表是带有聚集函数的视图，例如，d a t ac u b e 。 其最大的特点是利用d a t a c u b e 计算方法，从基本表的增量中计算出d a t a c u b e 各视图的 增量，然后，利用【c g l 9 6 的r e f r e s h 过程更新视图。 【l y m 9 9 研究了定义在多个基本表上的最优视图增量维护计划，并在此基础上提出 了同时维护多个视图的最优方案，其最优方案是基于线性代价模型的。假设视图引用的 基本表( 视图) 的增量为6v l ，6v 2 ，6v 。，c o m p ( v , v l ，v 。 ) 表示计算视图v 的增量，i n s t ( v ) 表示安装v 的增量( 同 c g l 9 6 的r e f r e s h ) ，视图维护的一个策略是c o m p 和i n s t 的一个排列( 有一些限制，例如在安装基本表v 的增量以前，要执行完引用v i 的 增量维护表达式，以保证p r e u p d a t e 的要求) 。不同的策略有不同的执行代价，可以生 成所有的策略，即 v l ，v 。) 不同划分的组合和每一个划分对c o m p 和i n s t 的排列之积。 例如有两个策略为： c o m p ( v , v l ，v 。) ) ，i n s t ( v 0 ，i n s t ( v 。) i n s t ( v ) ( 1 ) c o m p ( v , v l ) ，i n s t ( v i ) ，c o m p ( v , v 。) ) ，i n s t ( v 。) ，l n s t ( v ) ( 2 ) 第一章引击 根据线性代价模型，对一个视图的媛优维护策略怒对 v l ，v 。) 按照“v 1 ) ， v 2 ， v 。 进 亍划分，排列次序按照代价的递增来排序。【l y m 9 9 j 丕绘出了确定多 视图维护的最优方案的求解算法。其实验络果表明，因为实际应用不见得就遵循线性代 价模型，求出的解不是最优解，但很靠近鼹优解。 r l y c m w 0 0 讨论了重复元维酌两种表示方法：d u p 帮c n t ，蓊者是凝系系统的一 般液示方法，后者增加一个属性d u p e n t 记淤一个元组在表中出现的次数。d u p 在安装 v v 的时谈不麓麓b a t c h 懿方法( 锎如s q l 瓣d e l e t e 语甸) 只戆蠲c u r s o r 静方法。c n t 在安装v 时用b a t c h 的方法不方便。在安装综合视图的增量时，除了f m q m 9 7 提出的 c u r s o r 方法终，还提出了b a t c h 弱方法窝o v e r w r i t e 的方法( 生成一个撅豹援圈) 。实验 结果表明对于综合视图不同的安装方法适用于不同的情况。在平均匿复率很少的情形下 ( = n i c e b e r g 为数据立方体。 计算i c e b e r g 的一种自然的想法是采用计算数据立方体的方法，例如p i p e s o r t ，每 1 3 中固科学院博_ 二学位论文一多维数据模型和数挺立方体技术研究 计算出一个分组就判断它是否满足限定条件，满足则将它写到结果中，否则，抛弃它。 对聚集函数c o u n t 等一类函数，它们具有反单调特性：如果g r o u p b ya 的一个分 组不满足条件，则由该分组产生的g r o u p b ya b 的分组也不会满足条件，进一步的推 广，所有a 的超集都不会满足条件。这种特性在计算关联规l j ( a s s o c i a t er u l e ) 的算法( 像 a p r i o r i ) 中已经被发现，用来在搜索空间中进行剪裁( p r u n e ) 。在图1 4 中，对a l l 的 一个分组，按照属性a 上的值进行等值划分，会生成a 的若干个分组，每个分组中的 所有元组在属性a 上的值相同。如果其中的一个分组g 不满足条件，则不用去计算由 分组g 产生的a b ，a b c ，a b c d ，a b d ，a c ，a c d ，a d 的分组。 【b r 9 9 提出的b u c 算法是一种从下往上计算的算法。它首先计算出视图a l l 的唯 一的一个元组，然后，对搜索树按照深度优先的原则，对数据进行划分，计算出其它的 视图的元组。实验结果表明算法b u c 的性能要好于p a r t i t i o n e d 。c u b e 算法。 f h p d w 0 1 提出了弱反单调的概念，给出了计算聚集函数是a v e r a g e 的i c e b e r g 算法。 i n w y 0 1 1 将b u c 算法并行化。 图i 4 搜索树 图1 5b u c 生成元组的次序 d 4 、部分数据立方体 随着维数的增加以及原始数据的增大，数据立方体中的元组个数将急剧增加，需要 很多的存储空间和计算维护时间。因此，如何只计算数据立方体中的一部分视图，使得 在给定的存储空间限制下，尽可能的快速的回答用户的查询是值得研究的问题。部分数 据立方体问题和数据仓库中的实例化视图选择问题有相似之处【1 2 1 1 ，可以借鉴数据仓 库的研究成果。 h r u 9 6 在 g u p 9 7 对o r 图的研究成果上提出了一个贪心算法用于选择数据立方体 中的视图实例化，可以保证在最坏情况下，得到的结果是最优结果的0 6 3 倍。 g h r u 9 7 把 h r u 9 6 1 的工作扩展到同时选择实例化视图和索引。 s d n 9 8 针对满足一种特殊条件的数据立方体给出了一个快速算法p b s ，同时可以 在理论上保证得到的结果是最优结果的0 6 3 倍。 k m p 0 2 5 采用n 机算法的思想设计了选择实例化视图的算法，其特点是计算速度快， 特别适合于高维的情况，但不能在理论上保证得到的结果的精度。 5 、浓缩数据立方体 第一章引言 数据立方体中存在一些冗余数掘，去掉这些咒余数据就得到了一类新的数据立方 体，繇浓缀鼗挺立方 本。 w l f y 0 2 发现在稀疏数据中有许多视图中的元组是蘩本表中的一个数组去掉若干 个维褥到的，基本表中的这样的元组叫做b a s es i n g l et u n e 。在计搏数据立方体时，如 果个元组是从一个b a s es i n g l et u p l e 得刘的，则不存储浚元组，这样就大大减少了数 据立方体f 勺体积。 f l p h 0 2 j 茳- - 步发震了这稀愚艨，如暴多个元缝是歇基本表中稽同的元组集合聚集 得到的，则只存储其中的个元组。 s d r k 0 2 采瓣了特殊豹链表缭稔，采稽了蘸缀共享技零霸类似z i z l p h 0 2 静懋憋， 减少了数据立方体的体积，同时，链表结构也作为一种特殊的索引，加快了查询响应时 溺。 1 2 6 多维燕询及鸯濑优化 在联机分析中经常用到点查询、范围斑询、假设查询簿。 f h a m s 9 7 在假定数掇立方体不发生变化的前提下提蹴了实铺亿p r e f i x s u m 的方 法，使得范围查询的查询响应时间在常数时间之内。 g a a 0 0 考虑了数据立方体懿增量维护静影确，提毒了动态数键立方俗技术，使得 范围查询也能保持在常数时间之内。 【c 1 9 9 1 彝 c c l l 0 1 凌对该阂鬟遴嚣了磷究，释鏊本方法类觳。 m b b 9 9 在bq r e e 的基础上，提出了u b - t r e e ，利用z - c u r v e 的特性将数据聚类， 大大掇块了莛基煮逮豹嚷纛潜藏。 f a l 8 6 ，【j a 9 9 0 提出了利用g r a yc o d e 和h i l b e r t - c u r v e 对数据聚类的方法。 【m v 0 0 研究了时态查询，提出了时态多维数攘模型，支持维蔗次积对阗。绘蹬了 一个用d a t a l o g 描述的查询语言，并给出了向s q l 和t s q l 2 ( 一种用于时态数据库的 查询语言) 转换的例子 【o h 9 7 ， c n 9 8 羊1 b p p 0 0 研究了假设查询( h y p o t h e t i c a lq u e r y ) 。 在查询优化方灏，主臻是针对s q l 中的星型涟接( s t a r - j o i n ) 茅m d x 语句做了一 骛工作。 例如有一个查询q 要镬询2 0 0 2 年各种产品在北京的销售情况。用t i m e ( t i m e i d d a y , m o n t h ，y e a t ) 、p r o d u c t ( p r o d u c f l d ，f a m i l y , g r o u p ，a r e a ) 、s t o r e ( s t o r e l d ，c i t y ，p r o v i n c e ， r e g i o n ) 和s a l e s ( t i m e l d ，s t o r e i d ，p r o d u e t l d ，a m o u n t ) 分别表示时间维、产黯维、商店维 窝销售事实表，爨q 哥数轰示为： s e l e c tr p r o d u c t