48 东南大学学报 ( 自然科学版 ) 第 36 卷次聚集 Cube 的并行创建和增量更新维护. 1 分段 Cube 为了便于说明, 本文使用某企业销售数据仓库中的产品销售记录, 基表包括 3 个维 : 产品维 ( 大类名, 类名, 产品名 ) 地区维 ( 国名, 省名, 市名 ) 时间维 ( 年

Size: px

Start display at page:

Download "48 东南大学学报 ( 自然科学版 ) 第 36 卷次聚集 Cube 的并行创建和增量更新维护. 1 分段 Cube 为了便于说明, 本文使用某企业销售数据仓库中的产品销售记录, 基表包括 3 个维 : 产品维 ( 大类名, 类名, 产品名 ) 地区维 ( 国名, 省名, 市名 ) 时间维 ( 年"

父祝
5 years ago
Views:

1 第 36 卷第 1 期 2006 年 1 月东南大学学报 ( 自然科学版 ) JOURNAL OF SOUTHEAST UNIVERSITY(NaturalScienceEdition) Vol 36 No 1 Jan.2006 高维层次聚集 Cube 并行创建与存储方法胡孔法陈肞李斌 ( 扬州大学计算机科学与工程系, 扬州 ) 摘要 : 提出一种将高维层次聚集 Cube 划分成若干个低维立方体 Mini Cube 的并行创建与存储方法, 利用并行处理技术来创建这些分割的分段共享 Mini Cube 及其聚集 Cuboids, 实现高维层次聚集 Cube 的并行创建和增量更新维护, 从而解决高维 OLAP 聚集海量数据的存储与查询问题. 理论分析与实验结果都表明, 相对于以往的 FulCube 完全创建和 PartialCube 部分创建等传统方法, 基于分段 Mini Cube 并行处理方法的性能有显著的提高. 关键词 : 高维层次聚集 Cube; 分段 Mini Cube; 并行处理中图分类号 :TP311 文献标识码 :A 文章编号 : (2006) Improvedmethodofparalelconstructionandstorage forhigh dimensionalhierarchyaggregatecube HuKongfa ChenLing Liin (DepartmentofComputerScienceandEngineering,YangzhouUniversity,Yangzhou225009,China) Abstract:A novelapproachtopartitionthehigh dimensionalhierarchyaggregatecubeintosome low dimensionalshelsegmentmini Cubesisproposed.OLAP(onlineanalysisproces)queriesare computedonlinebydynamicalyconstructingcuboidsfrom theseshelsegmentmini Cubesthrough theparalelprocesingtechnology.withthisdesign,forhigh dimensionalolap,thetotalspace thatneedsto storesuch shelsegmentmini Cubesisnegligiblein comparison with ahigh dimensionalhierarchycube.comparisonbetweenthemethodsofshelmini Cubeandotherexisted onessuch asfulcube and partialcube wasconducted experimentaly. The analyticaland experimentalresultsshowthatthealgorithmsofsegmentmini Cubesproposedinthispaperaremore eficientthantheotherexistedones. Keywords:high dimensionalhierarchyaggregatecube;segmentmini Cube;paralelproces 联机分析处理 (OLAP) 是当前数据库应用和决策支持系统 (DSS) 的研究热点.OLAP 往往需在海量数据上进行 adhoc 的复杂聚集查询, 并要求及时向用户提供分析数据来辅助决策. 这就对查询响应速度提出了很高的要求, 使得提高 OLAP 查询和分析操作效率成为数据仓库应用中的关键问题 [1].OLAP 需要在超大规模的数据仓库上执行复杂的查询, 而查询响应时间必须满足交互环境的需要. 为了解决这个问题, 除了传统的查询优化和索收稿日期 : 基金项目 : 国家自然科学基金资助项目 ( ) 国家十五重大科技攻关资助项目 (2003A614A) 江苏省自然科学基金资助项目 (K ,K ,K ). 作者简介 : 胡孔法 (1970 ), 男, 博士, 副教授, 硕士生导师,kfhu@ yzu.edu.cn. [2,3] 引技术以外, 人们又引入了视图实例化 Cube, 一个 d 维的 datacube 可以生成 2 d 个聚集 Cuboids 和 d +1) 个聚集数据单元. 因此, 在实际应用中,Cube 中的元组个数往往是基表 (baseta ble) 的几百倍或几千倍, 要占用 G 甚至是 P 级的存储空间, 花费很长的计算和维护时间. 即使采用 IcebergCube [4],CondensedCube [5],Dwarf [6,7] 等 Cube 压缩技术, 都不能从根本解决高维层次聚集 Cube 的存储问题. 本文提出通过共享分段立方体 Mini Cube 技术, 将高维层次聚集 Cube 划分成若干个低维立方体 Mini Cube, 利用并行处理技术来创建这些分割的共享立方体 Mini Cube 及其聚集 Cuboids, 实现高维层

