（计算机软件与理论专业论文）基于p2p的视图维护架构及方法研究.pdf

摘。要数据仓库是集成了多个分布式、自治或异构数据源上的信息的数据储藏室，主要用来存储供查询和决策分析用的集成化信息。随着数据仓库应用的不断扩展和深入，数据仓库从脱机维护到联机维护，从面向单用户到为多用户服务，是一个必然的过程。在这一发展过程中，数据仓库的实化视图维护是保证整个系统可用性和可靠性的一个关键问题。实化视图维护是指在数据仓库为用户提供服务的同时，在数据源的原始数据发生改变时，实时地将这种变化反映到数据仓库中，使相应的实化视图得到及时的刷新本文首先阐述了数据仓库中实化视图维护的基础知识，包括视图的四个一致性级别、数据仓库体系结构、数据仓库视图维护策略及实化视图的分布等内容。介绍了p 2 p 这种新近兴起的网络模型的主要特点，分析了传统的视图维护模型的主要不足。本文的主要贡献与创新是针对传统的c s 视图维护模型中负载失衡和维护瓶颈问题，借鉴p 2 p 的对等思想，将p 2 p 引入到视图维护的体系结构中，构建了基于p 2 p 的分布式、并行、主动视图维护架构p 2 p a v m ，设计了全新的视图维护架构及其工作机制，探讨了节点管理与路由等关键问题，对数据仓库和数据源的工作任务进行了重新部署：首先，让每个d s 节点除了提供数据存储功能之外，还能主动地进行更新后的查询和维护工作，即还扮演了传统的c s 模型中d w 节点的角色。同时，为了保持节点的自治性，系统中的d s 节点只需对其衍生关系的更新主动发起维护，有效地实施了计算的分布与负载的均衡，进一步扩充了并行计算能力。针对p 2 p a v m 视图维护架l 构的环境特点，提出了基于p 2 p a v m 架构的并行多维视图维护方法。该方法在联机补偿维护方法中引入自维护方法和相关性更新处理，将这三种不同类别的算法有机地融合为一体。算法首先由更新节点对更新进行相关性检测，将不影响实化视图状态的不相关更新直接抛弃。对于相关更新，则由更新节点根据各相关视图的维护类型，确定对各相关视图进行并发联机补偿维护或自维护。同时，该方法修正了s w e e p 算法只能顺序处理的瓶颈，赋予其并行处理能力，并针对p 2 p a v m 架构提出了p p p s w e e p 算法。对于单个更新，p p p s w e e p 算法通过并行执行左右扫描过程来完成维护计算；对于并发更新，该算法通过延缓当前更新的计算，递归地处理并发更新的计算。增加了系统对更新的吞吐能力，减少了维护的延迟。此外，在对维护查询进行分解时，除了使用p p p s w e e p 算法的左右并行扫描方法之外，本文还提出了另一种可供选择的维护查询并行分解方案。该方案在增量式视图维护的基础上对维护查询进行分解，将分解后的维护子查询同时发送给相关节点，而这些节点可以相对独立地同时对维护子查询进行计算，进一步以并行的方式提高维护实化视图的效率。该方案提出了自顶向下地构造分解树、自底向上同层节点并行计算维护子查询结果的方法，从查询本身实施对实化视图维护的优化。最后，本文针对分布式环境下模式与数据全面并发更新的典型情形，讨论了p 2 p a v m 架构中的并行维护关键技术，分析了在全面并发更新条件下导致的维护异常问题，并给出了基于时态演算的并发更新侦测策略和用于解决乱序提交的提交代理机制。关键词：实化视图，p 2 p ，并发更新，增量维护，相关更新a b s t r a c tad a t aw a r e h o u s e ( d w ) i sar e p o s i t o r yo fi n t e g r a t e di n f o r m a t i o nf r o md i s t r i 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 u r c e s ( d s ) i ne f f e c t ，t h ew a r e h o u s es t o r e so n eo rm o r em a t e r i a l i z e dv i e w so ft h es o u r c ed a t a t h ed a t ai st h e nr e a d i l ya v a i l a b l et ou s e ra p p l i c a t i o n sf o rq u e r y i n ga n da n a l y s i s ，w i t ht h es p r e a do fd wa p p l i c a t i o n ，i ti sn e c e s s a r yf o rd wt oh a v eb e e nd e v e l o p e df r o mo f f - l i n et oo n l i n e ，f r o ms i n g l eu s e rt om u l t i p l eo n e s a n di no r d e rt ok e e pt h ev i e w si nt h ed a t aw a r e h o u s eu pt od a t e ，i ti sn e c e s s a r yt om a i n t a i nt h em a t e r i a l i z e dv i e w si nr e s p o n s et ot h ec h a n g e sa tt h es o u r c e s ，w h i c hi sa ni m p o r t a n ta n dk e yp r o b l e mt og u a r a n t e et h eu s a b i l i t ya n dt h er e l i a b i l i t yo ft h es y s t e m f i r s t l y ，t h ef u n d a m e n t a lc o n c e p t so ft h em a t e r i a l i z e dv i e w sm a i n t e n a n c e ，s u c ha st h ec o n s i s t e n tl e v e l so ft h ev i e w sa n dt h es t r a t e g i e so fv i e w sm a i n t e n a n c ea r ei n t r o d u c e d t h ee m p h a s i si sp u to nt h ea r c h i t e c t u r ea n dt h ei n c r e m e n t a lv i e wm a i n t a i n i n gs t r a t e g y ，w h i c hc a nb es i g n i f i c a n t l yc h e a p e rt h a nr e c o m p u t i n gt h ev i e wf r o ms c r a t c h ，e s p e c i a l l yi ft h es i z eo ft h ev i e wi sl a r g e rc o m p a r e dt ot h es i z eo ft h ec h a n g e t h e n ，t h ec h a r a c t e r i s t i c so fp 2 pn e t w o r km o d e la r ei n t r o d u c e da n dt h ed i s a d v a n t a g e so ft h et r a d i t i o n a lv i e wm a i n t a i n i n gm o d e la r ea n a l y z e d t h em a i nc o n t r i b u t i o no ft h i sd i s s e r t a t i o ni st h en e wm o d e lo fv i e wm a i n t e n a n c eb a s e do np 2 pa n dt h en e wa l g o r i t h mo fv i e wm a i n t e n a n c e a sf o rt h em o d e lo fv i e wm a i n t e n a n c e ，m o s tc u r r e n tw o r ka r eb a s e do nt h ew h i p s ( w a r e h o u s ei n f o r m a t i o np r o t o t y p ea ts t a n f o r d ) ，w h i c hw i l ll e a dt ot h eo v e r l o a da n de v e nc r a s ha tt h ed a t aw a r e h o u s ew h e nt h en u m b e ro fu p d a t e sa r en u m e r o u s ，b e c a u s ew h i p si sat r a d i t i o n a lc sm o d e lw h i c hh a si t si n h e r e n tl i m i t a t i o n s t oa d d r e s st h ep r o b l e m s ，t h em o d e lo fp 2 p b a s e da c t i v ev i e wm a i n t e n a n c e ( p 2 p a v m ) i sp r o p o s e d ，w h i c hc a nn o to n l ye x p l o i tt h ep o t e n t i a lm e r i t so fp 2 p ，b u ta l s oo v e r c o m et h ep r o b l e m so ft r a d i t i o n a lv i e wm a i n t e n a n c em o d e l s ( e go v e r l o a du n b a l a n c eb e t w e e nd a t aw a r e h o u s ea n dd a t as o u r c e ，l a c k i n go fs c a l a b i l i t ye t c ) w ed e p l o yt h ea r c h i t e c t u r eo fp 2 p a v ma n di t sp e e r s c o m p o n e n t s ，a n dd e s c r i b et h ek e yi s s u e so fi m p l e m e n t a t i o ns u c ha sw o r k i n gm e c h a n i s m ，d y n a m i c a lm a n a g e m e n ta n dt h er o u t i n go fp e e r se t c i nt h ep 2 p a v ma r c h i t e c t u r e ，t h ed sp e e ro nw h i c hu p d a t eo c c u r r e dw i l lc o n t a c to t h e rd sp e e ro ni t so w ni n i t i a t i v ea c c o r d i n gt ot h em e t a d a t a ，a n dc o o p e r a t ew i t ht h e mt of i n i s ht h eq u e r ya n dt h em a i n t e n a n c e a f t e rg e t t i n gt h em a i n t e n a n c er e s u l t ，t h ed sp e e rw i l lc o m m i tt h er e s u l tt od wa c t i v e l y w h i l et h ed wp e e rt a k e sr e s p o n s i b l ef o rt h ec o l l e c t i o na n dr e c o r do ft h em e t a d a t as u c ha sv i e wd e f i n i t i o n ，d sp e e ri n f o r m a t i o ne t c t h u s t h ed wp e e rc a nb el i b e r a t e df r o mt h eh e a v yw o r k l o a d b a s e do nt h ep 2 p a v ma r c h i t e c t u r e ，ap a r a l l e la n dm u l t i d i m e n s i o n a lv i e wm a i n t e n a n c ea l g o r i t h mi sp r o p o s e d ，t h ea l g o r i t h mi n t r o d u c e sv i e ws e l f - m a i n t e n a n c ei d e a si n t ot h eo n l i n ec o m p e n s a t i n gm a i n t e n a n c e ，i n c o r p o r a t i n gr e l e v a n tu p d a t ed e t e c t i n ga l g o r i t h m ，w h e na nu p d a t eh a so c c u r r e da tad s ，t h er e l e v a n tu p d a t ed e t e c t i n ga l g o r i t h mw i l lb ef i r s t l yu s e dt od e c i d ew h e t h e rt h eu p d a t ee f f e c t sm a t e r i a l i z e dv i e w so rn o t i ft h eu p d a t ed o e sn o ta f f e c ta n ym a t e r i a l i z e dv i e w s ，t h e ni ti sd i s c a r d e di m m e d i a t e l y o t h e r w i s e ，t h ed sp e e ro nw h o mt h eu p d a t eo c c u r r e dw i l li n c r e m e n t a l l ym a i n t a i nt h er e l e v a n tm a t e r i a l i z e dv i e w sa c c o r d i n gt ot h et y p eo ft h ev i e w m e a n w h i l e ，an e wa l g o r i t h m - - p p p s w e e pa l g o r i t h mi sd e v e l o p e d ，w h i c ho p t i m i z e st h ep e r f o r m a n c eo ft h es w e e pa l g o r i t h m ( s w e e pi saw e l l k n o w na l g o r i t h mw h i c hm a i n t a i n sv i e w so n l i n eb ym e a n so fc o m p e n s a t i o n ) f r o mt w oa s p e c t s o nt h eo n eh a n d ，p p p s w e e pe x e c u t e st h el e f ta n dr i g h ts w e e p si np a r a l l e lf o ro n es i n g l eu p d a t e o nt h eo t h e rh a n d ，p p p s w e e pr e c u r s i v e l yi n c o r p o r a t e sa l lt h ec o n c u r r e n tu p d a t e se n c o u n t e r e dd u r i n gt h ee v a l u a t i o no fa l lu p d a t e t h ea l g o r i t h mr e e u r s i v e l ye v a l u a t e sar e l e v a n tt o n e t e n tu p d a t eb ys u s p e n d i n gt h ec u r r e n te v a l u a t i o n i ti n c o r p o r a t e sa l lt h em i s s i n gt e r ma n dt h e nr e t u r n st ot h eo r i g i n a lq u e r y ，a f t e rm o d i f y i n gi tt or e f l e c ta l lr e l e v a n tc o n c u r r e n tu p d a t e s f u r t h e r m o r e ，t h ed e c o m p o s i t i o na n dt h ee x e c u t i o no ft h em a i n t e n a n c eq u e r yi np a r a l l e la r ee x p l o r e d t h e r e b y ，t h ea l g o r i t h mm a i n t a i n sv i e wc o n s i s t e n c yw i t ht h el e a s tt i m eo v e r h e a da n dp r o m o t e st h ee f f i c i e n c yg r e a t l y d u r i n gm a i n t a i n i n gt h em a t e r i a l i z e dv i e wi nt h ed a t aw a r e h o u s e ，h o wt oe f f i c i e n t l yh a n d l et h ec o n c u r r e n tu p d a t e si sa ni m p o r t a n ta n di n t r a c t a b l ep r o b l e m t h et y p i c a ls i t u a t i o n st h a ts c h e m ec h a n g em i x e sw i t hd a t au p d a t e sc o n c u r r e n t l ya r ed i s c u s s e da n dt h er e a s o n sw h yc o n c u r r e n tu p d a t e sr e s u l ti nv i e wm a i n t e n a n c ea n o m ya r ea n a l y z e d f i n a l l y ，at e m p o r a lm e t h o df o rd e t e c t i n gc o n c u r r e n tu p d a t e sa n dr e l a t e du p d a t e si sp r o p o s e d ，a n da ne n h a n c e dc o m m i ta g e n tt od e a lw i t hn o n - o r d e r l yc o m m i tp r o b l e mi sd e s i g n e dc o n s e q u e n t l y ，t h ec o n s i s t e n c yb e t w e e nd a t aw a r e h o u s ea n dd a t as o u r c ei sg u a r a n t e e dw i t ht h el e a s tt i m eo r e r h c a d k e y w o r d s ：m a t e r i a l i z a t i o nv i e w ；p 2 p ；c o n c u r r e n tu p d a t e ；i n c r e m e n t a lm a i n t e n a n c er e l e v a n tu p d a t ev中山大学博士论文：基于p 2 p 的视图维护架构及方法研究第1 章引言1 1 研究背景计算机的发展把人类推入了信息社会，信息的增长呈现指数上升。随着数据库技术的不断发展和数据库系统的广泛应用，数据库中存储的数据量急剧增大，全世界每天新存入数据库中的数据量超过万兆字节。无论是商业企业、金融机构，还是科研机构、政府部门，在过去若干年的时间里都积累了海量的、以不同形式存储的数据资料。虽然d b m s ( d a t a b a s em a n a g e m e n ts y s t e m ) 提供了一些对数据处理的简单功能，但目前所能做到的大部分操作还只是对数据库中已有的数据进行存取、增添、删除、修改等，只能看到这些数据的一些表面的东西，人们通过这些数据所获得的信息仅仅是整个数据库所包含的信息量的一部分，而不能看到隐藏在数据之间的更重要的信息，即关于这些数据的整体特征的描述和发展趋势的预测等等。但由于这些数据资料十分繁杂，而且缺乏集中存储和一致性的管理，从而导致这些数据不能为预测和决策服务提供有用的信息，而隐藏在数据之间的信息对决策过程具有尤其重要的意义。于是就需要一种能够对数据进行采集、处理、存贮的技术，来为更深层次的分析和处理提供数据。而这种技术正是数据仓库( d a t aw a r e h o u s e ，d w ) 技术，它是9 0 年代初期，由w h i n m o n 在其里程碑式的著作b u i l d i n gt h ed a t aw a r e h o u s e ) )中提出的概念【1 1 ，数据仓库的研究和应用开始得到了广泛的关注。数据仓库是集成了多个分布式、自治或异构数据源( d a t as o u r c e ，d s ) 上的信息的数据储藏室，主要用来存储供查询和决策分析用的集成化信息。数据仓库可将分布的不同异构数据源中的数据，按主题选择出与决策有关的信息，预先经过提取、转换、过滤等操作，并与相应数据源中的其他数据进行合并，最终存放在一个中央数据库中。人们在查询时可直接访问中央数据库，而不必访问其他数据源。数据仓库提供的这种异构数据源的集成方法，对快速响应联机分析处理f o n l i n ea n a l y s i sp r o c e s s i n g ，o l a p ) 查询和提高对决策支持系统( d e c i s i o ns u p p o r t e ds y s t e m ，d s s ) 的性能支持都是极为重要的。但由于数据仓库主要是用来供企业进行d s s 决策分析之用，其中存储了大量的历史数据，因此，在应用方面对数据仓库的查询性能提出了较高的要求。数据仓库技术是分布式异构数据库系统集成的一种较为先进的解决方案，目前，数据仓库技术正广泛应用于证券、银行、客户服务及营销、税务、保险、电信、医疗保健等领域。如福特汽车公司、m o t o r o l a 、a t & t 等在高端信息系统中也应用到数据仓库技术。而目前最大的数据仓库系统当数n c r 公司建立的基于其t e r a d a t a数据库、拥有2 4 t b 数据量的美国最大的零售连锁店沃尔玛数据仓库系统，并产生r 业界经典的“尿布与啤酒”的故事。中山丈学博：匕论文：基于p 2 p 的视图维护架构及方法研究随着数据仓库技术在现代信息领域中的广泛应用，如何建立一个数据仓库并正确高效地维护数据仓库数据，得到人们越来越多的关注。其中，核心问题之一就是如何傈证从数据仓库读取到的数据能反映正确的数据源状态。该问题可继续划分为两个子问题：1 ) 如何保证数据仓库数据与数据源数据的一致性，特别是在数据来自于多个自治、异构数据源的情况下；2 ) 如何保证在对数据仓库数据进行更新的同时从数据仓库读取数据时的数据一致性。本文主要针对前者展开讨论，文献 2 】对后者有详细的描述。从异地数据源拙取的为本地查询分析之用的完整信息存储即为数据仓库。当d s数据发生变化时，d w 数据应该相应地更新。通过维护d w 中定义的一组来源于d s中基表数据的实化视图( m a t e r i a l i z e dv i e w s ，m y ) 可以实现这种更新传递。数据仓库中的数据可以被看成由许多基础数据源生成的实化视图，实化视图主要用于加快大量数据的查询处理。所谓实化视图，是指根据某种视图定义，将来自不同数据源的数据，预先经过转换、过滤和集成等操作，使该视图最终含有大量数据，并存储在数据仓库的袁中。这样，一次生成就可以供多次使用。实化视图在基表访问代价较高的系统中很有用，如分布式数据库、移动数据库等：在对视图访问效率要求高的应用中也非常有用，如数据仓库就是比较典型的应用之一。从广义上讲，数据仓库中的数据都可以看作是以实化视图的方式来存储的。实化视图不仅是作为数据仓库中数据存储的基本方式，实化视图概念的提出，也有利于提商数据仓库的查询性能。首先在数据仓库中引入实化视图的概念，可以通过物理上存储视图定义的数据来减少联机分析处理的查询时间。这是由于o l a p 查询一般需要涉及大量的数据，而且需要对数据进行投影、联接、分组等复杂处理，而实化视图预先针对可能的o l a p 查询对数据仓库中的基本数据进行投影、联接、分组等处理，建立许多的实化视图并进行物理存储。这样，在查询时可直接查询已预先计算并存储的实化视图，从而可以快速响应o l a p 查询。其次，可以采用实化视图来进行数据仓库中的粒度划分及数据分割。粒度是指数据仓库中数据单元的详细程度和级别，不同粒度级别的数据用于不同程度的d s s分析处理。数据分割是指将数据源按照逻辑分割成较小的、可以独立管理的物理单元进行存储。例如，按时间对数据进行分割，即将同一时间段内的数据组织在一起，并在物理上也紧凑地存放在一起，这样就可以根据不同的查询需求大大减少数据检索的范围，从而达到提高系统查询性能的要求。同时，实化视图的引入，也带来了一些问题，其中最突出的就是实化视图的维护问题。由于实化视图拥有自己的数据，但实化视图一般不具备自动更新功能。因此，当数据源由于插入、删除和修改而发生变化时，就会导致导出的实化视图与其不一致。所以当数据源发生变化时，就需要对相应的实化视图进行更新，以维持实中山大学博士论文：基于p 2 p 的视图维护架构及方法研究化视图与数据源的一致性，确保访问查询的结果正确，这个过程就是实化视图维护。由于数据仓库中存储的是部分原始数据的拷贝和实化视图集合，它并不能完全满足用户的所有查询。对于某些o l a p 查询，数据仓库必须通过访问源数据库才能给出最终的查询结果。如何保证这类查询的正确性，是一个非常值得研究的课题。因而，视图维护和一致性维护也成为数据仓库中的重要问题之一。在传统数据库环境下，视图维护问题已得到了充分的研究一j j ，但它们大都建立在视图管理器和视图定义系统控制上。当d s 上的数据发生变化时，系统通过对源表加锁并由监视器捕获源变化，然后由管理器把相应的结果发送给视图。然而在数据仓库环境下。其视图定义与源库是相分离的，数据仓库不能主动地捕获源数据库的变化，而只能等待源库的更新信息报告。因此，利用传统算法来维护数据仓库视图可能会使视图数据与d s 数据不致，为了补偿这种不一致，就需要采用新的方式对数据仓库进行实化视图的维护。本文在分析已有的视图维护算法的基础上，针对新环境下的视图维护问题，提出了新的视图维护架构和维护算法。另一方面，在数据仓库模型方面，就目前而言，大多采用的是c s 模型。在c s模型中，大部分时间里很多客户机即d s 端是空闲的，它们拥有大量没有使用的磁舷存储能力和计算能力。采用何种方式才能最大限度地使用这些计算机? 在当今的全球经济形势下，人们努力搜寻一种提高处理能力而不用在软硬件上进行更多投资的方法，试图通过计算机的联合获得更强大的能力。随着对等连接的概念和有效的资源利用的逐步深入研究，对等计算( p e e r - t o ，p e e r ，p 2 p ) 的应用开始走向成熟，并与其它并行技术的研究趋势如网格计算等走到了一起。p 2 p 计算允许用户使用网络中集中的处理能力，帮助组织进行大量以前不能进行的计算工作。p 2 p 是一种新近兴起的网络模型，与传统的c s 模型比较，它在网络资源利用率、消除服务器瓶颈等多方面有明显的优势：1 ) p 2 p 模式最主要的优点就是资源的高度利用率。在p 2 p 网络上，闲散资源有机会得到利用，所有节点的资源总和构成了整个网络的资源，整个网络可以被用作具有海量存储能力和巨大计算处理能力的超级计算机。c s 模式下，纵然客户端有大量的闲置资源，也无法被利用。2 ) 随着节点的增加，c s 模式下，服务器的负载就越来越重，形成了系统的瓶颁，一旦服务器崩溃，整个网络也随之瘫痪。而在p 2 p 网络中，每个对等节点都是+ 个活动的参与者，每个对等节点都向网络贡献一些资源，如存储空间、c p u 周期等。所以，对等节点越多，网络的性能越好，网络随着规模的增大而越发稳固。3 ) 基于内容的寻址方式处于一个更高的语义层次，因为用户在搜索时只需指定具有实际意义的信息标识而不是物理地址，每个标识对应着包含这类信息的节点的集合。这将创造一个更加精炼的信息仓库和一个更加统一的资源标识方法。4 ) 信息在网络设备问直接流动，高速及时，降低中转服务成本。中山大学博士论文：基于p 2 p 的视图维护架构及方法研究5 ) c s 模式下的互联网是完全依赖于中心点服务器的，没有服务器，网络就没有任何意义。而p 2 p 网络中，即使只有一个对等节点存在，网络也是活动的，节点所有者可以随意地将自己的信息发布到网络上。因此，p 2 p 被认为是未来重构分布式体系结构的关键技术。通过对视图维护和p 2 p 的初步研究，我们认为，在数据仓库的视图维护思想中引入p 2 p 的技术模型和原理有助于另辟蹊径，在一定程度上突破目前视图维护效率的瓶颈。以p 2 p 这种新型的体系结构作为视图维护的模型基础可以发掘许多潜在的优势：首先，p 2 p 系统是自组织的、非集中式的，各节点是自治的、动态的。系统的鲁棒性、可用性和性能可随节点数目的增加而提高，系统的信息、带宽与计算资源随着节点的加入而不断丰富，因而系统的维护能力随之不断增强，而不像c s 模型中维护能力随d s 数目的增加丽减弱。在基于p 2 p 的视图维护模型中，产生更新的d s 节点将根据d w 节点提供的相关信息产生相应的维护查询，并对维护查询进行分解得到维护子查询。同时，该节点还主动联系维护节点，对其发送维护子查询消息，让它们并行地去完成各自的维护工作。其次，由于各个d s 节点功能与职责相同，它们之间的交互直接而对等，可以高效地利用系统的资源。发起更新的d s 节点将根据d w 节点提供的相关信息，自主地联系其他d s 节点，协同完成查询和更新维护工作，并将维护后的结果主动发送给d w 节点。而d w 节点主要负责收集和记录视图定义、d s 节点信息等元数据。从而使得d w 节点在很大程度上从数据集成功能中解放出来，进而更好地响应数据分析的计算需求，同时这种方法克服了传统视图维护模型中数据仓库和数据源负载失衡及可伸缩瓶颈等问题。此外，由于信息不再集中于某些服务器中，对它们的更新也更为方便，这也有助于提高信息的动态质量。因此，研究新的维护体系结构是改善视图维护性能的有效直接的手段。本文将p 2 p 思想合理地引入到视图维护的体系结构中，构建基于p 2 p 的分布式并行视图维护架构：并在此基础上，进一步对视图维护的一致性问题进行深入研究，以确保数据仓库与数据源的一致性。这些工作对于保证数据仓库中数据质量以及某些应用领域对数据的特殊时态性要求等，都具有十分紧迫的现实意义。1 2 研究现状数据仓库技术是近年来数据库领域中发展起来的新技术。数据仓库可以看作是一个用来存储预查询处理结果的全局性仓储，这些存储在数据仓库中的预查询结果即为实化视图。当数据源中的数据发生变化，数据仓库中的实化视图也应该进行相应的调整，即进行实化视图的维护。目前，大多数数据仓库产品在实化视图维护时往往采用脱机方式，利用晚上和周末的时间批量地装入新数据。然而这在很多情况中山大学博士论文：基于p 2 p 的视图维护架构及方法研究f 是不合适的，比如对于大型跨国公司，其子公司遍布全球，不可能有一个统一的“晚上”或“周末”。而在学术界，人们则关注于数据仓库实化视图的动态维护技术，即在前台数据源工作的同时，数据仓库系统能够动态地检测到已发生的修改并把这些修改增量地反映到数据仓库的实化视图中。要做到这一点并同时保证数据仓库的一致性是非常困难的，因此，实化视图的维护问题在学术领域得到了广泛的重视，成为数据仓库技术最重要的研究领域之一。实化视图维护作为数据仓库维护技术中的一个关键技术，其研究已成为数据仓库研究的一个专题。在国外，相应的研究已得到a n d e r s o nf a c u l t ys c h o l a r 基金、s t a n f o r d 大学、r o m el a b o r a t o r i e s 、d i g r a le q u i p m e n t 公司以及i b m 公司等的赞助。国内方面，主要有国防科技大学组织一批人进行维护更新理论方面的研究，并取得一些成果：华中科技大学侧重在产品开发方而，并得到国防科技预研项目的支持，1 2 1国外关于实化视图维护的研究在关于实化视图维护方面的研究工作中，具有代表性的是s t a n d f o r d 大学的数据仓库研究小组。a g u p t a l 3 1 为实化视图中的每个元组增加了一个c o u n t 属性，利用这属性跟踪实化视图中每个元组的来源情况，并对其进行相应的插入、删除操作。斯坦福大学的研究小组还提出了一个两层数据仓库体系结构模型，并据此模型做了许多研究工作 6 , 7 1 。实化视图维护可以采用重新计算和增量维护这两种方法，重新计算是每次当原始数据发生改变时，在数据仓库端对实化视图用更新后的基表从头计算，不再使用实化视图中原来的结果。这种方法会导致很大的额外存储和维护代价，而且由于数据仓库的空间是有限的，这种做法有时也是不可能的。因此，近年来对实化视图采用增量维护的方法比较多。所谓视图的增量维护是指当数据源中的数据发生变化时，通过已存在的视图和基关系的变化，只计算出视图的更新部分，用它去更新旧视图得到新视图，没有改变的那部分视图不必再重新计算。实验证明，当基表更新只占整个基表的较小比例时，增量维护比重新计算的性能要好。而且，对于增量视图维护的研究已经取得了许多成果 】。文献 1 0 】是一篇经典论文，yz h u g e 在这篇文献中论述了如何通过“补偿查询”对d w 中的实化视图进行刷新维护，以保证与源数据的一致性，并针对单个数据源的数据仓库提出渴求补偿算法( e a g e r c o m p e n s a t i n g a l g o r i t h m ，e c a ) ，其基本思想是当发送给数据源的查询还未返回就又收到了新的更新消息时，仓库将记录下这些更新事件，并在以后发送一个补偿查询来消除其不一致性。该算法对更新请求、补偿查询和报送查询结果三个过程发生的时序关系的保持要求严格。例如，在d s 收到补偿查询之前发生的新的更新操作必须在d w 处理这次补偿查询结果之前得到相应处理，即进行补偿。并且该算法不要求视图定义中包含每一个相关基表的主属性，但视图中可能包含重复元组，此时对基表进行删除操作，视图维护过程可能出现异中山大学博士论文：基于p 2 p 的视图维护架构及方法研究常。而且，由于算法e c a 要求仓库需在所有的查询都返回时才能提交维护，因此在实时性上存在不足，同时当源数据库存在并行事务时，利用算法e c a 也会产生不一致数据。e c a 、e c a ( e c a k e y ) 和e c a 。( e c a l o c a l ) 系列算法是较有代表性的补偿查询算法。其中，e c a 。和e c a 。是对e c a 进行改进的两个算法，e c a 算法由于要求视图包含每一个相关基表的主属性，e c a 。算法是e c a 和e c a 算法的结合。在进一步的研究中，yz h u g e 打破e c a 算法中单数据源的限制，在文献i l l 】中讨论了多视图的数据仓库视图维护：文献 1 2 ，1 3 ，1 4 进一步研究了更为复杂的多数据源的一致性维护问题，针对多数据源上的单更新本地事务、多更新本地事务和全局事务三种数据更新情况，提出了一套s t r o b e 算法( s t r o b e 、t - s t r o b e 、g - s t r o b e 、c s t r o b e等) 来解决它们所引起的视图维护一致性问题，并定义了数据仓库一致性的四个标准；同时对算法作了两个假设：1 ) 假设数据仓库中的视图是由关系投影、选择和连接操作所定义的；2 ) 假设投影属性集合中含有每个基关系的主属性，并要求实化视图更新时必须保证数据源是静止的。实质上，s t r o b e 系列算法也是通过补偿来消除删除更新异常问题，与e c a 算法不同的是，s t r o b e 系列算法不是在补偿查询表达式中添加补偿表达式，而是对需要补偿的补偿查询结果在d w 本地进行补偿。它通过对基关系和实化视图给出个前提条件来处理因并发更新带来的错误项，更新不立即有效地在实化视图中执行，而是在视图中产生个动作列表。对于删除操作，它为实化视图中的相应元组产生一个删除动作：对于插入操作，则对其发起一个查询，并产生个插入动作，将它放到动作列表中。当数据源相对静态时执行该列表并更新实化视图，对并发更新的错误项则根据主属性通过删除重复项来消除所包含的错误。s t r o b e 系列算法为了实现维护，须在数据仓库和数据源之间来回地传送查询及其结果，以对分布的多数据源补偿查询为代价，成功地解决了多源实化视图维护问题，但在时间代价远高于空问代价或者数据源周期性不可被访问的应用场合，补偿查询算法显然不适合。对于多数据源的视图维护问题，c a l i f o r n i a 大学的d a g r a w a l 等人【l 副根据在线纠错( o n l i n ee r r o rc o r r e c t i o n ，o l e c ) 思想，提出s w e e p 算法。算法用临时查询结果代替s t r o b e 中发送补偿查询的方法解决数据仓库系统中视图一致性问题，算法一旦侦测到并发更新就立即消除其影响，从而保证了完全一致性。所有在数据仓库执行的查询都能保证与分布式数据库的视图相一致，并且在更新数据仓库时，它也不需要静止状态，而e c a 和s t r o b e 则要求更新时数据源是静态的。s w e e p 算法对视图的定义更加灵活，不要求基关系的主属性必须保存在视图中。但s w e e p 算法对并发更新以顺序方式处理，而e c a 和s t r o b e 则能并发维护。关于实化视图如何应用在数据仓库中的比较系统的文献是s t a n d f o r d 大学d q u a s s 的博士论文【l ，在这篇论文中，d q u a s s 对实化视图的增量维护和自维护( s e l f - m a i n t e n a n c e ) 问题都做了较系统的研究，提出了一个2 v n l ( t w ov e r s i o nn o l o c k i n g ) 的算法实现数据仓库的联机维护，该算法采用版本控制的方法，采用不中山大学博士论文：基于p 2 p 的视图维护架构及方法研究同的版本来分别负责实化视图的查询与维护，在解决数据仓库维护和一致性方面作出了有益的尝试，不足之处是视图数据不能即时更新【2 1 。在数据仓库方案中，由于基关系分布在不同的数据源上，访问它们是非常困难的，加上其访问费用也是非常巨大的。如果视图不访问源数据就可以在数据仓库中进行维护，a ，g u p t a 和j h a m m e r 将这种方法称为视图自维护7 ，1 8 ，1 9 ，2 0 川，所谓视图自维护方法，指的是通过在数据仓库中通过辅助视图( a u x i l i a r yv i e w s ，a v ) 复制所有或部分数据源数据，从而在维护数据仓库实化视图时不需要访问基关系。视图的自维护方法是从自治可计算视图发展而来，仅使用实化视图和数据更新消息( u p d a t em e s s a g e ) 维护实化视图，而不用去访问基表【2 。一个视图自维护的简单方法是将所有数据源数据复制到数据仓库中，但这样会导致大量的额外存储空间和费用，因此，确定最小量的相关数据存储也是数据仓库研究的一个重要方面。文献【2 3 】仅仅考虑插入操作，提出z 划分算法来为视图自维护构造一含完全的测试，根据视图定义来测试一个视图是否是可自维护的。a g u p t a 等使用主属性信息决定视图对于某一类的修改的自维护能力【i ”。r h u l l 等通过降低选择条件和目标并把结果存在数据仓库中来考虑视图的自维护【2 ”。后来，斯坦福大学的d q u a s s 等扩展了文献 2 4 】的结果，给出算法去选定辅助视图，将其存放在数据仓库中维护s p j ( s e l e c t i o n p r o j e c tj o i n ) 视图，这些视图和辅助视图都是可自维护的，将主属性和参照完整性约束考虑进去来进一步减少辅助视图中元