（计算机应用技术专业论文）多数据库系统中的关键技术研究.pdf

武汉理工大学硕士学位论文 摘要 随着i n t c m e t 和数据库技术的发展，越来越多的应用系统需要访问一些异构的、 分布的数据库来完成任务。多数据库系统在不改变原来这些局部数据库的基础上， 为用户提供一个统一的、集成的多数据库环境，使用户能以统一的模式和简单的 查询语言访问这些数据库。 事务管理的基本任务就是有效管理事务读写操作的并发执行，保证事务的 a c i d 特性，保证事务对数据库操作的正确性。事务管理在维持事务的a c i d ( a u t o m i c i t y , c o n s i s t e n c y , i n d e p e n d e n c e , d u r a b i l i t y ) 特性上主要使用并发控制和恢复 机制，并发控制用以维护事务的一致性和隔离性，恢复机制用以维护事务的原予 性和持久性。 m d b s 是建立在多个l d b s 之上的，这些l d b s 存储了一些语义相关的数据。 但是，这些l d b s 是独立地开发出来的，它们在查询语言、数据模式及体系结构 方面都存在着差异为了能够向用户提供一个集成的、统一的多数据库环境，首 先必须将不同的l d b s 的数据模式统一成一个相同的全局模式。这就是m d b s 中 异构模式的消解，也称为模式集成。 在m d b s 中，用户提交的全局查询一般涉及到对多个不同的数据模式的 l d b s 的操作，因此必须将全局查询分解为若干个全局子查询j 每个子查询只对 一个l d b s 进行操作。l d b s 不能识别用全局查询语言书写的全局子查询，因此 必须将全局子查询转换为用u ) b s 上的查询语言书写的查询语句。为了缩短全局 查询的响应时间和降低执行代价，还需要对查询分解及子查询结果处理进行优化 本文对多数据库系统中模式集成、全局查询的分解和优化以及全局事务的处 理模式冲突消解等问题进行了详细而深入的论述，给出了一对一实体冲突的消解 算法和查询处理优化算法，并对这些算法进行了分析；同时还论述了全局死锁的 处理算法。最后，本文在借鉴国内外经验的基础上，把通用对象请求代理结构技 术与多数据库系统结合起来，提出了一个新的多数据库系统模型，并在该模型中 引入了安全管理机制。 关键词：多数据库系统，查询优化，事务处理，c o r b a 技术 武汉理工大学硕士学位论文 a b s t r a c t w i t l lr a p i dd e v e l o p m e n to f i n t e m e tt e c h n o l o g ya n dd a t a b a s et e c h n o l o g y , m o r ea n d m o r ea p p l i c a t i o ns y s t e m sh a v et oa c c e s sm a n yh e t e r o g e n e o u sa n dd i s t r i b u t e dd a t a h a s e m u l t i d a t a b a s e s y s t e mc 姐p r o v i d e au n i f o r ma n d e o m p o s i t i v e m u l t i d a t a b a s e e n v i r o n m e n ta n dm a k eu 螂a e 傥s st h e s ed a t a b a s e sb yu s i n gau n i f o r ms c h e m aa n da s i m p l eq u e r yl a n g u a g ew i t h o u tc h a n g i n gt h e s ed a t a b a s e s 1 1 圮b a s i ct a s ko ft r a n s a c t i o nm a n a g e m e n ti st h a tt h ec o n c u r r e n c yo fm a d - w r i t e 。 g u a r a n t e et h ea c i dc h a r a c t e r i s t i cp r o p e r t ya n dt h ed a t a b a s eo p e r a t i o nc o r r e c t l y t r a n s a c t i o nm a n a g e m e n tm a i n l yu s e sc o n c u r r e n c ya n dr e s t o r e sm e c h a n i s mt om a i n t a i n t h ec h a r a c t e r i s t i co fa c m c o n c u r r e n c yc o n t r o l sm a i n t a i nt h ec o n s i s t e n c ya n dt h e i n d e p e n d e n c e t h ea u t o m i c i t ya n dd u r a b i l i t yd e p e n do nr e c o v e r ym e c h a n i s m m d b si sb u i l to i lm a n yo fl d b s ，t h e s el d b ss t o r e daf e wd a t ao fs c m a n t e m e r e l e v a n c e s b u t t h e s el d b sa r cd e v e l o p e di n d e p e n d e n t l y t h e yh a v ed i f f e r e n c e si n a s p e c to fi n q u i r yl a n g u a g e ，d a t ap a t t e ma n ds y s t e ms t r u c t u r e f o rb e i n ga b l et op r o v i d e e o n s t a l l e rw i t hm a n yi n t e g r a t e da n du n i f i e dm u l t i d a t a b a s ee n v i r o n m e n t , u n i t i n g d i f f e r e n tl d b sd a t ap a t t e r ni sn e c e s s a r y t h i si sm d b st ob eh i tb yp a t t e r nd i s p e l i n go f i s o m e r i s m i ti sa l s oc a l l e dp a t t e r ni n t e g r a t e d i nm d b s t h eo v e r a l li n q u i r yw h i c ht h eu s e rs u b m i t sg e n e r a l l yi n v o l v e st h e o p e r a t i o nd e a l i n gw i t hl d b st om a n yd i f f e r e n td a t ap a t t e m s t h e r e f o r et h eo v e r a l l i n q u i r ym u s tb ed e c o m p o s e di n t oc e r t a i no v e r a l ls o ni n q u i r e s e a c hs o ni n q u i r yo n l y c a r r i e do no n el d b s l d b sc a nn o td i s t i n g u i s h 、i t l lt h eo v e r a l ls o ni n q u i r e sw h i c h w i l t e db yt h el a n g u a g eo fo v e r a l li n q u i r y t h e r e f o r et h eo v e r a l ls o ni n q u i r e sm u s tb e t r a n s f o r m e di n t oi n q u i r ys e n t e n c e sw r i t e db yt h ei n q u i r yl a n g u a g eo nl d b s i no r d e rt o r e d u c et h er e s p o n s et i m eo ft h eo v e r a l li n q u i r ya n dt h ei m p l e m e n t a t i o np r i c e i tn e e d s o p t i m i z a t i o no f t h ed e c o m p o s i t i o no f i n q u i r i e sa n d t h er e s u l to f s o ni n q u i r i e s i nt h i st h e s i s ，s c h e m ai n t e g r a t i o n , g l o b a lq u e r yd e c o m p o s i t i o na n do p t i m i z a t i o n a n dg l o b a lt r a n s a c t i o n sm a n i p u l a t i o ni nm u l t i d a t a b a s es y s t e m sa r cd i s c o u r s e d e l a b o r a t e l y n ea l g o r i t h mw h i c hc l e a r sl l po n et oo n ee n t i t yc o n f l i c ta n dq u e r yp r o c e s s o p t i m i z a t i o na l g o r i t h ma 北p r e s e n t e da n da n a l y z e d t h e a s s u r a n c e s t r a t e g y o f t r a n s a c t i o na t o m i t ya n dg l o b a ld e a d l o c kr e s o l u t i o na l g o r i t h ma r ca l s od i s c u s s e di nt h i s t h e s i s a te n do ft h i st h e s i s ，an e wm u l t i d a t a b a s es y s t e mm o d e li sp r e s e n t e db y c o m b i n i n gm u l t i d a t a b a s es y s t e ma n dc o r b at e c h n o l o g y , a n ds e c u r i t ym e c h a n i s mi s i n t r o d u c e di nt h i sm o d e l i i 武汉理工大学硕士学位论文 k e yw o r d s ：m u l t i d a t a b a s es y s t e m , q u e r yo p t i m i z a t i o n , g l o b a lt r a n s a c t i o n , c o r b a l l i 此页若属实，请申请人及导师签名。 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：盥囱鱼日期望z ：丛 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， e p 学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：勤咝导师签名 注：请将此声明装订在学位论文的目录前。 甘丑阳只谢el期b j 、叼 武汉理工大学硕士学位论文 1 1 引言 第一章绪论 由于各种原因，目前数据库还没有形成统一的标准，各种不同的数据库管 理系统( d b m s ：d a t a b a s em a n a g e r a c n ts y s t e m ) 都在使用当中文件系统、层次网 络系统、关系数据库、面向对象数据库等作为数据管理平台都曾广泛使用，而且 基于不同的数据管理系统都建立了大量的应用程序。随着通信技术和数据库技术 的发展，越来越多的应用系统需要访问一些分布的、异构的和自治的数据库来完 成其相应的任务。这些分布的、异构的和自治的数据库在数据模型、查询语言、 系统结构等方面可能存在差异，因此用户不能以统一的模式和查询语言访问这些 数据库。因此，我们面临着解决不同种类的数据管理系统之间的互操作问题1 1 j 人们提出了多种方法来解决不同种类的数据管理系统之间的互操作问题，如 数据转换、查询转换等等。但这些方法都有各自的局限性，很难真正实现不同种 类的数据管理系统之间的互操作。 目前，应用最广泛也是最成功的解决分布的、异构的和自治的数据库互操作 问题的方案就是多数据库系统( m d b s ：m u l t i d a t a b a s es y s t e m ) 。m d b s 是在已经 存在的数据库系统或者文件系统( 称为局部数据库系统：l d b s ：l o c a ld a t a b a s e s y s t e m ) 之上为用户提供一个统一的存取数据的环境。一个m d b s 是由一组独立 发展起来的l d b s 组成，并在这些l d b s 之上为用户建立一个统一的存取数据 的层次，使得用户像使用一个统一的数据库系统一样使用m d b s ，而不需要改变 l d b s ，从而屏蔽了各个l d b s 的分布性和异构性，并保持了各个l d b s 的自治 性，从而各个l d b s 的用户( 局部用户) 仍然可以对相应的l d b s 迸行访问。 1 2 多数据库系统的研究背景及研究现状 1 2 1 多数据库系统的研究背景 目前各种不同的数据管理系统都在使用之中，文件系统、层次网络系统、关 系数据库、面向对象数据库等作为数据管理平台都曾被广泛使用，而且基于不同 的数据管理系统都建立了大量的应用程序。由于不同的数据管理系统有不同的数 据模式和查询语言，用户不可能像使用一个数据库那样使用多个具有不同结构的 武汉理工大学硕士学位论文 数据管理系统1 2 】。但随着网络技术的成熟和信息时代的到来，大范围内的信息共 享与分布式事务成为计算机应用的迫切要求，越来越多的应用要存取的数据可能 涉及到分布在不同网络结点上的、不同种类的数据管理系统，因此，我们面临着 解决不同种类的数据管理系统之间的互操作问题。解决这种互操作问题有各种途 径，下面就介绍典型的几种。 一种方法是把一个数据管理系统中的所有数据都转换和移植到另一个数据 管理系统之中h j 当应用只需要把一个数据管理系统中的所有数据移植到另一个 数据管理系统中，以备以后读取之用，或是要用一个数据管理系统完全替代另一 个数据管理系统时，这种方法是可行的。这种方法存在着两个严重的问题：一是 这种方法把系统a 中的数据转换为系统b 中的数据后，仅使得a 中的数据对b 为可见的，但在很多情况下，应用希望系统b 能感知到系统a 中数据的改变， 且系统b 的执行结果可能还要改变系统a 中的数据，在这种移植转换方法中很 难实现这种逆转换；另一个问题是如果用数据管理系统b 完全替代数据管理系 统a 。即把系统a 中的数据转换移植到系统b 中以后不再使用系统a ，则系统 a 上原有的应用程序如何转换成在系统b 上能运行的应用程序也是一个难于解 决的问题。 另一种方法是在一对数据管理系统中设计一个称为信关的中介器【4 1 。系统a 与系统b 之间的信关可以把用系统a 的语言写的查询语句转换为对等的用系统 b 的语言写的查询语句。并把转换后的语句交予系统b 执行。这种信关解决方法 也存在着严重的问题：一是系统a 与系统b 之间的信关仅仅是查询语言的转换 器，信关不支持事务管理；另一个问题是信关对不同系统之间的不同数据结构及 表示无能为力。 还有一种方法是采取公共的数据协议。这种方法要求异构数据库在进行通信 时采用公认的数据协议，即公认的系统问传递s q l 请求和结果的形式。这种公 共数据协议方法的缺点是：协议本身所带来的速度问题，大多数数据库厂商都有 自己的相当好的数据协议及基于该协议的软件，要使用公共数据协议就需要有一 个d b m s 厂商在原有的数据协议外增加公共数据协议的支撑软件，或写模拟程 序来实现自己的数据协议与公共数据协议之间的转换，这是数据库厂商难以接受 的；公共数据协议无事务处理和数据库恢复能力。 目前，应用最广泛也是最成功的解决异构数据库互操作问题的方法就是多 数据库系统( m u l t i d a t a b a s es y s t e m s ：m d b s ) 。m d b s 是在已经存在的数据库或 文件系统( 称为局部数据库：l o c a ld a t a b a s e ，l d b ) 之上为用户提供一个统一的存取 数据的环境。一个m d b s 是由一组独立发展起来的l d b 组成，并在这些l d b 2 武汉理工大学硕士学位论文 之上为用户建立一个统一的存取数据的层次，使得用户像使用一个统一的数据库 系统一样使用m d b s 。 多数据库系统为用户和应用程序屏蔽了底层数据库操作环境的差异，包括计 算机、操作系统、网络协议、数据库查询语言、数据模式等，此外，多数据库系 统还提供全局事务处理能力，并维护各结点上l d b 的数据一致性。因此，多数 据库系统从较深的层次解决了异构数据库互操作问题，用户对异构数据库访问的 透明度较高，并且实现了异构数据库的全局事务管理，是目前异构数据库互操作 实现的主要途径和方式另外，由于多数据库系统中实现模式集成、查询语言转 换、全局事务管理、全局视图维护等的难度较大，还有很多技术问题有待进一步 解决，因此多数据库系统也是目前数据库领域的一个研究热点【1 1 1 2 2 研究现状 自从八十年代中期多数据库系统的概念首次提出后，立即引起了数据库方面 研究人员及数据库厂商的密切关注，到1 9 8 7 年左右，多数据库系统的理论研究 己形成体系，并出现了第一批原型系统，同时各主要数据库厂商也分别推出了支 持多数据库系统的商业产品，包括s y b a s e ，e m p r e s sv 2 ，i n g r e s s t a r , o r a c l e 等。目 前数据库厂商推出的多数据库系统产品主要包括： s y b a s e ：s y b a s e 数据库是加利福尼亚的b e r k e l e y 大学研制的，是一个高性能 的关系数据库系统。s y b a s e 数据库的查询语言是s q l 语言的扩展，称为 t r a n s a e s q l ，是市场上最先出现的多数据库系统语言，s y b a s e 后来又推出了更 便于用户使用的多数据库系统语言v q l ( v i s u a lq u e r yl a n g u a g e ) 。 e m p r e s s v 2 ：该系统是加拿大多伦多的r h o d i u s 研究中心研制的，e m p r e s s v 2 可以支持很多平台，包括s u n , v a x ，a p o l l o ，i b m - p c p s 等。 d i s t r i b u t e di n g r e s ：也称为i n g r e s s t a r ，该系统的特点是可以定义任意数量的 全局数据模式，全局数据模式一旦定义，就可以作为i n g r e s 的一个虚拟数据库来 使用，但i n g r e s 不支持对虚拟数据库的修改。 o r a c l e ：o r a c l e 支持的多数据库系统语言为s q l * p l u s ，o r a c l e 也不支持 分布式修改，即不支持对全局数据模式的修改 虽然越来越多的数据库厂商都声称提供对多数据库系统的支持，但通过对这 些产品的分析可以发现，这种支持往往只是对异地数据库访问的支持，有很大的 局限性，而对多数据库系统中的事务管理、异构模式消解、全局视图维护等关键 技术都没有提供很好的解决方案。而且一个数据库厂商的多数据库系统产品一般 只支持自己的数据库加入多数据库系统，对底层数据库异构性的支持还远远不 武汉理工大学硕士学位论文 够。 下面是目前主要的多数据库系统项目方面的研究1 6 , 7 。 p e g a s u s 是一个异构的多数据库管理系统，是h e w l e t t - p a e k a r d 实验室于1 9 9 0 年开始开发的，它允许用户用统一的接口存取分布、异构的多个数据库上的数据。 a d d s ( a m o c od i s t r i b u t e dd a t a b a s es y s t e m ) 是由a m o c o 研究中心研制从8 0 年代中期开始开发的一个多数据库系统原型，目前已经商品化，系统具有功能较 强的用户界面。 d q s ( d i s t r i b u t e dq u e r ys y a t e m ) 是意大利的c r a i 研究中心于1 9 9 5 年研制开 发的原型系统，该系统的查询优化工作做的很好。 m u l t i s t a r 是意大利的c r a i 研究中心为代表的联合研究小组研制的多数据 库系统原型，支持与其他多数据库系统的连接。 j d d b s ( j a p a n e s ed i s t r i b u t e dd a t a b a s es y s t e m ) 是r 本的信息处理发展中心于 9 0 年代中期开始研制的原型系统，该系统基于广播网络。 s i n u s - d e l t a 是由法国的i n r i a 研究中心研制的多数据库系统原型，该系统 代码量较小，有全局数据描述和统一的查询语言。 e d d s ( e x p e r i m e n t a ld i s t r i b u t e dd a t a b a s es y s t e m ) 是由美国的u l s t e r 大学研制 的多数据库系统原型，允许少量的计算机加入系统。 u n i b a s e 是波兰的科学技术及商务信息学会研制的多数据库系统，目前还处 于研究阶段。 p r o t e u s 是由英国大学研制的多数据库系统，支持星状拓扑结构的网络，并 支持多种全局查询语言，该系统只支持全局查询而不支持全局修改。 目前多数据库系统技术已在国际上获得了广泛的认同，各个国家都有研究组 织在进行相应的研究，并且推出了各自的原型系统及商品化的产品。目前多数据 库系统技术和产品的研究还处于生长期，有很多技术问题还没有很好解决，市场 上还未出现主流的产品，是国内开展该技术研究，推出自己产品的好时机一i 。 1 3 多数据库系统的基本概念及关键技术 1 3 1 多数据库系统的概念 多数据库系统的主要目的是解决异构数据库互操作问题。m d b s 是在一组己 经存在的数据库以及文件系统之上为用户提供一个统一的存取数据的环境。一个 m d b s 是由一组独立发展起来的l d b 组成，并在这些l d b 之上为用户建立一个 4 武汉理工大学硕士学位论文 统一的存取数据的层次，使得用户像使用一个统一的数据库系统一样使用 m d b s 【l o 】。另外，多数据库系统中的l d b 具有自治性，加入多数据库系统对l d b 上原来的应用程序应该没有任何影响，即l d b 上原来的应用程序及软件在l d b 加入多数据库系统以后仍能继续运行，并且这些l d b 上的局部事务不为m d b s 所知，更不受m d b s 控制。 多数据库系统与分布式数据库、互操作系统都是在分布式系统中( 网络环境 下) 为用户提供异地数据访问的工具，通过比较可知，多数据库系统是在分布式 数据库系统与互操作系统之间的折衷，它的优点是保存了l d b 的自治性，允许 一个事先已经存在的数据库加入多数据库系统而不改变原来的d b m s 及应用程 序，并可以为用户提供一个统一的全局视图。 多数据库系统与联邦数据库是两个非常相近的概念，有些研究人员认为它们 之间的区别在于i l o 】：联邦数据库更强调底层数据库的异构性及自治性，但对底 层数据库之间的互操作要求较弱；而多数据库系统恰恰相反，底层数据库的异构 性较小，甚至可以为同构数据库，但对系统的互操作能力要求较强。目前越来越 多的资料中己经不区分这两个概念，甚至认为这两个概念实际上指的是同一类数 据库。 1 3 2 多数据库中的关键技术 由于多数据库系统固有的一些特点，如允许事先己经存在的数据库加入多数 据库系统，l d b 的异构性、分布性、自治性，多数据库系统对外提供统一的数 据模式和查询语言，等等，使得多数据库系统的实现中有很多难点，有些技术问 题还没有得到很好的解决。目前关于多数据库系统的研究工作主要集中在以下几 个方向1 3 2 1 ： ( 1 ) 多数据库系统中的事务处理 由于多数据库系统中底层数据库具有自治性，底层数据库的局部事务不为全 局事务管理器所知，使得多数据库系统中的事务管理始终是一个难以解决的问 题。因此如何在多数据库系统中保证全局事务的a c i d 特性一壹是多数据库系统 领域的一个研究热点。 ( 2 ) 异构模式消解 m d b s 建立在一组独立的l d b 之上，它为用户提供一个统一的虚拟的全局 数据模式。而组成m d b s 的每个l d b 都有自己的数据模式，相同的信息可以用 不同的模式表示，相同的模式也可以表示不同的信息，所以在m d b s 中就存在 武汉理工大学硕士学位论文 着把不同的l d b 数据模式统一成一个相同的全局数据模式的问题，即多数据库 系统中的异构模式消解问题。 7 ( 3 ) 查询处理技术 ，在m d b s 中采用统一的全局查询语言，而全局查询语言与l d b 的查询语言 可能不同，因此需要把全局查询语言分解和转换为相应的l d b 查询语言，交予 l d b 执行，并合并各l d b 查询结果以产生最终的用户查询结果，这就是多数据 库系统中的查询处理技术。 m d b s 中的查询处理主要包括查询分解、查询转换和全局优化三部分。在 m d b s 中，用户可以根据全局数据模式用全局查询语言对多个l d b 同时进行查 询。一个全局查询一般要经过三步处理： 1 把全局查询分解成多个子查询，每一个子查询对应一个l d b 中的数据。 分解后的子查询仍是用全局查询语言表示的。 2 每一个子查询都转换成相应的l d b 的本地查询语言并传到相应的l d b 中执行。 3 子查询的结果返回并组合成最终的查询结果。 目前在查询处理领域，在查询分解、查询转换和查询优化三个方面都有很多 研究人员在进行相关的研究工作，并取得了较好的研究成果 1 4 课题来源 本论文研究工作的开展，得到了以下项目的支持： ( 1 ) 国家自然科学基金重大国际合作项目：5 0 6 2 0 1 3 0 4 4 1 ，以网络为基础的数字 制造环境的新理论和新技术研究。 ( 2 ) 武汉市重点科技攻关项目一汽车行业制造资源a s p 服务关键技术研究( n o ： 2 0 0 5 5 1 0 2 0 2 1 ) ( 3 ) 武汉市信息产业局电子发展基金( 武信发 2 0 0 7 1 8 号) ，制造网格资源共享 服务平台。 6 武汉理工大学硕士学位论文 2 1 引言 第二章多数据库系统中的事务处理 事务是事务处理的基础，所谓“事务”是一系列由单个用户或应用程序提交 的数据库操作，这些操作是一个不可分割的整体。例如，资金从一个帐号转帐到 另一个帐号就是一个事务，这个事务的所有操作要么都执行，即从一个帐号取出 一定数目的钱，同时向另一个帐号存入相同数目的钱，要么都不执行，即两个帐 号上的钱数保持不变。对一个事务而言，绝对不能出现事务的一部分操作执行了， 而另一部分操作没有执行的情况。 在事务的生命周期中，事务会经历许多状态，事务开始执行的时刻称为事务 的起点( b e g i nt r a n s a c t i o n ) ，事务完成所有操作的时刻称为事务的终点或交付点 ( c o m m i t ) 。从起点开始执行一直运行到终点才结束的事务称为交付事务或成功事 务，否则称为流产事务或未交付事务( a b o r t ) 事务将数据库从一个一致性状态转变到另一个一致性状态。即事务执行之前 和事务执行之后，数据库都处于一致性状态。但这种一致性在事务的执行过程中 不被保证。事务管理模块要负责保证在故障发生后将处于活跃状态的事务( 没有 提交的事务) 回退。回退操作的结果是将数据库恢复到当前活跃事务发生前的状 态，从而使数据库回到一致性状态。 事务具有四个基本特性，它们是原子性( a u t o m i c i t y ) 、一致性( c o n s i s t e n c y ) 、 隔离性( i n d e p e n d e n c e ) 和持久性( d u r a b i l i t y ) ，简称为a c i d 特性【9 1 本章重点研究并发控制及全局死锁的解决。 2 2 多数据库系统中的事务管理 2 2 1 多数据库系统中事务模型 m d b s 中对一个或多个l d b 数据的存取操作是通过事务处理来完成的， m d b s 中支持两类事务： 1 局部事务：l d b 的本地事务，由l d b 自己的d b m s 完成，只存取本地 数据，不在m d b s 的控制之下且不为m d b s 所知 2 全局事务：在m d b s 的控制之下完成。一个全局事务可以分解为若干子 事务，每一个子事务只需存取一个l d b 上的数据，在l d b 的d b m s 的控制之 武汉理工大学硕士学位论文 下作为一个本地事务完成。 因此在l d b 中有两类事务，一类是不为m d b s 所知的局部事务，另一类是 m d b s 交予l d b 执行的全局事务的子事务。每个l d b 的d b m s 都有一套控制 事务执行的方法，以保证事务的顺序执行及无死锁情况发生。m d b s 软件建立在 l d b 的d b m s 之上，包括一个全局事务管理器g t m ( g l o b a l t r a n s a c t i o nm a n a g e r ) 和一系列服务器，每个服务器与一个l d b 的d b m s 相连，如图2 1 所有全局事 务的执行都由g t m 控制，对全局事务的每一个子事务，g t m 决定是把它交给 l d b 执行、推迟还是退出事务对需要交给l d b 执行的子事务，则g t m 决定 交给哪个l d b 执行。 图2 1 事务模型 g t m 通过服务器把子事务操作交给l d b 的d b m s 执行，服务器相当于 g t m 与本地d b m s 的中介器。全局事务的子事务是作为一个本地事务交给 d b m s 的。服务器与d b m s 有两种联系方式：一种是d b m s 只接收一系列读写 指令，由服务器先发。开始事务”的指令，d b m s 返回一个事务标识号，然后服 务器发送这个事务的一系列读写指令，发送完毕后发“事务结束”指令；一种是 服务器向d b m s 发请求，由d b m s 负责用一系列读写操作完成该请求，即l d b 的d b m s 以服务调用的方式与m d b s 进行交互。 2 2 2 保持全局可串行化所面对的问题 所谓“串行调度”就是依次执行每个事务的每一个读写操作，因此没有事务 并发产生。如果对一组事务的读写操作顺序进行重新排列且其执行结果与该组事 务的串行调度的执行结果相同，则称该组事务是可串行化的。在m d b s 中，全 局可串行化不但要求每个l d b s 能保证局部可串行化，而且还要求全局事务的所 有子事务在每一个l d b s 上的调度表中出现的顺序必须相同，即：若有两个全局 事务g 。和g ：，在l d b s a 中g 1 的子事务先于g ：的子事务执行，那么在其它的 l d b s 中g l 的子事务也要先于g ：的子事务执行。 在m d b s 中，l d b s 上的可串行化并不能确保m d b s 的一致性。为了保证 s 武汉理工大学硕士学位论文 全局可串行化不被破坏，l d b s 上的调度须由m d b s 证明有效。为了确定全局 事务在每个l d b s 上的串行化顺序，m d b s 不但要处理存在于m d b s 事务的子 事务之间的直接冲突，还要处理由局部事务产生的间接冲突。因此，在m d b s 中保持全局可串行化是一个难题。为了说明这点，来考虑图2 2 ，它描述了两个 全局事务g 1 和g 2 ，一个局部事务五在l d b s 2 ，g l 和g 2 访问不同的数据项，g i 和g 之间没有直接冲突。然而，由于局部事务互写数据项b 读数据项c ，在 l d b s 2 ，g 1 和g ：之间产生间接冲突。从而，在l d b s 2 ，事务的串性化顺序是g 2 一正一g l 。因此全局事务的可串行化没有得到保证。 在m d b s 中，m d b s 控制全局事务及它们提交的操作的执行，从而m d b s 能够检查出全局事务问的直接冲突。然而，m d b s 中没有局部事务以及由它们可 能造成的间接冲突的信息，所以它不能检测间接冲突。尽管每一个局部调度是可 串行化的，但全局调度是非串行化的。 l d b s l d b s l ：w g l ( a ) r g 2 ( a ) g l g 2 b s 2 l d b s 2 ：w r , ( ”r g l ( b ) w g 2 ( c ) f 五( c ) g 2 一五一g l 图2 2 局部事务引起全局事务冲突示例 在早期研究中，间接冲突所造成的问题不被认识。p o p c s c u - z c l c t i n 和g l i g o r 提出只要发生( 直接) 冲突的全局事务在每个l d b s 中有相同的串行化顺序，全局 事务的调度就是正确的【i 。b r e i t b a r t 和s i l b e r s c h a t z 证明了保持全局事务一致性 的充分条件是确保全局事务在每个l d b s 有相同的串行化顺序【7 l 。 人们曾提出在每个l d b s 都执行严格的两阶段锁协议( r 2 p l ：r i g o r o u st w o p h a s el o c k i n g ) ( 读锁和写锁只有在事务结束时才释放) 来保持m d b s 中全局事务 9 武汉理工大学硕士学位论文 可串行化。这样在上例中，l d b s 2 上的局部事务t ，执行完才释放加在数据b 上的锁，因此g 1 只有在互执行完以后才能执行，从而在l d b s 2 上的执行顺序变 为正一g g 2 。这种方法虽然保证了全局事务的可串行化，但使得出现死锁的 可能性大大增加，同时也使事务的等待时间加长，造成很多不必要的等待。 下一节讨论一种方法，称之为乐观票方法( o t m ：o p t i m i s t i ct i c k e t m e t h o d ) 。这种方法不允许出现此类调度：一个全局事务g j 在一个全局事务g ，之 前由一l d b s 执行和提交，而它们的局部串行化顺序被颠倒了。 2 2 3 并发控制 1 并发事务之间的冲突 并发事务之间的冲突是多方面的，因此危及数据库完整性和一致性的因素也 是多样的。下面是三种典型的并发事务之间的冲突： ( 1 ) 丢失修改。 佗) 不可重读。 ( 3 ) 读脏数据。 2 并发控制技术 有三种基本的并发控制技术可以保证事务并发地、安全地执行，它们是： ( 1 ) 锁方法 ( 2 ) 时戳方法 ( 3 ) 乐观方法 这些方法主要应用于集中式数据库中，但也可以推广至分布式数据库及多数 据库系统中乐观方法是基于冲突很少发生，且事务可以异步执行，该方法仅在 事务提交时才检查冲突。 下面将说明乐观票方法是怎么进行并发控制的。 决定局部串行化顺序 0 1 m 利用票来确定在每个l d b s 上全局子事务的相应的串行化顺序。一张 票就是一个逻辑时间戳，它的值作为一个长期的数据项在每个数据项中保存。每 个全局子事务都必须发布t a k e - a t i c k e t 操作，该操作包括两部分：读票( 即 r ( t i c k e t ) ) 和给票增值( 即w ( t i c k e t ) ) 。每个l d b s 仅需一个票值。 电 加强全局可串行化 为了保持全局一致性，o t m 必须确保每个全局子事务在相应的l d b s 上有 相同的串行化顺序。由于在每个l d b s 上的子事务的串行化顺序反映了它们票的 1 0 武汉理工大学硕士学位论文 值，所以o t m 的基本思想就是允许每个全局子事务执行，但是只有当这些子事 务的票值在所有的l d b s 中有相同的顺序时才提交。这就需要l d b s 支持所有 全局子事务有一可见的准备提交状态。如果l d b s 不明确地支持准备提交状态， 它可以通过在每次读写操作之后以握手机制来模拟。 妈 对票进行操作的时间的选择 o t m 能够并发运行任意数量的全局事务，即使它们在多个l d b s 上发生冲 突。然而，o t m 迫使全局事务的子事务在票上直接冲突会造成一些子事务取消 或阻塞。予事务在其生命周期的任何时间内对票进行操作不会对o t m 的正确性 造成影响。如果所有的全局事务在一些l d b s 上直接冲突，那就没有必要让它们 对票进行操作。为了决定它们的串行化顺序，只要观察那些发生冲突的操作的顺 序就足够了。 o t m 的优点在于它只要求l d b s 保证本地的可串行化，而不破坏l d b s 的 自治性，就能保证全局可串行化，这在m d b s 中尤为难得。o t m 主要短处是它 造成了原本不会发生冲突的全局事务之间产生冲突，造成了不必要的事务取消或 阻塞，这会在m d b s 中容易造成资源浪费和不必要等待。 2 3 全局死锁的解决 2 3 1 两种解决全局死锁的方法 在m d b s 中，采用某些并发控制机制( 如严格的两段锁协议) 可能导致死锁。 在本节主要讨论全局死锁，即全局事务之间为竞争资源而造成的一种僵局。假设 不存在局部事务之间的死锁，或者说局部死锁能由l d b s 解决。为了更好地讨论 全局死锁的解决方法，不妨做以下假设： ( 1 ) g t m 无法访问l d b s ；每个全局事务在每个l d b s 上至多有一个子事务； 每个子事务由多个操作组成；g t m 按顺序一个一个地提交全局事务的操作；g t m 向一个l d b s 提交操作仅当该操作前面的操作己经完成。 ( 2 ) 每个l d b s 使用两阶段锁协议来进行局部串行化并且使用一种机制来阻 止局部死锁；l d b s 不能区分在该站点上的全局子事务和局部事务；每个l d b s 都不能和其它的l d b s 进行通信。 为了检测到全局死锁，必须知道全局事务之间的冲突信息。然而由于站点自 治，无法检测到间接冲突。这个问题可以通过潜在冲突图( p c g ：p o t e n t i a lc o n f l i c t g r a p h ) 来解决。当一个全局事务的一个子事务将在站点s j 执行时，那么该全局 事务在站点s j 上有一个服务器。该服务器用于在g t m 和站点s j 之间通信。如 武汉理工大学硕士学位论文 果全局事务豇在站点s j 上有一个服务器，并且当该服务器正在执行事务m 的操 作或者服务器完成事务面的当前的操作且正在准备接收事务面的下一个操作， 那么就称事务面在站点s j 是活动的。反之，如果一个事务在站点s j 有一个服务 器并且至少己提交了一个操作到该站点，但该事务在站点s j 不是活动的，则称 该事务在站点s j 等待。一个潜在冲突图实际上就是一个有向图g = ( va ) ，其中 顶点集由全局事务组成。如果在一个站点上事务n 是活动的而事务1 ：i 处于等待 状态，那么a 中就有弧1 ：j 专面 b l s 方法将潜在冲突图和超时机制结合起来消除全局死锁1 。这种方法对 每个全局事务设置一个时间戳和计时器。当一个等待事务t 超时，b l s 方法执 行以下两步： ( 1 ) 如果此时在潜在冲突图中有一个包含事务t 的环，确定在事务t 等待的 站点上通过事务t 的环中处于活动状态的事务的集合。如果事务t 比集合中所 有事务都老，那么事务t 继续等待，否则取消事务t 。 ( 2 ) 如果此时潜在冲突图中没有环，那么事务t 继续等待。 另外一种使用超时机制解决全局死锁的方法是p p c g ( p r i o r i t y - b a s e dp c 6 ) ， 当事务t 超时，该方法执行下列两步： ( 1 ) 如果在潜在冲突图中至少有一个环包含事务t ，确定所有包含事务t 的 环中事务的集合g 。如果事务t 在集合g 中是最年轻的，那么就取消t 。否则就 取消集合b 中最便宜的事务t 1 ；如果最便宜的事务t 1 和事务t 一样便宜，那么 就取消事务t 。 c ) 否则给事务t 重新设置一个时限让它继续