2 48 东南大学学报 ( 自然科学版 ) 第 36 卷次聚集 Cube 的并行创建和增量更新维护. 1 分段 Cube 为了便于说明, 本文使用某企业销售数据仓库中的产品销售记录, 基表包括 3 个维 : 产品维 ( 大类名, 类名, 产品名 ) 地区维 ( 国名, 省名, 市名 ) 时间维 ( 年, 月, 日 ) 和一个度量属性销售额. 基表的一个实例如表 1 所示. 记录表 1 产品销售数据基表为了提高 OLAP 查询效率, 通常将基表的数据进行预聚集计算并保存, 因此在基表所对应的多维数据集 Cuboids 中, 不仅要存储基表中的数据, 而且还要存储聚集数据. 基表 1 所对应的多维数据集单元格如表 2 所示, 其中表示 Al, 即可以匹配所在维层次值域中的任何值, 假设聚集函数为 Sum 和 Count. 产品维地区维时间维大类名类名产品名国名省名市名年月日销售额 / 万元 1 办公用品计算机类计算机中国江苏南京办公用品计算机类计算机中国江苏南京办公用品计算机类计算机中国江苏扬州办公用品计算机类计算机中国江苏扬州表 2 基表 1 对应的聚集数据 Cuboids 产品维地区维时间维度量大类名类名产品名国名省名市名年月日销售额 / 万元记录数办公用品计算机类计算机中国江苏南京办公用品计算机类计算机中国江苏南京办公用品计算机类计算机中国江苏扬州办公用品计算机类计算机中国江苏扬州办公用品计算机类计算机中国江苏南京 ,2 办公用品计算机类计算机中国江苏扬州 ,4 办公用品计算机类计算机中国江苏 ,2,3, ,2,3,4 定理 1 对于一个 d 维 (D 1,D 2,,D d ) 的 Cube 可以产生 2 d 个聚集 Cuboids 和 d +1) 个聚集数据单元, 其中 D i 为维 D i 中的不同属性值的取值个数. 证明对于上述的 P 维中, 由其生成的聚集 Cuboids 只取 P 或 Al, 即从 {P,Al}2 个值中选取, 不失一般性, 对于任何一个维都只会从它自身或 Al 的 2 个值中选取, 故可以产生 d 2=2 d 个聚集 Cuboids. 对于维 D i, 聚集 Cube 中各个聚集数据单元在该维属性上的可能取值为该维的不同属性值的取值个数加上一个值 ( 表示 Al 聚集值 ), 即 D i + 1. 则由这 d 个维 (D 1,D 2,,D d ) 的 Cube 生成的聚集 Cube 中共有的聚集数据单元个数为这 d 个维 (D 1,D 2,,D d ) 中的各个维属性上的可能取值个数的乘积, 即 d +1). 定理 2 对于 d 个维 (D 1,,D i,,d d ), 每个维 D i 有 h i 个维层次 (L 1,L i 2,,L i i h) 的 Cube 来说, 可以产生 d (h i + 1) 个聚集 Cuboids 和 d h i j=1 ( L i j +1) 个聚集数据单元. 其中,h i 为维 D i 的维层次数,L i 表示维 D j i 的第 j 层次不同取值的集合. 证明与定理 1 类似, 略. 例 1 表 1 中的原始数据立方体 PRT 由产品维地区维时间维 3 个维组成 ( 简称 P,R,T), 由其可以产生 8 个聚集 Cuboids:{(P,R,T),(P,R, Al),(P,Al,T),(Al,R,T),(P,Al,Al),(Al, R,Al),(Al,Al,T),(Al,Al,Al)}. 产品维有 1 个不同的属性值 {1}, 地区维有 2 个不同的属性值 {1,2}, 时间维有 3 个不同的属性值 {1,2,3}, 由其生成的聚集 Cube 有 (1+1) (2+1) (3+1)= 24 个聚集数据单元. 对于由表 1 生成的数据立方体 PRT, 其 3 个维及其维层次为产品维 ( 大类名, 类名, 产品名 ) 地区维 ( 国名, 省名, 市名 ) 时间维 ( 年, 月, 日 ), 它可以产生 d (h i +1)=(3+1) (3+1) (3+1)=64

