数据库系统概论-chp14-分布式数据库优秀PPT.ppt

数据库系统概论数据库系统概论An Introduction to Database System第十四章第十四章 分布式数据库分布式数据库An Introduction to Database System第十四章第十四章 分布式数据库分布式数据库14.1 概述概述14.2 分布式数据库系统的体系结构分布式数据库系统的体系结构14.3 查询处理和优化查询处理和优化14.4 分布事务管理分布事务管理14.5 小结小结An Introduction to Database System14.1 概述概述14.1.1 分布式数据库系统分布式数据库系统14.1.2 分布式数据库系统的特点分布式数据库系统的特点An Introduction to Database System14.1.1 分布式数据库系统分布式数据库系统v什么是分布式数据库？n分布式数据库由一组数据组成，这些数据物理上分布在计算机网络的不同结点(亦称场地)上，逻辑上是属于同一个系统。分布性逻辑整体性An Introduction to Database System分布式数据库系统分布式数据库系统(续续)图14.1 一个分布式数据库系统 v例1如图14.1所示An Introduction to Database System分布式数据库系统分布式数据库系统(续续)n区分一个系统是若干集中式数据库的简洁连网还是分布式数据库系统的技术要点在于：n 系统是否支持全局应用 n一个典型的例子是银行转账n从一个分行的账户(设在DB1数据库)中转移若干金额到另一个分行的账户(设在DB3数据库)中去n要同时更新两个结点上的数据库An Introduction to Database System分布式数据库系统分布式数据库系统(续续)图14.2 一个多处理机系统(SN并行结构)v例2如图14.2所示An Introduction to Database System分布式数据库系统分布式数据库系统(续续)n多处理机系统(SN并行结构)n没有局部应用n分布式数据库不仅要求数据的物理分布，而且要求这种分布是面对处理、面对应用的An Introduction to Database System分布式数据库系统分布式数据库系统(续续)v分布式数据库：v分布式数据库是由一组数据组成的，这组数据分布在计算机网络的不同计算机上，网络中的每个结点具有独立处理的实力(称为场地自治)，可以执行局部应用。同时，每个结点也能通过网络通信子系统执行全局应用。v场地自治性v自治场地之间的协作性An Introduction to Database System14.1 概述概述14.1.1 分布式数据库系统分布式数据库系统14.1.2 分布式数据库系统的特点分布式数据库系统的特点An Introduction to Database System分布式数据库系统的特点分布式数据库系统的特点(续续)v一、数据独立性v逻辑独立性v物理独立性v数据分布独立性(分布透亮性)v用户的应用程序书写起来就犹如数据没有分布一样An Introduction to Database System分布式数据库系统的特点分布式数据库系统的特点(续续)v二、集中与自治相结合的限制结构v数据共享：v(1)局部共享v(2)全局共享v限制机制：v集中v自治An Introduction to Database System分布式数据库系统的特点分布式数据库系统的特点(续续)v三、适当增加数据冗余度v提高系统的牢靠性、可用性v提高系统性能v四、全局的一样性、可串行性和可复原性v局部数据库要保证ACIDv全局数据库也要保证ACIDAn Introduction to Database System第十四章第十四章 分布式数据库分布式数据库14.1 概述概述14.2 分布式数据库系统的体系结构分布式数据库系统的体系结构14.3 查询处理和优化查询处理和优化14.4 分布事务管理分布事务管理14.5 小结小结An Introduction to Database System14.2 分布式数据库系统的体系结构分布式数据库系统的体系结构14.2.1 分布式数据库系统的模式结构分布式数据库系统的模式结构14.2.2 数据分片数据分片14.2.3 分布透亮性分布透亮性14.2.4 分布式数据库管理系统分布式数据库管理系统An Introduction to Database System14.2.1 分布式数据库系统的模式结构分布式数据库系统的模式结构图14.3 分布式数据库系统的模式结构An Introduction to Database System分布式数据库系统的模式结构分布式数据库系统的模式结构(续续)v分布式数据库系统增加的模式级别n(1)全局外模式(Global External Schema)n(2)全局概念模式(Global Conceptual Schema)n(3)分片模式(Fragmentation Schema)片段(Fragment)定义片段以及全局关系到片段的映象n(4)分布模式(Allocation Schema)定义片段的存放地点An Introduction to Database System14.2 分布式数据库系统的体系结构分布式数据库系统的体系结构14.2.1 分布式数据库系统的模式结构分布式数据库系统的模式结构14.2.2 数据分片数据分片14.2.3 分布透亮性分布透亮性14.2.4 分布式数据库管理系统分布式数据库管理系统An Introduction to Database System14.2.2 数据分片数据分片v数据分片v有利于依据用户的需求较好地组织数据的分布v有利于限制数据的冗余度v数据分片的方式v水平分片v垂直分片v混合分片v导出分片An Introduction to Database System数据分片数据分片(续续)v水平分片v按确定的条件将关系按行(水平方向)分为若干不相交的子集，每个子集为关系的一个片段。v垂直分片v指将关系按列(垂直方向)分为若干子集。v每个片段通常都包含关系的码 An Introduction to Database System数据分片数据分片(续续)v导出分片n是指导出水平分片，即水平分片的条件不是本身属性的条件而是其他关系的属性的条件。An Introduction to Database System数据分片数据分片(续续)例学生选课关系SC(Sno，Cno，Grade)，依据学生年龄18岁和18岁分片(学生年龄是学生关系Student的属性)年龄18岁的学生选课片段由下面的查询结果组成：SELECT Sno，Cno，Grade FROM S，SC WHERE S.SnoSC.Sno AND S.Sage18；年龄18岁的片段SC_B由下面的查询结果组成：SELECT Sno，Cno，Grade FROM S，SC WHERE S.SnoSC.Sno AND S.Sage18；An Introduction to Database System数据分片数据分片(续续)v混合分片v是指按上述三种分片方式得到的片段接着按另一种方式分片。v例如，先按垂直分片再按水平分片方式接着分片。v例如，先按水平分片得到的某一片段再进行垂直分片。An Introduction to Database System数据分片数据分片(续续)v分片应满足的条件v完全性v不相交性v可重构性v垂直分片：连接v水平分片：并操作An Introduction to Database System14.2 分布式数据库系统的体系结构分布式数据库系统的体系结构14.2.1 分布式数据库系统的模式结构分布式数据库系统的模式结构14.2.2 数据分片数据分片14.2.3 分布透亮性分布透亮性14.2.4 分布式数据库管理系统分布式数据库管理系统An Introduction to Database System14.2.3 分布透亮性分布透亮性v分片透亮性 最高层次v用户或应用程序只对全局关系进行操作而不必考虑关系的分片v位置透亮 下一层次v用户或应用程序不必了解片段的存储场地，当存储场地变更了，由于分片模式到分布模式的映像(映像3)，应用程序不必变更v局部数据模型透亮性 较低层次v是指用户或用户程序不必了解局部场地上运用的是哪种数据模型，模型的转换以及数据库语言的转换均由映像4完成An Introduction to Database System分布透亮性分布透亮性(续续)例1设在分布式数据库系统中有全局关系 Student(Sno，Sname，Sdept，Sage)Student关系被划分为两个片段S_A和S_B。S_A代表理学院的学生，S_B代表文学院的学生。S_A存储在场地1(Site1)，S_B冗余地存储在场地2和场地3上。An Introduction to Database System分布透亮性分布透亮性(续续)v要求n从终端读入一个学号，查找该学号的学生姓名、年龄，并把它们显示在屏幕上。n设应用程序是用嵌入SQL语句的C语言写的。现给出查询部分的算法思想。An Introduction to Database System分布透亮性分布透亮性(续续)v状况1系统具有分片透亮性v Scanf(“%s”,Snumber)；v EXEC SQL SELECT Sname,Sage INTO:NAME,:AGEv FROM Studentv WHERE Sno：Snumber；v Printf(%s，%d，NAME，AGE)；程序变量程序变量An Introduction to Database System分布透亮性分布透亮性(续续)v状况2系统具有位置透亮性，但不具有分片透亮性v Scanf(%s“,Snumber);v EXEC SQL SELECT Sname,Sage INTO:NAME,:AGEv FROM S_Av WHERE Sno:Snumber;v If(!FOUND)v EXEC SQL SELECT Sname,Sage INTO:NAME,:AGEv FROM S_Bv WHERE Sno:Snumber;v v Printf(%s,%d“,NAME,AGE)；An Introduction to Database System分布透亮性分布透亮性(续续)v状况3系统只具有局部数据模型透亮性，不具有位置透亮性v v Scanf(%s“,Snumber);v EXEC SQL SELECT Sname,Sage INTO:NAME,:AGEv FROM S_A AT Site1v WHERE Sno:Snumber;v If(!FOUND)v EXEC SQL SELECT Sname,Sage INTO:NAME,:AGEv FROM S_B AT Site2v WHERE Sno:Snumber;v v Printf(“%s,%d”,NAME,AGE);An Introduction to Database System14.2 分布式数据库系统的体系结构分布式数据库系统的体系结构14.2.1 分布式数据库系统的模式结构分布式数据库系统的模式结构14.2.2 数据分片数据分片14.2.3 分布透亮性分布透亮性14.2.4 分布式数据库管理系统分布式数据库管理系统An Introduction to Database System14.2.4 分布式数据库管理系统分布式数据库管理系统v分布式数据库管理系统(Distributed Data Management System，D-DBMS)n建立、管理和维护分布式数据库的一组软件 An Introduction to Database System分布式数据库管理系统分布式数据库管理系统(续续)vD-DBMS的结构 分布式数据库管理系统的结构 An Introduction to Database System分布式数据库管理系统分布式数据库管理系统(续续)vD-DBMS由四部分组成：n(1)局部数据库管理系统LDBMS(Local DBMS)n(2)全局数据库管理系统GDBMS(Global DBMS)n(3)全局数据字典(Global Data Directory，GDD)n(4)通信管理(Communication Management，CM)An Introduction to Database System分布式数据库管理系统分布式数据库管理系统(续续)v一、按全局限制方式分类v1.全局限制集中的D-DBMS v全局限制成分GDBMS集中在某一结点上，全局数据字典只有一个，也存放在该结点上。v2.全局限制分散的D-DBMS v全局限制成分GDBMS分散在网络的每一个结点上，全局数据字典也在每个结点上存放一份。v3.全局限制部分分散的D-DBMSv依据应用的须要将GDBMS和全局数据字典分散在某些结点上。An Introduction to Database System分布式数据库管理系统分布式数据库管理系统(续续)v二、按局部DBMS的类型分类 n同构型D-DBMS每个结点的局部数据库具有相同的DBMS即使操作系统和计算机硬件并不相同n异构型D-DBMS各结点的局部数据库具有不同的DBMSAn Introduction to Database System第十四章第十四章 分布式数据库分布式数据库14.1 概述概述14.2 分布式数据库系统的体系结构分布式数据库系统的体系结构14.3 查询处理和优化查询处理和优化14.4 分布事务管理分布事务管理14.5 小结小结An Introduction to Database System14.3 查询处理和优化查询处理和优化14.3.1 一个实例一个实例14.3.2 查询处理和优化要解决的问题查询处理和优化要解决的问题14.3.3 查询优化的目标查询优化的目标14.3.4 连接查询的优化连接查询的优化An Introduction to Database System14.3.1 一个实例一个实例v数据库：简化了的供应商和零件数据库 S(Sno，City)104个元组，存放在场地A；P(Pno，Color)105个元组，存放在场地B；SP(Sno，Pno)166个元组，存放在场地A；设每个关系的元组均为100字节长。v查询：求供应红色零件的、北京的供应商号 SELECT S.Sno FROM S，P，SP WHERE S.City=北京 AND SP.Pno=P.Pno AND P.Color=红色An Introduction to Database System一个实例一个实例(续续)v估算值(某些中间结果的元组数)红色零件数=10 北京供应商的装运单数=105v对通信系统的假定 数据传输速度=104字节/秒 传输延迟=1秒An Introduction to Database System一个实例一个实例(续续)v6种可能的查询存取策略，对每种i 分别计算通信时间Ti：Ti总传输延迟+总数据量/数据传输速度(单位：b/s)v策略1 把关系P传送到场地A，在A地进行查询处理。T1=1+105100/104=103秒(16.7分)An Introduction to Database System一个实例一个实例(续续)v策略2 把关系S、SP传到场地B，在B地执行查询处理 T2=2+(104+106)100/10410100秒(2.8小时)An Introduction to Database System一个实例一个实例(续续)v策略3 在场地A连接关系S和SP，选出城市为北京的元组(105个)，然后对这些元组中的每个元组的Pno，询问场地B，看此零件是否红色。共问答105次，由于不是传送数据，只是消息的问答，所以 T3=2105 s(2.3天)An Introduction to Database System一个实例一个实例(续续)v策略4 在场地B选出红色零件的元组(10个)，然后对每一个元组逐一检查场地A，看北京供应商的装运单中是否有这个零件装运单(若有则选出S#)。每做这样一次检查包括2次消息，共问一答10次，所以 T4=210=20秒An Introduction to Database System一个实例一个实例(续续)v策略5 在场地A选出北京的供应商的装运单把结果送到场地B，在场地B完成最终处理，所以v T5=1+(105100)/1041000秒(16.7分)An Introduction to Database System一个实例一个实例(续续)v策略6 在场地B的关系 P 中选出红色的元组(10个)，把结果送到场地A完成最终处理。所以 T6=1+(10100)/1041秒An Introduction to Database System一个实例一个实例(续续)表14.1 分布环境下查询策略实例比较策 略通信时间方 法116.7分把P传到场地A22.8小时把S，SP传到场地B32.3天对每一北京的装运单，检查相应零件是否红色420秒对每一红色零件，检查北京供应商中是否有人供应516.7分把北京供应商的装运单传送到场地B61秒把红色零件传送到场地AAn Introduction to Database System一个实例一个实例(续续)v(1)不同的存取策略通信时间相差很大，达多个数量级！-优化。v(2)不同策略，不同的考虑方式 n有些策略中数据传输速度和传输延迟都要考虑n有些策略中(如策略3、策略4)主要考虑传输延迟n有些策略中(如策略1、策略2、策略5)数据传输量大，主要考虑传输时间An Introduction to Database System14.3 查询处理和优化查询处理和优化14.3.1 一个实例一个实例14.3.2 查询处理和优化要解决的问题查询处理和优化要解决的问题14.3.3 查询优化的目标查询优化的目标14.3.4 连接查询的优化连接查询的优化An Introduction to Database System14.3.2 查询处理和优化要解决的问题查询处理和优化要解决的问题v分布式数据库系统中的三类查询：v局部查询v远程查询v全局查询v局部查询和远程查询优化v接受的技术是集中式数据库的查询优化技术(代数优化和非代数优化)An Introduction to Database System查询处理和优化要解决的问题查询处理和优化要解决的问题(续续)v全局查询处理和优化涉及的问题 n1.查询分解n2.选择操作执行的次序n3.选择执行操作的方法An Introduction to Database System14.3 查询处理和优化查询处理和优化14.3.1 一个实例一个实例14.3.2 查询处理和优化要解决的问题查询处理和优化要解决的问题14.3.3 查询优化的目标查询优化的目标14.3.4 连接查询的优化连接查询的优化An Introduction to Database System14.3.3 查询优化的目标查询优化的目标v集中式数据库的查询开销nI/O代价+CPU代价v分布式数据库的查询开销nI/O代价+CPU代价+通信代价n查询优化首要目标：通信代价最省An Introduction to Database System查询优化的目标查询优化的目标(续续)v通信代价可以用下面的公式粗略计算：v TC(X)C0+X*C1 vX：数据传输量，这里以b(位)为单位计算；vC0：两结点之间初始化一次传输所花费的开销，它由通信系统确定，近似为一个常数，单位为s(秒)；vC1：单位数据(b)传输的代价，单位为(s/b)。An Introduction to Database System14.3 查询处理和优化查询处理和优化14.3.1 一个实例一个实例14.3.2 查询处理和优化要解决的问题查询处理和优化要解决的问题14.3.3 查询优化的目标查询优化的目标14.3.4 连接查询的优化连接查询的优化An Introduction to Database System14.3.4 连接查询的优化连接查询的优化v两种优化方法v半连接：缩减关系（或片段）进而节约传输开销v干脆连接An Introduction to Database System14.3.4 连接查询的优化（续）连接查询的优化（续）v 半连接n R S R (B(S)v用半连接实现的连接运算nR S=(R S)SA=BA=BA=BA=BA=BAn Introduction to Database System14.3.4 连接查询的优化（续）连接查询的优化（续）n设关系R和S分别存放在结点r和s上结点结点rR结点结点sS B(S)R S RR n1.在结点s作关系S的投影n2.把投影 送到结点r，代价为 C0 C1 size(B)val(BS)n3.在结点r计算半连接，结果为R，R=R Sn4.把R从结点r送到结点s，代价为C0 C1 size(R)card(R)n5.在结点s执行连接操作B(S)B(S)A=BAn Introduction to Database System14.3.4 连接查询的优化（续）连接查询的优化（续）v半连接方案的总代价vCsj v2C0 C1(size(B)val(B(S)+size(R)card(R)v干脆连接代价vCjn=C0 C1 size(R)card(R)vCsj Cjn 时接受半连接。v An Introduction to Database System14.3.4 连接查询的优化（续）连接查询的优化（续）v干脆连接vR*系统(IBM SanJose探讨室研制)v嵌套循环v排序-合并v两种传输方式v整体传输v按需传输An Introduction to Database System第十四章第十四章 分布式数据库分布式数据库14.1 概述概述14.2 分布式数据库系统的体系结构分布式数据库系统的体系结构14.3 查询处理和优化查询处理和优化14.4 分布事务管理分布事务管理14.5 小结小结An Introduction to Database System14.4 分布事务管理分布事务管理14.4.1 分布事务的复原分布事务的复原14.4.2 并发限制并发限制 An Introduction to Database System14.4 分布事务管理分布事务管理v事务分布执行v分布事务的原子性v组成该事务的全部子事务要么一样地全部提交，要么一样地全部回滚v分布事务的可串行性An Introduction to Database System14.4.1 分布事务的复原分布事务的复原v故障和错误v各场地和集中式数据库相同v通信网络中信息丢失、长时间延迟、网络线路中断等v复原策略v局部事务管理器：保证子事务完整性v局部管理器之间相互协调An Introduction to Database System14.4.1 分布事务的复原（续）分布事务的复原（续）v两段提交协议(2-Phase-Commitment Protocol)v协调者：一个v做出提交还是撤销的最终确定v参与者：全部其他v管理相应子事务的执行An Introduction to Database System14.4.1 分布事务的复原（续）分布事务的复原（续）v第一阶段v协调者发出“准备提交”信息v参与者回答“就绪”或“撤销”信息v协调者作出提交或撤销的确定v其次阶段v协调者把确定信息写入日志，并发给全部参与者v参与者把收到的确定信息写入日志，并发送“应答”信息v协调者收到全部应答信息后，事务执行到此结束An Introduction to Database System14.4.1 分布事务的复原（续）分布事务的复原（续）v紧致一样性(Tight Consistency)v各结点完全同步v缺点v全局事务牢靠性低v系统效率低下v松散一样性(Loose Consistency)v数据各副本的修改是异步的v更加敏捷，提高系统的可用性An Introduction to Database System14.4.2 并发限制并发限制v集中式数据库封锁机制n锁的类型：共享锁(SLock)、排它锁(XLock)n封锁对象：表、记录n规则：遵守锁的相容性 遵守两段锁协议v分布式数据库n支持多副本n由于事务的分布执行，封锁会引起全局死锁An Introduction to Database System14.4.2 并发限制（续）并发限制（续）v多副本v几种解决方案v对写操作，要申请全部副本的X锁；对读操作，只要申请对某个副本的S锁。v无论读还是写都要对多数(大于半数)副本申请X或S锁v规定主副本，全部操作均申请对主副本的封锁T1在场地在场地1XLock(dsite1)T2在场地在场地2XLock(dsite2)An Introduction to Database System14.4.2 并发限制（续）并发限制（续）v死锁n全局死锁：包括两个以上场地上的死锁n检测方法：分布等待图n预防方法：对事务按某一标准排序，只允许事务沿这一次序单向等待An Introduction to Database System第十四章第十四章 分布式数据库分布式数据库14.1 概述概述14.2 分布式数据库系统的体系结构分布式数据库系统的体系结构14.3 查询处理和优化查询处理和优化14.4 分布事务管理分布事务管理14.5 小结小结An Introduction to Database System14.5 小结小结v分布式数据库系统n基本概念以集中式数据库系统技术为基础丰富了集中式数据库的概念和技术内容n主要问题查询优化事务管理An Introduction to Database System