数据库系统概论第4版第十四章.ppt

《数据库系统概论第4版第十四章.ppt》由会员分享，可在线阅读，更多相关《数据库系统概论第4版第十四章.ppt（73页珍藏版）》请在装配图网上搜索。

1、An Introduction to Database System 中国人民大学信息学院 数据库系统概论 An Introduction to Database System 第十四章 分布式数据库 An Introduction to Database System 第十四章 分布式数据库 14.1 概述 14.2 分布式数据库系统的体系结构 14.3 查询处理和优化 14.4 分布事务管理 14.5 小结 An Introduction to Database System 14.1 概述 14.1.1 分布式数据库系统 14.1.2 分布式数据库系统的特点 An Introductio

2、n to Database System 14.1.1 分布式数据库系统 什么是分布式数据库？ 分布式数据库由一组数据组成，这些数据物理上分布 在计算机网络的不同结点 (亦称场地 )上，逻辑上是属于 同一个系统。 分布性 逻辑整体性 An Introduction to Database System 分布式数据库系统 (续 ) 图 14.1 一个分布式数据库系统 例 1如图 14.1所示 An Introduction to Database System 分布式数据库系统 (续 ) 区分一个系统是若干集中式数据库的简单连网还是 分布式数据库系统的技术要点在于： 系统是否支持全局应用 一个典

3、型的例子是银行转账 从一个分行的账户 (设在 DB1数据库 )中转移若干金 额到另一个分行的账户 (设在 DB3数据库 )中去 要同时更新两个结点上的数据库 An Introduction to Database System 分布式数据库系统 (续 ) 图 14.2 一个多处理机系统 (SN并行结构 ) 例 2如图 14.2所示 An Introduction to Database System 分布式数据库系统 (续 ) 多处理机系统 (SN并行结构 ) 没有局部应用 分布式数据库不仅要求 数据的物理分布 ，而且要求这 种 分布是面向处理、面向应用的 An Introduction to

4、 Database System 分布式数据库系统 (续 ) 分布式数据库： 分布式数据库是由一组数据组成的，这组数据分布在计 算机网络的不同计算机上，网络中的每个结点具有独立 处理的能力 (称为场地自治 )，可以执行局部应用。同时， 每个结点也能通过网络通信子系统执行全局应用。 场地自治性 自治场地之间的协作性 An Introduction to Database System 14.1 概述 14.1.1 分布式数据库系统 14.1.2 分布式数据库系统的特点 An Introduction to Database System 分布式数据库系统的特点 (续 ) 一、数据独立性 逻辑独立

5、性 物理独立性 数据分布独立性 (分布透明性 ) 用户的应用程序书写起来就如同数据没有分布一样 An Introduction to Database System 分布式数据库系统的特点 (续 ) 二、集中与自治相结合的控制结构 数据共享： (1) 局部共享 (2)全局共享 控制机制： 集中 自治 An Introduction to Database System 分布式数据库系统的特点 (续 ) 三、适当增加数据冗余度 提高系统的可靠性、可用性 提高系统性能 四、全局的一致性、可串行性和可恢复性 局部数据库要保证 ACID 全局数据库也要保证 ACID An Introduction t

6、o Database System 第十四章 分布式数据库 14.1 概述 14.2 分布式数据库系统的体系结构 14.3 查询处理和优化 14.4 分布事务管理 14.5 小结 An Introduction to Database System 14.2 分布式数据库系统的体系结构 14.2.1 分布式数据库系统的模式结构 14.2.2 数据分片 14.2.3 分布透明性 14.2.4 分布式数据库管理系统 An Introduction to Database System 14.2.1 分布式数据库系统的模式结构 图 14.3 分布式数据库系统的模式结构 An Introduction

7、 to Database System 分布式数据库系统的模式结构 (续 ) 分布式数据库系统增加的模式级别 (1) 全局外模式 (Global External Schema) (2) 全局概念模式 (Global Conceptual Schema) (3) 分片模式 (Fragmentation Schema) 片段 (Fragment) 定义片段以及全局关系到片段的映象 (4) 分布模式 (Allocation Schema) 定义片段的存放地点 An Introduction to Database System 14.2 分布式数据库系统的体系结构 14.2.1 分布式数据库系统的

