第六讲-分布式数据库及相关问题课件

第六部分分布式数据库及相关技术的讨论（第8-11章内容）一分布式数据库概述产生和发展概念和分类体系结构模式结构及独立性。。。二分布式数据库系统中存在的技术问题分布式DB的设计分布式DB的查询分布式DB的事务管理及并发。。。第六部分分布式数据库及相关技术一分布式数据库概述1一分布式数据库概述I分布式数据库的产生及发展a经济的发展b计算机硬件环境及网络的发展发展历程：产生于20世纪70年代末期，成长于80年代第一个分布式数据库系统SDD-1是美国计算机公司（CAA）于1976年-1978年设计，79年在DEC-10/20上实现。德国斯图加特大学研制的porel系统美国IBM的R*和systemR美国加大学伯克利分校的Ingres法国INRA研制的SIRIUS-DELTA。。。一分布式数据库概述I分布式数据库的产生及发展a经济的发21987年：C.JDate提出了完全的，真正的分布式DBS应遵循的12条规则：本地自治性不依赖于中心站点可连续操作位置独立性数据分片独立性数据复制独立性分布式查询独立性分布式事务管理硬件独立性操作系统独立性网络独立性DBMS独立性1987年：C.JDate提出了完全的，真正的分布式DBS3II分布式数据库系统的定义及分类1分布式数据库的定义：

分布式数据库是一个数据集合，这些数据分布在由计算机网络连接起来的若干节点上，每个节点可以管理本地的数据应用，也可以参与全局数据应用。同时这些数据在逻辑上形成一个整体，由统一的数据库管理系统进行管理。（DDBMS）注：几个基本的概念站点：计算机连接的一个逻辑单位，称为一个站点。本地（或称：局部）用户、本地应用：一个用户或应用只访问他所注册的那个站点。全局用户、全局应用：一个用户访问涉及两个或两个以上的站点中的数据。全局数据库（GDB）、局部数据库（LDB）：。。。II分布式数据库系统的定义及分类1分布式数据库的定义：注42.分布式数据库系统的基本特点：A结构特点：物理分布，逻辑相关。B应用特点：站点自治。2.分布式数据库系统的基本特点：A结构特点：物理分布，逻5多处理机系统C.数据分布透明性：数据的物理独立性内容更丰富，增加了数据分布透明性。---数据的逻辑分片、数据的物理位置分布、数据的复制，对用户透明。D.集中与自治兼备的数据库系统控制机制.---两个层次的数据共享：局部/全局数据共享。多处C.数据分布透明性：数据的物理独立性内容更丰富，增加了数6E.增加数据冗余度。---利用数据冗余提高系统可靠性、可用性和系统性能。F.事务管理的分布性。---分布环境下，维护事务的原子性、一致性、隔离性和持久性。E.增加数据冗余度。F.事务管理的分布性。73.分布式数据库系统的模式结构3.分布式数据库系统的模式结构84.分布式数据库系统的分类A按局部DBMS的数据模型分类：---同构型：数据模型相同*同质同构：数据模型相同且局部DBMS相同。*异质同构：数据模型相同外交部局部DBMS不同。

SDD-1和DDM美国CCA公司SYSTEMR*美国IBM公司POREL德国斯图加特大学

---异构型：数据模型不同MULTIBASE美国CCA1981研制IMADAS:H佛罗里达大学1984研制DDTSHONEYWELL公司1980年研制。。。4.分布式数据库系统的分类A按局部DBMS的数据模型分类：9B按全局控制系统类型分类：---全局控制集中型DDBSDDBS的全局控制机制及数据字典位于一个中心站点，由中心站点完成全局事务的协调和局部数据库的转换等所有控制功能。---全局控制分散型DDBS

DDBS的全局控制机制及数据字典分散在网络的各个站点上，每个站点都能完成全局事务的协调和局部数据转换。---全局控制可变型（主从型）将站点分成两组，一组都包含全局控制机制和数据字典，另一组为辅助站点，只包含自己的数据应用。B按全局控制系统类型分类：104.分布式数据库管理系统的功能结构：除了具有集中式DBMS具有的功能外，还要有如下附加的功能：*数据跟踪*分布式查询处理能力*分布式事务管理的能力*复制数据的能力*安全性*分布式目录管理4.分布式数据库管理系统的功能结构：除了具有集中式DBMS具11二.分布式数据库系统中存在的技术问题：1分布式数据库系统的设计--全局模式的设计--数据分片，分布2分布式数据库的查询处理3分布式数据库的事务管理及并发控制4分布式数据库的可靠性5异构数据库的连接6安全性7目录管理二.分布式数据库系统中存在的技术问题：1分布式数据库系统12§1.分布式数据库设计一方法：根据设计是基于现存的数据系统还是构造一个全新的数据库系统，有两种方法创建分布式数据库：

组合法：基于现有的系统，建立一个协调管理系统。--采用自底向上的方式构建

重构法：创建全新的数据库系统--自顶向下的方式构建二分布式数据库设计的内容：

