分布式数据库系统及应用知识总结

1、第一章分布式数据库系统概述1、理解分布式数据库系统的特点:（1）物理分布性数据不是存放在一个站点上2、(2)(3)(4)(5)(6)(7)逻辑整体性 站点自治性 数据分布透明性 集中与自治相结合是与分散式数据库系统的区别 是与多处理机系统的区别存在适当的数据冗余度 事务管理的分布性能够按照不同标准描述分布式数据库系统的分类:（1）按局部DBMS的数据模型分类O同构型DDBSa）同构同质型（同一个公司的同一种模式）b）同构异质型（不同公司不同模式）异构型DDBS（2）按DDBS的全局控制类型分类全局控制集中型DDBS全局控制机制和全局数据词典位于中心站点 全局控制分散型 全局控制可变型 词典，另

2、外一组不包含。DDBS全局控制机制和全局数据词典分散在网络的各个站点上。DDBS也称主从型DDBS分成两组站点，一组包含全局控制机制和全局控制3、理解分布式数据库中数据的独立性和分布透明性:逻辑独立性物理独立性（表示用户程序与数据的全局逻辑结构和数据的物理结构无关）分布独立性（用户不必关心全局数据的分布情况，包括逻辑分片、物理位置分配情况以及各站 点数据库的数据模型等）分三个层次：分片透明性（完全分布透明性）：位于全局概念模式与分片模式之间，用户编写应用程序只对全局关系进行操作，不必考虑数据的逻辑分片位置透明性（中级分布透明性）：位于分片模式和分配模式之间。包括两情形 复制情况和片段及其各副本

3、的站点位置分配情况。各片段被局部数据模型透明性（低级分布透明性）：需要知道数据的分片情况和站点分配情况第二章分布式数据库系统设计1、理解分布式数据库的设计目标：（1）本地性或近地性0尽量减少通信次数和通信量，90/10准则分片和分布方案（本地和远程访问次数）择优（2）控制数据适当冗余0冗余增加了可靠性、可用性，提高了效率维护数据一致性开销增加（3）工作负荷分布各站点可以分担整个工作任本地性降低（4）存储能力和费用2、理解水平分片的定义、分类和应用：定义：水平分片是对全局关系执行选择”操作，把具有相同性质的元祖进行分组，构成若干个不相交的子集。可以分为两类：初级分片、导出分片（应用看课件_分布式

4、数据库系统设计 1 , 15页开始）。3、理解垂直分片的定义和应用定义：垂直分片通过 投影”操作把一个全局关系的属性分成若干组，基本目标是将使用频繁的属性聚 集在一起。（应用看课件_分布式数据库系统设计 2, 9页开始）能够描述分片的基本原则：原则：完整性、不相交性、可重构性4、5、掌握数据片段分配的分类和常用方法：分类：水平、垂直分配方法：（1）非冗余分配设计方法最佳适应法分片和分布方案（本地和远程访问次数）择优（2）冗余分配的设计方法 所有得益站点法 附加复制法6、掌握最佳适应法和所有得益站点法的基本特点：（1 ）最佳适应法特点：对每一种分配都进行估算，然后选择最佳站点。（2）所有得益站点

5、法特点：确定非复制问题的解确定一组站点分配副本。7、能够描述DATAID-D方法设计分布式数据库的各个阶段:（1）（2）分片设计 非冗余分配(3)(4)冗余分配局部模式的重新构造3、能够根据给出的条件对关系进行具体分片，给出正确的限定关系（见课后题67页2.9, 2.10）3.1)第三章分布式数据库系统中的查询处理和优化（连接与等值连接见课件1、2、3、掌握分布式数据库查询的分类局部查询：只涉及本地单个站点的数据，优化同集中式。远程查询：也只涉及单个站点的数据 ，但要远程通讯，选择站点。 全局查询：涉及多个站点数据，优化复杂。理解关系代数运算的交换率（书上83页）掌握直接连接优化算法的分类利用