3 第 1 期胡孔法, 等 : 高维层次聚集 Cube 并行创建与存储方法 49 个聚集 Cuboids, 分别为 {( 产品名, 市名, 日 ),( 产品名, 市名, 月 ),( 产品名, 市名, 年 ),( 产品名, 市名, Al),( 产品名, 省名, 日 ),,(Al,Al,Al)}. 定义 1( 分段 Cube) 对于一个 m 维的高维层次聚集 Cube(D,M), 每次分别从维集合 {D 1,D 2,,D m } 中选择 f 个不同维来组合成低维 Cube, 按照互不相交的原则将这 m 个维的高维层次聚集 Cube 分割成 k 个低维 Cube, 这 k 个分割而成的低维 Cube 就称为分段 Mini Cube. 从而对这个高维层次聚集 Cube 进行创建和存储可转化为这 k 个低维分段 Mini Cube 进行并行创建和存储. 通过共享这 k 个分段 Mini Cube 来实现高维层次聚集 Cube 的创建和存储. 例 2 对于一个 30 个维 (D 1,D 2,,D 30 ) 的高维层次聚集 Cube, 每次从中选择 3 个维, 将高维层次聚集 Cube(D 1,D 2,,D 30 ) 分割成 10 个互不相交的低维分段 Mini Cube:C 1 (D 1,D 2,D 3 ),C 2 (D 4, D 5,D 6 ),,C 10 (D 28,D 29,D 30 ), 对于每个低维分段 Mini Cube 可以利用它们 Latice 来创建它们各自的聚集 Cuboids. 对于 C 1 (D 1,D 2,D 3 ) 分段 Mini Cube 可以创建 8 个聚集 Cuboids:{(D 1,D 2, D 3 ),(D 1,D 2,Al),(D 1,Al,D 3 ),(Al,D 2,D 3 ), (D 1,Al,Al), (Al,D 2,Al), (Al,Al,D 3 ), (Al,Al,Al)}. 这里只会产生 =80 个聚集 Cuboids, 这比前面的创建整个聚集 Cube 方法中产生的个聚集 Cuboids 要少得多, 比选择 3 个维的 PartialCube 部分创建方法中产生的 C C C 1 30 =4525 个聚集 Cuboids 也要少. 2 高维层次聚集 Cube 存储结构 2 1 高维层次聚集 Cube 分割存储对于一个高维层次聚集 Cube, 采用以往传统 Cube 的存储方法是很难解决其高维聚集数据的存储问题, 一个可行的解决方案是将高维层次聚集 Cube 进行有效的分割, 来进行分布式存储. 本文考虑通过共享分段立方体 Mini Cube 技术, 将高维层次聚集 Cube 划分成 k 个低维立方体 Mini Cube, 并将这 k 个低维 Mini Cube 分配到并行处理系统的 k 个处理结点进行聚集处理, 来创建各个分段 Mini Cube 的聚集 Cuboids. 对于每个分段 Mini Cube 的聚集 Cuboids 创建仍采用立方体 Latice 进行聚集计算 [6], 从而实现高维层次聚集 Cube 的并行创建和增量更新维护. 高维层次聚集 Cube 分割成 Mini Cube 及其聚集 Cuboids 创建的并行处理体系结构如图 1 所示. 图 1 共享分段 Mini Cube 及其聚集 Cuboids 创建的并行处理结构为了提高数据的检索速度, 可以按文献 [8] 中的方法为 Cube 中的各个维创建压缩性能强且具有层次语义特性的维层次编码. 例如上述企业销售数据仓库中的时间维的各个维层次编码表见表 3. 在建立聚集 Cube 的同时, 建立各个维的维层次编码表, 例如表 1 中的地区维和产品维的维层次编码表分别如表 4 和表 5 所示. 通过这些维层次编表 3 时间维的维层次编码表年维层次编码表月维层次编码表日维层次编码表时间维维层次编码表年 y 月 m 日 d 时间 ID 时间 ID 时间码与各个记录的 TID 进行关联, 加快聚集 Cube 中的数据检索速度. 表 1 中地区维产品维和时间维 3 个维中各维成员的维层次编码与基表中各个记录 TID 的关联关系分别如表 6~ 表 8 所示. 考虑存储空间和检索效率, 将基表 1 的度量用一个多维数组 (TID measurearay) 来存储, 如表 9 所示. 表 4 地区维的维层次编码表国名省名市名 uuuuuuu vvvvv cccc uuuuuuuvvvvvcccc 1 中国江苏南京中国江苏扬州

