AnIntroductiontoDatabaseSystem中国人民大学信息学院第十四章分布式数据库14.1概述
14.2分布式数据库系统的体系结构14.3查询处理和优化14.4分布事务管理14.5小结14.1概述
14.1.1分布式数据库系统14.1.2分布式数据库系统的特点14.1.1分布式数据库系统什么是分布式数据库？
分布式数据库由一组数据组成，这些数据物理上分布在计算机网络的不同结点(亦称场地)上，逻辑上是属于同一个系统。分布性逻辑整体性
分布式数据库系统(续)分布式数据库系统(续)区分一个系统是若干集中式数据库的简单连网还是分布式数据库系统的技术要点在于：
系统是否支持全局应用一个典型的例子是银行转账从一个分行的账户(设在DB1数据库)中转移若干金额到另一个分行的账户(设
在DB3数据库)中去要同时更新两个结点上的数据库分布式数据库系统(续)分布式数据库系统(续)多处理机系统(SN并行结构)
没有局部应用分布式数据库不仅要求数据的物理分布，而且要求这种分布是面向处理、面向应用的分布式数据库系统(续)分布式数据库
：分布式数据库是由一组数据组成的，这组数据分布在计算机网络的不同计算机上，网络中的每个结点具有独立处理的能力(称为场地自治)，可
以执行局部应用。同时，每个结点也能通过网络通信子系统执行全局应用。场地自治性自治场地之间的协作性14.1概述14.1.
1分布式数据库系统14.1.2分布式数据库系统的特点分布式数据库系统的特点(续)一、数据独立性逻辑独立性物理独立
性数据分布独立性(分布透明性)用户的应用程序书写起来就如同数据没有分布一样分布式数据库系统的特点(续)二、集中与自治相结合
的控制结构数据共享：(1)局部共享(2)全局共享控制机制：集中自治分布式数据库系统的特点(续)三、适当增加数据冗
余度提高系统的可靠性、可用性提高系统性能四、全局的一致性、可串行性和可恢复性局部数据库要保证ACID全局数据库也要保证
ACID第十四章分布式数据库14.1概述14.2分布式数据库系统的体系结构14.3查询处理和优化14.4
分布事务管理14.5小结14.2分布式数据库系统的体系结构14.2.1分布式数据库系统的模式结构14.2.
2数据分片14.2.3分布透明性14.2.4分布式数据库管理系统14.2.1分布式数据库系统的模式结构分
布式数据库系统的模式结构(续)分布式数据库系统增加的模式级别(1)全局外模式(GlobalExternalSchema)
(2)全局概念模式(GlobalConceptualSchema)(3)分片模式(FragmentationSche
ma)片段(Fragment)定义片段以及全局关系到片段的映象(4)分布模式(AllocationSchema)定义片
段的存放地点14.2分布式数据库系统的体系结构14.2.1分布式数据库系统的模式结构14.2.2数据分片14.
2.3分布透明性14.2.4分布式数据库管理系统14.2.2数据分片数据分片有利于按照用户的需求较好地组织数
据的分布有利于控制数据的冗余度数据分片的方式水平分片垂直分片混合分片导出分片数据分片(续)水平分片按一定的条件将
关系按行(水平方向)分为若干不相交的子集，每个子集为关系的一个片段。垂直分片指将关系按列(垂直方向)分为若干子集。每个片段通
常都包含关系的码数据分片(续)导出分片是指导出水平分片，即水平分片的条件不是本身属性的条件而是其他关系的属性的条件。
数据分片(续)[例]学生选课关系SC(Sno，Cno，Grade)，按照学生年龄＞18岁和≤18岁分片(学生年龄是学生关系S
tudent的属性)年龄＞18岁的学生选课片段由下面的查询结果组成：SELECTSno，Cno，
GradeFROMS，SCWHERES.Sno＝SC.SnoAND
S.Sage＞18；年龄≤18岁的片段SC_B由下面的查询结果组成：SELECTSno，Cno
，GradeFROMS，SCWHERES.Sno＝SC.SnoAN
DS.Sage≤18；数据分片(续)混合分片是指按上述三种分片方式得到的片段继续按另一种方式分片。数据分片(续)分片
应满足的条件完全性不相交性可重构性垂直分片：连接水平分片：并操作14.2分布式数据库系统的体系结构14.2.1
分布式数据库系统的模式结构14.2.2数据分片14.2.3分布透明性14.2.4分布式数据库管理系统14.
2.3分布透明性分片透明性–最高层次用户或应用程序只对全局关系进行操作而不必考虑关系的分片位置透明–下一层次用
户或应用程序不必了解片段的存储场地，当存储场地改变了，由于分片模式到分布模式的映像(映像3)，应用程序不必改变局部数据模型透明性
–较低层次是指用户或用户程序不必了解局部场地上使用的是哪种数据模型，模型的转换以及数据库语言的转换均由映像4完成分布透明性
(续)［例1］设在分布式数据库系统中有全局关系Student(Sno，Sname，Sdept，Sag
e)Student关系被划分为两个片段S_A和S_B。S_A代表理学院的学生，S_B代表文学院的学生。S_A存储
在场地1(Site1)，S_B冗余地存储在场地2和场地3上。分布透明性(续)要求从终端读入一个学号，查找该学号的学生姓名
、年龄，并把它们显示在屏幕上。设应用程序是用嵌入SQL语句的C语言写的。现给出查询部分的算法思想。分布透明性(续)情况1
系统具有分片透明性Scanf(“%s”,Snumber)；EXECSQLSELECTSname,
SageINTO:NAME,:AGEFROMStudentWHERESno＝：Snumbe
r；Printf("%s，%d"，NAME，AGE)； 分布透明性(续)情况2系统具有位置透明性，但不具有
分片透明性Scanf("%s“,Snumber);EXECSQLSELECTSname,Sag
eINTO:NAME,:AGEFROMS_AWHERESno＝:Snumber;If(
!FOUND)｛EXECSQLSELECTSname,SageINTO:NAME,:AGEFR
OMS_B WHERESno＝:Snumber;｝Printf("%s,%d“,N
AME,AGE)；分布透明性(续)情况3系统只具有局部数据模型透明性，不具有位置透明性Scanf("%s“
,Snumber);EXECSQLSELECTSname,SageINTO:NAME,:AGE
FROMS_AATSite1 WHERESno＝:Snumber;If(!FOUND)
{EXECSQLSELECTSname,SageINTO:NAME,:AGEFROMS_
BATSite2 WHERESno＝:Snumber; }Printf(“%s,%
d”,NAME,AGE);14.2分布式数据库系统的体系结构14.2.1分布式数据库系统的模式结构14.2.2
数据分片14.2.3分布透明性14.2.4分布式数据库管理系统14.2.4分布式数据库管理系统分布式数据库管
理系统 (DistributedDataManagementSystem，D-DBMS)建立、管理和维护分布式数据库的
一组软件分布式数据库管理系统(续)D-DBMS的结构分布式数据库管理系统(续)D-DBMS由四部分组成：(1)局部数
据库管理系统LDBMS(LocalDBMS)(2)全局数据库管理系统GDBMS(GlobalDBMS)(3)全局数据字典
(GlobalDataDirectory，GDD)(4)通信管理(CommunicationManagement，CM)
分布式数据库管理系统(续)一、按全局控制方式分类1.全局控制集中的D-DBMS全局控制成分GDBMS集中在某一结点上，全
局数据字典只有一个，也存放在该结点上。2.全局控制分散的D-DBMS全局控制成分GDBMS分散在网络的每一个结点上，全局数据
字典也在每个结点上存放一份。3.全局控制部分分散的D-DBMS根据应用的需要将GDBMS和全局数据字典分散在某些结点上。分布
式数据库管理系统(续)二、按局部DBMS的类型分类同构型D-DBMS每个结点的局部数据库具有相同的DBMS即使操作系统和计
算机硬件并不相同异构型D-DBMS各结点的局部数据库具有不同的DBMS第十四章分布式数据库14.1概述14.2
分布式数据库系统的体系结构14.3查询处理和优化14.4分布事务管理14.5小结14.3查询处理和优化
14.3.1一个实例14.3.2查询处理和优化要解决的问题14.3.3查询优化的目标14.3.4连接查询的优化
14.3.1一个实例数据库：简化了的供应商和零件数据库S(Sno，City) 104个元组，存放在场地A；
P(Pno，Color) 105个元组，存放在场地B；SP(Sno，Pno) 166个元组，存放在场地
A；设每个关系的元组均为100字节长。查询：求供应红色零件的、北京的供应商号SELECTS.Sno
FROMS，P，SPWHERES.City=''北京''AND
SP.Pno=P.PnoANDP.Color=''红色''一个实例(续)估算值(某些
中间结果的元组数)红色零件数=10北京供应商的装运单数=105对通信系统的假定数据传输速度=10
4字节/秒传输延迟=1秒一个实例(续)6种可能的查询存取策略，对每种i分别计算通信时间T[i]： T[i]＝总传
输延迟+总数据量/数据传输速度(单位：b/s)策略1把关系P传送到场地A，在A地进行查询处理。
T[1]=1+105×100/104=103秒(16.7分)一个实例(续)策略2把关系S、SP传到场地B，在B地执
行查询处理T[2]=2+(104+106)×100/104≈10100秒(2.8小时)一个实例(续)策略3在
场地A连接关系S和SP，选出城市为北京的元组(105个)，然后对这些元组中的每个元组的Pno，询问场地B，看此零件是否红色。共
问答105次，由于不是传送数据，只是消息的问答，所以 T[3]=2×105s(2.3天)一个实例(续)策略4
在场地B选出红色零件的元组(10个)，然后对每一个元组逐一检查场地A，看北京供应商的装运单中是否有这个零件装运单(若有则选出S#)
。每做这样一次检查包括2次消息，共问一答10次，所以T[4]=2×10=20秒一个实例(续)策略5在
场地A选出北京的供应商的装运单把结果送到场地B，在场地B完成最后处理，所以 T[5]=1+(105×100)/104
≈1000秒(16.7分)一个实例(续)策略6在场地B的关系P中选出红色的元组(10个)，把结果送到场地A完成最终处理
。所以 T[6]=1+(10×100)/104≈1秒一个实例(续)一个实例(续)(1)不同的存取策略通信时间
相差很大，达多个数量级！--优化。(2)不同策略，不同的考虑方式有些策略中数据传输速度和传输延迟都要考虑有些策略中(
如策略3、策略4)主要考虑传输延迟有些策略中(如策略1、策略2、策略5)数据传输量大，主要考虑传输时间14.3查询处理和优
化14.3.1一个实例14.3.2查询处理和优化要解决的问题14.3.3查询优化的目标14.3.4连接查询的优化
14.3.2查询处理和优化要解决的问题分布式数据库系统中的三类查询：局部查询远程查询全局查询局部查询和远程查询优化
采用的技术是集中式数据库的查询优化技术(代数优化和非代数优化)查询处理和优化要解决的问题(续)全局查询处理和优化涉及的问题
1.查询分解2.选择操作执行的次序3.选择执行操作的方法14.3查询处理和优化14.3.1一个实例14.3.2
查询处理和优化要解决的问题14.3.3查询优化的目标14.3.4连接查询的优化14.3.3查询优化的目标集中式
数据库的查询开销I/O代价+CPU代价分布式数据库的查询开销I/O代价+CPU代价+通信代价查询优化首要目标：通信代价最
省查询优化的目标(续)通信代价可以用下面的公式粗略计算：TC(X)＝C0+XC1X：数据传输量，这里以
b(位)为单位计算；C0：两结点之间初始化一次传输所花费的开销，它由通信系统决定，近似为一个常数，单位为s(秒)；C1：单
位数据(b)传输的代价，单位为(s/b)。14.3查询处理和优化14.3.1一个实例14.3.2查询处理和优化要解
决的问题14.3.3查询优化的目标14.3.4连接查询的优化14.3.4连接查询的优化两种优化方法半连接：缩减
关系（或片段）进而节省传输开销直接连接14.3.4连接查询的优化（续）半连接RS＝R
(B(S))用半连接实现的连接运算RS=(RS)S14.3
.4连接查询的优化（续）设关系R和S分别存放在结点r和s上14.3.4连接查询的优化（续）半连接方案的总代价 Csj
＝ 2C0＋C1(size(B)×val(B([S])+size(R)×card(R’))直接连接代价
Cjn=C0＋C1×size(R)×card(R) Csj连接查询的优化（续）直接连接R系统(IBMSanJose研究室研制)嵌套循环排序-合并两种传输方式整体传输按需
传输第十四章分布式数据库14.1概述14.2分布式数据库系统的体系结构14.3查询处理和优化14.4分
布事务管理14.5小结14.4分布事务管理 14.4.1分布事务的恢复 14.4.2并发控制 14.4
分布事务管理事务分布执行分布事务的原子性组成该事务的所有子事务要么一致地全部提交，要么一致地全部回滚分布事务的可串行性
14.4.1分布事务的恢复故障和错误各场地和集中式数据库相同通信网络中信息丢失、长时间延迟、网络线路中断等恢复策略
局部事务管理器：保证子事务完整性局部管理器之间相互协调14.4.1分布事务的恢复（续）两段提交协议(2-Phase-Com
mitmentProtocol)协调者：一个做出提交还是撤销的最后决定参与者：所有其他管理相应子事务的执行14.4.1
分布事务的恢复（续）第一阶段协调者发出“准备提交”信息参与者回答“就绪”或“撤销”信息协调者作出提交或撤销的决定第二阶
段协调者把决定信息写入日志，并发给所有参与者参与者把收到的决定信息写入日志，并发送“应答”信息协调者收到所有应答信息后，事务
执行到此结束14.4.1分布事务的恢复（续）紧致一致性(TightConsistency)各结点完全同步缺点全局事务
可靠性低系统效率低下松散一致性(LooseConsistency)数据各副本的修改是异步的更加灵活，提高系统的可用性1
4.4.2并发控制集中式数据库封锁机制锁的类型：共享锁(SLock)、排它锁(XLock)封锁对象：表、记录规则：遵守锁
的相容性 遵守两段锁协议分布式数据库支持多副本由于事务的分布执行，封锁会引起全局死锁14.4.2并
发控制（续）多副本几种解决方案对写操作，要申请所有副本的X锁；对读操作，只要申请对某个副本的S锁。无论读还是写都要对
多数(大于半数)副本申请X或S锁规定主副本，所有操作均申请对主副本的封锁14.4.2并发控制（续）死锁全局死锁：包括两个
以上场地上的死锁检测方法：分布等待图预防方法：对事务按某一标准排序，只允许事务沿这一次序单向等待第十四章分布式数据库14
.1概述14.2分布式数据库系统的体系结构14.3查询处理和优化14.4分布事务管理14.5小结14
.5小结分布式数据库系统基本概念以集中式数据库系统技术为基础丰富了集中式数据库的概念和技术内容主要问题查询优化事务
管理T1在场地1XLock(dsite1)T2在场地2XLock(dsite2)分布式数据库管理系统的结构表14.1
分布环境下查询策略实例比较把红色零件传送到场地A1秒6把北京供应商的装运单传送到场地B16.7分5对每一红色零件
，检查北京供应商中是否有人供应20秒4对每一北京的装运单，检查相应零件是否红色2.3天3把S，SP传到场地B2.8小时2把P传到场地A16.7分1方法通信时间策略A=BA=BA=BA=BA=B结点rR结点sS②?B(S)①③RS＝R’R’?④1.在结点s作关系S的投影2.把投影送到结点r，代价为C0＋C1×size(B)×val(B[S])3.在结点r计算半连接，结果为R’，R’=RS4.把R’从结点r送到结点s，代价为C0＋C1×size(R)×card(R’)5.在结点s执行连接操作B(S)B(S)A=B数据库系统概论AnIntroductiontoDatabaseSystem第十四章分布式数据库图14.1一个分布式数据库系统［例1］如图14.1所示图14.2一个多处理机系统(SN并行结构)［例2］如图14.2所示图14.3分布式数据库系统的模式结构例如，先按垂直分片再按水平分片方式继续分片。例如，先按水平分片得到的某一片段再进行垂直分片。程序变量 |
|
