资源描述：
《动态数据立方的范围查询》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第24卷第11期小型微型计算机系统Vol.24No.112003年11月MINI-MICROSYSTEMSNov.2003动态数据立方的范围查询李华,冯玉才,张志斌(华中科技大学计算机学院多媒体与数据库研究所,湖北武汉430074)摘要:根据datacube层次性的特点和查询习惯提出了新的分块计算方法,并在此基础上提出了改进算法.这种方法节约了存储空间,在LBD粒度及其上的查询效率为O(1),同时数据的更新时间大约为O(),还节约了大量的存储空间,并且使得数据立方具有了一定的结构独立性,能有效的减少重
2、新构造数据立方(reprocess)的次数,因而在时间上和效率上有较大的优势.关键词:范围查询(rangequery);联机分析处理;数据立方;数据独立性中图分类号:TP311.13文献标识码:A文章编号:1000-1220(2003)11-2020-04RangeQueriesTechnologyonDataCubesLIHua-yang,FENGYu-cai,ZHANGZhi-bin,(HuazhongUniversityofScience&Technology,Wuhan430074,China
3、)Abstract:Inthepaper,theauthorreviewsR.Agrawalandotherscholars'researchinthisrespect,introducestheiral-gorithms&presentsnewtwoalgorithmstodivideblocksaccordingtothecharacteristicofrangeorderofdatacube&querycustom.Thenewalgorithmpresentedinthepaperischar
4、acterizedwithsuchstrongpointsassavingspace,in-creasingefficiencyinthecircumstanceoflargegranularity&processingstructuralindependencewhichefficientlyre-ducesthetimeofreprocess.Keywords:rangequery;datacube;structuralindependence;OLAP1概述中以后,学术工作者进行了大量的研究,如
5、何计算数据立方、如何索引、如何预计算(precomputing)等.在算法中我们假定在一个决策支持系统中,通常决策支持人员关心的是范只对Summarize考虑,因为其他的求法被证明是一样的〔1〕.围查询(Rangequery),例如一个典型的范围查询可能为查询2.1已有的成果武汉市2001年7月份冰饮的销售值等.我们知道,数据立方现在假设一个数据立方(Datacube),它有d个维,且每查询和更新操作十分耗时,因此一般采用预先求和的计算方个维的长度分别为ni,这样,我们就需要一个长度为A=n1式来提高
6、查询的速度.如Hoetal〔3〕提出了前缀和算法,该算×n2×⋯×nd数组来存储这个数据立方中的数据.不妨设每法对于任意的范围查询都可以以常数的时间实现,但是更新个维的长度都相等,那么A=nd.的开销就变得非常的昂贵;Geffner〔1〕在前缀和算法基础上提对于这样的一个数据立方,如果不预先计算好数据立方出了相关前缀和算法,改善了更新操作的时间开销,使之达到中的数据,那么一个更新操作只需要影响到数据立方的一个d/2了O(n).数据,显然耗费的时间是O(1),然而在最坏的情况下查询的但是数据立方很难在刚
7、一开始时就建立得十分完善,随效率却是O(nd),因为数据立方中的每个数据都必须被加起着数据仓库的日益应用和公司业务的发展、变化,有可能需要来.因此对于更新操作非常多查询相对很少的数据立方来说修改数据立方的结构,但现有的一些数据立方算法基本不能这是个理想的方案,但是这是不符合实际情况的.适应这一要求.这些算法都不能适应数据立方结构的动态变2.1.1前缀和算法(prefixsummethod)化,重构就难以避免,而且空间消耗极大.本文就是在他们工为了改善查询的性能,Hoetal.〔3〕提出了一个非常优秀作
8、的基础之上针对数据立方的层次性和可能的结构的动态更的算法,叫做前缀和算法.他引入了一个和数组A有同样大新提出了自己的分块处理方法和改进算法.小的数组P,其中P中每个以(x1,x2,...,xd)为索引的元素都包含它前面所有元素和它自己的和.因此这个算法需要预先2本文的工作计算,forall0xi
