（计算机软件与理论专业论文）gradual+cube：一个移动olap系统.pdf

第i v 页 摘要 联机分析处理( o l a p ) 是决策支持系统( d s s ) 中一款重要的分析工具。它提 供了数据立方的多维视图，用户可以通过一系列的上卷下钻操作来发现感兴趣 的模式和趋势。随着移动设备和无线网络技术的快速发展，用户希望在移动环境 中也能享受o l a p 服务。移动联机分析处理将o l a p 服务移植到移动设备上，与 传统o l a p 相比，它在提供更多的方便与快捷的同时，也带来了新的机遇和挑战。 如没有持续稳定的网络连接，数据传输瓶颈以及移动设备的存储空间限制等等。 本文的目标就为上述这些问题寻找合适的解决方案并实现一个移动联机分析处 理的原型系统。首先，我们介绍了一种新的数据立方存储结构c o n t o u rc u b e ，它 本身就是一个无损压缩表示，并且可以在给定的误差界限内被进一步压缩。其 次，我们在传输过程中采用了渐进式的传输方法。我们假定用户对于数据精度的 期望满足特定的概率分布，并提出了随机，最优和启发式3 个算法为不同用户定 制传输计划，在数据传输量和数据精度之间寻找较优的平衡点。再次，我们通过 对用户在观察精度和探索范围两方面做出限制，保证移动设备端的数据量不会 超过存储容量上限。最后，基于上述成果，我们实现了g r a d u a lc u b e ，一个移动 联机分析的原型系统。在网络通畅时用户可以自由地调整数据精度和探索范围， 在网络彳i 畅时，用户依然可以利用本地压缩聚集进行离线查询。并且上述两个状 态的转换是非常平滑的。此外，一系列详尽的实验证明了我们方法的有效性。 关键词：移动o l a p ，压缩，定制 中图分类号：t p 3 1 1 1 3 g r a d u a lc u b e ：一个移动o l a p 系统 第v 页 a b s t r a c t o l a pi sa ni m p o r t a n ta n a l y s i st o o li nd e c i s i o ns u p p o r ts y s t e m ( d s s ) n o w a d a y s i te n a b l e se n d u s e r se x p l o r et h ed a t ac u b em u l t i d i m e n s i o n a l l yt h r o u g ha s e - t i e so fo p e r a t i o n ss u c ha sr o l l u p sa n dd r i l l d o w n sa sw e l la 8p o s ea n a l y t i c a lq u e r i e s t of i n di n t e r e s t i n gt r e n d sa n dp a t t e r n s m e a n w h i l e ，w i t ht h er a p i dd e v e l o p m e n t o fm o b i l ea n dw i r e l e s st e c h n o l o g i e s ，e n d n s e r sw i s ht oe n j o yt h eo l a ps e r v i c e o ns u c hn e wd e v i c e s m o b i l eo l a pc o n v e r g e sb o t ho l a pa n dm o b i l ea p p l i c a ，- t i o nt e c h n o l o g i e st of a c i l i t a t ep e o p l e 8d a i l yl i f e t h e r ea r em a n yi s s u e so nm o - b i l eo l a pa g a i n s tt h et r a d i t i o n a lo n e s ，e g ，t h eu n s t a b l en e t w o r kc o n n e c t i o n ，t h e t r a n s m i s s i o nb o t t l e n e c k ，t h es t o r a g el i m i t s ，e t c a l lt h e s en e wc h a l l e n g e sp r o v i d e n e wo p p o r t u n i t i e sf o rt h eo l a ps e r v i c e i nt h i st h e s i sw o r k ，w ea r ea i m i n ga t d e v e l o p i n gp r o p e rs o l u t i o n st ot h ea b o v ep r o b l e m sa n di m p l e m e n tap r o t o t y p es y s t e m f i r s t l y , w ei n t r o d u c ean e ws t o r a g es t r u c t u r e ，n a m e l yc o n t o u rc u b e ，w h i c h i sal o s s l e s sc o m p r e s s i o no fo r i g i n a ld a t ac u b ea n di sc a p a b l eo ff u r t h e rc o m p r e s - s i o nu n d e ra n yg i v e ne r r o rb o u n d s e c o n d l y ，w ee m p l o yp r o g r a s s i v er e f i n e m e n t s t r a t e g yd u r i n gt h et r a n s m i s s i o n w es u p p o s et h eu s e r s r e q m r e m e n to np r e c i s i o n f o l l o w ss o m ed i s t r i b u t i o ns ot h a tt h r e em e t h o d s ，n a m e l yr a n d o m ，o p t i m a la n d h e u r i s t i c a r ed e v e l o p e dt oc u s t o m i z et h et r a n s m i s s i o np l a n w eb e l i e v et h i sk i n d o fc u s t o m i z a t i o nc a l lh e l pt om a k eab e t t e rt r a d e - o f fb e t w e e np r e s i c i o na n dd a t a s i z e t h i r d l y , w er e s t r i c tb o t ho b s e r v ep r e c i s i o na n de x p l o r er a n g ei no r d e rt o g u a r a n t e et h a tt h ed a t as i z eo nt h em o b i l ed e v i c ew i l lm e e tt h es t o r a g el i m i t f i n a l l y , g r a d u a lc u b e ap r o t o t y p es y s t e mo fm o b i l eo l a p i si m p l e m e n t e db a s e d o no u rr e s e a r c ha c c o m p l i s h m e n t s t h ee n d u s e r sc a na d j u s tt h eo b s e r v ep r e c i s i o n a n de x p l o r er a n g ef r e e l yw h e nt h en e t w o r ki so n ，t h e ya l s oc a nc o n t i n u et h e i rw o r k b yo f f - l i n eb r o w s m gw h e nt h en e t w o r ki so f f , t h ec o n v e r s i o no ft h e s et w os t a t e si s s m o o t he n o u g h b e s i d e s ，t h ee x t e n s i v ee x p e r i m e n t ss h o wt h a to u rm e t h o d sa r e e f f e c t i v ea n de f f i c i e n t k e y w o r d s ：m o b i l e0 l a p ，c o m p r e s s i o n ，c u s t o m i z a t i o n g r a d u a lc u b e ：一个移动o l a p 系统 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：型 论文使用授权声明 日期：塑! ：鱼：! ! 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：凌星垒导师签名：之逊日期： 1 1 数据仓库- 与o l a p 的研究背景 第l 页 第一章引言弟一早，l 苗 1 1数据仓库与o l a p 的研究背景 数据仓库( d a t aw a r e h o u s e ) 是一个面向主题的，集成的，相对稳定的，反 映历史变化的数据集合，主要用于支持管理决策 1 0 1 。使用数据仓库能够对数据 进行更好的加工处理，发现其内在的规律性，帮助决策者指导企业决策和发掘企 业的竞争优势。与传统的操作型系统不同，在数据仓库中，概要的、总体的数据 比细节的、单条的记录更重要，其数据可能来源于多个操作型数据库，包含海量 的历史数据，支持即时的、复杂的查询。这些查询通常需要访问大量记录，进行 复杂的连接和聚合运算。 数据仓库技术1 1 1 的提出引起了学术界和工业界的广泛关注，s t a n f o r d 大 学、w i s c o n s i n 大学、i b ma l m a d e n 研究中心等研究机构纷纷立项从事数据仓库 技术的研究，研究的方向覆盖了数据仓库的方方面面。许多著名的数据库厂商， 如i b m 、h p 、o r a c l e 等纷纷推出了自己的数据仓库产品和解决方案。这些产品为 大型零售业、制造业等食业所采用。而在国内，金融、证券、电信等计算机应用 较早、较成熟的行业近年来也纷纷开始采用数据仓库技术以更有效地进行决策 支持。 数据仓库系统之上包括了很多决策分析工具，而o l a p ( o n - l i n ea n a l y t i c a l p r o c e s s i n g ，联机分析处理) 可以说是与数据仓库联系最为紧密，同时也是 最为重要的一个验证型分析工具。o l a p 9 的概念由关系数据库之父e f c o d d 于1 9 9 3 年提出，它建立在多维视图的基础之上，通过对信息( 维数据) 的多种 可能的观察形式进行快速、稳定一致和交互性的存取，允许数据分析人员对数据 进行深入观察，从而获得能够真正为用户所理解的、并真实反映企业特性的信 息。o l a p 主要强调执行效率和对用户命令的及时响应，而其直接数据源一般就 是数据仓库。 o l a p 作为一个重要的分析工具，其研究领域相当活跃，近年来涌现了 很多重要的工作。包括计算【7 ，1 3 ，2 2 ，3 1 】，压缩 3 ，1 6 ，1 7 ，2 6 ，2 8 ，2 9 ，3 0 】， 近似表示【5 ，6 ，1 8 ，2 1 ，2 7 ，用户支持【2 3 ，2 4 】，各种环境下的实现【8 ，1 5 ，1 9 ， g r a d u a lc u b e ：一个移动o l a p 系统 1 2 o l a p 的相关概念第2 页 2 0 1 等。具体又分为r o l a p 和m o l a p 两种，研究重点各有不同。目前许 多软件企业已经有了相应的商业化产品，r o l a p 方面有m i c r o s o f t 的a n a l y s i s s e r v i c e ，i n f o r m i x 的m e t a c u b e 以及i b m 的0 l a ps e r v e r 等。m o l a p 方面有a r b o r 的e s s b a s e ，p i l o t 的l i g h t s h i p 等。由于同m o l a p 的系统相比，r o l a p 系统的灵活 性更好，尤其对于海量数据的处理能力更强，所以大部分产品都侧重于r o l a p ， 甚至完全基于r o l a p 。因此，本文也将主要关注r o l a p 相关的各项技术。 近年来，随着移动设备的日益普及，使移动联机分析处理( m o b i l eo l a p ) 成为可能。移动联机分析处理将o l a p 服务移植到移动设备上，在为决策分析人 员提供更多方便与快捷的同时，也对o l a p 的实现提出了更为苛刻的要求。这也 促使我们对受限的情况下，如何有效地提供o l a p 服务进行进一步的研究。 1 2 o l a p 的相关概念 1 2 1o l a p 的定义 o l a p 理事会【1 1 对o l a p 的定义是：o l a p 是一种软件技术，他使分析人员 能够迅速、一致、交互地从各个方面观察信息，以达到深入理解数据的目的，这 些信息是从原始数据直接转换过来的，他们以用户容易理解的方式反映食业的 真实情况。 根据o l a p 产品的实际应用情况和用户对o l a p 产品的需求，人们又提出了 一种对o l a p 更简单明确的定义，即共享多维信息的快速分析。 o l a p 主要由多维数据模型以及定义在其上的一组操作构成。在多维数据模 型中，数据被看作数据立方( d a t ac u b e ) 【1 2 】的形式，分析人员可以通过切片、 切块、上卷、下钻、旋转和转轴等操作获得从不同角度和粒度观察数据的能力： 通过按多维进行切片，切块能够缩小观察范围：通过上卷和下钻能够获得不同粒 度的数据；通过旋转和转轴则能够得到不同视角的数据。 1 2 2多维数据模型 如表1 1 为某超市销售情况的事实表，属性l o c a t i o n ，p r o d u c t 和t i m e 被称作 维，分别对应3 张维表表示观察数据的3 个不同角度。每个角度根据观察粒度的 不同又可以分为若干个维层次，层次之间构成偏序关系。如上例中的日期维按 照细节程度分为年、月、日三种不同的层次，且成日! 月三年的偏序关系。而属 性s a l e s 贝r j 被称为度量是作为分析目标的数值型指标。 表1 2 是上述事实表在聚集函数s u m 下所对应的数据立方。包括了三个 维所有可能的8 个g r o u p - b y 组合，每一个g r o u p - b y 的结果被称为一个数据小 g r a d u a lc u b e ：一个移动o l a p 系统 1 2o l a p 的关概念 第3 页 l o c a t i o n p r o d u c tt i m e s a l e s s h a n g h a i ( a 1 ) b o o k ( b 1 )2 0 0 7 - 5 - 1 ( c 1 ) 4 s h a n g h a i ( a x )f o o d ( 5 2 )2 0 0 7 - 5 - 1 ( e 1 ) 2 s h a n g h a i ( a x )f o o d ( b 2 )2 0 0 7 - 5 - 4 ( c 2 ) 5 b e i j i n g ( a 2 ) b o o k ( b 1 )2 0 0 7 - 5 - 1 ( c 1 ) 3 b e r i n g ( a 2 )b o o k ( b 1 )2 0 0 7 - 5 - 4 ( c 2 ) 4 表1 1 销售事实表 l o c 址i o np r o d u c tt i m es u m ( s a l e s ) 6 1 4 0 16 2c l 2 n 16 l 4 口l6 2 7 a l 1 1 眈 7 h 1 1 k 7 9 9 1 8 表1 2 数据立方 方( c u b i o d ) 。数据小方中的每条元组被称为一个c e l l ，c e l l 上取值为+ 的维表 示在该维上进行了概化，能够匹配维上的任意取值。女 1 c e l l ( a l ，c 2 ) 的值表示上 海在2 0 0 7 年5 月4 日当天所有产品销售量的总和。 数据立方中的两个c e l le l 和c 2 有偏序关系c 11c 2 ，当且仅当e l 中与c 2 取值不 同的那些维上，c 2 的取值为+ 。当c 116 2 时，我们说c l 具有较低的聚集度而c 2 具 有较高的聚集度，c 2 是c 。的祖先，而c l 是c 2 的后代。数据立方中的所有c e l l 连同 上述偏序关系构成了格( 图1 1 ) 。图1 1 中( a l ，b 2 ，c 2 ) 冬( a 1 ， ，c 2 ) ! ( a 1 ， ， ) 5 ( ， ， ) 。( a 1 ， ， ) 是( 0 1 ，6 2 ，c 2 ) 的祖先，( o l ， ，c 2 ) 是( n 1 ， ， ) 的后代。 目前，多维数据模型主要分为星型模型和雪花模型两种。星型模型中，一个 多维数据集包含一张事实表和多张维表，每个维对应一张维表。而雪花模型是将 星型模型中某些维经过规范化后等到的模型。由于规范化过程中会产生许多的 g r a d u a lc u b e ：一个移动o l a p 统 1 3 移动联机分析处理 第4 页 、誊j 蓄藿囊誊i 图1 1 数据立方格图 小表，降低查询性能的同时却不能有效地节省存储空间，所以雪花模型不如星型 模型流行。 1 2 3o l a p 上的基本操作 上卷( r o l l - u p ) 下钻( d r i l l - d o w n ) ：在当前数据对象基础上再减少一个 维或是在具有层次关系的属性中从底层属性切换到上层属性作聚集操作称为上 卷。随着上卷的进行，看到的数据细节越来越少，聚集度越来越高；下钻操作则 刚好与之相反，在当前数据对象基础上再增加一个维或是从具有层次关系的属 性中从上层属性切换到底层属性作聚集，随着下钻的进行，看到的数据细节逐渐 增加，聚集度越来越低。 ，切片( s l i c e ) 切块( d i c e ) ：进行聚合操作时，限定某一维( 或多维) 上成 员的取值范围，这样的操作称为切片或是切块。常见的是按一维、二维和三维切 片，例如，在“城市、产品、时间”三维立方体中对城市维作切片，选定某一城市， 可得到该城市中各产品历年的销售情况，即取出只由该城市构成的数据片。 转轴( p i v o t ) ：查询结果以报告形式出现。转轴即改变报告显示时的维方 向。转轴可能包含交换行或者列，或是把某个行维移动到列维，或是把页面中的 某个维和报告外的维进行交换( 令其成为新的行或者列中的一个) 。转轴操作并 不改变数值的聚集方式和聚集结果，但是它体现了用户视角的变化。 1 3 移动联机分析处理 a s m a n i a t i s 在【1 9 】一文中提出了术语移动联机分析处理( m o b i l eo l a p ) ， 架起t o l a p 与移动设备之间的桥梁。在移动设备上提供o l a p 服务，一般都采 取客户服务器( c s ) 方式。企业将分散在各个地区的业务数据统一收集，集中在 g r a d u a lc u b e ：一个移动0 l a p 系统 1 3 移动联机分析处理 第5 页 一个数据仓库中，并作为决策支持系统的一部分对外提供o l a p 服务。而分析人 员则以移动设备作为客户端与o l a p 服务器进行查询交互，通过在数据立方上进 行一系列上卷下钻操作，逐步找到感兴趣的规律或模式，并以此作为决策的基 础。与传统o l a p 相比，移动联机分析处理面临着一些新的挑战： 首先，没有持续稳定的网络连接。一方面，移动设备的网络连接并不持久， 无线网络可能随时由于信号原因而暂时失去连接。另一方丽，对于笔记本等移动 设备，经常会在一些没有网络的区域工作。在这种情况下，简单的查询一回答模式 并不适用于移动o l a p 。因为这种模式下旧的查询结果不能用来回答新的查询， 导致断网后无法继续工作。另外，查询结果往往会互相重叠而造成重复的数据传 输，浪费本已十分有限的带宽。因此，为了能够在各种网络环境中平滑地使用， 移动o l a p 需要有一定的离线工作的能力来保证用户失去连接后，在不访问服务 器数据的情况下，依然可以根据已存储在移动设备上的数据在一定的误差界限 内继续进行分析。而在连接恢复后，又能根据用户的要求获取更精确的数据。 其次，服务器端和客户端之间的数据传输量是系统的瓶颈所在。众所周知， 数据立方容量巨大，完全物化的数据立方的容量可达数百g 至几十t 的规模，即 便只传送某些数据小方数据量也是无法接受的。而如果只传送事实表，将计算任 务交由客户端进行，对于移动o l a p 而言同样不可取。因为计算数据立方本身是 一件耗时、耗电的工作，而省电是移动设备需要考虑的重要指标。另外，不管采 用上述哪种方法，都需要在所有数据传输计算完成后才能在客户端开始查询， 对于用户查询的响应能力很差。另一方面，由于很多情况下一定误差界限下的近 似值就足以支持决策和分析，因而也有一些方法采用近似有损压缩技术( 如小 波 2 7 1 ，直方图f 2 1 1 等) 对原数据立方进行压缩后再传输来减少需要传输和存储的 数据量。但是这些方法往往无法给出明确的误差界限，使得用户无法确信其在近 似数据上做出决策的可靠性。 最后，移动设备的存储空间限制。随着科技的进步，现在的移动设备的存储 空间一般可以达到几g 到几百g 之间。即便如此，要在客户端装下一个完整的数 据立方仍然是不可能的任务。幸运的是移动设备多为专人所有，这使得个性化定 制成为可能。一般而言，o l a p 的用户大多为分析人员，而不同身份的分析人员 所要观察数据的范围不同，对于数据的精度要求也不同。如w a l m a r t 的全球总裁 关心的是全球的销售数据，对于数据精度的要求比较低，4 0 以内的误差都不会 影响其做出正确的决策。而其亚太地区经理只关心中国，日本，韩国，新加坡等 地区的销售情况，但是对数据精度的要求较高，2 0 以上的误差就会影响其决策 的可靠性。因此，如何为不同身份的分析人员定制数据传送策略，在不影响其使 用的基础上，通过对数据精度、探索范围的限制将总的数据量控制在一个合理的 范围内，是应对移动设备空间制约的关键。 g r a d u a lc u b e ：一个移动o l a p 系统 1 4 本文研究成果 第6 页 综上，移动联机分析处理领域的挑战主要来自于无线网络和移动设备两方 面。无线网络的限制主要在于其不稳定性和带宽限制。而移动设备的问题则主要 在于其本地计算和存储能力。对于移动o l a p i 而言，如何克服上述各方面的限制， 为用户带来迅速，平滑的多维分析体验是目前需要解决的问题。 1 4本文研究成果 针对上述问题，本文中提出了g r a d u a lc u b e ，一个移动联机分析的原型系 统。在服务器端，使用c o n t o u rc u b e 结构存储经过无损压缩的数据立方。传输过 程采用渐进式传输，按照事先生成的、为用户定制的传输计划所规定的传输顺序 和时机增量式地传送数据，逐步提高客户端的数据精度。在客户端，已传输的数 据独立构成一个压缩聚集以提供离线有界近似查询能力。同时，通过对数据精度 和探索范围的控制，能够保证数据的总传输量不会超过客户端的容量限制。 本文主要贡献如下： 第一，我们提出了一种单调聚集函数( 非负数s u m ，c o u n t ，m i n ，m a x 等) 下，基于等值线的数据立方存储结构c o n t o u rc u b e 。它由数据立方的所有的等值 线构成，是原数据立方的一种无损压缩表示。在服务器端存储c o n t o u rc u b e 从根 源上减少了所需传输的总数据量。c o n t o u rc u b e 结构支持增量式传输，每次从服 务器端传输c o n t o u rc u b e 的一部分到客户端形成s u bc o n t o u rc u b e 。客户端上 的s u bc o n t o u rc u b e 也是一个压缩聚集，可以视作是c o n t o u rc u b e 的有损压缩 结果。随着增量式传输的进行，客户端s u bc o n t o u rc u b e 的精度逐渐提高，甚至 可以达到完全精确的程度。在增量式传输的任意阶段，客户端上的s u bc o n t o u r c u b e 都可以提供完整数据立方上的有界近似查询，既回答查询的近似值，又提 供近似值的误差界限。这保证了在离线的情况下，用户依然可以在一定的误差界 限内继续分析。 第二，我们提出了为不同用户定制数据传输计划以指导数据传输的顺序和时 机。o l a p 的用户一般数量比较少并且角色固定，这使得定制传输计划不仅可能 而且必要。我们假定用户对于数据精度的要求满足一个概率分布函数。对于不同 的用户，我们生成不同的传输计划，使得实际所需传输数据的数学期望尽量小。 我们提出了随机，最优和启发式三种传输计划生成算法，最优算法着眼于在渐进 过程中使传输数据的数学期望最小，而启发式算法则考虑减少数据传输量的同 时尽快提高客户端的数据精度。我们通过一系列详尽的实验对这些算法进行了 比较，并对它们所生成传输计划的质量进行了评估。 第三，我们从数据精度和探索范围两方面来进行容量控制。在传输开始前， 就将移动设备端的数据量控制在可以接受的范围内。 g r a d u a lc u b e ：一个移动o l a p 系统 1 5 本文组织结构 第7 页 由于大多数移动设备( 如手机，s m a r tp h o n e 等) 受输入设备和显示界面的局 限无法进行很复杂的查询而多以浏览为主，因此，本文中假定用户只做点查询。 虽然我们的工作主要是针对移动联机分析处理，但实际上本文的方法也可 以用在传统的o l a p 实现中。c o n t o u rc u b e 结构与定制传输计划等技术在传统 的o l a p 应用中同样可以为用户节省存储空间，平滑响应时间。另外，由于本文 提出的方法对客户端要求不高，因此不仅可以用来支持基于c s 的应用，在没有 特别要求的情况下还可以用来支持基于b s 架构的应用。 1 5本文组织结构 以下是本文的组织结构。 第一章，即本章，首先介绍了问题的背景知识，其次说明了当前的研究状况 以及遇到的主要挑战，然后叙述了本文的研究工作内容，最后介绍了本文的章节 安排。 第二章主要列举了近期的一些相关工作。 第三章提出了等值线的概念，而后介绍了c o n t o u rc u b e 结构的性质并给出 了以事实表为输入生成c o n t o u rc u b e 结构的算法。 第四章给出了如何在给定误差界限的情况下，对c o n t o u rc u b e 结构进行进 一步的有损压缩。同时也介绍了怎样在有损压缩的结果上进行有界近似查询。 第五章主要关于渐进式传输。首先介绍了基于c o n t o u rc u b e 的渐进式传输 原理，其次明确了传输计划的定义以及为不同用户定制传输计划必要性，最后提 出了随机、最优和启发式的j 种传输计划生成算法。 第六章中我们介绍了如何通过对c o n t o u rc u b e 结构进行切片与切块来限制 用户的探索范围。 第七章为实验部分，通过详尽实验和分析，充分说明了我们方法的有效性。 第八章综合了前面几章的工作，简单介绍了g r a d u a lc u b e 的系统架构以及 服务器端和客户端各个模块的功能。 最后在第九章对全文进行了总结并提出了值得进一步研究的方向。 g r a d u a lc u b e ：一个移动o l a p 系统 2 1 数据立方的无损压缩 第8 页 第二章相关工作 主要有三类工作与本文的工作相关，它们分别是数据立方的无损压缩、渐进 式回答以及o l a p 在移动环境下的应用。 2 1数据立方的无损压缩 这类工作主要包括q c - t r e e 1 6 】，q u o t i e n tc u b e 1 7 ，c o n d e n s e dc u b e 2 s 】以 及d w a r f 3 0 等。这类方法着力于在从根本上缓解数据立方的计算、存储压力，它 们的目标都是去除数据立方的内在冗余，在压缩时不丢失任何信息，能够精确回 答任何查询。 c o n d e n s ec u b e 2 8 首先在这个领域进行了尝试。他们观察到，当数据立方 中的一组c e l l 对应事实表中的同一条元组时，只需存储这条元组( “b a s es i n g l e t u p l e ”) 就可以保留这组c e l l 的全部信息，所有的b s t 构成了元数据立方的一个 压缩表示( c o n d e s e dc u b e ) 。可见，b s t 可以在一定程度上抓住数据立方的内在 冗余。 顺着这条思路，q u o t i e n tc u b e 1 7 年l l d w a r f 3 0 分别尝试用不同的方法来去除 数据立方的冗余。 q u o t i e n tc u b e 根据各c e l l 在事实表中的投影将数据立方分割成不同的等价 类。由于同一个等价类中的c e l l 投影到事实表中所对应的元组相同，因此不管采 取什么操作这些c e l l 的度量值必然相同。q u o t i e n tc u b e 将这些等价类的上界和下 界作为代表元压缩存储在q c t a b l e 中，并通过这些代表元将所有等价类组织成 格结构。由于等价类格是原数据立方格的商格，因此q u o t i e n tc u b e 在压缩的同 时完整保留了上卷下钻语义。他们的后续工作q c 一皿e e f l 6 1 进一步解决了q u o t i e n t c u b e 中一些遗留问题。他们首先证明了只需存储所有等价类的上界就足够无损 表示数据立方；而后利用树状结构对这些上界进行索引，通过共享前缀进一步进 行压缩；最后在树状索引中加入t r e e - l i n k s 来维护等价类之间的上卷下钻语义。此 外，文中还提供了增量式批量更新数据立方的方法。 d w a r f 则通过前缀共享( p r e f i x - s h a r i n g ) 和后缀接合( s u f f i x - c o a l e s c i n g ) 在数 据立方上建立一个类树状索引，并利用这个索引来压缩数据和回答查询。前缀共 g r a d u a lc u b e ：一个移动o l a p 系统 2 2 渐进式回答第9 页 享的想法与q c t r e e 类似，后缀接合的想法则是基于如下观察：如果在数据立方 中存在函数依赖y z ，那么所有形如( z ，y ，z ) 和( ，z ) 的c e l l 的度量值相同，z 这 个相同的后缀只需要存储一次。由于前缀共享在数据密集时有效，而后缀接合在 数据稀疏时有效，因此d w a r f 在任何数据分布下都有很好的压缩效果。随后，他 们在2 0 0 4 年的后续工作【2 6 】中证明了他们的方法相对于事实表的规模近乎接近线 性。 2 2渐进式回答 这类工作主要包括q u a s i - c u b e 5 ，6 1 m r t 1 8 ，h i s t o g r a m 2 1 1 ，w a v e l e t s 2 7 等。 渐进式回答的方法最初是用来提高查询响应速度，通过增量式地传送数据来逐 渐提高回答的精度，但由于这类方法大多都采用了有损压缩技术，因此实际上他 们也能够大大减少传输的数据量。 w a v e l e t s ，h i s t o g r a m 和m r t 都是基于查询的渐进式方法。给出一个特定查 询，这些方法能够渐进地提高回答的精度。w a v e l e t s 和h i s t o g r a m 分别用小波和 直方图进行有损压缩，他们将误差控制在事实表上。对于粗粒度聚集查询，由 于投影元组集中的误差趋于相互抵消，使结果有较小的误差界限。m r t 基于类 1 m r - t r e e 的多维索引结构，树中不同层次的节点对应了不同粒度的区域划分。回 答查询时，从根到叶的一条路径对应了渐进的回答过程。这些方法的一个问题在 于他们对于单个查询无法给出明确的误差界限，这会大大影响用户对近似数据 的信任度。另一个问题在于，由于他们都是基于查询的渐进式方法，应用到移动 联机分析处理后，先前客户端存下的查询的结果无法用来回答新的查询。因此在 离线的情况下无法工作。 q u a s i - c u b e 是基于数据立方的渐进式方法。将事实表划分成若千块，利用 对数线性( 1 0 9 l i n e a r ) 模型估计其中比较密集块，同时将估计误差大于误差界限 的c e l l 作为例外点保存下来。分别在所有数据小方上构造上述模型和保存例外点， 可以保证对所有查询回答都在给定的误差界限内。这个方法对于单个查询，同样 无法提供准确的误差界限。 这类基于近似压缩的渐进式回答的方法，无法支持由模糊到完全精确的完 整渐进过程。当用户需要获取完全精确的数据时，往往无法满足用户的需求。另 外上述所有方法都没有考虑用户定制的问题，对于所有的用户都采用相同的传 输策略。 g r a d u a lc u b e ：一个移动o l a p 系统 2 3o l a p 在移动环境下的应用 第1 0 页 2 3 o l a p 在移动环境下的应用 目前，这方面的工作相对较少。主要有a c u z z o c r e a 的h a n d o l a p 4 】，a s m a n i a t i s 的m o b i l eo l a p 1 9 1 ，以及m a s h a r a f 的s e m a n t i cd e l i v e r y 2 5 am o b i l e o l a p 1 9 中首先描述了在移动设备上进行o l a p 计算的现状，而后罗列了移动 联机分析系统所需要的基本要求。文中主要强调了用户交互方面的问题，包括屏 幕大小，分辨率，输入设备以及多维到2 维的转换模型等，而对于数据传输方面少 有涉及。h a n d o l a p 则主要强调了移动设备在存储空间上的限制，它采用了中 间件( m i d d l ew a r e ) 技术，用户发出查询后，在首先在中间件中计算并生成2 维视 图，而后用与m r t 类似的q u a d t r e e 技术压缩后传输。这个方法拥有与m r t 相同 的问题，即无法提供误差界限且不能应用与离线情况。而s e m a n t i cd e l i v e r y 贝l j 考 虑了在无线环境下数据广播的共享问题，该文以数据小方为基本单位，主要讨论 了在数据广播的环境下，各个节点如何自主地对本地缓存进行调度的问题。 g r a d u a lc u b e ：一个移动o l a p 系统 3 1 等值线 第1 1 页 第三章 c o n t o u rc u b e 观察图1 1 ，我们可以发现( n 1 ，6 2 ，c 2 ) ，( 口1 ， ，c 1 ) ，( 眈，b l ， ) 和( ，b l ，c 1 ) 是数据 立方中一组有“魔力”的c e l l 集合。它们所有祖先( 包括自身) 的度量值都大于等 于5 ，而除此以外其他c e l l 的度量值都小于5 。我们将这4 个c e l l 所构成的集合称为 值为5 的等值线，简称为等值线5 。直观上，一条等值线将格图中所有c e l l 按度量值 划分为两个不同的区域；不同值的数条等值线将格图中的c e l l 按度量值切分成若 干层片，每个层片中c e l l 的取值都在同一区间内；而所有等值线则一同构成了完整 的数据立方。 等值线有一些非常好的性质。首先，将数据立方按照等值线进行层状划分 只是一种逻辑上的划分，实质上并没有损失任何信息。其次，由于等值线划分 所得的层片上所有c e l l 的度量值相同，因此实际存储时只需要记录下位于每个层 片“底部”的那些c e l l ，而层片中其它c e l l 可以通过格中的偏序关系获得。这样在 去除数据立方内部冗余的同时可以获得可观的压缩收益。最后，利用等值线提供 的数据立方层状视图能够方便地进行进一步压缩和渐进式传输。因此，本节中我 们设计了c o n t o u rc u b e 结构来有效地计算和存储数据立方中所有的等值线。 3 1 等值线 定义1 ( 等值线7 - ) 等值线7 - 是满足下面条件的最小c e l l 集合：v c ，c 或 者j 一且一是c 的后代 - 3 且仅当m ( c ) t 。其中c 是一个c e l l ，m ( c ) 是它的度量 值。在本文的剩余部分中，我们将不区分等值线r 和对应的c e l l 集合。 例1 图1 1 中，等值线1 8 包括1 4 - c e l l ：( ， ， ) 。等值线7 包括4 + c e l l ，分剐 为( o l ，6 2 ， ) ，( 0 2 ，6 1 ， ) ，( $ ，b l ，c 1 ) 和( ， ，c 2 ) 。 定义2 ( 等值线段) 中度量值在h ，见】p n 也) 内的c e l l 构成的子集称 为在h ，乃】上的等值线段，记做h ，o 】。特别地，称l 在p ，叫上的等值线段为 等值线段7 _ ，并称等值线段7 r 是所对应的等值线段。 例2 按上述定义，等值线段5 为( n 1 ，6 2 ，c 2 ) ，厶在区间【6 ，7 1 j ：的等值线段 为( 0 1 ， ，c 1 ) ，( a s ，b l ， ) 和( ，b 1 ，c 1 ) 。 g r a d u a lc u b e ：一个移动o l a p 系统 3 2 c o n t o u rc u b e 结构 第1 2 页 性质1 包含度量值为r 的c e l lc ( r r ) 当且仅当对于c 的所有后代中值 最大的c e l lc ，有m ( c ，) 7 ，根据定义l ，必然存在属 于上r 且d 是c 的祖先。由于c 是d 的祖先，由传递性c 也是c ，的祖先。因此，c 与d 同 属于l 且互为祖先后代关系，一 c ) 依然可以满足定义1 ，与l 最小矛盾。 必要性：反证。如果c 不属于，由于m ( c ) = 7 j2r ，由定义1 ，必然存在c 的后 代c ，属于。因此有m ( c ，) 2 ，_ ，与m ( c ，) r 相矛盾。 口 推论1 对于任意两务等值线k 和k h 死一) ，必有xcy 。其 中x 与y 分别是和k 上值为，的c e l l 构成的集合。 证明v c ，r e ( c ) = 一，c x 。由性质1 ，对于c 取值最大的后代一有m ( d 1 1 1 1 - 2 。同样根据性质1 ，有c 岛，即c y 。 口 推论2 上值为，一7 _ 7 ) 的c e l l 集合j 必然是等值线段f 7 的子集。 证明证：在推论l 中，令 r l = 7 - ，也= 7 - t 时直接可得。 口 推论3 数据立方中所有等值线包含的c e l l 集合等于它们对应的等值线段所 包含的c e l l 集合。 证明由定义2 ，v v ，等值线段f 是l 的子集，所以命题中后者是前者的子集。 下面我们只需要证明v 丁，也是所有等值线对应的等值线段集合的子集。将上 的c e l l 按照度量值分组，由推论2 知道，比，值为f 的组是矗对应的等值线段的子 集。因此，命题中前者也是后者的子集。 口 不难发现，等值线问经常重叠( 如厶和乃都包含( 2 ，b 1 ，+ ) ，( + ，b l ，e 1 ) ) 。这给 等值线的存储带来了一定的困难。如果简单地按顺序存储所有的等值线，必然会 导致某些c e l l 被重复存储。推论3 为我们提供了一个解决方法：由于所有等值线的 集合等价于它们对应的等值线段集合，而根据定义，不同等值线对应的等值线段 之间没有重叠，因此上述等值线段的集合是所有等值线的一个无冗余表示( 每 个c e l l 全多出现一次) ，要存储所有等值线只需计算并存储所有的它们对应的等值 线段便可。 3 2 c o n t o u rc u b e 结构 由上一节分析，我们知道只需要计算并存储所有等值线对应的等值线段。但 这又带来了另外一个问题：如果每条等值线实际只存储对应的等值线段，那么如 g r a d u a lc u b e ：一个移动o l a p 系统 3 2 c o n t o u