（计算机应用技术专业论文）数据仓库环境中近似查询处理技术研究.pdf

：苎里一 摘要 f 在数据仓库上的许多决策支持应用需要在大数据量上进行复杂的查询，由于大数据 量凶及查询的复杂性使得一个查询的执行通常需要很长时间，显然不能满足用户的需 求，有时为了提高系统的响应时间，用户可以容忍一些查询结果的精度，因此近似查询 处理技术成为有效解决这一问题的方法。 数据仓库环境中的许多应用模式都对近似查询技术提出需求。例如，我们在做0 l a p 分析时，在一个钻取( d r 讣d o w n ) 查询序列中，最初查询的目的就是为了决定我们真正 感兴趣的数据，给这些查询提供快速、近似的查询结果可以使用户尽快找到有用的数据。 在数据仓库上的许多决策支持应用中的查询目的着重于分析数据间的关联关系或发展 趋势，有时在做聚集集查询时，对查询结果的要求并不需要精确到小数点。，卅一 本文主要研究在数据仓库环境中的近似查询处理技术，根据数据仓库中数据和 o l a p 查询的特点，提出了基于聚类技术的近似查询处理方法( c l u s t e r _ b a s e d a p p r o x i r r 斌e 0 u e r yp r o c e s s i n gm e m o d ，简记为c a q p ) ，其主要思想是对数据仓库中数据方体的数据 进行分块，每块数据相当于多维空间中的一个点，采用聚类技术对数据方体中的这些数 据块聚类，对于每个c l u s t e r ，使用其中心点的值代表其中所有的数据块，对数据方体进 行压缩，f 以后的查询操作则直接在压缩的数据结构上进行，减少查询处理时的l o 开销， 从而提高查询性能。 本文首先对聚类技术进行了深入的研究，提出了基于方格和密度的新聚类算法 s c a r g 忙的基本思想是把整个数据空间划分成矩形区域，如果个区域的密度大于 一个阀值，则该区域是一个密集区域，把所有相关联的密集区域连接起来，构成一个 c l u s t e r 。本文采用移动中心点的技术，对聚类结果进一步细化，提高聚类的精度。s c a r g 算法兼具了基于方格算法的处理速度和基于密度方法处理任意形状c l u s t e r 的能力。本文 还通过人工合成数据和b e n c i l i l l a r k 数据进行实验，与其它著名的聚类算法( d b s c a n ， c l a r a n s ) 对比，验证了s c a r - g 算法的有效性和性能。同时，本文还给出了s c a r g 算法的并行版本p s c a r g ，该算法充分利用硬件资源，进一步提高了对海量数据的处理 能力。a 一一 本文在深入研究了聚类技术的基础上，又对基于聚类的近似查询处理的关键技术进 行研罗谢即对于数据仓库中的数据，如何采用聚类技术进行近似查询处理，主要包括数 据的预处理、聚类的分层计算以及数据的增量维护算法等。针对数据仓库上的常用操作， 本文设计了数据的存储结构，给出了在数据方体压缩结构上进行查询处理的算法，并给 出了对查询结果集置信区间的估算方法，并通过实验与抽样技术对比，说明了c a o p 方 法的有效性和可扩展性。、，一 本文对近似扩展数据方体技术进行了研究。妊似扩展数据方体是由2 n - 1 个子方体组 l l 成，本文给出了从基本方体的压缩结构分块计算近似扩展数据方体中所有子方体的算 法a 对于扩展数据方体中的所有子方体都实体化，会占用很多存储空间，如果只存储基 本方体，则不能保证查询的精度，因此，本文对近似扩展数据方体的配置问题进行研究， 并证明了该问题是一个n p 完全问题，同时设计了一个启发式算法找出近似的最优配置。 最后简要介绍了近似扩展方体的维护和查询优化方法。 一，一 关键词：缈库，誓塑! 塑处理，寒拳分析，塑堡立体，塑塑堡缉 i i r e s e a r c ho na p p r o x i m a t eq u e r y p r o c e s s i n gt e c h n i q u e s i nt h e d a t a w a r e h o u s e f e n gy u ( c o m p u t e ra p p l i c a t i o nt e c t l i l o l o g y ) d i r e c t e db yw a n gs h a n t o d a y sd e c i s i o ns u p p o ns y s t e ma p p l i c a t i o n sn e e dp o s ev e r yc o m p l e xq u e r i e st 0 d a 上a w a r e h o u s e t h eh u g e 踟o u n t so f d a t aa 1 1 dt 1 1 ec o i n p l e x i t yo fm eq u e 巧m a k em eq u e 巧t ot a l 【e av e r yl o n gt i m et oe x e c u t ea j l dp r o d u c ee x a c ta n s w e r s d u et ot h ee x p l o r a t o d r n a t u r eo f m a n y d s s a p p l i c a t i o i l s ，t h e yc a n t o l e r a t es m a l le n o r si nq u e r yr e s u l t si nr e t u r nf o ri a 唱er e d u c t i o n s i nr e s p o i l s et i i n e s s o 印p r o x i m a t eq u e r yp r o c e s s i n gh a sr e c e n t l yc m e r g c d a sav i s i b i es o l u t i o n f o rd e a l i n gw i m h u g e 锄o u n 协o f d a 诅a n d 也eh i g h q u e r y c o m p l e x 咄 t h e r ea r can u m b e ro fs c e 删o si nw h i c ha ne x a c ta n s w c rm a y n o tb et e q u i r e d ，a 1 1 da u s e rm a yi nf a c tp r e f e raf a s t ，印p r o x i m a t ea 1 1 s w e lf o re x 锄p l e ，d u r i n gad r i l l d o w nq u e r y s e q u e n c e i na d h o cd a t am i n i n g ，i n j t i a iq u e r i e si nt h es e q u e n c e 疗- e q u e n t l yh a v et l l e s o l e p u r p o s e o f d e t e 珊i i l i n g t i l e t m l yi n t e r e s t i n gq u e r i e s a n d r e g i o n s o fm ed a t a b a s e p r o v i d i n 甙r e a s o n a b l y8 c c u 伯把) 印p r o x i m a t ea n s w e r st o m e s ei 枷a lq u e 啦sg i v e su s e r sm e a b i l i t y t of o c t l sm e i re x p l o m t i o n sq u i c l ( 1 ya l l de 吼c t i v e l y w i t h o u tc o n s u m i n gi n o r d i n a t e a m o u n t so fv a l u a b l es y s t e mr e s o u r c e s m a n ya g g r e g a t eq u e r i e sn e e dn o tt h ep r e c i s i o nt ol a s t d e c i m a l i nt l l i s d i s s e r t a t i o n ，w e d e a l 谢mt 1 1 e 印p m x i m a t e q u e r yp r o c e s s i n g i nd a t a 、v a r e h o u s ea i l d p r o p o s e ac l u s t e 卜b a s e d a p p m x i m a t eq u e r yp r o c e s s i n gm e t l l o d ( e a q p ) a c c o r d i n g t 0 也ec h a r a c t e ro f d a t ai i lt h ed a t a w a r e h o u s e t h i sd i s s e 嘣i o n 丘r s td e a l sd e e p l yw i 也t h ec l u s t e r i n gt e c h n i m l e sa n dp u t sf o r w a r dan e w d e n s i t y 七a s e d 觚d 鲥d _ b a s e dc l u s t e r i n ga l g o r i t h m s c a r g t h em a i ni d e ao fs c a r gi sm a t i td i v i d e st h ed a t as p a c ei n t om a n y r e c t a r l g l ec e l l s ，i ft h ed e n s i t yo f ac e l li sg r e a t e rm a na t h r c s h o l d t h e nt t l i sa r e ai sad e n s ec e l l a l lt 1 1 ec o r u l e c t e dc e l l sc o n s t i t l i t eac l u s t e ls c a r g f i n d sp r i m a r y p o r t i o n so fe v e r yc l u s t e rv e r yf 酤ta i l dt l l e nu s e sr e f i n e m e n tt e c l l i l i q u e st ob u i l d g o o dc l u s t e r s ，w ba l s os h o wt h er e s u l t so f o u re x p e r i m e m so nb o m s y n t h e t i cd a t aa n dr e a l d a t ao fs e q u o i a2 0 0 0b e n c h i n a r kw h i c hv a l i d a t em ee 仃e c t i v c n e s sa n dp e 怕啪a i l c eo f s c a r 0c o m p a r e d 、v i mo m e r 加n o u sc l u s t e r i n g a l g o r i t h m s ( d b s c a n ，c l a r a n s ) t o i m p r o v e t h e s c a l a b i l i t y ，w e a i s o p r e s e mp s c a r g ( p a r a l l e ls c a r g )b a s e d o nd a t a p a n i t i o n i n g i 垒! 塑生一 1 1 1 i sd i s s e 删i o nn r s tp m p o s e s t h e a p p r o x i m a t eq u e r yp m c e s s i n g m e t h o d 、】l ，h i c h c o m p r e s st h ed a t ac u b eu s i n gc l u s t e r i n gb yd i v i d i n gm e d a t ac u b ei n t oc h u r 出s ，t l eq u e “e s a r ea p p i i e dd i r e c t l yo v e rt h ec o m p r e s s e dd a 协c u b et oo b t a i n 协ta i l da c c u r a t ea p p r o x i m a t e q u e r y a n s w e r s t h i sd i s s e r t a t i o nd i s c u s s e st h ek e yt e c h n i q u e so fa p p r o x i m a t eq u e r yp r o c e s s i n gb a s e d0 n c l u s t e r w h i c hi n c l u d ed a t ap r e p r o c e s s i n gm e t h o d ，h i e r a r c h i c a lc l u s t e r i n ga i g o r i m m s t oe n s u f e t l l ee r r o r b o 岫da 1 1 di m p r o v et h ee m c i e n c yo fc l u s t e r i n ga n dt h ed a t ai n c r e m e n t a lm a i n t e n a n c e a j le x t e n s i v ee x p e “m e n t a ls t u d yw i m0 l a pc o u n c i lb e n c h m a r ks h o w st h ee f f 毫c l i v e n e s sa i l d s c a l a b i l i t y o fo i l r c l u s t c r b a s e d 印p r o a c hc o m p a r e d t o s a m p l i n g t h i s d i s s e r t a t i o na l s o p r o p o s e st h ea l g o r i t l l m sf o r i h e0 l a pq u e r i e s a 1 1 dp r o v i d e st 1 1 ec o n f i d e n c ei n t e n ，a l so f q u e r y r e s u l t s a ne x t e n d e d a p p r o x i m a t e d a 土ac u b ei sc o n s i s t i n go f2 “一ls u b d a c a c u b e s t h i sd i s s e r t a t i o n p r e s e r 她t h ea l g o r i 协mo fc o m p u t m ga l l t h eo t h e rd a t a c u b e sf r o mc o m p r e s s e db a s e c u b e m a t 酣a l i z i l l g a l lt l l es u b c u b e s 、i l l o c c u p y t o om u c h s t o r a g es p a c e ，b mo n l ys t 砸n g c o m p r e s s e db 鼬e c u b ec a r i te n s u f em ea c c u r a c ys om i sd i s s e r t a t i o ns t u d i e st h j sp r o b l e ma 1 1 d p r o v e s l i sp r o b l e m i s n p c o m p l e t e ，t h e n ah e u r i s t i c a p p r o a c h i s p r o p o s e d t 0f i n da n e a r o p 岫a lc o n f i g u r a t i o n k e ”m r d s ：d a 乜w 弛h o u s e ，a p p r o x i m a t eq u e r yp r o c e s s i n g ，c 【u s t e r i n ga n a 【y s i s ，d a 诅c u b e ， d a t a c 0 m p r e s s i o n 独创性声明 本人声明我所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本 文所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：冯多 日期：劲口，2 ，j ， 关于论文使用授权的说明 中国科学院计算技术研究所有权保留送交论文的复印件，允许论文被 查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、缩印或 其它复制手段保存该论文。 作者签名：；与量 导师签名：孑硎鳎 日期：2 帅。r 舌 兰二兰! li 一 第一章引言 当前，信息技术已经成为社会发展的重要推动力。如何利用计算机实现对大规模数 据的管理，以及如何分析这些数据以有效地支持决策过程，这既是信息科学学科的前沿 问题，也是一个系统工程的理论和实践问题。本文对数据仓库环境中的近似查询技术进 行了深入的研究，为在海量数据的数据仓库上进行的复杂查询的性能问题提供一条有效 的解决途径。 1 。1 数据仓库技术的产生与发展 随着计算机技术的飞速发展和在我国的广泛应用，传统的事务处理系统( 0 l t p ) 已经比较成熟，它大大方便了我们日常的事务处理工作，并保存了大量的业务数据。在 企业的日常事务处理信息化以后，数据分析和决策支持应用成为发展的必然。如何有效 组织企业数据以更好地支持决策分析应用，是近年来数据处理研究的一项主要内容。 数据库系统作为数据管理手段，主要用于事务处理，以分析处理为主的d s s 应用 具有极不相同的特点，直接使用事务处理环境来支持d s s 是行不通的，它们是两种不 同的数据处理工作，我们分别把它们称作操作型处理和分析型处理( 或信息型处理) 。 操作型处理也叫事务处理，是指对数据库联机的日常操作，通常是对一个或一组记 录的查询和修改，主要是为企业的特定应用服务的，人们关心的是响应时间，数据的安 全性和完整性。分析型处理则用于管理人员的决策分析，决策支持过程要求系统保存大 量的历史数据，以支持长期趋势分析；集成全局范围的数据，以支持宏观及综合分析的 能力：具有对大量数据进行复杂分析的能力：对复杂的决策检索过程具有快速响应的能 力等。 操作型处理和分析型处理之间的差异使得传统的数据库技术不能同时满足要求，数 据仓库概念的提出，为这个问题提供了一个很好的解决方法，数据仓库技术就此应运而 生。数据仓库系统是近年来在计算机应用科学领域的新兴技术，是当前数据库学科研究 的重要课题。数据仓库系统的建设是企业信息系统建设向体系化、集成化发展的必然组 成部分。 在【i n m 9 3 】中，w h i n m o n 给出数据仓库的如下定义：数据仓库就是一个用以更好地 支持企业或组织的决策分析处理的、面向主题的、集成的、不可更新的、随时间不断变 化的数据集合。数据仓库主要有以下特点： 面向主题( s u b j e c t o r i e n t c d ) ：数据仓库中的数据是面向主题进行组织的。主题 是一个抽象的概念，在逻辑意义上，它对应企业中某一宏观分析领域所涉及的 ! 璺型兰堕壁主兰壁堕苎二二塑塑垒堡墅塑主望型至塑竺堡苎查竺垄一 分析对象，例如客户、供应商、产品及销售情况等。面向主题的数据组织方式 能完整、统一地刻画各个分析对象所涉及的企业的各项数据以及数据之间的联 系。 集成化( i n t e g r a t c d ) ：数据仓库中通常集成了多个异质数据源的数据，例如关系 数据库、文件系统等。在集成过程中，需要对数据进行清洗、转换以保证数据 的一致性，例如要去除属性的同名异义，异名同义、单位不统一、字长不一致 等。 稳定性( n o n v o l a t i l e ) ：数据仓库的数据反映的是一段相当长的时间内历史数据 的内容，是不同时点的数据库快照的集合，以及基于这些快照进行统计、综合 和重组的导出数据，主要供企业决策分析之用，所涉及的数据操作主要是数据 查询，一般情况下并不进行修改操作。 时变性( t i m e v 撕a 1 1 t ) ：数据仓库随时间变化不断增加新的数据内容，删去旧的 数据内容。数据仓库数据的码键都包含时间项，以标明数据的历史时期。 图1 1 是个典型的数据仓库系统的结构。 操作型数据源 前台工具 从图1 一l 可以看出，数据仓库系统总体上来讲分为以下几个部分：数据仓库的后台 工具、数据仓库管理系统和前台工具。 数据仓库的后台工具，包括数据抽取、清洗、转换、装载和维护工具。它们负责把 企业或组织中各部门的操作型数据进行转换，装载到数据仓库系统中，同时维护数据仓 库和操作型数据源数据的一致性。 数据仓库服务器相当于数据库系统中的d b m s ，它负责管理数据仓库中数据的存 储，并给前端工具提供s q l 和多维查询的接口。 数据仓库服务器是数据仓库系统的核心，它采用多种适合数据仓库特点的技术提高 2 用户查询的响应速度。 前台工具包括查询报表、多维分析( o l a p ) 和数据挖掘等几类。 建立数据仓库的目的主要是给决策支持提供丰富的数据基础，前台工具用于向数据 仓库管理系统发出请求，并把返回的结果通过各种可视化方式展现给用户。 数据库学科领域的研究和系统开发都是和我国信息化建设一定阶段的实际需求紧 密相连。现阶段，以数据仓库为中心，建立一个企业或组织的体系化数据环境t 并在这 个数据环境上建立企业决策支持应用，已经成为目前我国企业信息化建设的现实需求。 而且，随着我国信息化建设的不断深入，这种需求还会迅猛增长。 数据仓库技术在过去的几年中得到迅速发展，它成功地应用到制造、零售、金融服 务、交通、电信、保险等多个行业。 1 2 近似查询处理技术的研究背景与意义 数据仓库是一个更好地支持企业或组织的决策分析处理的、面向主题的、集成的、 不可更新的、随时间不断变化的数据集合。决策分析着重于分析数据间的关联关系或发 展趋势，因此数据仓库中要包含大量的历史数据，随着时间的推移，数据仓库中的数据 会越来越多，同时在数据仓库上的查询通常是一些需要多表连接并具有聚集操作的复杂 查询。数据仓库中的大量数据和在其上进行的查询的复杂性会导致查询的响应时间过 长，这在决策支持应用中是不能接受的。如何更有效地组织、存储海量数据，提供海量 数据上高效率的查询操作一直是该研究领域的一个热点问题。 在数据仓库系统中有多种方法提高提高查询性能。例如，针对不同的查询类型提出 了查询修改、路径选择、h a s h 法等多方面的优化策略提高查询性能；根据数据仓库中 数据更新比较少的特点，采用了新的索引技术，例如b i t m a p 索引等；使用冗余的数据 ( 实体化视图) 来提商查询性能，即预计算一些常用的查询，并把结果保存下来( 也称 作实视图) ，这样在真正处理查询时，就不需要查询多个基表并进行连接或聚集操作， 而直接查询该实视图；查询的并行处理以及数据压缩技术等等。这些技术在一定程度上 提高了查询的性能，但是对于数据仓库的大数据量和在其上进行的复杂查询操作还是很 难实现交互式的快速响应速度。 数据仓库上通常是决策支持应用，在做查询处理时，为了提高系统的响应时阆，可 以容忍一些查询结果的精度，因此可以在一定的容错范围内使用近似查询处理技术来提 高响应速度。 数据仓库环境中的许多应用模式都对近似查询技术提出需求，例如： 1 我们在做o l a p 分析时，在一个钻取( “l l d o w n ) 查询序列中，最初查询 的目的就是为了决定我们真正感兴趣的数据，给这些查询提供快速、近似的 查询结果可以使用户尽快找到有用的数据。 2 在数据仓库上的许多决策支持应用中的查询目的着重于分析数据阃的关联 3 ! 璺型堂堕堕圭兰堡笙奎二= 塑塑鱼壁堡垫! 重型垒塑竺墨垫查竺型一 关系或发展趋势，有时在做聚集查询时，对查询结果的要求并不需要精确到 小数点。例如，查询今年公司员工的平均工资： ( 1 ) 在l o 秒内给出结果：3 2 0 0 0 置信度：9 0 ( 2 ) l o 分钟给出结果：3 2 3 2 1 9 5 两者相比，如果只是想对公司员工的工资状况有个了解，则( 1 ) 更能让人 接受。 3 在数据仓库中数据集成过程中，随着数据量的增加，有些原始数据需要归档， 则做查询时只能使用本地可用的数据，因此可以把对原始数据进行压缩处理 后的小数据集存放在本地，对用户的查询给出近似结果。 随着数据仓库中数据量的进一步增长，使用近似查询处理技术来提高查询性能的要 求会越来越迫切，学术界和工业界对该项技术会更加关注。本文就数据仓库环境中近似 查询处理技术进行研究，对用户提交的查询提供快速、近似的( 合理的) 查询结果，这 从理论和实践上具有重要的意义： 1 解决数据仓库系统上决策支持应用的性能问题，这在实际工作中是非常重要 的因素。 2 近似查询处理技术涉及数据压缩、数据挖掘、统计分析、数据库等多个领域 的技术，通过该项目的研究，把这些技术应用到数据仓库领域中，进步促 进这些技术的发展，具有重要的学术价值。 1 3 近似查询处理技术的国内外研究状况 国际上对数据仓库技术的研究始于九十年代初。各国大学和研究机构就纷纷展开了 对数据仓库的研究，并获得了许多有价值的研究成果，例如斯坦福大学( s t a r 讧b r d u n i v e r s i t y ) 开展的数据仓库项目w h i p s 等。 数据仓库领域的研究主要集中在数据仓库的体系结构、数据仓库中数据生成和维护 策略、数据仓库的性能提高等。在数据仓库的体系结构方面，提出了数据仓库系统体系 结构的三层模型；在数据生成和维护策略方面，包括数据建模方法的研究，数据集成和 抽取算法研究，也提出了如实视图选取和增量维护技术，并应用到数据仓库数据组织和 维护中；在数据仓库的性能提高方面，对实体化视图、索引、数据方体、并行处理、数 据压缩等技术进行了深入的研究。正如前所述，这些技术在一定程度上提高了查询的性 能，但是对于数据仓库的大数据量和在其上进行的复杂查询操作还是很难实现交互式的 快速响应速度，加之数据仓库上决策支持应用的特点，因此可以在一定的容错范围内使 用近似查询处理技术来提高响应速度。 近似查询处理技术的研究动机早期主要是在实时数据库中，由于时间的限制不能给 出精确结果或由于网络等问题不能查询到需要的数据而只能给出近似结果。对近似查询 的早期研究主要针对非聚集查询，对查询结果的近似是基于子集和超集的定义 r o d g h 9 2 ，v l 9 3 】。在数据仓库环境下，对近似查询的研究主要针对聚集查询操作。 近年来由于数据量的迅速膨胀，磁盘i o 的速度相对于内存和c p u 的发展相对缓慢， 近似查询处理技术又越来越受到学术界和工业界的重视，成为一个十分活跃的研究领 域，下面列出在近似查询处理领域中具有代表性的研究项目： b e l l 实验室的a q u a ( a p p m x i m a t eq u e r ya n s w e r i n g ) 项目，它实现了一个原 型系统a q u a ，a q u a 是在用户和数据仓库之间的一个中问件，它把原始数据 通过预计算生成小的数据提要( s y n o p s e s ) ，存储在数据仓库中。a q u a 解释用 户提交的s q l 查询q ，并把查询q 改写成在s y n o p s e s 上运行的查询q ，由数 据仓库返回近似结果集。它采用的主要的预计算技术是抽样和直方图，对于抽 样在连接操作和聚集操作中存在的问题进行了深入了研究，并提出相应的解决 方法。 b e l l 实验室的n e m e s i s ( n e t w o r k m a n a g e m e n t d a t aw a r e h o u s i n ga n da n a i y s i s ) 项目，它在近似查询方面的主要研究成果是实现了一个对大数据表的语义压缩 系统s 鼢j 淞n ，采用分类技术对数据表在一定的误差范围内进行有损压缩，另 外对采用小波变换技术对数据进行预处理用于近似查询进行了深入的研究。 u c b e r l 【e l e y 的c o n t r o l ( c o n t i n u o u s0 u t p u ta n dn a v i g a t i o nt e c h n o l o g y 埘t h r e f i n e m e n to n l i n e ) 项目，该项目的主要技术是对于一些需要很长时间执行的 应用请求，不是让用户一直等待，而是在系统运行时给用户反馈，用户可以控 制系统的执行，该技术应用到查询领域，则表现为对于复杂的聚集查询，突破 传统先排序的聚集查询算法，采用非阻塞的连接操作，对聚集查询的各组数据 同时计算，尽快给出近似的查询结果，并给出置信区间，然后逐渐细化查询结 果，我们称之为联机查询处理。 m i c m s o f i r e s e a r c h 的a p p m x i m a t eq u e r yp r o c e s s i n g 项目，该项目的主要研究目 标是在数据库中提供近似匹配和搜索，在近似查询处理方面的主要成果有对抽 样技术在近似查询处理中存在的问题进行了探讨。 a r & t 研究中心的d lk n o w ( d a t ar e d u c t i o na i l dk n o w l e d 鼯e x t m c t i o nf o r0 n l i n e d a t aw h 幽o u s e s ) 项目，该项目在数据约简技术方面的主要成果包括使用s v d 技术提供近似查询和对数据库中数据在一定的误差范围内进行有损压缩等。 在国内，中国人民大学、哈尔滨工业大学、南京大学、西北工业大学等都对数据仓 库技术进行了研究，国内对数据仓库的研究主要集中在数据仓库的体系结构、数据仓库 的建模、数据仓库中数据的组织与存储、数据方体的计算等方面，就我所知，其它在数 据仓库上近似查询处理技术的研究尚未看到。 在系统开发方面，各大数据库厂商均对数据仓库的研制给予了相当的关注，都把数 据仓库市场的开发作为一个利润增长点，数据仓库技术正在从理论走向实际应用。i b m 、 0 r a c l e 和s y b a 分另l j 推出了各自的数据仓库整体解决方案，另外还有许多第三方厂家开 发了许多数据仓库的前台工具，例如c o 鼬s 、b r i o 等。但对于近似查询处理技术的支 ! 曼型兰堕堕主兰垡堡壅二= 堂塑垒壁竺塑茎竺丝壁型壁坚型堕苎堕墨一 持还不太多，只有在0 r a c i e 和i b m i n f o m i x 中提供了s 姗p l i n g 操作符。 在国家自然科学基金项目的支持下，中国人民大学数据与知识工程研究所也研究和 开发了劳行数据仓库系统原型p a m 砒l r e 。 1 。4 论文的主要工作 本人在攻读博士学位期间主要从事数据仓库和数据挖掘的研究和歼发工作，先后参 加了国家自然科学基金资助项目“数据仓库系统技术研究”和中国人民大学青年项目“基 于数据仓库的数据挖掘技术研究”的研究工作。 由于数据仓库中大数据量的存在和查询的复杂性使得数据仓库的性能问题一直是 学术界和工业界关注的热点之一，本人选择“在数据仓库环境中的近似查询技术研究” 作为博士论文题目的目的是为了从另外一个角度来解决数据仓库在实际应用中所面临 的性能问题，为数据仓库的实用化提供切实可行的解决方案。 本文对数据仓库环境中近似查询处理技术进行了深入的研究，主要包括以下内容： 1 根据数据仓库中数据和0 l a p 查询的特点，提出基于聚类技术的近似查询 处理方法( c l u s t e r - b a s e da p p m x i m a t eq u e r yp m c e s s i n gm e m o d ，简记为 c a q p ) ，其主要思想是对数据仓库中数据方体的数据进行分块，每个数据 块相当于多维空间中的一个点，采用聚类技术对数据方体中的这些数据块 聚类，对于每个c l u s t e r ，使用其中心点代表其中所有的数据块，从而对数 据方体进行压缩。对数据方体的查询操作则直接在压缩的数据结构上进行， 减少查询处理时的i o 开销，提高查询性能。 2 聚类是一个老问题，在统计学、人工智能、模式识别等领域得到了广泛的 应用，但在数据库领域，由于数据量大的特点，又对聚类技术提出了新的 要求。本文首先对聚类技术进行了深入的研究，提出了基于方格和密度的 新聚类算法s c a r g ，它的基本思想是把整个数据空间划分成矩形区域， 如果一个区域的密度大于一个阀值，则该区域是个密集区域，把所有相 关联的密集区域连接起来，构成一个c l l l s t e r 。本文采用移动中心点的技术， 对聚类结果进一步细化，提高聚类的精度。s c 。6 汰g 算法兼具了基于方格 算法的处理速度和基于密度方法处理任意形状c l u s t e r 的能力。本文同时又 给出该算法的并行化版本p s c a r g ，采用分区技术对数据“分而治之”， 充分利用硬件资源来提高性能，并通过实验与其它著名的聚类算法 ( d b s c a n ，c l a r a n s ) 对比，说明了s c a r g 及其并行算法的有效性 和性能。 3 本文在深入研究了聚类技术的基础上，又对基于聚类的近似查询处理的关 键技术进行研究，即对于数据仓库中的数据，如何采用聚类技术进行近似 查询处理，主要包括以下几个方面： 6 笙二里! l 亘 一一 i 根据数据仓库上o l a p 查询的特点，设计了适用于查询处理的数据存 储结构。 i i 提出了基于分区的数据预处理算法对数据仓库中数据方体的数据进行 分块，使得c a q p 算法可以作为一个中间件与其它数据仓库系统配合 使用。 i i i 当聚类用于近似查询处理技术时，对聚类算法提出了新的要求，例如能 处理海量数据：每个c l u s t e r 的半径应该小于某个阀值；c l u s t e r 的个数 应该能够控制等，本文设计了分层的聚类算法来满足近似查询处理的要 求。 i v 通过聚类方法对数据方体预处理，然后进行近似查询操作，因此当对数 据方体中的数据更新时，就要对预先计算的数据进行维护。本文给出了 对数据方体压缩结构的增量维护算法，避免了对所有数据的重新计算。 v 针对数据仓库上的常用操作，本文给出了在数据方体压缩结构上进行查 询处理的算法，并给出了对查询结果集置信区间的估算方法。 v i 本文还通过实验与抽样技术对比，说明了c a q p 方法的有效性和可扩 展性。 4 一个完整的数据方体是由2 “1 个子方体组成，其中一个是基本数据方体， 其它子方体存放的是综合数据，可以由基本方体计算生成。在数据仓库领 域，对于精确方体中这些子方体的实体化视图的计算、选择、维护和优化 问题已经得到了广泛的研究，对于近似方体来说也存在同样的问题。本文 对近似扩展数据方体技术进行了研究，主要包括以下几个方面： i 给出了从基本方体的压缩结构计算近似扩展数据方体中所有子方体的 分块算法。 试扩展数据方体中的所有子方体都实体化，会占用很多存储空间，如果只 存储基本方体，则不能保证查询的精度，因此，本文对近似扩展数据方 体的配置问题进行研究并证明了该问题是一个n p 完全问题，同时设计 了一个启发式算法找出近似的最优配置，并证明了该算法得出的近似解 与最优解之间的误差边界。 谶 简要介绍了扩展数据方体的维护和查询优化方法。 1 5 论文的组织安排 本文对数据仓库环境中近似查询处理技术进行了深入的研究，全文安排如下： 第一章引言，介绍了数据仓库中近似查询处理技术的研究背景和意义、国内外的研 究状况以及本文的主要研究工作和组织安排。 第二章综述了数据仓库和近似查询处理领域的基本概念和相关工作，主要介绍数据 7 生里型兰垦堕! 兰堡堕兰二= = 墼塑垒壁堡竺! 堑型壅塑丝璺垫查婴丝一 仓库提高查询性能和近似查询处理的常用技术以及存在的问题和解决办法。 第三章概括介绍基于聚类技术的近似查询处理方法c a q p 。本章首先介绍了数据仓 库中的数据模型以及实现技术，然后着重说明c a q p 的基本结构、功能以及特点。 第四章首先对聚类技术进行了深入的研究，介绍聚类的基本概念和相关的研究成 果，并根据数据库应用的特点提出了新的聚类方法s c a r g ，并通过实验说明了该方法 的性能和效果，同时给出了该算法的并行版本p s c a r g 。 第五章研究了基于聚类的近似查询处理的关键技术，包括数据的预处理、数据的存 储结构、数据的分层聚类计算和维护以及各类查询处理算法和误差估算，并通过实验说 明了该方法的有效性和可扩展性。 第六章研究了近似扩展数据方体的问题。本章首先介绍了从基本方体的压缩结构计 算整个数据方体的计算方法，然后说明实体化哪些子方体可以保证所有子方体的误差小 于一个阀值，并把该近似数据方体的配置问题抽象为一个优化问题，并设计了一个启发 式算法解决该问题，同时证明了该算法的近似程度。 第七章对本文工作进行了总结，说明了本文的主要贡献和创新，以及进一步的研究 工作。 8 璺三兰墼堡鱼壁皇堕型重塑塾查堕塑璧型坚l 一 第二章数据仓库与近似查询术的相关研究 数据仓库中存储的是用于决策分析的历史数据，随着时间的推移，数据仓库中的数 据会越来越多。在数据仓库上的查询通常是一些复杂查询，这就可能会出现无法接受的 响应时间。如何更有效地组织、存储海量数据，提供海量数据上高效率的查询操作成为 该研究领域的一个热点问题。本章首先介绍在数据仓库领域为提高查询性能所进行的研 究成果，然后着重介绍近似查询处理技术的基本概念、通常采用的技术以及对近似查询 结果集的评价方式。 2 1 数据仓库技术 提高数据仓库环境中复杂查询的性能在数据仓库领域中一直倍受关注，在过去若干 年中，研究人员根据数据仓库系统的特点，提出了一系列的新技术来提高查询的性能， 下面分别说明。 2 1 1 实体化视图 实体化视图技术就是在数据仓库中使用冗余的数据( 实体化视图) 来提高查询性能。 考虑到数据仓库中数据更新不频繁，因此可以在数据仓库中使用冗余的数据( 实体化视 图) 来提高查询性能，即充分利用预计算功能。例如，预先计算一些常用的查询，并把 结果保存下来( 也称作实视图) ，这样在真正处理查询时，就不需要查询多个基表并进 行连接和聚集操作，而直接查询该实视图即可。在基本数据方体( b a s e c u b e ) 的基础上 预先计算并生成一系列子方体，这样就可以将用户对基本数据方体的查询转移到相应的 子方体上，既避免了数据的大量聚集计算，又减少了获取数据时的i o 开销。 使用实视图来提高查询性能需要解决以下几个问题： ( 1 ) 如何选择实视图。实视图的存在一方面可以提高查询性能，但同时也还有 负面作用，例如占用磁盘空间、必须对这些实视图进行一致性维护，因此 必须有效地对应该实体化的视图进行选择h r u 9 6 ，b p t 9 7 ，g h r u 9 7 ， s d n 9 8 t t s 9 7 ，r s s 9 6 ，g u p 9 7 ，y k l 9 7 】。 ( 2 ) 如何利用实视图进行查询优化 l m s s 9 5 ，g h q 9 5 ，c k p s 9 5 ，c s 9 6 a ， s d j l 9 6 ，z c l + 0 0 】。 ( 3 ) 在数据装载和刷新时，如何维护实视图的一致性z g h w 9 5 ，z g m w 9 6 ， q w 9 7 ，a a s y 9 7 ，m q m 9 7 】。 9 主塑型兰堕塑! ：鲎垡丝苎二二塑塑竺垦型堡堕垒型坠垒型竺些塾查型兰二一 2 1 2 索弓 在数据仓库中可以使用合适的索引结构来提高性能。传统的b t r e e 索引非常适合 于查找并取回少量记录的查询。但是，在数据仓库应用中，通常是复杂的查询，并经常 带有分组及聚合条件，此时，b 仃e e 索引往往是无能为力的。在数据仓库环境下，数据 通常是只读的，更新常常是周期性地批量进行，因此可以采用不同于传统索引的结构来 提高查询的性能。 在数据仓库环境中，数据通常以多维模型组织，因此，一系列多维索引方式，如r 树 g u n 8 4 】、r 十树【s i 球8 7 】、r 树【b b s 9 0 】、b u d d y 树【s k 9 0 】等更适合数据仓库下的多维 环境。但利用树形索引来完成含有大量结果集的查询其效率始终是很低的a 实验表明， 当结果集到达一定程度时，树形索引的效率将退化为直接对数据表的扫描。而数据仓库 的典型查询又经常包含大量结果集。 与此同时，另一种非树形索引b i t m a p 索引以其较小的存储代价和高效的索引效率 成为数据仓库中的主要索引策略【0 n 8 7 1 。【o q 9 7 ，c 1 9 8 ，c 1 9 9 a ，w b 9 8 ，w u 9 9 1 中都对 b i