4 50 东南大学学报 ( 自然科学版 ) 第 36 卷表 5 产品维的维层次编码表产品 ID 产品 ID 大类名类名产品名 gggg aaaaa ppppppp ggggaaaaappppppp 1 办公用品计算机类计算机表 6 产品维 TID 关联表产品 ID 表 7 地区维 TID 关联表表 8 时间维 TID 关联表时间 ID TIDList 表 9 表 1 中的 TID measure 数组 TID 销售额 / 万元可以充分利用维层次编码具有前缀层次语义特性, 来求得各个维的相应维层次属性的维层次编码及其 TID 关联关系. 具体算法参见文献 [8]. 上述事例中的时间维的月层次和地区维的省名层次的维层次编码及其 TID 关联关系如表 10 和表 11 所示. 表 10 月层次的维层次编码前缀及其 TID 关联表时间 ID 时间 prefix( ID, 月 ) 表 11 省名层次的维层次编码前缀及其 TID 关联表地区 prefix( ID, 省名 ) 通过 Cube 的 Latice 由底向上 (botom up) [6] 计算方式, 对各个维的进行交运算, 来求得各个聚集 Cuboids. 例如计算单元 { , , }, 可以产品在中对 ID 地区 = , ID = 时间和 prefix( ID, 月 )= 进行交运算得到新的聚集 Cuboids 的 {1,2} 及其销售量为 100. 基于共享分段 Mini Cube 的高维层次聚集 Cube 并行创建算法如算法 1(shelsegmentmini cubeparalelconstruction) 所示. 算法 1 {partitionthesetofdimensions:(d 1 ; ;D d )intoasetofk Mini Cubefragments{P 1 ; ;P k }; scanbasecuboidc(d 1 ; ;D d )onceanddothefolowing withparalelprocesing {inserteach tid,measure intoid measurearay; ;} foreachatributevaluea i ofeachdimensiond i ; buildandimensionhierarchyencodingindexentry: ; paralelprocesingalfragmentpartitionp i asfolows {buildalocalfragmentmini cubesc i byintersecting theircorespondingtid listsandcomputingtheirmeasures; buildc i saggregatecuboidsbythecuboidlatice;}} 在数据仓库中通常要进行元组的插入和删除, 以及维及其层次的增加和删除模式更新等数据更新问题. 在以往的 Cube 中, 模式更新的过程则需要重新构建 Cube. 尤其是在插入新维及其维成员数据单元时, 以往传统 Cube 是不能进行增量更新, 只得重新构建 Cube. 如果对高维层次聚集 Cube 进行更新时, 则采用传统 Cube 更新方法的代价非常昂贵. 但在本文提出的基于共享分段 Mini Cube 的高维层次聚集 Cube 存储结构中, 不需要重新构建 Cube, 只需在多维 TID measure 数组中插入或删除元组的 TID,measure. 在相应分段 Mini Cube 中, 插入或删除其相应的维层次编码及其 TID, 即可实现高维层次聚集 Cube 的增量更新. 2 2 高维 OLAP 聚集查询在对高维层次聚集 Cube 进行 OLAP 聚集查询时, 要充分利用各个维的维层次编码位图索引, 选择并行分布式系统中相应结点上的共享立方体 Mini Cube 存储数据块 Chunk, 来进行语义层次聚类查询, 以完成用户提交的高维 OLAP 查询. 其算法见算法 2(high dimensionalolapqueryalgo rithm). 算法 2 {ComputethebitmapencodingQ 1,, n,m ofthequery Q a 1,,a n,m ; LocaltheshelMini CubeC i throughthedimensionatributein thequeryq 1,, n,m foreachc i {ComputealdimensionD i withc i { 1,, n }bycompa ringthec i andq 1,, n,m incuboidlatice; ComputetheofalcelinthesedimensionD i withc i

5 第 1 期胡孔法, 等 : 高维层次聚集 Cube 并行创建与存储方法 51 { 1,, n };} ComputetheoftheOLAPquerieswiththesesby intersectingthetid listsinthedimensionanditshierarchiesinthecu boidlatice; SelecttheTID tuplesandmeasuresfrom ID measuresarayby thetidinthesoftheolapqueries; ComputetheaggregateofthoseclusteredTID tuplesmeasures, andsubmitthisaggregatetotheolapuser;} 3 算法性能分析对于一个含有 T 条记录和 d 个维的高维层次聚集 Cube, 如果采用基于分段长度为 f 的共享 Mini Cube 方法, 则 d 个维的高维层次聚集 Cube 划分成 d/f 个 Mini Cube, 每个共享分段 Mini Cube 会产生 2 f 个聚集 Cuboids, 则共产生 2 f d/f 个聚集 Cuboids, 需要 O( T2 f d/f ) 存储空间. 基于 Mini Cube 和传统 PartialCube 等不同高维层次聚集 Cube 创建方法的创建聚集 Cu boids 个数和所需存储空间如表 12 所示. 基于分段 Mini Cube 与 PartialCube 部分创建等传统方法的存储性能比较如图 2 和图 3 所示. 表 12 不同高维层次聚集 Cube 创建方法的存储性能比较 Cube Cuboids Storage Mini Cube 2 f d/f O( T2 f d/f ) PartialCube f C i d O( T f C i d) FulCube 2 d O( T 2 d ) 图 2 聚集 Cuboids 个数比较图 3 存储性能比较表 12 图 2 和图 3 表明, 基于分段 Mini Cube 的高维层次聚集 Cube 并行创建要比传统的 Ful Cube 完全创建和 PartialCube 部分创建等传统方法的存储性能要有优势得多, 解决了高维层次聚集 Cube 的分布式存储问题. 4 结语提出了一种将高维层次聚集 Cube 划分成若干个低维 Mini Cube 的并行处理方法, 利用并行处理技术来创建这些分割的分段共享 Mini Cube 及其聚集 Cuboids, 以解决高维 OLAP 聚集海量数据的存储与查询问题. 理论分析与实验结果都表明, 相对于以往的 PartialCube 部分创建等传统方法, 基于分段 Mini Cube 并行处理方法的性能有显著的提高. 从而有效地解决了高维 OLAP 聚集数据的存储问题. 参考文献 (References) [1] ChaudhuriU,DayalU.DatawarehousingandOLAP fordecisionsupport[j].acm SIGMODRecord,1997, 26(2): [2]StockingerK.itmapindicesforspeedinguphigh di mensionaldataanalysis[c]//proceedingsofthe13th Int lconfondexa.heidelberg:springer,2002: [3] WuK,KoeglerW,ChenJ,etal.Usingbitmapindexfor interactiveexplorationoflargedatasets[c]//proceedings ofthe15thinternationalconferenceonscientificandsta tisticaldatabasemanagement.losalamitos:ieeecom putersocietypres,2003: [4] XinD,HanJ,LiX,etal.Star cubing:computingice bergcubesbytop downandbotom upintegration[c]// The29thInt lconfonvld.sanfransisco:morgan KaufmannPublishers,2003: [5] WangW,LuHJ,FengJL,etal.CondensedCube: anefectiveapproachtoreducingdatacubesize[c]// Procofthe18thInternationalConferenceonDataEngi neering.losalamitos:ieeecomputersocietypres, 2002: [6] SismanisY,DeligiannakisA,RousopoulosN,etal. Dwarf:shrinkingthePetaCube[C]//ProcoftheACM SIGMODInternationalConferenceonManagementofDa ta.newyork:acm Pres,2002: [7]SismanisY,DeligiannakisA,KotidisY,etal.Hierar chicaldwarfsfortherolupcube[c]//the30thint l ConfonVLD.SanFransisco:MorganKaufmannPub lishers,2004: [8] 胡孔法, 董逸生, 徐立臻, 等. 一种基于维层次编码的 OLAP 聚集查询算法 [J]. 计算机研究与发展,2004, 41(4): HuKongfa,DongYisheng,XuLizhen,etal.Anovel aggregationalgorithm foronlineanalyticalprocesing queriesevaluationbasedonthedimensionhierarchical encoding[j].journalofcomputerresearchandde velopment,2004,41(4): (inChinese)

7 北京大学学报医学版 # +94* 4 ' % 论著!! "# $ #% %"&!%'!! $ "( )& * $ +,-.)/ ) 01 " * ). " 2")3 )01 ( /" 433% /1 " 0 "51 " -.)/$ 6',)") 4.))%) 0

7 北京大学学报医学版 # +94* 4 ' % 论著!! # $ #% %&!%'!! $ ( )& * $ +,-.)/ ) 01 * ). 2)3 )01 ( / 433% /1 0 51 -.)/$ 6',)) 4.))%) 0 论著!! "# $ #% %"&!%'!! $ "( )& * $ +,-.)/ ) 01 " * ). " 2")3 )01 ( /" 433% /1 " 0 "51 " -.)/$ 6',)") 4.))%) 0 ".. " - 23 )"." ( ).)") 4. " ' $ 7 " #$%"$8 &' + +." 0"3 / 3 3( 0 ) %.% "(% 2). +.) ")( ) (