1.数据库设计基础---需求分析1）数据需求2）应用需求●应用的原发站点：发出应用请求的站点●应用在站点被激活的频率●应用对数据对象访问次数、类型和分布统计§1.分布式数据库设计一方法：二分布式数据库设计的内容：132.数据库设计（设计的核心任务）全局模式设计局部数据库设计数据分片设计片段的位置分配设计三分布式数据库设计的目标：确保数据库数据和应用具有最大程度的本地性。分布式数据的可用性和可靠性工作负荷分布存储的能力和费用2.数据库设计（设计的核心任务）三分布式数据库设计的目标14四自顶向下的方式构建分布式数据库需求分析全局概念模型全局逻辑模型分片设计系统实现试运行及维护分布设计局部逻辑设计物理设计1设计的步骤：四自顶向下的方式构建分布式数据库需全全分系试分局物1设计152数据库的分片设计（1）.什么叫“片段”？指在分布式数据库系统中，某一站点上存储的数据集合。（2）.分片设计的目的？产生全局数据的一个合理的划分，从而使每个站点只获得它所需要的数据，最大可能保证应用的本地性。（3）分片应遵循的一般规则：设：R={R1,R2,…,Rn}1）完整性即，t∈R,则，必有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,且i≠j）或Ri∩Rj=主码属性(i,j=1,…,n,且i≠j）2数据库的分片设计（1）.什么叫“片段”？（2）.分片设16（4）分片的基本类型和方法水平分片，垂直分片，混合分片A水平分片：对全关系进行选择操作，把具有相同性质的元组进行分组，构成若干不相交的子集。初级分片和导出分片初级分片：以关系自身属性性质分组例1S(S#,Sname,Age,Sex)definefragmentS1asselect*fromSwhereSex=‘M’；definefragmentS2asselect*fromSwhereSex=‘F’；（4）分片的基本类型和方法A水平分片：对全关系进行选择操作17导出分片：用其它关系的属性对某一全关系进行分组例2设：全局关系SC(S#,C#,Grade)S(S#,Sname,Age,Sex)设计需求：按S的“性别”属性（Sex）去划分SCDefinefragmentSC1asselectSC.S#,C#,GradefromSC,SwhereSC.S#=S.S#andS.Sex=‘M’DefinefragmentSC2asselectSC.S#,C#,GradefromSC,SwhereSC.S#=S.S#andS.Sex=‘F’导出分片：用其它关系的属性对某一全关系进行分组例2设：全18B垂直分片：利用投影操作把全关系的属性分成若干组，目标是把频繁使用的属性聚集在一起，且各片段只在键属性下重叠。例3设：全局关系EMP(E#,Name,Dept,Job,Sal,tel)Key={E#}垂直分片：EMP1(E#,Name,Sal,tel)EMP2(E#,Dept,Job)B垂直分片：利用投影操作把全关系的属性分成若干组，目标是193数据库片段位置分配的设计两种方式：非冗余分配：一个片段映射到一个站点冗余分配：一个片段映射到多个站点非冗余“最佳适应”分配法：计算：Bij=Σk(Fkj*Nki)即，计算所有的应用在站点j上访问片段i的总次数。对所有站点j确定j′,使得Bij′=max(Bij)即，把片段Ri分配到有最大访问次数的站点j′。i--片段序号j---站点序号k---应用序号Fkj----应用k在站点j上激活的频率Rki----应用k对片段i进行检索访问的次数(Read)Uki----应用k对片段i进行更新访问的次数Nki=Rki+Uki----应用k对片段i进行访问的总次数3数据库片段位置分配的设计两种方式：非冗余“最佳适应”分配20冗余分配比较复杂，一般采用下列方法之一进行估算：--所有得益站点法：--附加复制法（1）“所有得益站点”法对所有站点确定非冗余分配方案。从全部结点中选择一组站点，使得给这组站点分配片段Ri的一个拷贝所得到的检索效益，大于从其它站点对Ri实施更新的代价。把片段Ri拷贝分配给该组站点冗余分配比较复杂，一般采用下列方法之一进行估算：（1）“所有21（2）附加拷贝法对所有站点确定非冗余分配方案。计算把片段Ri分配给所有站点所能得到的总效益fi（以及一个站点分得Ri所得到的效益）从分得片段Ri能够获取最大益处的站点起，对各站点依次附加片段Ri的一个拷贝，直到增加片段Ri不能使系统得到明显效益（或者说效益增大“接近”fi）为止。总结：数据库片段及位置分配的设计所需要的参数均从应用需求中得来，总结这些参数可用如下三个表表达：A频率表：各站点每一应用激活的次数B划分表：各实体的潜在水平分片规则C极化表：给定站点发出一给定应用访问一给定片段的概率（2）附加拷贝法对所有站点确定非冗余分配方案。总结：数据库片22需求分析全局概念模型全局逻辑模型分片设计系统实现试运行及维护分布设计局部逻辑设计物理设计频率表划分表极化表需全全分系试分局物频率表划分表极化表23分布式数据库设计的一个例子订票系统维护分布在三个网络站点（与机场1，2，3处于同一地理区域）上的数据库。数据库存储机场规程、班机起降和旅客订票等数据。（1）概念设计---全局概念模式（E-R图）分布式数据库设计的一个例子订票系统维护分布在三个网络站点（与24（2）收集数据与其最相关的应用知识---用操作模式表示a订票:用于旅客预订机票。（2）收集数据与其最相关的应用知识---用操作模式表示a订25b登记:用于旅客登机登记任务记录。b登记:用于旅客登机登记任务记录。26c起飞应用:查询即将从一个机场起飞的30个班机信息。c起飞应用:查询即将从一个机场起飞的30个班机信息。27（3）在操作模式的基础上，对每一实体估算应用的定量数据，建立逻辑访问表例“班机”实体逻辑访问表（3）在操作模式的基础上，对每一实体估算应用的定量数据，例“28（4）分布需求分析a.频率表：调研并给出在三个站点上使用各个应用的频率（激活的次数）（4）分布需求分析a.频率表：调研并给出在三个站点上使用各29b.划分表：分析各个实体各种可能的分片方式及其选择性*基本划分b.划分表：分析各个实体各种可能的分片方式及其选择性*基本划30*导出划分注释表：*导出划分注释表：31c.极化表：调研并给出从一个站点发出一个应用所需要访问某片段的概率。c.极化表：调研并给出从一个站点发出一个应用所需要访问某片段32（5）飞机订票系统的分布式设计a.为各个实体选择合适的分片,原则:满足本地性，不造成应用困难。对本例来予，各个实体采用水平分片：●“机场”由基于区域的基本水平分片（片段(F1～F3)：机场1，机场2，机场3）●“班机”由基于起飞机场区域的导出水平分片（片段(A1～A3)：班机1，班机2，班机3）●“旅客”由基于旅客订票涉及的班机起飞机场所在区域的导出水平分片（片段(P1～P7)：旅客1，旅客2，旅客3，……，旅客7）（5）飞机订票系统的分布式设计a.为各个实体选择合适的分片,33b.进行片段的非冗余分配：1）站点1：机场1，班机1，旅客12）站点2：机场2，班机2，旅客2旅客4，旅客6，旅客73）站点3：机场3，班机3，旅客3旅客5根据频率表和极化表c.进行片段的冗余分配：根据应用可以将旅客4.5.6分配在两个站点上，旅客7分配在三个站点上。b.进行片段的非冗余分配：1）站点1：机场1，班机1，旅客134（6）重构局部模式（6）重构局部模式35第六讲-分布式数据库及相关问题课件36第六讲-分布式数据库及相关问题课件37本节要点1.理解分布式数据库系统的基本概念及特征，总结分布式数据库分片设计方法。熟练掌握使用SQL语句，定义全局关系模式的分片方法。2.总结“自顶向下”设计分布式数据库的方法。掌握从设计全局设计模式到各站点上局部模式的分布设计方法。3.理解分布式数据库片段分配设计方法的思想。本节要点1.理解分布式数据库系统的基本概念及特征，总结分布38§2.分布式数据库查询处理一、分布式查询处理的步骤查询分析若该查询属于局部查询，则执行局部查询处理后，即可结束。查询分解把全局查询或远程查询转换成定义在全局关系上的关系代数表达式，并优化该表达式。查询本地化把一个全局关系上的查询，转化为对片段的局部查询。全局查询优化：找出对各个片段局部查询结果之间的最佳操作次序，使得代价最小。其重点在连接运算和并运算的优化局部优化：由确定的片段所在站点执行§2.分布式数据库查询处理一、分布式查询处理的步骤查询分析若39二、分布式查询处理的代价QC估算：QC=I/O+通信代价T*通信代价T估算T=Σ传输次数（每次传输延迟时间+每次传输数据量/数据传输速率）=Σ传输次数（C0+X/D）二、分布式查询处理的代价QC估算：*通信代价T估算T=Σ40三、分布式查询策略的重要性：例设：教学数据库中：S(S#,Sname,Age,Sex)10,000个元组，存放在A站点（男/女各一半）SC(S#,C#,Grade)1,000,000个元组，存放在A站点（每人选课100门）C(C#,Cname,Teacher)100,000个元组，存放在B站点假设：每个元组的长度为100bit;通信系统传输速率为10,000bit/秒；每次通信延迟时间为1秒。查询：选修课名‘Maths’的男生的学号和姓名对于本例，C0=1秒，D=10,000bit/秒三、分布式查询策略的重要性：例设：教学数据库中：S(S#,41解：SQL语句是：SELECTS.S#,SnameFROMS,SC,CWHERES.S#=SC.S#ANDSC.C#=C.C#ANDSEX=‘M’ANDCname=‘Maths’策略1：把关系C传到A站点；在A站点进行处理。T1=1+(100,000*100)/10,000≈16.7(分)解：SQL语句是：策略1：把关系C传到A站点；在A站点进行处42策略2：先在A站点找出男生选课情况（每人平均选100门课），再根据C#向B站点核查这些男生的选课是否是‘Maths’。(结果在A站点)T3=2*500,000*1秒≈11.6(天)策略3：先在B站点找出‘Maths’元组（假设最多有10门），再把查找结果传到A站点，在A站点继续执行查询处理。T6=1+10*100/10,000≈1秒策略2：先在A站点找出男生选课情况（每人平均选100门课），43四、基于关系代数等价变换的查询优化例1S(S#,Sname,Age,Sex)SC(S#,C#,Grade)

其中，S和SC都采取水平分片：用户查询：SELECTdistinctSnameFROMS,SCWHERES.S#=SC.S#andSex=‘M’andGrade>90转成关系代数表达式：πSname(σSex=‘M’∧Grade>90(σS.S#=SC.S#(S×SC)))四、基于关系代数等价变换的查询优化例1S(S#,Snam44把关系代数表达式转换成查询树并优化从全局查询到片段查询的转换把关系代数表达式转换成查询树并优化从全局查询到片段查询的转换45优化片段查询树a.对于水平分片，检查选择运算（σ）与水平分片的条件（谓词）。b.对于垂直分片，注意消去不提供连接运算后所需要属性的分支。优化片段查询树a.对于水平分片，检查选择运算（σ）与水平分46例2设：全局关系:EMP(E#,Ename,Sal,Dept,Dname)现采取垂直分片：查询问题：SELECTEname,SalFROMEMP查询关系代数表达式πEname,Sal(EMP)例2设：全局关系:EMP(E#,Ename,Sal,47第六讲-分布式数据库及相关问题课件48五基于半连接算法的全局查询优化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五基于半连接算法的全局查询优化1、半连接运算:由投影和连接493.采用半连接运算实现连接运算的代价及优化令：tuple(R)表示关系R的元组数size(B)表示属性B的数据长度现假设，用户希望在站点2上得到R与S自然连接的结果RS网络站点1站点2RS网络站点1站点2(1)πB(S)(2)传送πB(S)(3)R′=RπB(S)B(4)传送R′(5)R′SB3.采用半连接运算实现连接运算的代价及优化令：tuple(R50总代价：T半=2C0+C1*[size(B)*tuple(πB(S))+size(R′)*tuple(R′)]采用半连接操作优化的原理：两个关系进行连接操作之前，去掉无用的无组，减少数据传输量。采用直接连接运算的总代价：T=C0+C1*size(R)*tuple(R)选择半连接实现连接运算的原则：经半连接操作产生少量元组。4.查询优化策略1）计算各种半连接运算的代价。2）计算直接连接运算的代价。3）比较并选出最优者。总代价：T半=2C0+C1*[size(B)*t51六基于直接连接算法的查询优化1、利用站点依赖信息的连接算法∪R1R2=F11F21(F12F22)其成立的条件是什么?六基于直接连接算法的查询优化1、利用站点依赖信息的连接算法52条件：πA(F11)∩πA(F12)=φπA(F21)∩πA(F22)=φπA(F11)∩πA(F22)=φπA(F12)∩πA(F21)=φ站点依赖：设：Ri[A]、Rj[A]、Si[A]、Sj[A]分别表示关系R、S在站点i、j的A属性上的取值。若对于i≠j,有：Ri[A]∩Sj[A]=φ,则称关系R和S在属性A上站点依赖。性质：若关系R和S在属性A上站点依赖，则：∪iRS=(RiSi)条件：πA(F11)∩πA(F12)=φπA(F253推论：*如果R和S在属性A上站点依赖，B⊇A,则，R和S在属性B上站点依赖。*如果R和S在属性A上站点依赖，S和T在属性B上站点依赖，则：RS=(RiSiT∪iTi）使用站点依赖算法实现直接连接运算的优点:1）无数据传送2）可进行并行计算3）可利用本地索引在查询优化过程中，可以判断什么时候使用站点依赖算法（P87）推论：*如果R和S在属性A上站点依赖，B⊇A,则，R和542、分片和复制算法当查询不能在无数据传送方式下处理，可采用分片和复制算法，算法的原理：选择一组站点，将查询中的某一个关系的所有片段分布到这些站点上，然后把查询中的其余关系复制到每一个选定的站点上。优点：1）可进行并行计算2）在一定程度上可利用本地索引选择方法：从假定某一关系分片，其余关系复制，计算代价，然后再选择另一关系为分片，最后从中选择代价最小的方案。2、分片和复制算法当查询不能在无数据传送方式下处理，可采用分55本节重点1.总结分布式数据库查询优化的主要步骤，并与集中式数据库查询优化相比较。2.总结利用半连接算法实现直接连接运算的全局查询优化方法特点。在什么条件下可以利用半连接算法实现直接连接运算？本节重点1.总结分布式数据库查询优化的主要步骤，并与集中式56§3.分布式事务管理及恢复的讨论一、分布式事务概述1.事务的特点分布式数据库的事务称为全局事务。一个全局事务在执行时分解为由若干与相应站点有关的操作序列组成的“子事务”。1.原子性2.一致性（或可串行性）3.隔离性4.持久性5.系统效率6.系统可用性：分布式事务既不能影响本站点上事务的执行，也不能影响其它站点上事务的执行§3.分布式事务管理及恢复的讨论一、分布式事务概述1.事务的57BeginTransaction开始事务T1T2……TnCommit/Abort(或Rollback)结束事务子事务或操作序列全局事务3分布式事务代理执行机制2.分布式事务的结构事务代理的概念：一个事务代理就是一个站点上的一个进程BeginTransaction开始事务T1Commit58应用请求（源站点总代理根代理）RollbackCommit总代理（根代理）子事务1失败子事务1成功子事务代理n子事务代理1BeginTransaction子事务n失败子事务n成功应用请求总代理根代理）RollbackCommit总代理（根59例银行转帐事务：把帐号FROM_ACC上数量为AMOUNT的资金，转入帐号TO_ACC。全局应用事务：read(@AMOUNT,@FROM_ACC,@TO_ACC);begintransactionselectBALANCEinto@FROM_AMOUNTfromACCOUNT_TABLEwhereACCOUNT_NO=@FROM_ACC;if@FROM_AMOUNT-@AMOUNT<0thenabortelsebeginupdateACCOUNT_TABLEsetBALANCE=BALANCE-@AMOUNTwhereACCOUNT_NO=@FROM_ACC;updateACCOUNT_TABLEsetBALANCE=BALANCE+@AMOUNTwhereACCOUNT_NO=@TO_ACC;commitend例银行转帐事务：把帐号FROM_ACC上数量为AMOUNT的60设：转出帐户在源站点上。ROOT_AGENT:read(@AMOUNT,@FROM_ACC,@TO_ACC);begintransactionselectBALANCEinto@FROM_AMOUNTfromACCOUNT_TABLEwhereACCOUNT_NO=@FROM_ACC;if@FROM_AMOUNT-@AMOUNT<0thenabortelsebeginupdateACCOUNT_TABLEsetBALANCE=BALANCE-@AMOUNTwhereACCOUNT_NO=@FROM_ACC;createAGENT;sendtoAGENT(@AMOUNT,@TO_ACC);waittingcommit/abortend设：转出帐户在源站点上。ROOT_AGENT:read(@A61AGENT（子代理）:begintransactionreceivefromROOT_AGENT(@AMOUNT,@TO_ACC);updateACCOUNT_TABLEsetBALANCE=BALANCE+@AMOUNTwhereACCOUNT_NO=@TO_ACC;sendtoROOT_AGENT(‘SUCCESS’/‘FAIL’)waittingcommit/abortAGENT（子代理）:begintransaction62二.分布式事务的两阶段提交协议2-PC:Two-PhaseCommitmentProtocal协调者日志参与者。。。参与者参与者日志日志日志两阶段提交协议的活动机制：二.分布式事务的两阶段提交协议协调者日志参与者。。。参与者63初始协调者写endoftrans到日志初始参与者写begintransaction等待准备提交写ready到日志有要求撤消的？写abort到日志提交撤消就绪消息类型?撤消提交准备撤消提交全局撤消全局提交写abort到日志no写commit到日志no写abort到日志abort写commit到日志commit初始协调者写endoftrans到日志初始参与者写beg64两阶段提交协议的执行过程：1）表决阶段：对当前事务形成一个决定。①协调者：●写“开始事务”日志；●向各个参与者发出“准备”命令；●进入等待状态。②对于每一个参与者●参与者接收“准备”消息；●参与者检查子事务，确定是否提交子事务：Case1:可以提交子事务：※参与者写“就绪”日志；※向协调者发“建议提交”消息；※参与者进入“就绪”状态。Case2:不可以提交子事务：※参与者写“撤消”日志；※向协调者发“建议撤消”消息；※参与者进入“撤消”状态。两阶段提交协议的执行过程：1）表决阶段：对当前事务形成一个决65③协调者接收到所有参与者的回答后，作出决定：Case1:若所有参与者发出“建议提交”的消息，则，协调者作出提交全局事务的决定。●协调者写提交日志；●协调者发出“全局提交”消息；●协调者进入“提交”状态。Case2:若发现某参与者发出“建议撤消”的消息，则，协调者作出撤消全局事务的决定。●协调者写撤消日志；●协调者发出“全局撤消”消息；●协调者进入“撤消”状态。“一票否决”制！2）执行阶段①对于每一个处于“就绪”状态的参与者：●参与者根据协调者发出的全局事务处理指令，或者撤消子事务，或者提交子事务③协调者接收到所有参与者的回答后，作出决定：2）执行阶段①66●参与者发出“确认”(ACK)收到全局事务处理指令消息。●参与者进入“撤消”或“提交”状态。②协调者写“结束事务”日志。两阶段提交协议的特点：●参与者有权单方面撤消事务。●参与者作出“建议提交”或“建议撤消”决定之后，不能“翻悔”。●处于“就绪”状态的参与者可能进入提交状态，或撤消状态。●协调者和参与者可能进入互相等待状态。●参与者发出“确认”(ACK)收到全局事务处理指令消息。两671.试比较集中式、分布式事务的特点。2.总结分布式数据库2-PC的特点，并指出它所存在的问题。本节重点1.试比较集中式、分布式事务的特点。2.总结分布式数据库68§4.分布式数据库并发控制机制一、分布式并发控制概述1分布式并发控制的目的：为并发执行的全局事务，产生一个可串行化调度。2局部调度：每个站点上的调度称为局部调度3全局调度：数据库系统全局事务的调度。4全局调度的可串行性→局部调度的可串行性！局部调度的可串行性：→全局调度的可串行性？问题：一个数据对象x，可能存在多个副本x1,x2,…,xn。§4.分布式数据库并发控制机制一、分布式并发控制概述1分布69T1:Read(y);y:=y–15;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)任意两个冲突操作在它们同时出现的各个局部调度中，必须有相同的执行顺序。T1:Read(y);T2:Read(y);站点1调度70二、并发控制法并发控制算法悲观法乐观法封锁法时标排序法混合法加锁法时标排序法集中式加锁主副本加锁分布式加锁基本时标排序法多版本时标排序保守时标排序二、并发控制法并发控制算法悲观法乐观法封锁法时标排序法混合法711）集中式加锁法:网络中某一个站点被指定为主站点，用于存放整个分布式数据库的加锁表，负责整个系统事务的加锁.2）主副本加锁法：每个数据对象指定一个主副本，不同数据对象的主副本放在不同站点上。算法：对主副本加锁；执行更新操作；开锁3）分布式加锁算法：锁的管理由各个站点调度器参与、协调，本地调度器负责本站数据加锁。算法：对全部副本加锁；执行更新操作；开锁1）集中式加锁法:网络中某一个站点被指定为主站点，用于存放整72三、分布式数据库并发控制的加锁技术1.分布式数据库加锁准则●读，锁一个；写，锁全部(ROWA协议)。●遵守锁的相容性规则●遵守两段锁协议（TwoPhaseLocking---2PL)●持有X锁的事务，必须到结束事务才能开锁。2、死锁管理1）全局死锁：分布式数据库中，涉及多个站点的死锁称为全局死锁。三、分布式数据库并发控制的加锁技术1.分布式数据库加锁准则73站点A站点B事务T1持有对X的锁事务T2持有对Y的锁事务T2请求对X的锁事务T1请求对Y的锁T2等待T1完成释放对X的锁T1等待T2完成释放对Y的锁站点A站点B事务T1持有事务T2持有事务T2请求事务T1请求742）全局等待图（GWFG）站点A:拥有x、y的副本；T1:read(x),write(y)站点B:拥有y、z的副本；T2:read(y),write(z)站点C:拥有z的副本；T3:read(z),write(x)T1T2T3Xyz2）全局等待图（GWFG）站点A:拥有x、y的副本；T1:753）死锁的检测A集中式死锁检测法●指定某站点上的锁管理器作为全局死锁检测器●其余站点周期地向全局死锁检测器发送LWFG●全局死锁检测器产生GWFG，并检测有无回路B分布式死锁检测法●每个站点都有死锁检测器，负责检测本地可能的死锁。●每个站点按照一定规则，向相关站点发送潜在的死锁回路图。4）死锁的解决原则：撤消并恢复代价最小的事务。●撤消并恢复年轻的事务。●撤消并恢复占用资源较少的事务。●撤消并恢复具有最短运行时间的事务。3）死锁的检测A集中式死锁检测法●指定某站点上的锁管理器76四并发控制的时标技术1.时标:唯一识别一个事务，并用于对事务进行排序的标识符。2.时标的构成：“本地计数器值，站点标识符’3.时标的创建：一个事务Ti初始化时，事务管理器给该事务分配一个时标ts(Ti)4.时标排序（TO）规则：已知Qi和Qj是分别属于事务Ti和Tj冲突操作。若ts(Ti)<ts(Tj),则Qi在Qj之前执行。5、基本时标法四并发控制的时标技术1.时标:唯一识别一个事务，并用于对77规则：1）每个事务在本地站点开始时被赋以一个全局唯一的时标。3）事务的每个读或写操作都有该事务的时标。2）如果事务被重新启动，则被赋予新的时标。4）在事务结束之前，不对数据库进行物理操作。5）对于数据库每个数据对象x，记录对它进行读操作和写操作的最大时标RTM(x)和WTM(x)基本时标法的执行过程：1）设TS是对数据对象x进行读操作的当前时标。若TS<WTM(x)，则，拒绝该操作；并使发出该操作的事务用新时标重新启动；否则，执行读操作，且使：RTM(x)=max（RTM(x),TS）规则：基本时标法的执行过程：782）设TS是对数据对象x进行写操作的当前时标。若TS<RTM(x)ORTS<WTM(x)，则，拒绝该操作；并使发出该操作的事务用新时标重新启动；否则，执行写操作，且使：WTM(x)=max（WTM(x),TS）6、保守时标法特点：采用缓冲区缓冲“年轻”操作，以便尽量消除“拒绝操作”，避免了事务重新启动。规则：（1）每个事务只在一个站点执行。不激活远程程序，只能向远程站点发出读/写操作请求。（2）每个站点必须按照时标时间的顺序发送读/写数据的请求。对于每个事务的更新操作，必须做到对同一数据对象先读后写。2）设TS是对数据对象x进行写操作的当前时标。6、保守时标法79（3）每个站点都开辟一个缓冲区，用于保存其它站点发来的读/写操作。保守时标法的执行过程一旦某个站点上的各个缓冲区队列都不空，即，每个站点至少向该站点发送了一个读和一个写，就停止接收，转入处理缓冲区队列上的操作。例站点i上缓冲区队列情况如下：站点1站点2…站点nR11R12R13W11R21R22R23R24W21W22…Rn1Rn2Wn2读队列写队列（3）每个站点都开辟一个缓冲区，用于保存其它站点发来的读/80站点i上处理缓冲区队列上的操作算法：重复执行如下步骤，直到没有满足执行条件的Rij和Wij，或者至少出现一个读/写队列为空，此时RT/WT=0：1）令：RT=min(Rij),WT=min(Wij)i：站点序号；j：读/写操作的序号2）按下列原则处理缓冲区内各个站点读/写队列：*扫描读队列若各队列存在若干个Rij<WT,则，按时标顺序逐一执行Rij，并使Rij出队列*扫描写队列若各队列存在若干个Wij<RT,则，按时标顺序逐一执行Wij，并使Wij出队列站点i上处理缓冲区队列上的操作算法：重复执行如下步骤，直到81五并发控制的乐观方法验证读/计算写/提交悲观法事务的执行过程读/计算验证写/提交乐观法事务的执行过程乐观方法的特点：1）任何事务在写一个数据项之前，必须首先读该数据项。2）事务在读/计算阶段，在读取一个数据项之后，接着只是做了对该数据项进行写操作所需新值的“准备”，实际上并没有执行物理写盘操作！五并发控制的乐观方法验证读/计算写/提交悲观法事务的执行过82读/计算阶段在本站点上：从数据库读入数据；进行计算；准备写数据库的数据新值；形成事务更新表。更新表的内容：1）所有读数据对象及其时标2）所有写数据对象的新值。3）事务本身的时标。2.验证阶段：检测事务对数据库的更新是否会导致破坏数据库的一致性。步骤：1）源站点向相关站点发送更新表。2）各站点进行表决，并把表决结果回送源站点。3）源站点作出最终裁决，并把结果通知各站点。3.写阶段：如果验证获得通过，则提交该事务，否则重新启动事务。读/计算阶段2.验证阶段：检测事务对数据库的更新是否会导83各站点表决原则：如果更新表中每一个读数据对象的时标，与本站点上同一数据对象的时标都相等，则，该站点投肯定票。//说明两者之间没有发生过其他更新操作！否则，该站点投否定票。各站点表决原则：如果更新表中每一个读数据对象的时标，与本站点84本节重点1.总结分布式数据库加锁法的特点。2.总结基本时标法和保守时标法控制并发事务的过程。3.分析、比较并发控制的时标技术与乐观方法的特点。本节重点1.总结分布式数据库加锁法的特点。2.总结基本时85第六部分分布式数据库及相关技术的讨论（第8-11章内容）一分布式数据库概述产生和发展概念和分类体系结构模式结构及独立性。。。二分布式数据库系统中存在的技术问题分布式DB的设计分布式DB的查询分布式DB的事务管理及并发。。。第六部分分布式数据库及相关技术一分布式数据库概述86一分布式数据库概述I分布式数据库的产生及发展a经济的发展b计算机硬件环境及网络的发展发展历程：产生于20世纪70年代末期，成长于80年代第一个分布式数据库系统SDD-1是美国计算机公司（CAA）于1976年-1978年设计，79年在DEC-10/20上实现。德国斯图加特大学研制的porel系统美国IBM的R*和systemR美国加大学伯克利分校的Ingres法国INRA研制的SIRIUS-DELTA。。。一分布式数据库概述I分布式数据库的产生及发展a经济的发871987年：C.JDate提出了完全的，真正的分布式DBS应遵循的12条规则：本地自治性不依赖于中心站点可连续操作位置独立性数据分片独立性数据复制独立性分布式查询独立性分布式事务管理硬件独立性操作系统独立性网络独立性DBMS独立性1987年：C.JDate提出了完全的，真正的分布式DBS88II分布式数据库系统的定义及分类1分布式数据库的定义：

分布式数据库是一个数据集合，这些数据分布在由计算机网络连接起来的若干节点上，每个节点可以管理本地的数据应用，也可以参与全局数据应用。同时这些数据在逻辑上形成一个整体，由统一的数据库管理系统进行管理。（DDBMS）注：几个基本的概念站点：计算机连接的一个逻辑单位，称为一个站点。本地（或称：局部）用户、本地应用：一个用户或应用只访问他所注册的那个站点。全局用户、全局应用：一个用户访问涉及两个或两个以上的站点中的数据。全局数据库（GDB）、局部数据库（LDB）：。。。II分布式数据库系统的定义及分类1分布式数据库的定义：注892.分布式数据库系统的基本特点：A结构特点：物理分布，逻辑相关。B应用特点：站点自治。2.分布式数据库系统的基本特点：A结构特点：物理分布，逻90多处理机系统C.数据分布透明性：数据的物理独立性内容更丰富，增加了数据分布透明性。---数据的逻辑分片、数据的物理位置分布、数据的复制，对用户透明。D.集中与自治兼备的数据库系统控制机制.---两个层次的数据共享：局部/全局数据共享。多处C.数据分布透明性：数据的物理独立性内容更丰富，增加了数91E.增加数据冗余度。---利用数据冗余提高系统可靠性、可用性和系统性能。F.事务管理的分布性。---分布环境下，维护事务的原子性、一致性、隔离性和持久性。E.增加数据冗余度。F.事务管理的分布性。923.分布式数据库系统的模式结构3.分布式数据库系统的模式结构934.分布式数据库系统的分类A按局部DBMS的数据模型分类：---同构型：数据模型相同*同质同构：数据模型相同且局部DBMS相同。*异质同构：数据模型相同外交部局部DBMS不同。

SDD-1和DDM美国CCA公司SYSTEMR*美国IBM公司POREL德国斯图加特大学

---异构型：数据模型不同MULTIBASE美国CCA1981研制IMADAS:H佛罗里达大学1984研制DDTSHONEYWELL公司1980年研制。。。4.分布式数据库系统的分类A按局部DBMS的数据模型分类：94B按全局控制系统类型分类：---全局控制集中型DDBSDDBS的全局控制机制及数据字典位于一个中心站点，由中心站点完成全局事务的协调和局部数据库的转换等所有控制功能。---全局控制分散型DDBS

DDBS的全局控制机制及数据字典分散在网络的各个站点上，每个站点都能完成全局事务的协调和局部数据转换。---全局控制可变型（主从型）将站点分成两组，一组都包含全局控制机制和数据字典，另一组为辅助站点，只包含自己的数据应用。B按全局控制系统类型分类：954.分布式数据库管理系统的功能结构：除了具有集中式DBMS具有的功能外，还要有如下附加的功能：*数据跟踪*分布式查询处理能力*分布式事务管理的能力*复制数据的能力*安全性*分布式目录管理4.分布式数据库管理系统的功能结构：除了具有集中式DBMS具96二.分布式数据库系统中存在的技术问题：1分布式数据库系统的设计--全局模式的设计--数据分片，分布2分布式数据库的查询处理3分布式数据库的事务管理及并发控制4分布式数据库的可靠性5异构数据库的连接6安全性7目录管理二.分布式数据库系统中存在的技术问题：1分布式数据库系统97§1.分布式数据库设计一方法：根据设计是基于现存的数据系统还是构造一个全新的数据库系统，有两种方法创建分布式数据库：

组合法：基于现有的系统，建立一个协调管理系统。--采用自底向上的方式构建

重构法：创建全新的数据库系统--自顶向下的方式构建二分布式数据库设计的内容：

1.数据库设计基础---需求分析1）数据需求2）应用需求●应用的原发站点：发出应用请求的站点●应用在站点被激活的频率●应用对数据对象访问次数、类型和分布统计§1.分布式数据库设计一方法：二分布式数据库设计的内容：982.数据库设计（设计的核心任务）全局模式设计局部数据库设计数据分片设计片段的位置分配设计三分布式数据库设计的目标：确保数据库数据和应用具有最大程度的本地性。分布式数据的可用性和可靠性工作负荷分布存储的能力和费用2.数据库设计（设计的核心任务）三分布式数据库设计的目标99四自顶向下的方式构建分布式数据库需求分析全局概念模型全局逻辑模型分片设计系统实现试运行及维护分布设计局部逻辑设计物理设计1设计的步骤：四自顶向下的方式构建分布式数据库需全全分系试分局物1设计1002数据库的分片设计（1）.什么叫“片段”？指在分布式数据库系统中，某一站点上存储的数据集合。（2）.分片设计的目的？产生全局数据的一个合理的划分，从而使每个站点只获得它所需要的数据，最大可能保证应用的本地性。（3）分片应遵循的一般规则：设：R={R1,R2,…,Rn}1）完整性即，t∈R,则，必有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,且i≠j）或Ri∩Rj=主码属性(i,j=1,…,n,且i≠j）2数据库的分片设计（1）.什么叫“片段”？（2）.分片设101（4）分片的基本类型和方法水平分片，垂直分片，混合分片A水平分片：对全关系进行选择操作，把具有相同性质的元组进行分组，构成若干不相交的子集。初级分片和导出分片初级分片：以关系自身属性性质分组例1S(S#,Sname,Age,Sex)definefragmentS1asselect*fromSwhereSex=‘M’；definefragmentS2asselect*fromSwhereSex=‘F’；（4）分片的基本类型和方法A水平分片：对全关系进行选择操作102导出分片：用其它关系的属性对某一全关系进行分组例2设：全局关系SC(S#,C#,Grade)S(S#,Sname,Age,Sex)设计需求：按S的“性别”属性（Sex）去划分SCDefinefragmentSC1asselectSC.S#,C#,GradefromSC,SwhereSC.S#=S.S#andS.Sex=‘M’DefinefragmentSC2asselectSC.S#,C#,GradefromSC,SwhereSC.S#=S.S#andS.Sex=‘F’导出分片：用其它关系的属性对某一全关系进行分组例2设：全103B垂直分片：利用投影操作把全关系的属性分成若干组，目标是把频繁使用的属性聚集在一起，且各片段只在键属性下重叠。例3设：全局关系EMP(E#,Name,Dept,Job,Sal,tel)Key={E#}垂直分片：EMP1(E#,Name,Sal,tel)EMP2(E#,Dept,Job)B垂直分片：利用投影操作把全关系的属性分成若干组，目标是1043数据库片段位置分配的设计两种方式：非冗余分配：一个片段映射到一个站点冗余分配：一个片段映射到多个站点非冗余“最佳适应”分配法：计算：Bij=Σk(Fkj*Nki)即，计算所有的应用在站点j上访问片段i的总次数。对所有站点j确定j′,使得Bij′=max(Bij)即，把片段Ri分配到有最大访问次数的站点j′。i--片段序号j---站点序号k---应用序号Fkj----应用k在站点j上激活的频率Rki----应用k对片段i进行检索访问的次数(Read)Uki----应用k对片段i进行更新访问的次数Nki=Rki+Uki----应用k对片段i进行访问的总次数3数据库片段位置分配的设计两种方式：非冗余“最佳适应”分配105冗余分配比较复杂，一般采用下列方法之一进行估算：--所有得益站点法：--附加复制法（1）“所有得益站点”法对所有站点确定非冗余分配方案。从全部结点中选择一组站点，使得给这组站点分配片段Ri的一个拷贝所得到的检索效益，大于从其它站点对Ri实施更新的代价。把片段Ri拷贝分配给该组站点冗余分配比较复杂，一般采用下列方法之一进行估算：（1）“所有106（2）附加拷贝法对所有站点确定非冗余分配方案。计算把片段Ri分配给所有站点所能得到的总效益fi（以及一个站点分得Ri所得到的效益）从分得片段Ri能够获取最大益处的站点起，对各站点依次附加片段Ri的一个拷贝，直到增加片段Ri不能使系统得到明显效益（或者说效益增大“接近”fi）为止。总结：数据库片段及位置分配的设计所需要的参数均从应用需求中得来，总结这些参数可用如下三个表表达：A频率表：各站点每一应用激活的次数B划分表：各实体的潜在水平分片规则C极化表：给定站点发出一给定应用访问一给定片段的概率（2）附加拷贝法对所有站点确定非冗余分配方案。总结：数据库片107需求分析全局概念模型全局逻辑模型分片设计系统实现试运行及维护分布设计局部逻辑设计物理设计频率表划分表极化表需全全分系试分局物频率表划分表极化表108分布式数据库设计的一个例子订票系统维护分布在三个网络站点（与机场1，2，3处于同一地理区域）上的数据库。数据库存储机场规程、班机起降和旅客订票等数据。（1）概念设计---全局概念模式（E-R图）分布式数据库设计的一个例子订票系统维护分布在三个网络站点（与109（2）收集数据与其最相关的应用知识---用操作模式表示a订票:用于旅客预订机票。（2）收集数据与其最相关的应用知识---用操作模式表示a订110b登记:用于旅客登机登记任务记录。b登记:用于旅客登机登记任务记录。111c起飞应用:查询即将从一个机场起飞的30个班机信息。c起飞应用:查询即将从一个机场起飞的30个班机信息。112（3）在操作模式的基础上，对每一实体估算应用的定量数据，建立逻辑访问表例“班机”实体逻辑访问表（3）在操作模式的基础上，对每一实体估算应用的定量数据，例“113（4）分布需求分析a.频率表：调研并给出在三个站点上使用各个应用的频率（激活的次数）（4）分布需求分析a.频率表：调研并给出在三个站点上使用各114b.划分表：分析各个实体各种可能的分片方式及其选择性*基本划分b.划分表：分析各个实体各种可能的分片方式及其选择性*基本划115*导出划分注释表：*导出划分注释表：116c.极化表：调研并给出从一个站点发出一个应用所需要访问某片段的概率。c.极化表：调研并给出从一个站点发出一个应用所需要访问某片段117（5）飞机订票系统的分布式设计a.为各个实体选择合适的分片,原则:满足本地性，不造成应用困难。对本例来予，各个实体采用水平分片：●“机场”由基于区域的基本水平分片（片段(F1～F3)：机场1，机场2，机场3）●“班机”由基于起飞机场区域的导出水平分片（片段(A1～A3)：班机1，班机2，班机3）●“旅客”由基于旅客订票涉及的班机起飞机场所在区域的导出水平分片（片段(P1～P7)：旅客1，旅客2，旅客3，……，旅客7）（5）飞机订票系统的分布式设计a.为各个实体选择合适的分片,118b.进行片段的非冗余分配：1）站点1：机场1，班机1，旅客12）站点2：机场2，班机2，旅客2旅客4，旅客6，旅客73）站点3：机场3，班机3，旅客3旅客5根据频率表和极化表c.进行片段的冗余分配：根据应用可以将旅客4.5.6分配在两个站点上，旅客7分配在三个站点上。b.进行片段的非冗余分配：1）站点1：机场1，班机1，旅客1119（6）重构局部模式（6）重构局部模式120第六讲-分布式数据库及相关问题课件121第六讲-分布式数据库及相关问题课件122本节要点1.理解分布式数据库系统的基本概念及特征，总结分布式数据库分片设计方法。熟练掌握使用SQL语句，定义全局关系模式的分片方法。2.总结“自顶向下”设计分布式数据库的方法。掌握从设计全局设计模式到各站点上局部模式的分布设计方法。3.理解分布式数据库片段分配设计方法的思想。本节要点1.理解分布式数据库系统的基本概念及特征，总结分布123§2.分布式数据库查询处理一、分布式查询处理的步骤查询分析若该查询属于局部查询，则执行局部查询处理后，即可结束。查询分解把全局查询或远程查询转换成定义在全局关系上的关系代数表达式，并优化该表达式。查询本地化把一个全局关系上的查询，转化为对片段的局部查询。全局查询优化：找出对各个片段局部查询结果之间的最佳操作次序，使得代价最小。其重点在连接运算和并运算的优化局部优化：由确定的片段所在站点执行§2.分布式数据库查询处理一、分布式查询处理的步骤查询分析若124二、分布式查询处理的代价QC估算：QC=I/O+通信代价T*通信代价T估算T=Σ传输次数（每次传输延迟时间+每次传输数据量/数据传输速率）=Σ传输次数（C0+X/D）二、分布式查询处理的代价QC估算：*通信代价T估算T=Σ125三、分布式查询策略的重要性：例设：教学数据库中：S(S#,Sname,Age,Sex)10,000个元组，存放在A站点（男/女各一半）SC(S#,C#,Grade)1,000,000个元组，存放在A站点（每人选课100门）C(C#,Cname,Teacher)100,000个元组，存放在B站点假设：每个元组的长度为100bit;通信系统传输速率为10,000bit/秒；每次通信延迟时间为1秒。查询：选修课名‘Maths’的男生的学号和姓名对于本例，C0=1秒，D=10,000bit/秒三、分布式查询策略的重要性：例设：教学数据库中：S(S#,126解：SQL语句是：SELECTS.S#,SnameFROMS,SC,CWHERES.S#=SC.S#ANDSC.C#=C.C#ANDSEX=‘M’ANDCname=‘Maths’策略1：把关系C传到A站点；在A站点进行处理。T1=1+(100,000*100)/10,000≈16.7(分)解：SQL语句是：策略1：把关系C传到A站点；在A站点进行处127策略2：先在A站点找出男生选课情况（每人平均选100门课），再根据C#向B站点核查这些男生的选课是否是‘Maths’。(结果在A站点)T3=2*500,000*1秒≈11.6(天)策略3：先在B站点找出‘Maths’元组（假设最多有10门），再把查找结果传到A站点，在A站点继续执行查询处理。T6=1+10*100/10,000≈1秒策略2：先在A站点找出男生选课情况（每人平均选100门课），128四、基于关系代数等价变换的查询优化例1S(S#,Sname,Age,Sex)SC(S#,C#,Grade)

其中，S和SC都采取水平分片：用户查询：SELECTdistinctSnameFROMS,SCWHERES.S#=SC.S#andSex=‘M’andGrade>90转成关系代数表达式：πSname(σSex=‘M’∧Grade>90(σS.S#=SC.S#(S×SC)))四、基于关系代数等价变换的查询优化例1S(S#,Snam129把关系代数表达式转换成查询树并优化从全局查询到片段查询的转换把关系代数表达式转换成查询树并优化从全局查询到片段查询的转换130优化片段查询树a.对于水平分片，检查选择运算（σ）与水平分片的条件（谓词）。b.对于垂直分片，注意消去不提供连接运算后所需要属性的分支。优化片段查询树a.对于水平分片，检查选择运算（σ）与水平分131例2设：全局关系:EMP(E#,Ename,Sal,Dept,Dname)现采取垂直分片：查询问题：SELECTEname,SalFROMEMP查询关系代数表达式πEname,Sal(EMP)例2设：全局关系:EMP(E#,Ename,Sal,132第六讲-分布式数据库及相关问题课件133五基于半连接算法的全局查询优化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五基于半连接算法的全局查询优化1、半连接运算:由投影和连接1343.采用半连接运算实现连接运算的代价及优化令：tuple(R)表示关系R的元组数size(B)表示属性B的数据长度现假设，用户希望在站点2上得到R与S自然连接的结果RS网络站点1站点2RS网络站点1站点2(1)πB(S)(2)传送πB(S)(3)R′=RπB(S)B(4)传送R′(5)R′SB3.采用半连接运算实现连接运算的代价及优化令：tuple(R135总代价：T半=2C0+C1*[size(B)*tuple(πB(S))+size(R′)*tuple(R′)]采用半连接操作优化的原理：两个关系进行连接操作之前，去掉无用的无组，减少数据传输量。采用直接连接运算的总代价：T=C0+C1*size(R)*tuple(R)选择半连接实现连接运算的原则：经半连接操作产生少量元组。4.查询优化策略1）计算各种半连接运算的代价。2）计算直接连接运算的代价。3）比较并选出最优者。总代价：T半=2C0+C1*[size(B)*t136六基于直接连接算法的查询优化1、利用站点依赖信息的连接算法∪R1R2=F11F21(F12F22)其成立的条件是什么?六基于直接连接算法的查询优化1、利用站点依赖信息的连接算法137条件：πA(F11)∩πA(F12)=φπA(F21)∩πA(F22)=φπA(F11)∩πA(F22)=φπA(F12)∩πA(F21)=φ站点依赖：设：Ri[A]、Rj[A]、Si[A]、Sj[A]分别表示关系R、S在站点i、j的A属性上的取值。若对于i≠j,有：Ri[A]∩Sj[A]=φ,则称关系R和S在属性A上站点依赖。性质：若关系R和S在属性A上站点依赖，则：∪iRS=(RiSi)条件：πA(F11)∩πA(F12)=φπA(F2138推论：*如果R和S在属性A上站点依赖，B⊇A,则，R和S在属性B上站点依赖。*如果R和S在属性A上站点依赖，S和T在属性B上站点依赖，则：RS=(RiSiT∪