（计算机应用技术专业论文）数据仓库物化视图在线算法研究.pdf

摘要作为数据仓库的一项关键技术物化视图是加快o l a p 查询响应速度，提高决策支持性能的重要手段由于受到空间开销和视图维护代价等因素的约束，物化数据仓库中所有可能的视图是不可能也是没有必要的，可行的策略是在海量的视图中进行选择性的物化，并加以高效维护而如何选择适当的视图进行物化，以及如何维护可能是成千上万的物化视图，是数据仓库及o l a p 一个非常关键的问题，得到了广泛而深入的研究物化视图集的选择和维护，通常是在数据仓库脱机状态下进行的，如选择夜晚停机时间实施然而随着数据仓库的发展以及应用全球化的趋势，很多因素制约了脱机时间，使系统能够提供“脱机”处理的时间越来越难以保证于是对不停机条件下物化视图选择和维护算法的研究得到了学术界，企业界普遍的重视本文就此领域重点对数据仓库在线条件下物化视图的各种相关算法进行了较为深入的研究主要内容及其取得的成果体现在以下几个方面：( i ) 针对物化视图静态选择算法存在的不足。提出一种预处理算法p m v s 该算法充分利用多维数据集中查询稀疏性和数据稀疏性的特点。对静态选择算法的视图搜索空间进行很大程度地约减，有效地降低算法的复杂度，使之基本适合在线运行，从而可以用于实现物化视图集的周期性动态调整( 2 ) 提出一种基于c a c h e 机制的物化视图动态选择算法d m v r ，相比于其他动态选择算法都是内存机制简单移植，算法d m v r 建立在一个合理的代价模型之上，充分考虑各种影响物化效益的各种因素，可以更好地用于实现物化视图的动态选择和实时调整( 3 ) 利用动态c a c h e 机制的优势，对已有的静态物化集进行有效地动态补充，使其对查询分布的变化和即席查询具有良好的在线适应能力。从而实现物化视图静态选择算法和动态选择算法这两种基于不同机制算法的优势互补1 4 ) 针对物化视图在线维护的需求，引入机会更新的维护方式，实现系统资源合理的调配和利用，并基于机会更新和延迟更新相结合的策略提出一种在线维护算法o d u a , 在保证数据一致性的前提下，通过系统资源合理利用以及更新效率的提高。尽最大可能减少在线维护对系统性能的影响关键词：数据仓库，o l a p , 物化视图，视图选择，预处理，c a c h e 机制，在线维护，延迟更新a b s t r a c tad a t ew a r e h o u s ei sad a t ar e p o s i t o r y , w h i c hc o l l e c t sa n dm a i n t a i n sal a r g em o u n to fd a t af r o mm u l l i p l ed i s m b u t e d ，a u t o n o m o u sa n dp o s s i b l yh e t e r o g e n e o u sd a t as o i m o f t e nt h ed a t ai ss t o r e di nt h ef o r mo fm a t e r i a l i z e dv i e w 3f o rt h ep u r p o s ee f f i c i e n t l yi m p l e m e n t i n gd c c i s i o n - s u p p o 仳o ro l a pq u e r i e s f i r s t l y , t h es e l e c t i o no f v i e w sf o rm a t e r i a l i z a t i o ni so n eo f t h em o s ti s s u e si nt h ed e s i g nd a t ew a r e h o u s e , i t sg o a li st os e l e c t a p p r o p r i a t es e to fv i e w st h a tm i n i m i z e st o t a lq u e r yr e s p o n s et i m ea n d o rt h ec o s to fm a i n t a i n i n gt h es e l e c t e dv i e w s , g i v o nal i m i t e da m o u n to f r a s o n s c e ，e g ，s t o r a g es p a c e ，m a t e r i a l i z a t i o nt i m e ，o rt o t a lv i e wm a i n t a n a n c et i m e s e c o n d l y , m a i n t a i n i n gl o t so f m a t e r i a l i z e dv i e w si sc h a l l e n g i n g e s p e c i a l l yf f t h ed a t as o u r c e s2 r ea u t o n o m o u sa n dv i e w so f t h ed a t aa tt h ed a t aw a r e h o u s es p a nm u l t i p l es o u m e “q t h ev i e w sh a v et ob em a i n t a i n e di nt i m et or e f l e c tt h eu p d a t e sd o n ea g a i n s tt h eb a s er e l a t i o n ss t o r e da tt h ev a r i o u sd a t es o u r c e s n 圮e 伍c i e n tm a i n t e n a n c eo fm a t e r i a l i z e dv i e w sh a sb e c o m ea n o t h e ri m p o r t a n tr e s e a r c hi s s t h eu s u a lm e t h o d si s 廿扭tt h em a t e r i a l i z e dv i e w sa r as e l e c t e da n dm a i n t a i n e do f f l i n e 。f o re x a m p l e , t h es t a t i cs e l e c t i o na l g o r i t h mo f v i e wi se m p l o y e dt og e n e r a t eo rr e g e n e r a t et h em a t e r i a l i z e dv i e ws e t ，a n db a t c hu p d a t ep o l i c y i su s e d t o m a i n t a i n t h e m a tn i g h t ，h o w e v e r , w h e r e m t h e a m o u n t o f d a t a e n t e r i n g a w e r c h o u s c ,t h eq u e r yl o a d s ，a n dt h en e e dt oo b t a i n 叩- t o - d a t er e s p o n s e sa r ea ui n c r e a s i n g , t h e n i g h t t i m ea v a i l a b l ef o rm a k i n gt h ew a r e h o u s eu p - t o - d a t ei ss h r i n k i n g t h e s eu a n d sn e c e s s i t a t ee f f i c i e n to n l i n ea l g o r i t h m sf o rm a t e r i a l i z e dv i e w s i nt h i sp a p e r , i ti se m p h a s i z e dt om a k ed e e p e rr e s e a r c ho nt h es e l e c t i o na l g o r i t h m sa n dm a i n t e n a n c ea l g o r i t h m so f m a t e r i a l i z e dv i e w sd u r i n gt h ed a t aw a r e h o u s eo n - l i n e t h em a i nc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ：( 1 ) t os o l v et h es h o r t a g eo ft h es t a t i cs e l e c t i o na l g o r i t h mo fm a t e r i a l i z e dv i e w , t h ep a p e rp r e s e n t sp m v s p r e p r o c e s s o ro fm a t e r i a l i z e dv i e ws e l e c t i o na p p r o a c h p m v sm a k e su o ft h eq u e r ys p a r s e n e s sa n dd a t as p a r s e n a s si nm u l t i - d i m e n s i o n a ld a t a s e t s ，a n dr e d u c e st h et i m ec o m p l e x ( s e a r c hs p a c c ) o f t h es t a t i cs e l e c t i o na l g o r i t h m ，s ot h ec o s to fs t a t i ca l g o r i t h m so ns p a c ea n dt i m ec a nb ec u td o w nt of i tf o ro n l i n ed e m a n d ( 2 ) p r e s e a tai m p r o v e da l g o r i t h mf o rd y n a m i cm a t e r i a l i z e dv i e ws e l e c t i o n ，c a l l e dd m v r ( d y n a m i cm a t e r i a l i z e dv i e wr e p l a c e m e n t ) c o n t r a s tt oo t h e ra l g o r i t h m sb a s e do nc a c h e ，d m v ri sn o tas i m p l ec o p yo fm e m o r ym e c h a n i s m ，a n di sb a s e do nar e a s o n a b l ec o s tm o d e l t h em o d e lc o n s i d e r sa l lo fi m p o r t a n tf a c t o r sr e l a t e dt om a t e r i a l i z a t i o nb e n e f i t ，a n dc a nb ev a r ys t a t a b l ef o ri m p l e m e n t i n gt h ed y n a m i cs e l e c t i o no f m a t e r i a l i z e dv i e w ( 3 ) t a k ea d v a n t a g eo f t h ec a c h em e c h a n i s mt oo p t i m i z et h es t a t i cm a t e r i a l i z e dv i e ws c t s ot h es e tg a i n sab e t t e ra d a p t a b i l i t yt oa l t e r i n gq u e r yd i s t r i b u t i n ga n dab e t t e rr e s p o n s ep e r f o r m a n c et oa d - h o cq u e r i e s 1 1 1 i sm e t h o dc o m b i n e st h es t a t i cs e l e e t l o na l g o r i t h ma n dt h ed y n a m i cs e l e c t i o na l g o r i t h m a n dm a k e st h ev i e ws a tw o r kb e t t e r ( 4 ) t om e e tt h er c q u i r 吼to ft h e o n l i n em a i n t e n a n c e ，p r o p o s eah y b r i da p p r o a c ho d u a ( o p p o r t u n i t y d e f e r r e du p d a t ea p p r o a c h ) ，w h i c hc o m b i n eo p p o r t u n i t yu p d a t ea n dd e f e r r e du p d a t et om a i n t a i nt h em a t e r i a l i z e dv i e w se f f i c i e n t l y o nt h ep r e m i s eo fk e e p i n gt h ed a t ac o n s i s t e n c y , i td o e si t sb a s tt or e d u c et h en e g a t i v ee f f e c to f t h eu p d a t ec o s tt ot h eq u e r yr e s p o n s ep e r f o r m a n c e k e y w o r d s ：d a t aw a r e h o u s e , o l a p , m a t e r i a l i z e dv i e w , v | c ws e l e c t i o n , o n l i n em a i n t e n a n c e ，p r e p r o c e s s o r ,c a c h em e c h a n i s m ，d e f e r r e du p d a t e东南大学学位论文独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名：堑堑茎鱼日期：东南大学学位论文使用授权声明东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。研究生签名：韭燧坠导师签名：赴型云日期：够穸第一章引言1 1 研究的背景第一章引言数据仓库是现代信息技术构架的新焦点，它集成了不同种类的应用系统，并从事物发展和历史的角度来组织和存储数据，为决策支持或智能商务提供集成化和历史化的数据【l 】联机分析处理( o n - l i n e a n a l y t i c a lp r o c e s s i n g ，简称o l a p 作为数据仓库的主要应用，它通常需要在海量数据上进行复杂的查询，包括分组聚集、多表连接以及针对数据立方体的下钻、上卷、旋转、切块等【2 一。相对于事务型数据库系统这些操作是相当耗时；然而决策应用要求系统必须及时快速地向用户提供分析数据，这对查询性能捷出了很高的要求，使得提高查询响应速度和分析操作效率成为数据仓库应用研究中的一个热点问题，为此研究人员提出了聚集快速计算、物化视图、高效索引、多维数据库与立方体( c u b e ) 技术以及并行处理等一系列相关技术【2 州物化视图技术是通过将一部分查询结果视图进行实际的物理存储，避免每次查询结果都从数据仓库基础数据集甚至数据源重新生成，从而可以显著地提高相关的o l a p 查询的响应速度它已成为一种提高数据仓库查询响应性能的重要手段l s - q 1 1 由于实现物化视图需要额外的空问开销和维护代价，物化所有可能的视图不太可能也没有必要，因此切实可行的策略是考虑空间开销和维护代价，选择一部分适当的视图予以物化然而在多数情况下，物化视图集的选择是一个n p h a r d 问题f 1 2 现有的各种算法大多都是对最优解的近似，在一定的应用领域内可以显示出各自有效性和优越性，但也存在很多不足和一些难以解决的理论与应用问题另外在物化视图可有效地提高系统对用户查询响应速度的同时，也带来了物化视图的维护问题慨“由于数据仓库中的数据来自其他独立的数据源，当这些数据源的数据发生变化时，需要通过增量维护或重新计算的方法对相关的物化视图进行更新，以保证系统内数据的一致性，这也成为数据仓库研究领域中非常关键和难以解决的技术问题以上这些富有挑战性的研究吸引了国内外很多研究人员的兴趣，其中以斯坦福、维斯康辛等大学计算机系、i b m 的a l m a d e n 研究中心以及微软和a t & t 等公司存这方面的研究最为活跃目前有关数据仓库物化视图技术的研究主要集中在以下几个方向t5 1 1 , 1 4 “1 ：( 1 ) 最优物化集的选择除了对传统的贪婪算法进行不断地改进。很多研究人员都在尝试将其他各种最优解理论用于物化视图的选择，如启发式算法、遗传算法和空阁转移等算法同时在空间代价和维护代价等单一约束或多重约束下，物化视图选择问题也是研究的一个重点( 2 ) 物化视图集的动态调整和在线选择算法在数据仓库创建阶段，对物化视图的选择往往建立在对用户需求较为粗糙的分析之上，表现为选择的物化视图集与真正的最优集有较大的差异同时实际应用中用户的需求也在不断的变化难以准确掌握和预测，因而即使开始阶段用户需求得到了较为客观准确的分析，随着时间的推移和应用的变化，也会使物化视图集逐渐偏离最优，而导致查询响应性能的f 降所以必须采用适当算法进行物化视图的在线动态调整，以保证系统具有较高的查询响应性能。为此研究人员进行了深入的研究，提出很多不同的解决方案( 3 ) 分组聚集的计算和c u b e 相关计算牲戈系型o l a p ( r e l a t i o n a lo l a p , 简称r o l a p ) 查询中通常包含了多袭连接和分组聚集这些l东南大学博士学位论文操作的性能直接影响o l a p 查询响应的速度和物化视图的生成及维护代价，特别是对即席查询的性能起决定性的作用有效地减少多表连接和采用高效的分组排序方法，是提高算法效率的主要方法与分组聚集的计算相对应，在多维o l a p ( m u l t i d i m e n s i o n a lo l a p , 简称m o l a p ) 中同样存在着c u b e 的计算效率问题，它直接影响了即席查询速度，以及c u b e 的预聚集计算和更新效率另外，对c u b e 而言还存在着多维数据压缩，提高空间利用率等问题，这些一直是o l a p 研究的热点( 4 ) 基于物化视图的查询优化如何利用已有的物化视图对用户查询进行重写，避免从数据仓库基础表数据源生成，以提高用户查询或物化视图的生成和刷新速度，这属于查询优化问题它对于充分发挥物化视图的作用非常重要查询的重写和优化往往还伴随着最小物化视图和最优生成路径的选择问题( 5 ) 物化视图的维护，尤其是在线维护算法研究一个大中型数据仓库中物化视图的数量可能是非常巨大的如何对这些视图进行高效维护以保证用户查询的质量和性能，一直是非常具有挑战性的工作以往物化视图的维护大多采用脱机方式实施，而目前更希望的是在数据仓库在线条件下完成，即在不影响数据仓库正常业务处理的条件下，完成视图更新，并要确保查询数据一致性，这也是数据仓库的一个关键技术而受到广泛的关注随着信息全球化的浪潮和i n t e m e t 的迅速发展，对数据仓库连续不问断提供7 x 2 4 方式服务的要求越来越强烈，导致以往可以在离线状态进行的物化视图的选择、维护、重构、优化等各种工作必须能够在数据仓库在线条件下实施，从而对各种算法的效率、速度等方面提出了更高的要求综上所述，物化视图在线算法的研究具有重要理论意义和应用价值，而国内外对这方面系统性研究的报道尚不多见鉴此背景，在国家自然科学基金项目! 基于数据挖掘技术的中观审计风险研究”( 项目编号：7 0 3 7 1 0 1 5 ) 的资助下，结合实际应用背景一国家中小型企业创新基金项目“企业商务智能决策导航器e b i d n ”( 项目编号：0 2 c 2 6 2 1 3 2 1 0 0 7 0 ) ，作者开展了“数据仓库物化视图在线算法”的论文研究工作研究的主要内容有：物化视图的在线选择、动态调整和在线维护等相关算法，并期望在一定程度上解决现有算法适用性较差、效率较低等方面的不足，获得一些适用于在线使用的高效物化视图选择和维护算法，以满足数据仓库不问断运行要求，提高用户的满意度1 2 研究的现状在数据仓库迅速发展的上世纪9 0 年代学术界、企业界相关的研究人员在这一领域进行了广泛而深入的研究，物化视图作为其中一项可以提供数据存储方式和提高用户查询响应性能的关键技术得到了充分的重视，在斯坦福大学和i b m 等很多机构都成立了专门的研究小组，从事这方面的研究，其中国内的国防科技大学、中国人民大学、华中科技大学、复旦大学以及香港科技人学等院校这方面的研究也较为活跃；而且在实际系统中物化视图技术已作为一种常规的方法得到一定程度的应用但是如何选择适当的物化视图集并进行及时的更新，以克分地发挥它提高决策支持查询性能的作用，却是一个迫切需要解决的关键性技术问题1 2 1 视图选择算法从1 9 9 5 年开始。针对物化视图选择问题一些研究人员进行了深入的研究【1 2 , 1 3 , 1 6 - 3 2 ：斯坦福大学h a r i n a r a y a n 在文献 1 6 】首先提出数据屯方体的格模型，以此来描述视图间的相瓦依赖关系，然后假设格图中各个视图上的备询是均匀分布的，给出了基于物化效益最优的贪婪算法b p u s 来解决视图的选择问题，这一算法简单可行且具有开创件的意义，它并从理论上证明其物化效益和最优解的比2第一章引言值不小于1 i e 斯坦福大学的另一位学者g u p t a , 在更为广泛的a n d - o r 图基础上，对物化视图选择问题进行系统性的描述。针对不同的情况提出了一系列启发式算法i i l ”1 “，包括对基于存储空问约束、维护代价约束和视图索引等情况的考虑y a n gj 在文献 1 8 】中通过对查询共享子式的提取和物化，以期达到物化效益的最大丽文献【1 9 1 则针对以b p u s 算法为代表的贪婪算法时间复杂度较大的问题，提出了一种基于各视图尺寸进行选择排序的p b s 算法，其算法时间复杂度在一定前提下降至o ( n l g n ) r 算法很简洁，具有很好实用性文献 2 0 】对维护时间约束条件下的情况进行了进一步的研究，提出了寻找更好的启发式函数并将物化选择问题转化为常见的优化问题来加以研究在各种启发式算法得到充分研究的基础上，有些研究人员尝试采用其他优化方法应用于物化视图选择问题【2 l 一捌如文献 2 1 2 4 将物化视图选择问题转化为空间转移问题进行研究，并以所有查询都可由物化集得到响应为前提。而以维护代价最小为优化目标；而文献 2 5 1 将遗传算法获取最优鼹的能力用于物化集的选择，其选择的物化集在理论上具有很好的参照意义；还有一些研究人员则对各种混合算法进行研究，其中文献【2 6 】将遗传算法和启发式算法加以结合，以得到物化集最优和算法复杂度较低的平衡以上选择算法都是基于查询分布预知或者查询均匀分布的假设，本质上都可归结为静态算法田”i 它们都是在确定的查询集基础上考虑各视图间相互生成关系而致力于获取最优物化集的近似算法虽然在一定的应用领域和理论方面有着较大优越性和有效性，然而由于数据仓库的时变性使用户查询集在不断变化，特别是决策支持应用中存在较大成分的即席访问，从而实际系统中的查询模式变得难以预测，导致静态算法所选择的物化视图集逐步偏离最优。无法对用户查询做出快速的响应而现存的各种静态视图选择算法，由于时间复杂度偏高，不适合在线运行，无法根据查询分布的变化对物化集做出即时的调整为此一些研究人员针对这个问题，通过改造静态算法使之具有一定的动态调整能力9 ”，从而可以用于用户需求变化不是很快的情况，一定程度上减少了管理员的工作量，但对于即席查询或模式变化较快的查询，则无法进行即时的调整；文献t 3 6 1 8 0 提出了一种动态算法p f u s ，但即时调整策略导致系统开销很大难有真正的实用价值，且物化集可能出现频繁的“抖，动”而缺乏必要的稳定性。由于动态c a c h e 机制具有直观快速和算法简单的特点，在虚拟内存管理和数据库缓存方面已得到了广泛的应用和充分的研究p ”m ，一些研究人员将之应用到查询视图的物化和动态选择，提琳否些时间复杂度较低适合在线的算法d “o - o s ! ，如文献f 4 9 】提出的w a t c h m a n 算法和文献1 3 4 提出的d y n a m a t 算法，这些基于c a c h e 机制的动态算法目标在于使每一次的查询结果尽最大可能的重复利用，以最大限度地抵销其生成时的开销，算法具有简单直接，可以有效地提高物化视图集的动态自适应性能。并具备了即时调整的能力，但它们都是基于内存机制的简单移植，其实现模型较为粗糙，均未考虑物化视图从硬盘回读的代价，即对于基于硬盘的c a c h e 机制没有考虑到即使硬盘中有直接的物化视图存储，其读取同样需要代价；而且只考虑与查询直接相关的视图集的物化，而对那些可以提供间接帮助的非直接视图都未加以考虑，即没有象静态算法那样考虑到视图之间存在着相互生成和相瓦依赖的关系，所以在获取最优物化集的能力方面缺乏必要的保证1 2 2 视图维护算法在数据仓库中，随着基础数据源的更新，物化视图必须得到及时的更新维护，以保证查询结果的数据质量，这是数据仓库技术中极其复杂和重要的工作，得到了广泛的讨论1 1 4 6 ”视图维护最直接的方法垦根据视图的定义重新计算生成，这种方法算法非常简单，无器一直保持数据源和数据仓库的连接，但算法的时问和空间代价很大，即使数据源出现很小的变动，都要对整个视图进行重新计算，其效率很低，除非一些特殊情况或别无选择，一般情况下很少采用比较实用的方法是采用增量维护f 1 4 , 6 ”7 i 的方法，它根据数据源的更新信息，只计算视图的变化部分使视图得到刷新虽然算法较复杂，但维护效率得剑提高，。般情况f ，可以显著地降低算法的开销，加快视图的维护速度3东南大学博士学位论文增量维护算法中一个必须解决的问题，是在视图和数据源一致性维护中出现的“更新异常”1 7 ，为此yz h u g e 等人首先针对单一数据源，提出了e c a 算法p ”，该算法采用补偿查询来解决更新问题其后，yz h u g e 又提出了s t r o b e 算法1 7 “”1 用以进行多数据源的数据仓库一致性维护，为了实现维护，算法需在数据仓库和数据源之间来回地多次传送查询和结果于是a g r a w a l 提出的s w e 印算法1 7 ”，没有采用查询补偿机制，而利用临时查询结果解决了视图一致性维护中出现的“更新异常”问题，克服了e c a 和s t r o b e 算法中补偿查询算法的不足以上算法在网络拥塞时，都会引起性能的显著下降因此为了降低更新算法的网络开销和提高算法的效率，研究人员在增量维护的基础上又提出了自维护的概念【7 ”“它充分利用了中间辅助视图或是视图表达式所含的信息，以及部分数据源的备份，使视图的维护可以无需或者很少访问源数据即可实现以上这些维护算法最初都是针对数据仓库脱机状态设计，没有考虑到在线维护的策略，而随着用户对数据仓库7 x 2 4 不间断运行需求的增长，脱机维护的方式很难满足这种需求，导致对不影响数据仓库业务处理的在线维护算法越来越受到广泛的重视 8 - 9 - z 对于在线维护而言，它的核心技术在于：在保证系统查询响应性能的同时，完成数据一致性的维护。而选择适当的维护算法和维护时机显得非常重要从维护操作时机选择来看，即时更新和周期更新是两种比较常见的方法 7 3 a 3 ，而在具体实现中，为了保证查询数据的一致性，往往需要通过多版本控制的办法来支持查询与更新的并发 a 4 - - 9 0 1 其中d c i u a s $ 提出了一个2 v n l 算法 8 4 ”j ，它采用当前版本和影子版本分别负责物化视图的查询和维护：当前版本只允许进行读操作，不允许更新，所有的更新操作都在影子版本上进行当影子版本提交后，当前版本被废除，影子版本成为当前版本，以后的更新操作将在新的影子版本上进行，从而可以在线实现一致性维护但由于该算法只采用两个版本，则在版本切换时需要当前版本的o l a p 查询结束，同时影子版本的更新也要完成，否则影子版本无法提交为此文献 8 6 - - 8 8 1提出了多版本控制的改进算法，解决2 v n l 算法的不足，然而其空间开销和版本维护成本将是非常巨大，非一般数据仓库所能普遍采用和即时更新、周期更新不同，延迟更新” ”将视图的更新维护推迟到查询发生时刻进行可避免大量无用的更新。作为一种高效的维护方式，也得到很多研究人员的关注【s x8 9 “】，为在线条件下实现视图的更新和查询数据的一致性提供了一条新径，但也造成部分查询的速度很慢。等待时间过长由此可见关于物化视图相关技术经过近十年的研究，取得了相当的成果，同时也存在很多问题需婴解决，研究并解决上述诸多问题的途径具有十分现实的意义为此本论文将以现有的研究成果为基础，对物化视图的相关问题进行深入的研究1 3 研究的内容本论文研究工作的重点是，在数据仓库在线条件下对物化视图相关算法进行深入的研究，包括物化视图的在线选择算法、动态调整，在线维护等算法( 1 ) 静态物化视图选择的预处理算法研究在对静态物化视图选择算法深入分析的基础上，研究一种预处理算法，使之能有效地对静态选择算法需璺遍历的对象空间( 即候选视图集) 进行压缩，从而以较小的算法开销，获得一个视图总代价较优井动态地反映用户查询分布变化的物化视图集其目的是克服静态算法在时间复杂度存在的不足，使算法能够适用于在线运行，满足物化视图动态调整的应用需求在这方面研究的主要内容包括：从用户查询集出发，提出一种候选视图立方格构造算法c v l c 。它利用多维数据集中查询的稀疏性对数据立方格图节点进行合理的筛选，获得+ + 个在节点数量上得到较大约减的候选立方格图，作为静态物化视图选择算法的输入证明c v l c 构建的格罔所对应候选视图集对物化视图选抒具有算法的充分性和必要性针对多维数据集中数据稀疏性，提出一种可以有效压缩候选视图数蕈的启发式算法c v f , 它能进步对视图的搜索空间进行有效约减而获得一个更加精简的候选视4第一一章引言图集利用系统运行日志和各种统计信息实现用户查询集的动态调整，及时真实地反映用户查询分布的变化，另外算法中剩用假设检验来有效地降低查询视匿l 选择抖动现象，并从数理统计的角度构建q s d m 算法理论基础最后将所研究的上述算法与经典的b p u s 算法进行对比实验，以验证算法的有效性( 2 ) 基于c a c h e 机制的物化视图选择算法的研究现存的基于c a c h e 机制的物化视图选择和动态调整算法都是基于内存机制的简单移植，均未考虑物化视图从硬盘回读的代价，即对于基于硬盘的c a c h e 机制没有考虑这样一个重要因素：即使硬盘中有直接的物化视图存储，其读取同样需要代价为此本文研究一种新的代价模型，对现有的物化视图动态选择算法进行改进，提出一种基于c a c h e 的动态物化视图置换算法在这方面研究工作具体包括以下几部分内容：分析了完整c a c h e 机制实现的组成，以及c a c h e 置换算法所处的核心地位对影响c a c h e 效果的各种因素和进行c a c h e 保存的目标进行充分的考虑，建立一个合理查询代价和物化效益模型，在此基础上提出基于空间约束下的物化视图c a c h e 置换算法d m v r 实时对发生的壹询进行评估和比较，选择那些物化效益较差的予以淘汰。以腾出足够的空间保存那些具有更好物化价值的查询结果 对算法的关键变量一物化效益测度进行充分的讨论。并就其实时频度的计算提出一种新的算法a i f , 用以真正客观地反映用户决策查询的动态变化情况对d m v r 算法解的最优性进行研究。由于该算法能够保证：在一定约束条件下每次的c a c h e 数据置换都是遵循物化效益增加为准则，从而在一定近似条件下，可以证明d m v r 算法获得的物化集具有算法最优性从算法的复杂性讨论出发，提出一种算法复杂度更低的d m v r - i d l e 算法，它将d m v r 中开销段大的排序部分改为i d l e 方式运行，以获得更高的执行效率和更小的运行代价 通过实验将d m v r算法，d m v r - i d l e 算法与d y n a m a t 算法进行性能的比较，对算法的实际效果予以验证最后对c a c h e 机制下维护代价问题进行研究，讨论以查询总代价和维护总代价的综合值最小为目标的物化视图动态选择问题，( 3 ) 静态物化集的动态c a c h e 优化研究从实现机制的角度来看，物化视图选择方案大体上可分为静态算法和动态算法田3 4 】两类，其节静态篝法都基于用户查询分布预知的假设基础之上，充分地利用各视图相互生成相互影响的内在联系，选择的物化视图不仅考虑对查询的影响，而且考虑对其他视图的帮助，所以静态算法相对而言理论基础比较坚实，算法有着严格的复杂度和最优性方面测度，更着眼于对最优性的逼近，然而对查询分布的变化，特副是决策支持系统中常见的即席查询，其响应能力存在明显的不足；而动态算法则可以较好地适用于这种情况，它借鉴了虚拟内存管理机制和数据库缓存的成熟方法并将它应用于物化视图的动态选择和存储，它基于每一次查询结果应尽最大可能地被重复利用的原则，以最大限度地抵销其生成时的开销，具有算法简单、高效的使用特点，然而其实现的模型较为粗糙，没有能够考虑物化视图间的内在联系，所以在最优物化集的获取方面与静态算法有着一定的差别本文对静态算法与动态算法的结合进行探讨，将c a c h e 机制的高效快速和静态算法获取最优解的优势相结合。从而克服模型粗糙和动态响应性能的不足，实现两种摹于不同机制算法的优势互补具体分为以下几个部分讨论：建立基于静态物化集的动态物化视图效益模型，将查询总代价最小的目标转换为视雷的动态物化总效益最大为目标在此基础上提出基于空问约束的d c o s 算法，用于选择动态物化集以弥补静态物化集动态适应能力的不足然后对算法解的最优性和复杂性进行相应的讨论借鉴现代操作系统中文件回收箱的) 0 t 帮j ，利用系统剩余硬盘空间作为c a c h e 空间，并能在系统剩余空间比较紧张时淘汰部分物化视图主动释放空间，而在系统剩余空间增多时可以扩大c a c h e卒问，使更多的视图得到物化针对动态物化视图的维护问题进行研究基于失效机制提出一种d c o - s m 算法，该算法不考虑动态物化集的更新，c a c h e 中的物化视图一旦过时只是简单地予以淘汰，让出空间保存更多的新鲜视图，也避免了额外的维护对系统造成太大的负担将经d c o - s 算法东南大学博士学位论文优化的物化集与仅有静态物化集的情况进行了一系列性能的比较实验，即进行在动态物化集+ 静态物化集共同支持下与在静态物化集单独支持下的系统查询性能的比较。验证了算法的有效性，并指出实验中的一个发现：由于结合了c a c h e 机制，可以一定范围内有效地克服静态物化视图空间性能的饱和效应( 4 ) 物化视图的在线维护策略研究物化视图在线维护的目的在于满足用户对查询数据时新性和一致性的前提下，以不影响数据仓库提供正常服务的方式完成物化视图的更新显然，在线维护增加了系统的工作负荷，过多的更新将造成系统查询性能的下降，影响数据仓库的服务效率延迟更新是将物化视图的更新延迟到相关查询发生时进行，这种方式更新的效率很高，可保证每次更新的有效性，从总体上降低了系统的开销这为在线条件下实现视图的更新提供了一种新的方案，但也会造成部分查询的响应速度变慢，等待时闻过长为此本文提出一种机会更新的方式。并将之与延迟更新相结合。尽最大可能减少在线维护对系统性能的影响，确保查询数据的一致性具体内容包括：分析数据仓库在线条件下，数据一致性维护的问题以及对用户查询响应性能产生的负面影响，并从一个较高的层次，提出主要的解决思路建立考虑延迟更新影响的查询代价模型，然后以满足查询对数据一致性和时新胜的前提下，提出一种在线更新算法o d u a ，它引入了机会更新机制，充分利用系统的空闲时间对物化视图进行随机维护减少查询发生时延迟更新的需求，在整体上提高查询响应速度具体阐述组成o d u a 算法的几个子算法的出发点和基本算法思想，包括实时更新检测算法i u i m v 、机会更新算法o u m v 、延迟更新算法d u m v 和数据源批次更新算法d s b u ，设计一个单数据源在线维护的实验环境，将o d u a 算法与基本的延迟更新算法d e f e r r e d 进行比较，通过改变负荷水平、更新频度，检验两种在线维护算法的动态适应能力1 4 本文的创新点本文主要有以下几处创新点：( 1 ) 摹于立方格图和多维数据集查询的稀疏性及数据的稀疏性，提出了一种候选视图集的构造算法和筛选算法，而得到一种有效的预处理方法，可以显著地降低静态物化视图选择算法的时问复杂度，使之适合于在线运行；并从理论角度证明了其中核心算法的有效性( 2 ) 建立一个具有良好理论基础的c a c h e 效益模型和一个新的物化效益测度值，以此提出了一系列考虑各种约束条件的动态c a c h e 改进算法，用于c a c h e 置换机制的实施，并证明算法解在一定假设条件f 具有的最优性( 3 ) 将动态c a c h e 机制和静态选择算法进行结合，在静态算法获得近似最优的物化集基础上，额外地选择一个实时变化的动态物化集，有效地提高了物化视图集的动态适应能力，并在一定程度上克服了静态物化集的空间性能饱和效应( 4 ) 提出机会更新的维护方法并将之与延迟更新方法进行自效结合，而获得一种更为合理的在线维护镱略，克服了延迟更新单独使用时存在的不足，实现系统查询响应性能与数据时新性、数据傲性之间很好的平衡1 5 本文的组织结构本文宅婴研究数据仓库在线条件下，物化视图集的动态选择和在线维护，全文分为三个组成部分，第部分包括第二章，主蛰概璺地阐述有关物化视图的预备知识，第二部分包括第三章、第州章和第 革，重点论述在线条件f ，物化视图的选择调整问题，第三部分则对物化视图在线维护策略6第一章引言进行研究各章节具体安 如下：第一章为引言，介绍数据仓库中物化视图技术研究的意义和应用需求分析，说明本论文研究的背景和来源详细描述了物化视图研究的国内外研究现状，并指出现有的各种方案、算法的特点和存在的不足，然后说明论文主要的研究内容和创新点第二章为预备知识，较为系统地介绍了数据仓库、决策支持系统、o l a p 以及物化视图的基本概念，并讲述了它们之间相互联系、相互影响的关系，为充分了解物化视图技术的相关问题提供必要预备知识然后详细介绍基于不同机制的两种选择算法静态选择算法和动态选择算法，着重描述基于不同的目标函数和约束条件下，算法的基本思想和针对数据仓库在线条件下进行的调整和改进最后较详细地论述了增量维护、自维护以及即时更新和延迟更新等各种不同的维护方式和不同的维护策略的基本原理和应用的背景第三章讨论一种物化视图选择的预处理算法，针对物化视图集动态调整的需求，指出静态选择算法用于在线调整所存在的不足，然后分析了数据仓库中多维数据集所具有查询稀疏性特点和数据稀疏性特点。由此提出候选视图集的构造算法和筛选算法，用于构造一个得到很大程度约减的候选视图集本质上看，这个候选视图集来自对用户查询集处理的结果，为了保证最终所选择的物化视图能够正确反映用户查询分布的变化，本章还提出用户查询集的动态调整算法，对用户查询集及时进行调整第四章提出一种动态c a c h e 的置换算法，用以物化视图的动态选择首先分析了物化视图动态算法的机理和特点。以及与物化视图静态选择算法的不同，然后指出动态选择算法的不足由此建立一个新的更为合理的视图物化效益模型，在这基础上可获得一个用于进行c a c h e 置换的物化效益测度值，并以此为核心提出动态算法的改进一d m v r 算法本章对测度值的计算也进行详细的讨论最后证明该算法可以获得近似的最优解，而对于算法的复杂性问题，提出了另一个算法d m v k - i d l e ，其算法运行效率更高，更加适合在线运行第五章对物化视图选择的动态算法与静态算法的结合进行较为系统而深入的研究首先详细务析了静态算法和动态算法两种不同机理的选择方法在性能方面的优劣，然后尝试着将c a c h e 机制的高效快速和静态算法获取最优解的优势相结合，克服了两者模型粗糙和动态响应性能方面的不足实验表明这种优化组合具有良好的效果，同时也发现由于结合了c a c h e 机制，可以一定范围内有煞。地克服静态物化视图空间一性能的饱和效应s p s e ，使通过增加物化空间进一步提高系统的查询响应性能成为可能另外。在c a c h e 机制的物理空间申请方面，借鉴操作系统中回收箱的实现机制，即充分利用系统的剩