《移动数据库中基于物化视图的数据同步机制》由会员分享,可在线阅读,更多相关《移动数据库中基于物化视图的数据同步机制(4页珍藏版)》请在金锄头文库上搜索。
1、计算机科学2 0 0 2 V 0 1 2 9 N o 8移动数据库中基于物化视图的数据同步机制* ,AM a t e r i a l i z e dV i e w b a s e dD a t aS y n c h r o n i z a t i o nM e c h a n i s mi nM o b i l eD a t a b a s e陈黎赵培翔陈立军杨冬青唐世渭 ( 北京大学信息科学中心北京1 0 0 8 7 1 )A b s t r a c tD a t as y n c h r o n i z a t i o ni st h em o s ti m p o r t a n tc
2、h a r a c t e r i s t i co fM o b i l eD a t a b a s e I no r d e rt od e c r e a s et h ec o s to fc o m m u n i c a t i o n ,w ei n t r o d u c ead a t as y n c h r o n i z a t i o nm e c h a n i s mb a s e do nM a t e r i a l i z e dV i e wi nt h i sp a p e r D e t a i l e dd e s i g na n dg e n
3、e r a li m p l e m e n t a t i o na r eg i v e n K e y w o r d sM o b i l ed a t a b a s e ,M a t e r i a l i z e dv i e w ,D a t as y n c h r o n i z a t i o n1 引言随着移动通信技术的迅速发展和广泛应用,许多计算节点都可以在自由移动的过程中保持网络连接。人们迫切需要能在任何时间、任何地点高效即席地访问任何数据,于是,一种更加灵活、复杂的移动数据库技术应运而生,并迅速成为新的研究热点。移动数据库位于移动单元( 如移动计算机) 中,它和固
4、定节点( 服务器端) 构成移动计算环境。这种计算环境具有移动性、频繁断接性( 指移动计算机可主动或被动地间歇入网、断接) 、网络条件多样性( 指移动计算机在不同时间内可使用的网络条件是变化多端的) 以及网络通信的非对称性( 指服务器到移动计算机的下行链路与移动计算机到服务器的上行链路相比较,它们之间的通信带宽和代价相差很大) 等特点。数据同步是移动数据库最主要的功能之一,它可以使移动数据库系统与其它数据库系统( 主要是指位于固定节点的中央数据库) 进行数据交换、共享和同步,保持两个数据库中数据的一致性。移动计算 环境的特点决定了固定节点数据的更新不能及时反映到移动单元,只有当移动单元通过网络与
5、固定节点连接时,才能够进行数据同步。最简单的同步方式就是在固定节点重新计算移动数据库中的元组,以代替原有元组。但是这种方式会造成较高的通信量,从而影响到数据同步的效率。所以如何有效地减少同步时的通讯代价,是数据同步技术中最值得研究的问题之一。在移动计算环境中,某些应用只要求对移动单元中的数据执行查询操作,不需要更新,数据同步的目的就是将固定节点中的数据变化情况反映到移动单元。在这种应用模式下,为了减少同步时的通信代价,我们提出了一种基于物化视图的数据同步机制。物化视图不同于一般的虚视图,它的元组被实际存储起来。所以移动数据库中的表就可以视为固定节点数据库的物化视图。在数据同步过程中,根据有关
6、物化视图维护的判定准则,实现对视图( 即移动数据库中的表) 的增量更新,而不是刷新整个视图,从而可以大大地节省通信开销。本文首先给出了在设计过程中用到的一些基本定义,然后是基于物化视图的数据同步机制的设计,其中包括主要设计思想和数据同步处理流程,以及视图定义向可自维护方向扩充和更新操作合并等扩展策略。最后简要介绍了基于物化视图的数据同步系统的实现。2 基本定义这些定义来自文E z ,用于下文的数据同步机制设计中。S P J 视图:通过选择、投影、连接操作定义的视 图。一个S P J 视图V 可以写成“S E L E C TAF R O M RW H E R EC ”的形式,记作V 一( A ,
7、R ,C ) 。其中A是构成视图的属性列,A 一( A 。,A 。,A ;R 是派生出视图的一个或多个基本表R = ( R ,R i 2 ,R i k ) ;C 是视图中元组所满足的条件。S P 视图:在S P J 视图的F R O M 定义语句中,只有一个表出现。可自维护视图:不需要访问源数据库中的数据,只根据视图本身数据和基本表的更新信息就可以进行维护的视图。* ) 本项研究得到国家8 6 3 计划基金资助,编号Z D l 2 0 1 2 。陈黎硕士研究生,研究方向为数据库与信息系统。赵墙翔硕士研究生,研究方向为数据库与信息系统。陈立军副教授,研究方向为数据库与信息系统。杨冬青教授,博士生
8、导师,研究方向为数据库与信息系统。唐世渭教授,博士生导师。研究方向为数据库与信息系统。2 1 2 插入I N S E R T ( R 。,T ) :向表兄中插入元组集T 。删除D E L E T E ( 凡,C D ) :删除表R 。中所有满足 条件C D 的元组。 修改M O D I F Y ( R ,C M ,F M ) :修改表R 。中所有 满足条件C M 的元组,F 肘是一组更新表达式的集合,即F 肘= f A ,f A :,f 脚) ,其中A 。,A 。,A ,是R 。上的属性,氏三( A ,:一g ,( A n ,A ,A “) ) ,g ,是函数,被称为A 的更新函数。 可见属性
9、:表R 的属性A 如果出现在视图V 的S E L E C T 定义语句中,则称A 对V 是可见的。暴露属性:在视图V 的定义中,如果属性A 出现在谓词中,则称A 是暴露属性。5 基于物化视图的数据同步机制设计5 1 主要设计思想 通过在移动端采用物化视图的方式存储派生数据,在固定节点执行的某些更新操作可以直接传给移动单元。以增量的方式更新视图,而不是刷新整个 视图,这样可以节省通信开销,使同步过程变得高效。在基于物化视图的数据同步系统中,中央数据库存储在固定节点( 服务器端) 。移动单元的数据库采用物化视图的方式,存储中央数据库的派生数据,并通过移动通信网络产生与固定节点或其他移动单 元的连接
10、。固定节点和移动单元的数据同步通过增量方式或快照方式来完成。增量方式是当物化视图 对基本表的更新操作满足相关性和可自维护性时进 行的,它只需将在固定节点进行的更新操作语句传给移动单元;而快照方式是通过访问基本表重新计 算视图,并将所得到的元组传给移动单元。这种数据同步处理思想适用于中央数据库中的数据可更新, 而移动单元的数据不会被更新,只对其进行查询操作的情况。基于以上分析,我们设计了基于物化视图的数据同步系统的基本流程( 图1 ) 。鬻船甚碧否满足相关惶一终止根据视图定 义生成对物化 视图的更新操作图1 数据同步基本处理流程在数据同步过程中,固定节点需执行以下步骤( 以对基本表执行的更新操作
11、为单位) :1 ) 该更新操作是否影响到与所对应的表相关的物化视图。如果否,则说明基本表的变化与派生的物 化视图无关,因此不需要同步;反之,转2 ) 。具体的判 定策略依赖于以下阐述的相关性判定准则( 证明可见文 2 ) : 插入操作的相关性判定插入操作I N S E R T( 尺。,T ) 对于视图V 一( A ,R ,C ) 是不相关的,尺。R ,当且仅当对于每元组t E T ,C t 是不可满足的。删除操作的相关性判定删除操作I N S E R T( 尺。,C D ) 对于视图V = ( A ,R 。C ) ,是不相关的,凡 R ,当且仅当条件c D C 是不可满足的。更新操作的相关性判
12、定修改操作M O D I F Y( 风,C M ,F 肘) 对于视图V 一( A ,R ,C ) 是不相关的,其中,R 。R ,当且仅当V C MAC a 【F M ) 兮( 一C 一C ( F M ) ) V ( CAC ( F M ) A (N( A ,= ,9 ( f A i A f l a ( j k ) ( A i ) ) ) ) ) 注:a ( R 。) 一 A 。,A 。,A r ,即R 。中的属性。符号P ( 氏) 表示更新表达式 m 等号右侧的部分。用p ( k ) 替代C 中每个属性A i 的值,可以得到一个新的条件表达式,用C ( F M ) 表示。2 ) 判断物化视图对
13、该更新操作是否可自维护。如果是,就只需将更新语句传给物化视图,由移动单元根据所得到的更新语句以及物化视图的定义生成对视图的更新操作;反之,转3 ) 。具体的判定策略依 赖于以下阐述的可自维护性判定准则( 证明可见文 2 ) :插入操作的可自维护性判定 准则一如果一个S P J 视图基于多个不同的基本表,则它对于插入操作是不可自维护的。 准则=如果一个S P l 视图是基于表R 的自连接,且每个连接是基于k e y ( R ) ( R 的主码) ,则它 对于插入操作是可自维护的。准则三所有的S P 视图对于插入操作都是可自维护的。 删除操作的可自维护性判定对于一个s P J 视图V = ( A
14、,R ,C ) ,若它对于表R i ( R i E R ) 上的删除操作是可自维护的,当且仅当:对R i 的码,每个码属性或者在视图定义中,或者被设为常值。这样,对 于视图V 中的元组t ,我们得到R i 中派生出t 的元组r 。修改操作的可自维护性判定一个S P J 视图V ,如果它基于多个不同表,那么它对表R i ( R i R )上的修改操作是可自维护的,当且仅当:修改属性对 视图V 非暴露且不可见( 在2 中有定义) ;或者修改 属性对视图V 非暴露且V 对R ;上的删除操作可自维护。2 1 3 囊3 ) 对于物化视图不可自维护的情况,我们就使用传统的数据同步方法,通过访问基本表重新计
15、算视图,在固定节点与移动单元之间通过快照的方式进行数据同步。移动单元根据接受到的更新语句或元组( 集) ,分别执行以下操作:1 ) 如果是更新语句插入操作a ) 对S P 视图,插入可以通过选择 + 投影来实现;b ) 对基于码的自连接S P J 视图,每个插入的元组都与自已连接。删除操作对于R i 上删除元组r 的操作,检查视图中与k e y ( r ) 相等的元组,并删除之。修改操作在码上将被修改元组与视图进行连接,得到被修改的视图元组值。2 ) 如果是元组( 集) ,先清空对应的物化视图,再将元组插入其中。5 2 视图定义向可自维护方向的扩充对于某些不可自维护的视图,可以通过增加冗余列(
16、 通常是增加码属性) ,即扩充视图定义的方式使其具备可自维护性。以下分别给出对应于各种更新操作的扩充条件:插入操作1 ) 如果一个S P J 视图是基于多个不同的基本表,那么扩充视图定义对于插入操作是毫无意义的。 2 ) 如果一个S P J 视图是基于关系R 的自连接, 而且每个连接不是基于k e y ( R ) ,那么对于插入操作,添加码属性可以使视图可自维护。删除操作添加基本表的码属性,可以使视图对删除操作可自维护。修改操作添加基本表的码属性,并且要求修改属性非暴露,则视图对修改操作可自维护。 5 5 更新操作的合并将在固定节点发生的一系列更新操作经过合并组合成较少数量的操作,可以很大程度上减少数据 同步时处理的开销和通信量。更新操作合并的前提 是合并前后对于移动数据库的状态影响是一致的。我们讨论的合并策略是基于表中的同一个元组,因为只有对同一元组的操作进行整合才有意义,以下给出针对两个相继操作的具体合并策略: