分布式数据库及相关问题课件

1、第六部分 分布式数据库及相关技术的讨论（第8-11章内容）一 分布式数据库概述产生和发展概念和分类体系结构模式结构及独立性。二 分布式数据库系统中存在的技术问题分布式DB的设计分布式DB的查询分布式DB的事务管理及并发。第1页，共85页。一 分布式数据库概述I 分布式数据库的产生及发展a 经济的发展b 计算机硬件环境及网络的发展发展历程：产生于20世纪70年代末期，成长于80年代 第一个分布式数据库系统SDD-1是美国计算机公司（CAA）于1976年-1978年设计，79年在DEC-10/20上实现。德国斯图加特大学研制的porel系统美国IBM的R*和system R美国加大学伯克利分校的I

2、ngres法国INRA研制的SIRIUS-DELTA。第2页，共85页。1987年：C.J Date提出了完全的，真正的分布式DBS应遵循的12条规则：本地自治性不依赖于中心站点可连续操作位置独立性数据分片独立性数据复制独立性分布式查询独立性分布式事务管理硬件独立性操作系统独立性网络独立性DBMS独立性第3页，共85页。II 分布式数据库系统的定义及分类1 分布式数据库的定义： 分布式数据库是一个数据集合，这些数据分布在由计算机网络连接起来的若干节点上，每个节点可以管理本地的数据应用，也可以参与全局数据应用。同时这些数据在逻辑上形成一个整体，由统一的数据库管理系统进行管理。（DDBMS）注：几

3、个基本的概念站点：计算机连接的一个逻辑单位，称为一个站点。本地（或称：局部）用户、本地应用：一个用户或应用只访问他所注册的那个站点。全局用户、全局应用：一个用户访问涉及两个或两个以上的站点中的数据。全局数据库（GDB）、局部数据库（LDB）：。第4页，共85页。2.分布式数据库系统的基本特点：A 结构特点：物理分布，逻辑相关。B 应用特点：站点自治。第5页，共85页。多处理机系统C.数据分布透明性：数据的物理独立性内容更丰富，增加了数据分布透明性。-数据的逻辑分片、数据的物理位置分布、数据的复制，对用户透明。D.集中与自治兼备的数据库系统控制机制.-两个层次的数据共享：局部/全局数据共享。第6

4、页，共85页。E.增加数据冗余度。-利用数据冗余提高系统可靠性、可用性和系统性能。F.事务管理的分布性。-分布环境下，维护事务的原子性、一致性、隔离性和持久性。第7页，共85页。3.分布式数据库系统的模式结构第8页，共85页。4.分布式数据库系统的分类A 按局部DBMS的数据模型分类：-同构型：数据模型相同 *同质同构：数据模型相同且局部DBMS相同。 *异质同构：数据模型相同外交部局部DBMS不同。 SDD-1和DDM 美国CCA公司 SYSTEM R* 美国IBM公司 POREL 德国斯图加特大学 -异构型 ：数据模型不同 MULTIBASE 美国CCA1981研制 IMADAS:H 佛罗

5、里达大学1984研制 DDTS HONEYWELL公司1980年研制。第9页，共85页。B 按全局控制系统类型分类：-全局控制集中型DDBS DDBS的全局控制机制及数据字典位于一个中心站点，由中心站点完成全局事务的协调和局部数据库的转换等所有控制功能。-全局控制分散型DDBS DDBS的全局控制机制及数据字典分散在网络的各个站点上，每个站点都能完成全局事务的协调和局部数据转换。-全局控制可变型（主从型） 将站点分成两组，一组都包含全局控制机制和数据字典，另一组为辅助站点，只包含自己的数据应用。第10页，共85页。4.分布式数据库管理系统的功能结构：除了具有集中式DBMS具有的功能外，还要有如

6、下附加 的功能： * 数据跟踪 * 分布式查询处理能力 * 分布式事务管理的能力 * 复制数据的能力 * 安全性 * 分布式目录管理第11页，共85页。二.分布式数据库系统中存在的技术问题： 1 分布式数据库系统的设计 -全局模式的设计 -数据分片，分布 2 分布式数据库的查询处理 3 分布式数据库的事务管理及并发控制 4 分布式数据库的可靠性 5 异构数据库的连接 6 安全性 7 目录管理第12页，共85页。1.分布式数据库设计一 方法：根据设计是基于现存的数据系统还是构造一个全新的数据库系统，有两种方法创建分布式数据库： 组合法：基于现有的系统，建立一个协调管理系统。 -采用自底向上的方式

7、构建 重构法：创建全新的数据库系统 -自顶向下的方式构建二 分布式数据库设计的内容： 1. 数据库设计基础-需求分析 1）数据需求 2）应用需求 应用的原发站点：发出应用请求的站点 应用在站点被激活的频率 应用对数据对象访问次数、类型和分布统计第13页，共85页。2. 数据库设计（设计的核心任务） 全局模式设计 局部数据库设计 数据分片设计 片段的位置分配设计三 分布式数据库设计的目标： 确保数据库数据和应用具有最大程度的本地性。 分布式数据的可用性和可靠性 工作负荷分布 存储的能力和费用第14页，共85页。四 自顶向下的方式构建分布式数据库需求分析全局概念模型全局逻辑模型分片设计系统实现试运

