分布式数据库系统及其应用复习大纲
第一章 分布式数据库系统概述
1、理解分布式数据库系统的特点
分布式数据库系统的定义：
分布式数据库系统，通俗地说，是物理上分散而逻辑上集中的数据库系统。分布式数据库
系统使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通
常是集中是数据库系统）连接起来，共同组成一个统一的数据库系统。
分布式数据库系统的特点：１物理分布性：数据不是存放在一个站点上２逻辑整体性：是
与分散式数据库系统的区别３站点自治性：是与多处理机系统的区别４数据分布透明性５集
中与自治相结合的控制机制６存在适当的数据冗余度７事务管理的分布性
2、能够按照不同标准描述分布式数据库系统的分类
按局部数据库管理系统的数据模型分类：同构性（homogeneous）（分为同构同质型和
同构异质型）DDBS和异构性(heterogeneous)DDBS
按分布式数据库系统的全局控制系统类型分类：全局控制集中型DDBS，全局控制分散型
DDBS，全局控制可变型DDBS。
3、理解分布式数据库中数据的独立性和分布透明性
所谓数据独立性是指用户或用户程序使用分布式数据库如同使用集中式数据库那样，不必
关心全局数据的分布情况，包括全局数据的逻辑分片情况、逻辑片段站点位置的分配情况，
以及各站点上数据库的数据模型等。也就是说，全局数据的逻辑分片、片段的物理位置分配，
各站点数据库的数据模型等情况对用户和用户程序透明。所以，在分布式数据库中分布独立
性也称为分布透明性。
分布透明性包括三个层次：分片透明性（完全分布透明性）：映像2
位置透明性（中级分布透明性）：映像3
局部数据模型透明性（低级分布透明性）：映像4
无分布透明性：异构数据
第二章 分布式数据库系统设计
1、理解分布式数据库的设计目标
分布式数据库设计的目标1分布式数据库的本地性或近地性2控制数据的适当冗余3工作负
荷分布4存储的能力和费用
2、理解水平分片的定义、分类和应用
水平分片是对全局关系执行“选择操作”，把具有相同性质的元组进行分组，构成若干个不
相交的子集。水平分片的方法可归为初级分片和导出分片两类。
初级分片：以关系自身的属性性质为基础，执行“选择”操作，将关系分为若干个不相交的
片段。例子2.1
S（S#，SNAME, AGE, SEX）
Define fragment S1 as select * from where sex=’M’
Define fragment S2 as select * from where sex=’F’
导出分片：全局关系的导出分片不是以其自身的属性性质为基础，而是从另一个关系的属性
性质或水平片段推导出来的。采用导出分片可片可使片段与片段之间的“连接”变得更容易。
例2.3 设全局关系SC（Ｓ＃，Ｃ＃，GRADE），S（S#，SNAME, AGE, SEX）若要将ＳＣ划分
为男生的各门课成绩和女生的各门课成绩，这就不可能从SC本身的属性性质来执行选择，必须从关系S的属性性质或水平片段来导出。
Define fragment SC1 as select SC.S#,C#,GRADE from SC,S where SC.S#=S.S# and SEX=’M’ Define fragment SC2 as select SC.S#,C#,GRADE from SC,S where SC.S#=S.S# and SEX=’F’
如果S已经进行水平分片，分为SF和SM，分别为男生全体和女生全体，则上述的片段定义可以基于片段SF和ＳＭ导出：
Define fragment SC1 as select * from SC where S# in(select SF.S# from SF)
Define fragment SC2 as select * from SC where S# in(select SM.S# from SM)
3、理解垂直分片的定义和应用
一个全局关系的垂直分片是通过“投影”操作把它的属性分为若干组。确定一个全局关系R的垂直分片需要根据应用以“同样方式”（例如具有相同的使用频率）访问的属性来进行分组。
例2.4全局关系EMP（E#，NAME，SAL，TEL，MAGNUM，DEPT），主码为E#。主要应用有：集中在站点3上的管理性应用要求查询雇员的：NAME，SAL，TEL；和从其他站点发出的应用要求查询雇员的：NAME，DEPT，MAGNUM。
解：如果使用垂直分片：EMP１（E#，NAME，SAL，TEL）和EMP２（E#，MAGNUM，DEPT） 则NAME属性只属于一个片段，对于上述的应用，必须进行连接操作和非本地访问。
如果使用垂直群集：EMP１（E#，NAME，SAL，TEL）和EMP２（E#，NAME，MAGNUM，DEPT）
则对于上述应用，不需要执行连接操作，且可实现较好的本地性。
4、能够描述分片的基本原则
完备性原则：要把所有的数据映射到各个片断中
可重构原则：关系分片后的各个片断可重构整个关系
不相交原则：关系分片后的各个片断不能重叠
5、掌握数据片断分配的分类和常用方法
分配的简化模型有：读代价、写代价、存储代价和目标函数。
常用方法：非冗余分配设计方法（包含最佳适应法和其他方法）和冗余分配的设计方法（包含所有得益站点法和附加复制法）
6、掌握最佳适应法和所有得益站点法的基本特点
最佳适应法是对每一种分配方式进行估算，然后选择最佳的站点。这种方法不考虑把一个片段与一个相关片段放在同一站点的“相互”影响。
特点：将片断Ri分配到访问Ri次数最多的那个站点上
Bij= ∑kFkj*Nki
所有得益站点法：首先确定非复制为题的解，然后在全部站点中确定一组站点，给这组站点中的每一个站点分配片断的一个副本，这样做所得到的好处要比为此而付出的费用合算。 特点：将片断Ri的副本分配到所有得益站点j上
Bij= ∑kFkj*Rki -c*∑k ∑j’≠j Fkj*Uki
如果Bij＞0，则站点j是得益站点，放置Ri的一个副本
7、能够描述DATAID-D方法设计分布式数据库的各个阶段
需求分析，概念设计，分布要求分析，全局逻辑设计，分布设计，局部逻辑设计，局部物理设计。逻辑设计分为全局逻辑设计和局部逻辑设计
8、能够根据给出的条件对关系进行具体分片，给出正确的限定关系
上边的例子。
第三章 分布式数据库系统中的查询处理和优化
1、掌握分布式数据库查询的分类
局部查询、远程查询和全局查询
2、理解关系代数运算的交换率
?∪1 (∪2 (R)) =∪2 (∪1 (R))
条件:∪1 ∪2 是 选择操作 时总成立，∪1 ∪2 是 投影操作 时要求其属性集合相等 ∪1 与∪2 是投影和选择操作时:πA1,?An(σF(R)) =σF (πA1,?An (R)) 的条件是 F中的属性是 A1, ?. An 的子集。R ∞ S = S ∞ R R × S = S × R
R ∪S = S∪ R R ∩S = S ∩ R R ∝ S ≠? S ∝ R R - S ≠? S - R
3、掌握直接连接优化算法的分类
利用站点依赖信息的算法，分片与复制算法，站点依赖和数据复制结合算法，Hash划分算法
4、掌握半连接运算
见Ｐ８３－８４例子
5、掌握半连接和直接连接查询优化算法的区别
取决于数据传输和局部处理的相对费用；如果传输费用是主要的，采用半连接；如果本地费用是主要的，采用直接连接,
6、理解Hash划分算法的特点
１数据传送量是R；２索引方面, 比片段复制算法更低，３每个站点的连接数据量同站点依赖
7、能够描述基于半连接算法查询优化的基本原理和步骤
基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数据量，从而减小传输代价
步骤：１计算每种半连接方案的代价，并从中选择一种最佳方案
２选择传输代价最小的站点，计算采用全连接的方案的代价
３比较两种方案，确定最优方案
8、能够描述基于关系代数等价变换的查询优化算法原理、算法实现步骤
原理：1查询问题——〉关系代数表达式2分析得到查询树3进行全局到片段的变换得到基于片段的查询树4利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作 算法：1连接和合并尽可能上提（树根方向）2选择和投影操作尽可能下移（叶子方向） 实现步骤：转换一：1查询问题——〉关系代数表达式。2转换二：关系代数表达式——〉查询树。3转换三：全局查询树分拆成片段查询树。4优化：利用关系代数等价变换规则的优化算法，优化查询树，进而优化查询
9、能够根据提供的条件完成分片和复制算法应用，通过计算判断哪个关系保持分片最优 P88例3-6 考试
第四章 分布式数据库中的事务管理和恢复
1、掌握事务的四大特性
原子性（Atomicity）,一致性（Consistency）,持久性（Durability）.隔离性（ Isolation）
2、能够描述两阶段提交协议的工作流程
两阶段提交协议的基本思想是：将本地原子性提交行为的效果扩展到分布式事务, 保证了分布式事务提交的原子性, 并在不损坏Log的情况下, 实现快速故障恢复, 提高DDB系统的可靠性.
2PC把事务的提交过程分为两个阶段：第一阶段：表决阶段，目的是形成一个共同的决定 首先，协调者给所有参与者发送“准备”消息，进入等待状态
其次，参与者收到“准备”消息后，检查是否能够提交本地事务
如能，给协调者发送“建议提交”消息,进入就绪状态
如不能，给协调者发送“建议撤销”消息，可以单方面撤销
第三，协调者收到所有参与者的消息后，他就做出是否提交事务的决定，
只要有一个参与者投了反对票，就决定撤销整个事务，发送“全局撤销”消息给所有参与者，进入撤销状态
否则，就决定提交整个事务，发送“全局提交”消息给所有参与者，进入提交状态 第二个阶段：执行阶段，实现表决阶段的决定，提交或者撤销
3、掌握事务故障的分类
分布是数据库的故障
分布是数据库的故障分为站点故障和通信故障。站点故障包括事务故障、系统故障和介质故障。
事务故障包括计算溢出。完整性被破坏、操作员干预、输入或输出出错等。
通信故障分为报文故障和网络分割故障。
4、掌握分布式数据库事务执行的控制模型的分类
分为三类：主从模型，三角模型，层次控制模型
5、理解日志文件的特点
日志文件保存到磁盘上。日志
Log：记录所有对DB的操作
事务标识：每个事务给定一个具有惟一性的标识符
Log记录项 :
[start_transaction, T]
[write_item, T, x, 旧值, 新值]
[read_item, T, x]
[commit, T]
[abort, T]
写动作：写Log比写数据优先
Log存储：一般存在盘上, 还会定期备份到磁带上
6、理解分布式数据库数据更新常见方法
多站点数据更新、主文本更新法、快照方法
7、理解故障恢复时检查点知识
检查点（Checkpoint）：设置一个周期性（时间/容量）操作点
a) Log Buffer内容写入Log数据集
b) 写检查点Log信息：当前活动事务表, 每个事务最近一次Log记录在Log文件中的位置 c) DB Buffer内容写入DB
d) 将本次检查点Log项在Log文件中的地址记入“重启动文件”
8、能够描述两阶段提交协议的特点：2PC协议的重要特点：1允许参与者单方面撤销事务 2一旦参与者确定了提交或撤销协议，它就不能再更改它的提议3当参与者处于就绪状态时，根据协调者发出的消息种类，它可以转换为提交状态或者撤销状态4协调者根据全局提交规则做出全局终止决定5协调者和参与者可能进入互相等待对方消息的状态，使用定时器，保证退出消息等待状态
第五章 分布式数据库中的并发控制
1、理解封锁的基本准则
1事务T在执行任何read_item（x）操作之前，必须先执行read_lock(x)或者write_lock(x)操作
2事务T在执行任何write_item（x）操作之前，必须先执行write_lock(x)操作
3如果事务T执行read_lock(x)操作,数据项x必须没有加锁或者已经加了读锁，否则事务T的这个操作不能进行
4如果事务T执行write_lock(x)操作,数据项x必须没有加锁，否则事务T的这个操作不能进行
5事务T在完成所有read_item（x）和write_item（x）操作之后，必须执行unlock(x)操作 6如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行read_lock(x)操作
7如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行write_lock(x)操作
8如果事务T没有持有数据项x上的一个读锁或者一个写锁，那么它不能执行unlock(x)操作
2、理解基于时标的并发控制方法
并发控制方法包含全局时标和局部时标
3、掌握死锁检测的方法分类
局部死锁：仅在一个站点上发生的死锁
全局死锁：涉及多个站点的死锁(即等待圈由多个站点组成)
4、理解一致性调度和可串行化调度的特点
一致性调度：调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度
可串行化调度：如果一个调度等价于某个串行调度，则该调度称为可串行化调度。 也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度
5、能够描述死锁发生的四个必要条件：会考试
互斥条件：事务请求对资源的独占控制
等待条件：事务已持有分配给它的资源, 又去申请并等待别的资源
非抢占条件：直到资源被持有它的事务释放前, 不可能将资源强制从持有它的事务夺去 循环等待条件：存在事务互相等待的等待圈
6、能够列举并发控制算法
悲观并发控制法和乐观并发控制法
悲观并发控制法有基于封锁的算法、基于时标排序的算法和混合算法。乐观的方法也可分为基于封锁或基于时标排序的算法。