8、模式结构 14.2.2 数据分片 14.2.3 分布透明性 14.2.4 分布式数据库管理系统 An Introduction to Database System 14.2.2 数据分片 数据分片 有利于按照用户的需求较好地组织数据的分布 有利于控制数据的冗余度 数据分片的方式 水平分片 垂直分片 混合分片 导出分片 An Introduction to Database System 数据分片 (续 ) 水平分片 按一定的条件将关系按行 (水平方向 )分为若干不相交的 子集，每个子集为关系的一个片段。 垂直分片 指将关系按列 (垂直方向 )分为若干子集。 每个片段通常都包含关系的 码 An

9、 Introduction to Database System 数据分片 (续 ) 导出分片 是指导出水平分片，即水平分片的条件不是本身属性 的条件而是 其他关系的属性的条件 。 An Introduction to Database System 数据分片 (续 ) 例 学生选课关系 SC(Sno， Cno， Grade)，按照学生年龄 18岁和 18岁分片 (学生年龄是学生关系 Student的属性 ) 年龄 18岁的学生选课片段由下面的查询结果组成： SELECT Sno， Cno， Grade FROM S， SC WHERE S.Sno SC.Sno AND S.Sage 18；

10、年龄 18岁的片段 SC_B由下面的查询结果组成： SELECT Sno， Cno， Grade FROM S， SC WHERE S.Sno SC.Sno AND S.Sage18； An Introduction to Database System 数据分片 (续 ) 混合分片 是指按上述三种分片方式得到的片段继续按另一种 方式分片。 例如，先按垂直分片再按水 平分片方式继续分片。 例如，先按水平分片得到的 某一片段再进行垂直分片。 An Introduction to Database System 数据分片 (续 ) 分片应满足的条件 完全性 不相交性 可重构性 垂直分片：连接 水平

11、分片：并操作 An Introduction to Database System 14.2 分布式数据库系统的体系结构 14.2.1 分布式数据库系统的模式结构 14.2.2 数据分片 14.2.3 分布透明性 14.2.4 分布式数据库管理系统 An Introduction to Database System 14.2.3 分布透明性 分片透明性 最高层次 用户或应用程序只对全局关系进行操作而不必考虑关系的分片 位置透明 下一层次 用户或应用程序不必了解片段的存储场地，当存储场地改变了， 由于分片模式到分布模式的映像 (映像 3)，应用程序不必改变 局部数据模型透明性 较低层次 是指用

12、户或用户程序不必了解局部场地上使用的是哪种数据模型， 模型的转换以及数据库语言的转换均由映像 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 分布透明性 (续 ) 要求 从终端读入一个

13、学号，查找该学号的学生姓名、年龄， 并把它们显示在屏幕上。 设应用程序是用嵌入 SQL语句的 C语言写的。现给出查 询部分的算法思想。 An Introduction to Database System 分布透明性 (续 ) 情况 1 系统具有分片透明性 Scanf(“% s”,Snumber)； EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE FROM Student WHERE Sno ： Snumber； Printf(% s， % d， NAME， AGE)； 程序变量 An Introduction to Database System 分布透明

14、性 (续 ) 情况 2 系统具有位置透明性，但不具有分片透明性 Scanf(% s“,Snumber); EXEC SQL SELECT Sname,Sage INTO:NAME,:AGE FROM S_A WHERE Sno :Snumber; If(! FOUND) EXEC SQL SELECT Sname,Sage INTO :NAME,:AGE FROM S_B WHERE Sno :Snumber; Printf(% s,% d“,NAME,AGE)； An Introduction to Database System 分布透明性 (续 ) 情况 3 系统只具有局部数据模型透明性