8、行及维护分布设计局部逻辑设计物理设计1 设计的步骤：第15页，共85页。2 数据库的分片设计（1）. 什么叫“片段”？ 指在分布式数据库系统中，某一站点上存储的数据集合。（2）.分片设计的目的？ 产生全局数据的一个合理的划分，从而使每个站点只获得它所需要的数据，最大可能保证应用的本地性。（3）分片应遵循的一般规则：设：R = R1, R2, , Rn 1）完整性 即，tR, 则，必有t Ri ( i = 1,2, , n ) 2）可重构性 即，R = Ri ( i = 1,2, , n ) 或R = Ri ( i = 1, , n ) 3）不相交性 即，Ri Rj = (i,j= 1, , n

9、,且i j） 或Ri Rj = 主码属性(i ,j= 1, , n,且i j）第16页，共85页。（4）分片的基本类型和方法 水平分片，垂直分片，混合分片A 水平分片：对全关系进行选择操作，把具有相同性质的元组进行分组，构成若干不相交的子集。初级分片和导出分片 初级分片：以关系自身属性性质分组例1 S( S#, Sname, Age, Sex )define fragment S1 asselect * from S where Sex = M ；define fragment S2 asselect * from S where Sex = F；第17页，共85页。 导出分片：用其它关系的属

10、性对某一全关系进行分组例2 设：全局关系 SC( S#, C#, Grade ) S( S#, Sname, Age, Sex )设计需求：按S的“性别”属性（Sex）去划分SCDefine fragment SC1 as select SC.S#, C#, Grade from SC, S where SC.S# = S.S# and S.Sex = MDefine fragment SC2 as select SC.S#, C#, Grade from SC, S where SC.S# = S.S# and S.Sex = F第18页，共85页。 B 垂直分片：利用投影操作把全关系的属性

11、分成若干组，目标是把频繁使用的属性聚集在一起，且各片段只在键属性下重叠。例3 设：全局关系EMP(E#,Name,Dept,Job,Sal,tel)Key = E# 垂直分片： EMP1(E#, Name, Sal, tel) EMP2(E#, Dept, Job)第19页，共85页。3 数据库片段位置分配的设计两种方式： 非冗余分配：一个片段映射到一个站点 冗余分配：一个片段映射到多个站点非冗余“最佳适应”分配法： 计算：Bij = k( Fkj * Nki ) 即，计算所有的应用在站点j上访问片段i 的总次数。 对所有站点j确定j, 使得Bij = max( Bij )即，把片段Ri分配到

12、有最大访问次数的站点j。i-片段序号j-站点序号k-应用序号Fkj-应用k在站点j上激活的频率Rki-应用k对片段i 进行检索访问的次数(Read)Uki-应用k对片段i 进行更新访问的次数Nki = Rki + Uki -应用k对片段i进行访问的总次数第20页，共85页。冗余分配比较复杂，一般采用下列方法之一进行估算：-所有得益站点法：-附加复制法（1）“所有得益站点”法对所有站点确定非冗余分配方案。从全部结点中选择一组站点，使得给这组站点分配片段Ri的一个拷贝所得到的检索效益，大于从其它站点对Ri实施更新的代价。把片段Ri拷贝分配给该组站点第21页，共85页。（2）附加拷贝法对所有站点确定

13、非冗余分配方案。计算把片段Ri分配给所有站点所能得到的总效益fi（以及一个站点分得Ri所得到的效益）从分得片段Ri能够获取最大益处的站点起，对各站点依次附加片段Ri的一个拷贝，直到增加片段Ri不能使系统得到明显效益（或者说效益增大“接近”fi ）为止。总结：数据库片段及位置分配的设计所需要 的参数均从应用需求中得来，总结这些参数可用如下三个表表达：A 频率表：各站点每一应用激活的次数B 划分表：各实体的潜在水平分片规则C 极化表：给定站点发出一给定应用访问一给定片段的概率第22页，共85页。需求分析全局概念模型全局逻辑模型分片设计系统实现试运行及维护分布设计局部逻辑设计物理设计频率表划分表极化

14、表第23页，共85页。分布式数据库设计的一个例子订票系统维护分布在三个网络站点（与机场1，2，3处于同一地理区域）上的数据库。数据库存储机场规程、班机起降和旅客订票等数据。（1）概念设计-全局概念模式（E-R图）第24页，共85页。（2）收集数据与其最相关的应用知识-用操作模式表示a 订票: 用于旅客预订机票。第25页，共85页。b 登记: 用于旅客登机登记任务记录。第26页，共85页。c 起飞应用:查询即将从一个机场起飞的30个班机信息。第27页，共85页。（3）在操作模式的基础上，对每一实体估算应用的定量数据，建立逻辑访问表例“班机”实体逻辑访问表第28页，共85页。（4）分布需求分析a.

15、 频率表：调研并给出在三个站点上使用各个应用的频率（激活的次数）第29页，共85页。b.划分表：分析各个实体各种可能的分片方式及其选择性*基本划分第30页，共85页。*导出划分注释表：第31页，共85页。c.极化表：调研并给出从一个站点发出一个应用所需要访问某片段的概率。第32页，共85页。（5）飞机订票系统的分布式设计a.为各个实体选择合适的分片,原则:满足本地性，不造成应用困难。对本例来予，各个实体采用水平分片： “机场” 由基于区域的基本水平分片（片段(F1F3)：机场1，机场2，机场3） “班机” 由基于起飞机场区域的导出水平分片（片段(A1A3) ：班机1，班机2，班机3） “旅客”

16、 由基于旅客订票涉及的班机起飞机场所在区域的导出水平分片（片段(P1P7)：旅客1，旅客2，旅客3，旅客7）第33页，共85页。b.进行片段的非冗余分配：1）站点1：机场1，班机1，旅客12）站点2：机场2，班机2，旅客2 旅客4，旅客6，旅客73）站点3：机场3，班机3，旅客3 旅客5根据频率表和极化表c.进行片段的冗余分配： 根据应用可以将旅客4.5.6分配在两个站点上，旅客7分配在三个站点上。第34页，共85页。（6）重构局部模式第35页，共85页。第36页，共85页。第37页，共85页。本节要点1. 理解分布式数据库系统的基本概念及特征，总结分布式数据库分片设计方法。熟练掌握使用SQL

17、语句，定义全局关系模式的分片方法。2. 总结“自顶向下”设计分布式数据库的方法。掌握从设计全局设计模式到各站点上局部模式的分布设计方法。3. 理解分布式数据库片段分配设计方法的思想。第38页，共85页。2.分布式数据库查询处理一、分布式查询处理的步骤查询分析若该查询属于局部查询，则执行局部查询处理后，即可结束。查询分解把全局查询或远程查询转换成定义在全局关系上的关系代数表达式，并优化该表达式。查询本地化把一个全局关系上的查询，转化为对片段的局部查询。全局查询优化：找出对各个片段局部查询结果之间的最佳操作次序，使得代价最小。其重点在连接运算和并运算的优化局部优化：由确定的片段所在站点执行第39页

18、，共85页。二、分布式查询处理的代价QC估算： QC=I/O+通信代价T*通信代价T估算T = 传输次数（每次传输延迟时间+ 每次传输数据量/ 数据传输速率）= 传输次数（C0 + X / D）第40页，共85页。三、分布式查询策略的重要性：例设：教学数据库中：S(S#, Sname, Age, Sex) 10,000个元组， 存放在A站点（男/女各一半）SC(S#, C#, Grade) 1,000,000个元组， 存放在A站点（每人选课100门）C(C#, Cname, Teacher) 100,000个元组， 存放在B站点假设：每个元组的长度为100 bit; 通信系统传输速率为10,0

19、00bit / 秒；每次通信延迟时间为1秒。查询：选修课名Maths 的男生的学号和姓名对于本例， C0 = 1秒，D = 10,000 bit / 秒第41页，共85页。解：SQL语句是： SELECT S.S#, Sname FROM S, SC, C WHERE S.S# = SC.S# AND SC.C# = C.C# AND SEX = M AND Cname = Maths策略1：把关系C传到A站点；在A站点进行处理。T1 = 1 + (100,000 *100) / 10,000 16.7(分)第42页，共85页。策略2：先在A站点找出男生选课情况（每人平均选100门课），再根据

20、C#向B站点核查这些男生的选课是否是Maths。(结果在A站点)T3 = 2 * 500,000 *1秒 11.6 (天)策略3：先在B站点找出Maths元组（假设最多有10门），再把查找结果传到A站点，在A站点继续执行查询处理。T6 = 1 + 10* 100/10,000 1秒第43页，共85页。四、基于关系代数等价变换的查询优化例1 S(S#, Sname, Age, Sex) SC(S#, C#, Grade)其中，S 和SC都采取水平分片：用户查询：SELECT distinct Sname FROM S, SC WHERE S.S# = SC.S# and Sex = M and

21、Grade 90转成关系代数表达式：Sname ( Sex = M Grade 90 ( S.S#=SC.S#( S SC ) ) )第44页，共85页。把关系代数表达式转换成查询树并优化从全局查询到片段查询的转换第45页，共85页。优化片段查询树a. 对于水平分片，检查选择运算（）与水平分片的条件（谓词）。b. 对于垂直分片，注意消去不提供连接运算后所需要属性的分支。第46页，共85页。例2 设：全局关系:EMP(E#, Ename, Sal, Dept, Dname)现采取垂直分片：查询问题：SELECT Ename, SalFROM EMP查询关系代数表达式Ename, Sal( EMP

22、 )第47页，共85页。第48页，共85页。五 基于半连接算法的全局查询优化1、半连接运算:由投影和连接操作导出的一种关系代数操作。设：关系R和S在属性R.A=S.B上的半连接操作记为：RA=BS=R ( RA=BS )(B (S)=RA=BSA=BR=S ( SA=BR )(A (R)=SA=B或者:2、利用半连接运算实现连接运算S=RA=B(RA=BS)A=BS(SA=BR)A=BR或者:S=RA=B第49页，共85页。3.采用半连接运算实现连接运算的代价及优化令：tuple(R) 表示关系R的元组数 size(B) 表示属性B的数据长度现假设，用户希望在站点2上得到R 与 S自然连接的结

23、果RS网络站点1站点2RS网络站点1站点2(1)B(S)(2)传送B(S)(3)R=RB(S)B(4)传送R(5)RSB第50页，共85页。总代价：T半= 2C0 + C1 *size(B) * tuple(B(S) +size(R) * tuple(R) 采用半连接操作优化的原理：两个关系进行连接操作之前，去掉无用的无组，减少数据传输量。采用直接连接运算的总代价：T = C0 + C1 * size(R) * tuple(R)选择半连接实现连接运算的原则：经半连接操作产生少量元组。4. 查询优化策略1）计算各种半连接运算的代价。2）计算直接连接运算的代价。3）比较并选出最优者。第51页，共8

24、5页。六 基于直接连接算法的查询优化1、利用站点依赖信息的连接算法R1R2=F11F21(F12F22)其成立的条件是什么?第52页，共85页。条件： A(F11) A(F12) = A(F21) A(F22) = A(F11) A(F22) = A(F12) A(F21) = 站点依赖：设：RiA、RjA、SiA 、SjA分别表示关系R、S在站点i、j的A属性上的取值。若对于i j ,有： RiA SjA = ,则称关系R和S在属性A上站点依赖。性质：若关系R和S在属性A上站点依赖，则：iRS=(RiSi)第53页，共85页。推论：* 如果R和S在属性A上站点依赖，B A,则，R和S在属性B

25、上站点依赖。* 如果R和S在属性A上站点依赖， S和T在属性B上站点依赖，则：RS=(RiSiTiTi）使用站点依赖算法实现直接连接运算的优点:1）无数据传送2）可进行并行计算3）可利用本地索引在查询优化过程中，可以判断什么时候使用站点依赖算法（P87）第54页，共85页。2、分片和复制算法当查询不能在无数据传送方式下处理，可采用分片和复制算法，算法的原理： 选择一组站点，将查询中的某一个关系的所有片段分布到这些站点上，然后把查询中的其余关系复制到每一个选定的站点上。优点：1）可进行并行计算 2）在一定程度上可利用本地索引选择方法：从假定某一关系分片，其余关系复制，计算代价，然后再选择另一关系

26、为分片，最后从中选择代价最小的方案。第55页，共85页。本节重点1. 总结分布式数据库查询优化的主要步骤，并与集中式数据库查询优化相比较。2. 总结利用半连接算法实现直接连接运算的全局查询优化方法特点。在什么条件下可以利用半连接算法实现直接连接运算？第56页，共85页。3.分布式事务管理及恢复的讨论一、分布式事务概述1.事务的特点分布式数据库的事务称为全局事务。一个全局事务在执行时分解为由若干与相应站点有关的操作序列组成的“子事务”。1. 原子性 2. 一致性（或可串行性）3. 隔离性 4. 持久性 5. 系统效率6. 系统可用性：分布式事务既不能影响本站点上事务的执行，也不能影响其它站点上事

27、务的执行第57页，共85页。Begin Transaction 开始事务T1T2TnCommit / Abort (或Rollback) 结束事务子事务或操作序列全局事务3 分布式事务代理执行机制2. 分布式事务的结构事务代理的概念：一个事务代理就是一个站点上的一个进程第58页，共85页。应用请求（源站点总代理根代理）RollbackCommit总代理（根代理）子事务1失败子事务1成功子事务代理n子事务代理1Begin Transaction子事务n失败子事务n成功第59页，共85页。例银行转帐事务：把帐号FROM_ACC上数量为AMOUNT的资金，转入帐号TO_ACC。全局应用事务：read

28、(AMOUNT, FROM_ACC, TO_ACC);begin transactionselect BALANCE into FROM_AMOUNTfrom ACCOUNT_TABLEwhere ACCOUNT_NO = FROM_ACC;if FROM_AMOUNT - AMOUNT 0then abortelse beginupdate ACCOUNT_TABLEset BALANCE = BALANCE - AMOUNTwhere ACCOUNT_NO = FROM_ACC;update ACCOUNT_TABLEset BALANCE = BALANCE + AMOUNTwhere

29、ACCOUNT_NO = TO_ACC;commitend第60页，共85页。设：转出帐户在源站点上。ROOT_AGENT:read(AMOUNT, FROM_ACC, TO_ACC);begin transactionselect BALANCE into FROM_AMOUNTfrom ACCOUNT_TABLEwhere ACCOUNT_NO = FROM_ACC;if FROM_AMOUNT - AMOUNT 0then abortelse beginupdate ACCOUNT_TABLEset BALANCE = BALANCE - AMOUNTwhere ACCOUNT_NO =

30、 FROM_ACC;create AGENT;send to AGENT(AMOUNT, TO_ACC);waittingcommit / abortend第61页，共85页。AGENT（子代理）:begin transactionreceive from ROOT_AGENT( AMOUNT,TO_ACC );update ACCOUNT_TABLEset BALANCE = BALANCE + AMOUNTwhere ACCOUNT_NO = TO_ACC;send to ROOT_AGENT(SUCCESS / FAIL)waittingcommit / abort第62页，共85页。二

31、. 分布式事务的两阶段提交协议2-PC:Two-Phase Commitment Protocal协调者日志参与者。参与者参与者日志日志日志两阶段提交协议的活动机制：第63页，共85页。初始协调者写end of trans到日志初始参与者写begin transaction等待准备提交写ready到日志有要求撤消的？写abort到日志提交撤消就绪消息类型?撤消提交准备撤消提交全局撤消全局提交写abort到日志no写commit到日志no写abort到日志abort写commit到日志commit第64页，共85页。两阶段提交协议的执行过程：1）表决阶段：对当前事务形成一个决定。 协调者： 写“

32、开始事务”日志； 向各个参与者发出“准备”命令； 进入等待状态。 对于每一个参与者 参与者接收“准备”消息； 参与者检查子事务，确定是否提交子事务： Case1:可以提交子事务： 参与者写“就绪”日志； 向协调者发“建议提交”消息； 参与者进入“就绪”状态。 Case2:不可以提交子事务： 参与者写“撤消”日志； 向协调者发“建议撤消”消息； 参与者进入“撤消”状态。第65页，共85页。 协调者接收到所有参与者的回答后，作出决定：Case1: 若所有参与者发出“建议提交”的消息，则，协调者作出提交全局事务的决定。 协调者写提交日志； 协调者发出“全局提交”消息； 协调者进入“提交”状态。Cas

33、e2: 若发现某参与者发出“建议撤消”的消息，则，协调者作出撤消全局事务的决定。 协调者写撤消日志； 协调者发出“全局撤消”消息； 协调者进入“撤消”状态。 “一票否决”制！2）执行阶段 对于每一个处于“就绪”状态的参与者： 参与者根据协调者发出的全局事务处理指令，或者撤消子事务，或者提交子事务第66页，共85页。 参与者发出“确认”(ACK)收到全局事务处理指令消息。 参与者进入“撤消”或“提交”状态。 协调者写“结束事务”日志。两阶段提交协议的特点： 参与者有权单方面撤消事务。 参与者作出“建议提交” 或“建议撤消”决定之后，不能“翻悔”。 处于“就绪”状态的参与者可能进入提交状态，或撤消

34、状态。 协调者和参与者可能进入互相等待状态。第67页，共85页。1. 试比较集中式、分布式事务的特点。2. 总结分布式数据库2-PC的特点，并指出它所存在的问题。本节重点第68页，共85页。4.分布式数据库并发控制机制一、分布式并发控制概述1 分布式并发控制的目的：为并发执行的全局事务，产生一个可串行化调度。2 局部调度：每个站点上的调度称为局部调度3 全局调度：数据库系统全局事务的调度。4全局调度的可串行性局部调度的可串行性！局部调度的可串行性：全局调度的可串行性？问题：一个数据对象x，可能存在多个副本x1, x2, , xn。第69页，共85页。T1: Read(y);y := y 15;

35、Write(y);Commit;T2: Read(y);y := y * 2;Write(y);Commit;站点1 调度S1 = R1, W1, C1, R2, W2, C2 站点2 调度S2 = R2, W2, C2 , R1, W1, C1 设：站点1，站点2上都有y的副本，且都执行事务T1, T2。全局调度不可串行！5. 全局调度的冲突可串行性应满足的条件:单副本控制协议1) 每一个局部调度是冲突可串行化的。2) 任意两个冲突操作在它们同时出现的各个局部调度中，必须有相同的执行顺序。第70页，共85页。二、并发控制法并发控制算法悲观法乐观法封锁法时标排序法混合法加锁法时标排序法集中式加

36、锁主副本加锁分布式加锁基本时标排序法多版本时标排序保守时标排序第71页，共85页。1）集中式加锁法:网络中某一个站点被指定为主站点，用于存放整个分布式数据库的加锁表，负责整个系统事务的加锁.2）主副本加锁法：每个数据对象指定一个主副本，不同数据对象的主副本放在不同站点上。算法：对主副本加锁；执行更新操作；开锁3）分布式加锁算法：锁的管理由各个站点调度器参与、协调，本地调度器负责本站数据加锁。算法：对全部副本加锁；执行更新操作；开锁第72页，共85页。三、分布式数据库并发控制的加锁技术1. 分布式数据库加锁准则 读，锁一个；写，锁全部(ROWA协议)。 遵守锁的相容性规则 遵守两段锁协议（Two

37、 Phase Locking-2PL) 持有X锁的事务，必须到结束事务才能开锁。2、死锁管理1）全局死锁：分布式数据库中，涉及多个站点的死锁称为全局死锁。第73页，共85页。站点A站点B事务T1持有对X的锁事务T2持有对Y的锁事务T2请求对X的锁事务T1请求对Y的锁T2等待T1完成释放对X的锁T1等待T2完成释放对Y的锁第74页，共85页。2）全局等待图（GWFG）站点A:拥有x 、y的副本；T1: read(x), write(y)站点B:拥有y 、z的副本；T2: read(y), write(z)站点C:拥有z 的副本； T3: read(z), write(x)T1T2T3Xyz第75

38、页，共85页。3）死锁的检测A 集中式死锁检测法 指定某站点上的锁管理器作为全局死锁检测器 其余站点周期地向全局死锁检测器发送LWFG 全局死锁检测器产生GWFG，并检测有无回路B 分布式死锁检测法 每个站点都有死锁检测器，负责检测本地可能的死锁。 每个站点按照一定规则，向相关站点发送潜在的死锁回路图。4）死锁的解决原则：撤消并恢复代价最小的事务。 撤消并恢复年轻的事务。 撤消并恢复占用资源较少的事务。 撤消并恢复具有最短运行时间的事务。第76页，共85页。四 并发控制的时标技术1. 时标:唯一识别一个事务，并用于对事务进行排序的标识符。2. 时标的构成：“本地计数器值， 站点标识符3. 时标

39、的创建：一个事务Ti 初始化时，事务管理器给该事务分配一个时标ts(Ti )4. 时标排序（TO）规则：已知Qi和Qj是分别属于事务Ti和Tj冲突操作。若ts(Ti) ts(Tj) , 则Qi在Qj之前执行。5、基本时标法第77页，共85页。规则：1）每个事务在本地站点开始时被赋以一个全局唯一的时标。3）事务的每个读或写操作都有该事务的时标。2）如果事务被重新启动，则被赋予新的时标。4）在事务结束之前，不对数据库进行物理操作。5）对于数据库每个数据对象x，记录对它进行读操作和写操作的最大时标RTM(x)和WTM(x)基本时标法的执行过程：1）设TS是对数据对象x进行读操作的当前时标。若TS WTM(x)， 则， 拒绝该操作；并使发出该操作的事务用新时标重新启动；否则， 执行读操作，且使： RTM(x) = max（