6、站点依赖信息的算法分片与复制算法站点依赖和数据复制结合算法Hash划分算法4、5、6、掌握半连接运算（课件 3.2）掌握半连接和直接连接查询优化算法的区别取决于数据传输和局部处理的相对费用如果传输费用是主要的，采用半连接，SDD-1如果本地费用是主要的，采用直接连接System R*Hash划分算法的特点数据传送量是R索引方面，比片段复制算法更低每个站点的连接数据量同站点依赖算法1)2)3）理解1）2）3）7、能够描述基于半连接算法查询优化的基本原理和步骤1)2)3)4)5)6)1)2)3)1)2)3)4)实现步骤和方法转换一转换二转换三1)2)3)4)查询问题一一关系代数表达式(一一是转换的

7、意思)关系代数表达式一一查询树全局查询树分拆成片段查询树优化：利用关系代数等价变换规则的优化算法，优化查询树，进而优化查询9、能够根据提供的条件完成分片和复制算法应用，通过计算判断哪个关系保持分片最优(课件 书本88页)3.3习题,基本原理 通常有两次传输但是传输的数据量和传输整个关系相比，要远远少一般有：T 半card ( R，可减少站点间的数据传输量 半连接的损失：传输 W (S) =C+C1* size (B)* val( BS)基本原理是在传到另一个站点做连接前，消除与连接无关的数据，减少做连接操作的数 据量，从而减小传输代价采用半连接优化算法的步骤计算每种半连接方案的代价，并从中选择

8、一种最佳方案 选择传输代价最小的站点，计算采用全连接的方案的代价 比较两种方案，确定最优方案 &能够描述基于关系代数等价变换的查询优化算法原理、算法实现步骤基本原理查询冋题关系代数表达式(是转变的意思)分析得到查询树进行全局到片段的变换得到基于片段的查询树利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作1、第四章 分布式数据库中的事务管理和恢复掌握事务的四大特性特性：原子性、一致性、持久性、隔离性。2、能够描述两阶段提交协议的工作流程表决阶段目的是形成一个共同的决定首先，协调者给所有参与者发送“准备”消息，进入等待状态 其次，参与者收到“准备”消息后，检查是否能够提交本地事务?女

9、哺去给协调者发送“建议提交”消息，进入就绪状态? 如不能，给协调者发送“建议撤销”消息，可以单方面撤销第三，协调者收到所有参与者的消息后，他就做出是否提交事务的决定，? 只要有一个参与者投了反对票，就决定撤销整个事务，发送“全局撤销”消息 给所有参与者，进入撤销状态? 否则，就决定提交整个事务，发送“全局提交”消息给所有参与者，进入提交 状态执行阶段实现表决阶段的决定，提交或者撤销 掌握事务故障的分类站点故障1) 介质故障：2) 事务故障4、5、6、7、3)系统故障通讯故障4) 报文故障5) 网络分割故障掌握分布式数据库事务执行的控制模型的分类主从模型三角模型层次控制模型理解日志文件的特点Lo

10、g：记录所有对DB的操作事务标识：每个事务给定一个具有惟一性的标识符Log记录项start_transaction, Twrite_item, T, x, 旧值，新值read_item, T, xcommit, Tabort, T写动作：写Log比写数据优先Log存储：一般存在盘上，还会定期备份到磁带上 理解分布式数据库数据更新常见方法多站点数据更新1) 方法：站点A上有事务T对X更新,X在B1,Bn和C1,Cm上有副本，则也要对这些副本更新 主文本更新2) 指定主副本，修改只对主副本进行，修改辅助副本时，也按在主副本上执行的更新顺序执行 快照方法3)与视图相似，是导出的关系；快照的数据是实际

11、存放在数据库中的，视图不是；周期地更新；用 于某些需要“冻结”数据的应用。理解故障恢复时检查点知识设置一个周期性(时间/容量)操作点Log Buffer内容写入Log数据集写检查点Log信息：当前活动事务表，每个事务最近一次 Log记录在Log文件中的位置DB Buffer内容写入DB将本次检查点Log项在Log文件中的地址记入“重启动文件”1)2)3)4)能够描述两阶段提交协议的特点允许参与者单方面撤销事务一旦参与者确定了提交或撤销协议，它就不能再更改它的提议当参与者处于就绪状态时，根据协调者发出的消息种类，它可以转换为提交状态或者撤销状态 协调者根据全局提交规则做出全局终止决定协调者和参与

12、者可能进入互相等待对方消息的状态，使用定时器，保证退出消息等待状态分布式数据库中的并发控制第五章1、理解封锁的基本准则事务T在执行任何事务T在执行任何read item(X)操作之前，必须先执行read_lock(x)或者write_lock(x)操作(X)操作之前，必须先执行write_lock(x)操作如果事务T执行read_lock(x)操作,数据项x必须没有加锁或者已经加了读锁，否则事务T的这个操作不能进行write item如果事务T执行write_lock(x)操作,数据项x必须没有加锁，否则事务T的这个操作不能进行2、3、4、I （ X）和write_item （ x）操作之后，

13、必须执行 x上的一个读锁或者一个写锁，那么它不能再执行 X上的一个读锁或者一个写锁，那么它不能再执行 X上的一个读锁或者一个写锁，那么它不能执行unlock(x)操作 read_lock(x)操作 write_lock(x)操作unlock(x)操作事务T在完成所有read_item如果事务T已经持有数据项：如果事务T已经持有数据项：如果事务T没有持有数据项理解基于时标的并发控制方法（是选择一个事先的串行次序依次执行事务）每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行如果发生冲突，是通过撤销并重新启动一个事务来解决事务重新启动时，则赋予新的时标优点是没有死锁，不必设置锁封锁和死锁