15、，不具有位 置透明性 Scanf(% s“,Snumber); EXEC SQL SELECT Sname, Sage INTO : NAME,:AGE FROM S_A AT Site1 WHERE Sno :Snumber; If(! FOUND) EXEC SQL SELECT Sname, Sage INTO : NAME,:AGE FROM S_B AT Site2 WHERE Sno :Snumber; Printf(“% s,% d”, NAME,AGE); An Introduction to Database System 14.2 分布式数据库系统的体系结构 14.2.1

16、分布式数据库系统的模式结构 14.2.2 数据分片 14.2.3 分布透明性 14.2.4 分布式数据库管理系统 An Introduction to Database System 14.2.4 分布式数据库管理系统 分布式数据库管理系统 (Distributed Data Management System， D-DBMS) 建立、管理和维护分布式数据库的一组软件 An Introduction to Database System 分布式数据库管理系统 (续 ) D-DBMS的结构 分布式数据库管理系统的结构 An Introduction to Database System 分布式数

17、据库管理系统 (续 ) D-DBMS由四部分组成： (1)局部数据库管理系统 LDBMS(Local DBMS) (2)全局数据库管理系统 GDBMS(Global DBMS) (3) 全局数据字典 (Global Data Directory， GDD) (4) 通信管理 (Communication Management， CM) An Introduction to Database System 分布式数据库管理系统 (续 ) 一、按全局控制方式分类 1.全局控制集中的 D-DBMS 全局控制成分 GDBMS集中在某一结点上，全局数据字典只 有一个，也存放在该结点上。 2.全局控制分散

18、的 D-DBMS 全局控制成分 GDBMS分散在网络的每一个结点上，全局数 据字典也在每个结点上存放一份。 3.全局控制部分分散的 D-DBMS 根据应用的需要将 GDBMS和全局数据字典分散在某些结点 上。 An Introduction to Database System 分布式数据库管理系统 (续 ) 二、按局部 DBMS的类型分类 同构型 D-DBMS 每个结点的局部数据库具有相同的 DBMS即使操作系统 和计算机硬件并不相同 异构型 D-DBMS 各结点的局部数据库具有不同的 DBMS An Introduction to Database System 第十四章 分布式数据库 1

19、4.1 概述 14.2 分布式数据库系统的体系结构 14.3 查询处理和优化 14.4 分布事务管理 14.5 小结 An Introduction to Database System 14.3 查询处理和优化 14.3.1 一个实例 14.3.2 查询处理和优化要解决的问题 14.3.3 查询优化的目标 14.3.4 连接查询的优化 An Introduction to Database System 14.3.1 一个实例 数据库：简化了的供应商和零件数据库 S(Sno， City) 104个元组，存放在场地 A； P(Pno， Color) 105个元组，存放在场地 B； SP(Sno

20、， Pno) 166个元组，存放在场地 A； 设每个关系的元组均为 100字节长。 查询：求供应红色零件的、北京的供应商号 SELECT S.Sno FROM S， P， SP WHERE S.City=北京 AND SP.Pno=P.Pno AND P.Color=红色 An Introduction to Database System 一个实例 (续 ) 估算值 (某些中间结果的元组数 ) 红色零件数 =10 北京供应商的装运单数 =105 对通信系统的假定 数据传输速度 =104字节 /秒 传输延迟 =1秒 An Introduction to Database System 一个实例

21、 (续 ) 6种可能的查询存取策略，对每种 i 分别计算通信时间 Ti： Ti总传输延迟 +总数据量 /数据传输速度 (单位： b/s) 策略 1 把关系 P传送到场地 A，在 A地进行查询处理。 T1=1+105 100/104=103秒 (16.7分 ) An Introduction to Database System 一个实例 (续 ) 策略 2 把关系 S、 SP传到场地 B，在 B地执行查询处 理 T2=2+(104+106) 100/10410100秒 (2.8小时 ) An Introduction to Database System 一个实例 (续 ) 策略 3 在场地

