基于位图连接索引的复杂多维层次的连接和聚集算法

《基于位图连接索引的复杂多维层次的连接和聚集算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Feb.2007,Volume4,No.2(SerialNo.27)通讯和计算机JournalofCommunicationandComputer,ISSN1548-7709,USA基于位图连接索引的复杂多维层次的连接和聚集算法荀亚玲，张素兰（太原科技大学计算机学院，太原030024）摘要：在ROLAP中往往涉及到大量数据的复杂即席查询，从SQL角度看，这些查询通常都包含多表连接和分组聚集操作。本文提出了一种连接和聚集操作的新算法JAMDHBJI，该算法充分考虑了ROLAP中复杂多维层次的特点，同时考虑到并非全部维都具有维层次的语义特性，将维层次编码和位图连接

2、索引有效结合，把复杂的连接和分组聚集操作转化为在事实表上的区域查询，从而大大提高了连接和分组聚集的效率。理论分析表明该算法是高效的。关键词：ROLAP；多表连接；聚集查询；维层次编码；位图连接索引将查询开销非常大的多表连接转化为事实表上的1.引言范围查询。这两种方法只考虑了全部维的维属性均具有层次性的语义特性，而实际上在RLOAP查询OLAP是一种面向数据仓库的联机分析技术，中涉及到的维表，并不是所有的维表的维属性都具其主要功能是管理决策所需要的总结数据，满足用有层次性的语义特征。户的即席查询，及时向用户提供分析数据来辅助决本文从优化维表和事实表的连接和分组聚

3、集策，从而对查询的响应速度提出了更高的要求。[3]操作出发，在位图连接索引的基础上，提出了一OLAP查询主要分为MOLAP（Multi-dimensional种新的算法JAMDHBJI（JoinandAggregationofOLAP）和ROLAP（RelationalOLAP)两种实现方Multi-DimensionalHierarchiesbasedonBitmapJoin式。Index）。JAMDHBJI算法对维属性具有层次语义的近几年，人们在ROLAP方面开展了大量的研维表，通过维层次树创建的维层次编码来代替维表究工作，并且提出了若干技术来提高ROLA

4、P查询中的关键字，实现维关键字的压缩，通过这种比维[1-3]的响应速度，如新的索引技术、实物化视图技术表外关键字小得多的维层次编码来替代事实表中[4]等。在ROLAP中，通常都包含多表连接和分组的维表外键；对维不具有层次语义的维表则引入了聚集操作，提高这些操作的性能成为提高ROLAP位图连接索引。通过对两个或两个以上的位图连接查询响应速度的关键。文献[5]提出了聚集操作和多索引执行适当的AND或OR操作，获得各分组的[6]表连接算法Mjoin相结合的方法，该方法最主要位图；通过利用维层次属性的查询范围和位图中的的缺点是没有充分考虑维属性具有层次性的语义置1位快

5、速从事实表中检索出与检索关键字相匹配特性。文献[7]提出了一种基于星型模式的改进分组的记录，最后利用维层次相对编码前缀和不具有层聚集技术，但其混合代替键采用的是整数编码。在次语义维表的分组属性编码对已检索出的事实表此基础上，文献[8]提出了基于维层次编码的OLAP记录进行快速的预分组和聚集操作，从而大大减少聚集查询算法，用维层次编码来代替维表中的关键和简化了事实表与维表之间的多表连接，提高了字和事实表中的维表外键，实现维关键字的压缩，ROLAP的查询效率。图1为原始的星型模式结构，【作者简介】荀亚玲（1980－），女，硕士研究生；研究方向：数据仓库。张素兰，女

6、，硕士，副教授；研究方向：数据仓库，数据挖掘，人工智能及应用。10基于位图连接索引的复杂多维层次的连接和聚集算法图2为经过改进的星型模式结构。表示维成员dk和dl有层次依赖关系，即在维层次iiijProductIDl树中有边连接（d表示D维的第j层次的第l个属ijinameDateIDDateID性成员）。typedayProductID[8]idescription定义2维层次属性编码。设lj为维表DimonthRegionIDunitprice中的第j层属性集，其值域为yearoutputi12miincomeRegionIDdom(lj)={dij,di

7、j,…,dij}，则在维表的维层次lj各cityilj属性成员编码为B：provinceiareadoml()jk→<{b−10......bbii>∈b{0,1},i=0,...,-1}k。其图1星型模式中k为维D的维层次li中成员二进制编码位数,即ijik=⎡logl⎤=⎡⎢logm⎤⎥。ProductID⎢2j⎥2Name定义3维层次编码[8]。D维各成员的维层次iDateIDDateIDBtypeiii编码是由Di维中所有维层次属性（l1,l2,…,lh）编dayProductIDdescriptionmonthRegionIDunitprice码按层

8、次由高到低依次进行组合而成的混合编码，