14、检测引起的通信开销也避免了但要求时标在全系统中是唯一的掌握死锁检测的方法分类集中式死锁检测法层次式死锁检测法分布式死锁检测法理解一致性调度和可串行化调度的特点一致性调度1） 调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度 可串行化调度1）如果一个调度等价于某个串行调度，则该调度称为可串行化调度。2）也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度 串行调度（1） 一个事务的第一个动作是在另一个事务的最后一个动作完成后开始 操作不会交叉，每个事务相继执行.即调度中事务的各个5、6、1、理解可靠性和可用性的含义与关系 可靠性能够描述死锁发生的四个必

15、要条件互斥条件：事务请求对资源的独占控制等待条件：事务已持有分配给它的资源 ，又去申请并等待别的资源非抢占条件：直到资源被持有它的事务释放前，不可能将资源强制从持有它的事务夺去循环等待条件：存在事务互相等待的等待圈 能够列举并发控制算法算法：丢失更新、不一致性分析、读脏数据第六章 分布式数据库中的可靠性6、指数据库在一给定时间间隔内不产生任何失败的概率。它强调数据库的正确性，要求数据库正确运行。通常用来描述不可修复的系统。可用性强调的是当需要访问数据库时，它是可用的。指在给定的时间点系统可以正常运行的概率。通常用于描述那些可以修复的系统。两者关系通常认为构建可用性的系统比可靠性的系统容易两者是

16、统一的，可靠性高的系统可用性自然是好的2、两者又是矛盾的，增加错误风险的情况下，可提高可用性；采用太谨慎的策略会降低可用性理解两阶段提交协议如何转为三阶段提交协议3、4、5、提交协议是非阻断的充要条件是，在其状态转换图中不存在： 没有状态是既与提交又与撤销状态“相邻” 不存在不可提交状态是与提交状态“相邻”相邻从一个状态直接转换到另一个状态2PC中的状态C（提交）状态是可提交状态，其它为不可提交状态?Ready状态是不可提交状态；Wait状态是不可提交状态它们都侵犯了非阻断协议的充要条件，从而考虑改变2PC,使其满足非阻断协议条件在Wait和Commit之间,或者在Ready和Commit之间

17、加入另一种状态作为缓冲状态，从而有了 3PC掌握分布式可靠性协议的组成可靠性协议组成：提交协议、终结协议、恢复协议提交和恢复协议详细说明提交命令和恢复命令是如何执行的终结协议是分布式系统特有的协议。在执行一个分布式事务时，若一个 其它Site也停止该事务。处理这种情况的技术就称为终止协议。终结协议与恢复协议的比较假若一个Site失效?终结协议确定了未失效 Site如何处理该失效事件?恢复协议确定失效 Site重启动后，进程（协调者，参与者）恢复它的状态的过程网络分割时? 终结协议采取必要的措施来终结在不同网络区间执行的活动事务?当网络重新连接后，恢复协议保证使各个冗余DB相互一致理解发生网络分

18、割时冗余分布式数据库和非冗余数据库采用的处理协议非冗余数据库处理网络分割的终结协议集中式协议，基于集中式并发控制算法（主站点法和主副本法） 基于表决的协议冗余数据库处理网络分割的终结协议复制控制协议能够描述三阶段提交协议中事务协调者和参与者的状态转换（町协fl若O者preparevot aboi*V0tr-7DlDlllLlprepare-to-CO nimitpriurt Qic le-co nunil 匚orp-nhAFf /to CDDhiuktglolMLl-BborE /oelDDal-ADDltACKi-fady-tQ-coiuQjit|-4inRLISite故障，希望能够采用版本

19、号法进行不一致性检测，并且应用于实际需求处理故障的策略有可能牺牲正确性来提高可用性，因此接受了不一致性的风险在这种情况下，监测这些不一致性，并尽可能地加以解决是很有用的概念需要首先发现哪些数据部分已经不一致（不一致性检测）然后根据发生的情况，给这些部分赋予一个最合理的值(不一致性的解法)提出问题假设网络分割期间，在两个或多个站点组中已执行了若干事务 ，可能对同一数据片断的不同副 本进行了独立更新检测方法一种比较自然的方法? 比较各副本的内容，检查其是否相同，但是这种方法不仅效率低，一般也是不正确的。检测方法采用版本号? 允许对数据项操作的站点的副本是主副本，其它是孤立或隔离的副本? 正常工作期间，全部副本都是主副本，并且互相一致，每份副本维持一个原版号和一个当前版 本号? 网络分割时，每个孤立副本的原版本号被置为当前版本号值，并且，直到分割修复为止，此原版号不会改变例子已知前提? 数据项X的副本x1, x2, x3存储在三个不同站点?V1, V2, V3分别是x1, x2, x3的版本号初始时，三份副本一致，所以有：?V1=(0, 2)，V2 =(0, 2)，V3=(0, 2),假设经过了两次更新?(原版本号，当前版本号)把X3从其它两个副本分开，多数法选择x2和