22、A连接关系 S和 SP，选出城市为北京的元组 (105个 )，然后对这些元组中的每个元组的 Pno，询问场地 B，看此零件是否红色。 共问答 105次，由于不是传送数据，只是消息的问答，所以 T3=2 105 s(2.3天 ) An Introduction to Database System 一个实例 (续 ) 策略 4 在场地 B选出红色零件的元组 (10个 )，然后对每一 个元组逐一检查场地 A，看北京供应商的装运单中是否有 这个零件装运单 (若有则选出 S#)。 每做这样一次检查包括 2次消息，共问一答 10次，所以 T4=2 10=20秒 An Introduction to Da

23、tabase System 一个实例 (续 ) 策略 5 在场地 A选出北京的供应商的装运单把结果送到 场地 B，在场地 B完成最后处理，所以 T5=1+(105 100)/1041000秒 (16.7分 ) An Introduction to Database System 一个实例 (续 ) 策略 6 在场地 B的关系 P 中选出红色的元组 (10个 )，把结 果送到场地 A完成最终处理。所以 T6=1+(10 100)/1041秒 An Introduction to Database System 一个实例 (续 ) 表 14.1 分布环境下查询策略实例比较 策 略 通信时间 方 法

24、 1 16.7分 把 P传到场地 A 2 2.8小时 把 S， SP传到场地 B 3 2.3天 对每一北京的装运单，检查相应零件是否红色 4 20秒 对每一红色零件，检查北京供应商中是否有人供应 5 16.7分 把北京供应商的装运单传送到场地 B 6 1秒 把红色零件传送到场地 A An Introduction to Database System 一个实例 (续 ) (1) 不同的存取策略通信时间相差很大，达多个数 量级！ - 优化 。 (2)不同策略，不同的考虑方式 有些策略中数据传输速度和传输延迟都要考虑 有些策略中 (如策略 3、策略 4)主要考虑传输延迟 有些策略中 (如策略 1、

25、策略 2、策略 5)数据传输量 大，主要考虑传输时间 An Introduction to Database System 14.3 查询处理和优化 14.3.1 一个实例 14.3.2 查询处理和优化要解决的问题 14.3.3 查询优化的目标 14.3.4 连接查询的优化 An Introduction to Database System 14.3.2 查询处理和优化要解决的问题 分布式数据库系统中的三类查询： 局部查询 远程查询 全局查询 局部查询和远程查询优化 采用的技术是集中式数据库的查询优化技术 (代数优化 和非代数优化 ) An Introduction to Database

26、System 查询处理和优化要解决的问题 (续 ) 全局查询处理和优化涉及的问题 1.查询分解 2.选择操作执行的次序 3.选择执行操作的方法 An Introduction to Database System 14.3 查询处理和优化 14.3.1 一个实例 14.3.2 查询处理和优化要解决的问题 14.3.3 查询优化的目标 14.3.4 连接查询的优化 An Introduction to Database System 14.3.3 查询优化的目标 集中式数据库的查询开销 I/O代价 +CPU代价 分布式数据库的查询开销 I/O代价 +CPU代价 +通信代价 查询优化首要目标： 通

27、信代价最省 An Introduction to Database System 查询优化的目标 (续 ) 通信代价可以用下面的公式粗略计算： TC(X) C0 + X * C1 X：数据传输量，这里以 b(位 )为单位计算； C0 ：两结点之间初始化一次传输所花费的开销，它由 通信系统决定，近似为一个常数，单位为 s(秒 )； C1 ：单位数据 (b)传输的代价，单位为 (s/b)。 An Introduction to Database System 14.3 查询处理和优化 14.3.1 一个实例 14.3.2 查询处理和优化要解决的问题 14.3.3 查询优化的目标 14.3.4 连接

28、查询的优化 An Introduction to Database System 14.3.4 连接查询的优化 两种优化方法 半连接：缩减关系（或片段）进而节省传输开销 直接连接 An Introduction to Database System 14.3.4 连接查询的优化（续） 半连接 R S R ( B(S) 用半连接实现的连接运算 R S = (R S) S A = B A = B A = B A = B A = B An Introduction to Database System 14.3.4 连接查询的优化（续） 设关系 R和 S分别存放在结点 r和 s上 结点 r R 结点

29、 s S B(S) R S R R 1. 在结点 s作关系 S的投影 2. 把投影 送到结点 r，代价为 C0 C1 size(B) val(BS) 3. 在结点 r计算半连接，结果为 R， R = R S 4. 把 R从结点 r送到结点 s，代价为 C0 C1 size(R) card(R) 5. 在结点 s执行连接操作 B(S) B(S) A = B An Introduction to Database System 14.3.4 连接查询的优化（续） 半连接方案的总代价 Csj 2C0 C1(size(B) val(B(S) + size(R) card(R) 直接连接代价 Cjn =

30、 C0 C1 size(R) card(R) Csj Cjn 时采用半连接。 An Introduction to Database System 14.3.4 连接查询的优化（续） 直接连接 R*系统 (IBM SanJose研究室研制 ) 嵌套循环 排序 -合并 两种传输方式 整体传输 按需传输 An Introduction to Database System 第十四章 分布式数据库 14.1 概述 14.2 分布式数据库系统的体系结构 14.3 查询处理和优化 14.4 分布事务管理 14.5 小结 An Introduction to Database System 14.4 分布

31、事务管理 14.4.1 分布事务的恢复 14.4.2 并发控制 An Introduction to Database System 14.4 分布事务管理 事务分布执行 分布事务的原子性 组成该事务的所有子事务要么一致地全部提交，要么 一致地全部回滚 分布事务的可串行性 An Introduction to Database System 14.4.1 分布事务的恢复 故障和错误 各场地和集中式数据库相同 通信网络中信息丢失、长时间延迟、网络线路中断等 恢复策略 局部事务管理器：保证子事务完整性 局部管理器之间相互协调 An Introduction to Database System 1

32、4.4.1 分布事务的恢复（续） 两段提交协议 (2-Phase-Commitment Protocol) 协调者：一个 做出提交还是撤销的 最后 决定 参与者：所有其他 管理相应 子事务 的执行 An Introduction to Database System 14.4.1 分布事务的恢复（续） 第一阶段 协调者发出“准备提交”信息 参与者回答“就绪”或“撤销”信息 协调者作出提交或撤销的决定 第二阶段 协调者把决定信息写入日志，并发给所有参与者 参与者把收到的决定信息写入日志，并发送“应答” 信息 协调者收到所有应答信息后，事务执行到此结束 An Introduction to Dat

33、abase System 14.4.1 分布事务的恢复（续） 紧致一致性 (Tight Consistency) 各结点完全同步 缺点 全局事务可靠性低 系统效率低下 松散一致性 (Loose Consistency) 数据各副本的修改是异步的 更加灵活，提高系统的可用性 An Introduction to Database System 14.4.2 并发控制 集中式数据库封锁机制 锁的类型：共享锁 (SLock)、排它锁 (XLock) 封锁对象：表、记录 规则：遵守锁的相容性 遵守两段锁协议 分布式数据库 支持多副本 由于事务的分布执行，封锁会引起全局死锁 An Introductio

34、n to Database System 14.4.2 并发控制（续） 多副本 几种解决方案 对写操作，要申请所有副本的 X锁；对读操作，只要申 请对某个副本的 S锁。 无论读还是写都要对多数 (大于半数 )副本申请 X或 S锁 规定主副本，所有操作均申请对主副本的封锁 T1在场地 1 XLock(dsite1) T2在场地 2 XLock(dsite2) An Introduction to Database System 14.4.2 并发控制（续） 死锁 全局死锁：包括两个以上场地上的死锁 检测方法：分布等待图 预防方法：对事务按某一标准排序，只允许事务沿这 一次序单向等待 An Introduction to Database System 第十四章 分布式数据库 14.1 概述 14.2 分布式数据库系统的体系结构 14.3 查询处理和优化 14.4 分布事务管理 14.5 小结 An Introduction to Database System 14.5 小结 分布式数据库系统 基本概念 以集中式数据库系统技术为基础 丰富了集中式数据库的概念和技术内容 主要问题 查询优化 事务管理