分布式课后习题答案.doc

第一章 分布式数据库系统概述1.1请用自己的语言定义下列分布式数据库系统中的术语：（1）局部数据:只提供本站点的局部应用所需要的数据。全局数据：虽然物理上存储在个站点上，但是参与全局应用（2）全局/局部用户：局部用户： 一个用户或一个应用如果只访问他注册的那个站点上的数据称为本地或局部用户或本地应用；全局用户： 如果访问涉及两个或两个以上的站点中的数据，称为全局用户或全局应用。全局/局部DBMS：1）LDBMS(Local DBMS)：局部场地上的数据库管理系统，其功能是建立和管理局部数据库，提供场地自治能力，执行局部应用及全局查询的子查询。（2）GDBMS(Global DBMS)：全局数据库管理系统，主要功能是提供分布透明性，协调全局事物的执行，协调各局部DBMS以完成全局应用，保证数据库的全局一致性，执行并发控制，实现更新同步，提供全局恢复功能等。（3）全局外模式：全局应用的用户视图，也称全局视图。从一个由各局部数据库组成的逻辑集合中抽取，即全局外模式是全局概念式的子集。对全局用户而言，都可以认为在整个分布式数据库系统的各个站点上的所有数据库都如同在本站点上一样，只关心他们自己所使用的那部分数据（4）全局概念模式：描述分布式数据库中全局数据的逻辑结构和数据特性，是分布式数据库的全局概念视图。采用关系模型的全局概念模式由一组全局关系的定义(如关系名、关系中的属性、每一属性的数据类型和长度等)和完整性定义(关系的主键、外键及完整性其他约束条件等)组成。（5）分片模式：描述全局数据的逻辑划分。每个全局关系可以通过选择和投影的关系操作被逻辑划分为若干片段。分片模式描述数据分片或定义片段，以及全局关系与片段之间的映像。这种映像是一对多的。（6）分配模式：根据选定的数据分布策略，定义各片段的物理存放站点，即定义片段映像的类型，确定分布式数据库是冗余的还是非冗余的，以及冗余的程度。如果一个片段分配在多个站点上，则片段的映像是一对多的，分布式数据库是冗余的，否则是不冗余的。（7）局部概念模式：是全局概念模式的子集。全局概念模式经逻辑划分成一个或多个逻辑片段，每个逻辑片段被分配在一个或多个站点上，称为该逻辑片段在某个站点上的物理映像或称物理片段。对每个站点来说，在该站点上全部物理映像的集合称为该站点上的局部概念模式。或者说，一个站点上的局部概念模式是该站点上所有全局关系模式在该站点上物理映像的集合。（8）局部内模式：是分布式数据库中关于物理数据库的描述，描述的内容不仅包含局部本站点的数据的存储描述，还包括全局数据在本站点的存储描述。1.4什么是分布式数据库系统？它具有哪些主要特点？怎么样区别分布式数据库系统与只提供远程数据访问功能的网络数据库系统？（分布式数据库系统的定义、特点详见课件第1章4.1.课本P6）分布式数据库系统：物理上分散而逻辑上集中的系统，它使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通常是集中式数据库系统）连接起来，共同组成一个统一的数据库系统。分布式数据库系统可以看成是计算机网络和数据库系统的有机结合。特点：物理分布性、逻辑整体性、站点自治性、数据分布透明性、集中与自治相结合的控制机制、存在适当的数据冗余度、事务管理的分布性。1.6用自己的语言解析“什么时候需要进行数据分片和数据复制”？（课本第10,11页）数据分片又称数据分割、数据分段，局部数据库是由全局数据库分割而成；全局数据库 是由各个局部数据库逻辑组合而成。一个关系描述了某些数据之间的逻辑相关性，不同站点的用户需要该关系中的元组可能不同，需要对这个关系进行分割，并将 分割后得到的各部分元组，称为该关系的逻辑片段，存放在相应的站点上。这样 处理各得其所，可以减少网络上的通信，提高系统的相应效率。数据复制指分布式数据库中的数据根据需要将数据划分成逻辑片段，按某种策略把数据 分片所得的逻辑片段分散地存储在各个站点上。全局数据有多个副本，每个站点都有一个完整的数据副本。系统可靠性高，响应速度快，数据库恢复也较容易。但要保持各个站点上数据的同步修改，将要付出高昂的代价。1.7在分布式数据库系统中，为什么要对数据进行分片？什么是关系的片段？关系的片段有哪些主要类型？（课本第9-10页。数据分片又称数据分割、数据分段，局部数据库是由全局数据库分割而成；全局数据库 是由各个局部数据库逻辑组合而成。一个关系描述了某些数据之间的逻辑相关性，不同站点的用户需要该关系中的元组可能不同，需要对这个关系进行分割，并将 分割后得到的各部分元组，称为该关系的逻辑片段，存放在相应的站点上。这样 处理各得其所，可以减少网络上的通信，提高系统的相应效率。数据分片是指数据存放单位不是全部关系，而是关系的一个片段。也就是关系的一部分。包括： （1）水平分片：按一定的条件把全局关系的所有元组划分成若干不相交的子集，每个子集为关系的一个片段。 （2）垂直分片：把一个全局关系的属性集分成若干子集，并在这些子集上做投影运算，每个投影为垂直分片。 （3）混合型分片：将水平分片与垂直分片方式综合使用则为混合型分片。 ）1.8为什么说分布式数据库系统中，数据独立性这一目标比集中式数据库系统更为重要，也更为复杂？（详见课本第25页第二段）1.9概述分布式DBMS的参考模型中，用户处理器、数据处理器、全局数据库控制和通信子系统的组成和功能。（组成（参考模型）：详见课件5.6；功能：用户处理器课本第18页；数据处理器课本第20页；全局数据库控制和通信子系统课本第21页）用户处理器：用户结果格式化器用户命令翻译器约束实施器用户结果用户命令规范化数据规范化命令外部模式概念模式规范化命令用户处理器用户处理器的功能一是它把数据操纵语言中的用户命令，翻译成规范化命令。；二是它把来自数据处理器的数据，翻译成用户理解的格式。数据处理器：数据处理器负责存取数据库的数据，数据处理器的组成主要包括：规范化命令翻译器、规范化结果格式器和运行时支持处理器。全局数据库控制和通信子系统的组成和功能：全局数据库控制和通信子系统负责通信和控制分布式的执行。由多个处理器组成：1. 分解器：分解器由一个或几个数据处理器组成，主要任务是把来自用户处理器的请求，翻译成一个由若干命令组成的分布式执行策略。2. 合并器：它的任务是在提交给用户处理器之前，把分布式执行策略访问不同站点所得到的结果数据组合起来。3. 分布式执行监视器：负责分布式执行策略的正确执行以及保证分布式环境中事务的原子性。同时还负责提供复制独立性和分布式并发控制。4. 通信子系统：提供站点之间的信息传送。每个站点都有一个通信处理器，与此通信子系统相接口。通信处理器使用一组通信协议来正确利用通信设施和为分布系统提供无错的和可靠的通信。5. 本地执行监视器：负责在本地数据处理器中，执行该分布式执行策略中与本站点有关的部分。当执行策略的某一部分在该数据处理器中完成执行，或出现故障时，就由它来通知全局执行监视器。1.10分布式数据库系统潜在的优点是什么？存在哪些技术问题？（优点：详见课本第34-35页共6点；技术问题详见课本第35-36页面共7点）优点：1. 良好的可靠性和可用性2. 提高系统效率，降低通信费用3. 较大的灵活性和可伸缩性4. 经济性和保护投资5. 适应组织的分布式管理和控制6. 数据分布具有透明性和站点具有较好的自治性技术问题：1. 如何控制数据的分片、分布与冗余度2. 如何实现异构数据库的互联（P.36）3. 如何优化分布式数据库的查询处理（P.36）4. 如何更好地实现分布式数据库的更新处理（P.36）5. 如何实现分布式数据库的并发控制机制（P.36）6. 如何实现分布式数据库的恢复控制机制（P.36）7. 如何实现目录管理（P.36）第二章课后习题2.1 概述分布式数据库系统的创建方法、方法特点和适用范围答：创建方法有：组合法、重构法组合法的特点：剖析网络功能；剖析原有数据库系统；解决数据的一致性、完整性和可靠性；难度较大；组合法适用范围：通常是异构或者同构异质DDBS重构法的特点：根据实现环境和用户需求；按照DDBS的设计思想和方法；从总体设计做起，包括LDBS,重新建立一个DDBS；可有效解决数据一致性、完整性和可靠性问题。重构法的适用范围：通常是同构异质或同构同质DDBS2.2 分布式数据库设计的主要目标是什么?1. 目标一：分布式数据库的本地性或近地性2. 目标二：控制数据适当冗余3. 目标三：工作负荷分布4. 目标四：存储的能力和费用2.3 概述分布式数据库设计的关键问题及解决方法答：关键问题：1）数据的实际分布情况。访问的多个数据对象是存放在同一站点上还是分布在多个站点所需的时间和费用有很大区别。2）数据对否被复制、复制副本的多少问题3）数据分片、片段如何复制、数据或片段如何分布、分布式数据库管理系统的透明性解决方法：1）分布式数据库遵循本地性或近地性，尽量减少通信次数和通信量，90/10准则，分片和分布方案（本地和远程访问次数）择优；90%的数据应当在本地站点找到，而只有10%的数据需要在远程站点上进行访问。也即最有效的设计是确保数据对最大数目的应用具有本地性。可以采用的设计方法是对每一种可供选择的分片方法和片段的分配方法都统计出本地访问和远程访问的次数，然后从其中选择一个最佳的方案。2）控制数据适当冗余，冗余增加了可靠性、可用性，提高了效率，维护数据一致性开销增加。在分布式数据库系统中，为了提高系统的本地性、并发度和可靠性，需要增加数据的副本。这不仅使应用具有高度的可用性和本地性，而且当数据的任何一个副本不能使用时，可方便地使用在另一站点中的该数据的副本进行恢复，从而提高系统的可靠性。3）工作负荷分布分布式计算机系统的一个重要特征是把工作负荷分布在网络中的各个站点上。分布工作负荷的目的是充分利用每个站点计算机的能力和资源，以提高应用执行的平行程度，从而提高系统的性能。4）存储能力和费用 数据库的分布会受到各站点的存储能力的影响。在网络中可以有专门用于存储数据的站点，也可以有完全不支持大容量存储的站点。一般，数据存储的费用与 CPU，I /O及传输的费用相比是不重要的，但是必须考虑各站点可用存储空间的限制。2.4 考虑为局域网设计的分布式数据库系统和为广域网设计的分布式数据库系统由什么区别?这道不会，参考p42 1.分布式数据库的本地性或近地性2.5 请用自己的语音阐述分布式数据库设计的自顶向下和自底向上设计方法及其适用范围。答: 自顶向下：(1) 从概念设计到形成形式规格说明设计分布式数据库。从头开始设计分布式数据库。该方法假定设计者理解用户的数据库应用要求，历经概念设计、逻辑 设计和物理设计阶段，并将与计算机系统无关的规格说明逐渐求精成 低级的、与计算机系统有关的规格说明。概念设计和逻辑设计的结果 是数据库的全局模式，包含了数据库的所有数据元素及其使用形式。 专门针对分布式数据库的一个设计阶段称为分布设计，将全局模式映 射成几个可能交叠的子集模式，每一个子模式表示与一个站点有关的 信息子集，然后完成每一单个数据库的设计。(2) 适用范围：通常是同构异质或同构同质DDBS。自底向上： (1)通过聚集现存数据库设计分布式数据库。假定由于需要互联一些现存数据库以形成一个多数据库系统，或由于对各站点已独立完成了数据库的概念说明，所以各站点上数据库的规格说明已是现存的。需要综合各站点的规格说明，以便得到分布式数据库的全局概念模式。(2)适用范围：通常是异构或者同构异质DDBS。2.6数据分片应遵守哪些原则?数据分片要准守的原则：完备性原则：要把所有的数据映射到各个片断中可重构原则：关系分片后的各个片断可重构整个关系不相交原则：关系分片后的各个片断不能重叠数据分片有哪些基本类型和方法?有两种基本的数据分片方法：水平分片方法和垂直分片方法。通过交替水平分片与垂直分片，可以产生混合分片。 水平分片 水平分片是对全局关系执行“选择”操作，把具有相同性质的元组进行分组，构成若干个不相交的子集。水平分片的方法可归为初级分片和导出分片两类。 垂直分片和垂直群集 一个全局关系的垂直分片是通过“投影”操作把它的属性分成若干组。根据应用以“同样方式”(具有相同的使用频率)访问的属性来进行分组。垂直分片的组必须只在某个键属性上重叠，其他属性不可重叠；垂直群集的组在其他属性上也可以重叠。 2.7为什么说在关系型分布式数据库中使用导出式水平分片，使关系之间的连接变得更加容易？试举例。 答：原因：全局关系的导出式水平分片不是以其自身的属性性质为基础，而是从另一个关系的属性性质或水平片段推导出来的。 确定一方便的导出式水平分片要求确定应用所执行的最重要的结合操作。导出分片可使片段与片段间“连接”变得更容易。可将连接条件代之以子查询，从而使它变为一般的判别条件。具体实例： 例2.3 设全局关系 SC( S#, C#, GRADE) S ( S#, SNAME, AGE, SEX ) 要求： 将SC划分为男生各门课成绩和女生的各门成绩。 这不可能从SC本身的属性性质来执行选择，必须从关系S的属性性质或水平片段来导出。 按S的属性导出 Define fragment SC1 as （ Define fragment SM as ） Select SC.S#, C#, GRADE From SC, S Where SC.S#=S.S# and SEX=M Define fragment SC2 as （ Define fragment SF as ） Select SC.S#, C#, GRADE From SC, S Where SC.S#=S.S# and SEX=F 如果S已经进行水平分片，分为SF和SM, 分别为男生全体和女生全体， 则按S的水平分片（SF/SM）导出： 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)2.8 采用DATAID-D方法的分布式数据库设计与传统的集中式数据库设计在步骤和内容上有什么不同？分布要求分析设计位于概念设计阶段之后进行，主要工作：1. 收集用户分布要求信息2. 水平分片的划分谓词3. 每一应用在各站点激活的频率分布设计全局逻辑设计之后进行，主要工作：1. 分布要求和全局逻辑模式作为输入2. 形式为全局数据库模式和逻辑访问表3. 输出为分片模式和分配模式 第三章3.1 用自己的语言概述分布式查询优化与集中式查询优化的异同。 分布式查询和集中式查询的相同点即在本地的CPU和I/O代价，不同点为分布式查询比集中式查询多了通讯代价3.2 试述分布式查询优化的层次结构。分布式查询处理按不同层次结构执行，符合分布式DBMS的体系结构。分布式查询处理可分为四个层次。 查询分解 将查询问题（SQL）转换成一个定义在全局关系上的关系代数表达式。 本层转换所需要从全局概念模式中获得。 数据本地化 把一个在全局关系上的查询具体化，落实到合适的(使尽可能做到本地化或近地化)片段上的查询。即将全局关系的关系代数表达式变换为相应片段上的关系代数表达式。 这一变换所需要的信息在分片模式和片段的分配模式中 获得。 全局优化 输入的是分片查询，查询优化目标是寻找一个近于最优 的执行策略。 全局优化即是找出分片查询的最佳操作次序，使得代价函数最小。代价函数一般是I/O、CPU和通信代价之和。 全局优化的一个重要方面是关于连接操作的优化。全局 优化处理层输出是一个优化的、片段上的关系代数查询。 局部优化 局部查询优化由拥有与查询有关的片段的各个站点执行。在每个站点上执行的子查询被称为局部查询。它由该站 点上的DBMS进行优化，采用集中式数据库系统中查询 优化的算法。所需信息取自局部模式。3.3 概括基于关系代数等价变换的查询优化算法的基本原理与实现步骤。 基本原理1. 把查询问题转化为关系代数表达式；2. 分析得到查询树；3. 进行全局到片段的变换得到基于片段的查询树；4. 利用关系代数等价变换规则的优化算法，尽可能先执行 选择和投影操作，后执行连接和合并操作；5. 对该查询树进行优化，从而达到查询优化的目的。 优化算法1. 连接操作和合并操作尽可能上提（树根方向）；2. 选择操作和投影操作尽可能下移（叶子方向）；3. 尽可能先执行选择和投影操作，后执行连接和合并操作。4. 经过选择和投影操作不但可以减少其后操作量，还可以 减少操作次数。 实现步骤和方法 将一个查询问题转换成关系代数表达式。 从关系代数表达式到查询树的变换：对一个关系 代数表达式进行语法分析，可以得到一棵语法树 (或查询树)，即查询树根节点是最终的查询结果，叶子节点是查询涉及的所有关系或片段，中间节 点是按关系代数表达式中的操作顺序组成的一组 关系操作符。 从全局查询到片段查询的变换：把基于全局关系 的查询树中的全局关系名，用其重构该全局关系 的各个片段名替换，变换成相应片段上的查询树。 利用关系代数等价变换规则优化算法，对片段的 查询树进行优化处理，最后达到优化查询目的。3.4 概述基于半连接算法查询优化的基本原理和适用情形。基本原理：p84p85 适用情形：p85，由此可见那段，第四行的“所以。”开头3.5 概述基于直接连接算法查询优化的基本原理和适用情形。另一种是自然连接。自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。 3.6 设有关系R，S，T 如图3.13所示。（1）设计连接RS T。（2）计算半连接R S, S R,ST,T R,T S,R T。 A B C B C D B C D2353563565363593591686836833465965965354164162685845846、（1）RSTABCDEI235669168389535669268389（2）RSABC235168535268SRBCD356359683S TBCD356683596416TR 为空RT 为空TSDEI6693893.7 如果习题3.6中的三个关系R,S,T分别位于三个不同的站点X,Y,Z。若采用基于半连接算法计算连接R S T，请选择使得传输代价最小的连接执行的站点和确定半连接序列。解：假设每个属性域长度均为1B，考虑所有的半连接a) 选择得益最高的P2进行优化，得到新的R,S,T，并对受到影响的的方案重新计算得益和费用。新的R, S, T如下：对受到影响的的方案重新计算得益和费用b) 选择得益最高的P4进行优化，得到新的R,S,T，并对受到影响的方案重新计算得益和费用。 新的R, S, T如下：对受到影响的的方案重新计算得益和费用c) 选择得益最高的P1进行优化，得到新的R,S,T，并对受到影响的方案重新计算得益和费用。 新的R, S, T如下：对受到影响的的方案重新计算得益和费用d) 选择得益最高的P3进行优化，得到X,Y,Z站点上最终的R,S,T。 X,Y,Z站点上最终的R,S,T如下：所以选择各站点做连接的代价为： X站点代价=2*3+2*3=12 Y站点代价=4*3+2*3=18 Z站点代价=4*3+2*3=18故选择X站点作为收集站点代价最低。由简化过程得知半连接过程为：1. S = SR 2. 将S传送给T,做半连接TS得到T 3. 将S传送给R,做半连接RS得到R4. 将T传送给S,做半连接ST得到S即:(R(SR)(SR) (T(SR)(T(SR) 3.8 设某公司的雇员关系为employee(name,address,salary,plant-number)，按plant-number水平分片这个关系，每个片段都有两个副本：一个副本存放在New York站点，另一个副本存放在工厂的站点。请为在Toronto站点提出的下列查询设计一个好的处理策略。（1）找出Boce厂的所有雇员。（2）找出所有雇员的平均工资。（3）找出在如下每个站点工资最高的雇员姓名：Toronto，Edmonton，Vancouver，Montreal。（4）找出该公司中工资最低的雇员姓名1)将New York站点上的副本传至Toronto站点； 2)在New York站点上求平均工资，传至Toronto站点； 3)Toronto, Edmonton, Vancouver, Montreal求最高工资，传至Toronto汇总；3.9 考虑关系employee(eno,name,address,salary,plant-number)主码为eno，machine(machine-number,type,plant-number)主码为machine-number。假定关系employee按plant-number水平分片，且每个片段本地存放在它所对应的工厂站点；关系machine没有被分片，整个关系存放在Armonk站点（整个系统站点的个数等于工厂的个数+1），并且假定存放machine关系的Armonk站点就是提出查询和需要结果的站点。请为下列的查询设计一个好的处理策略：（1）找出生成机器号为1130的工厂的所有雇员的雇员号和姓名。（2）找出包含机器类型为milling machine的工厂的所有雇员的雇员号和姓名。（3）找出employee machine。（1）提出查询的站点：（1）Aromonk站点，plant-number=X的站点；（2）Aromonk站点，plant-number=Xi的站点；（3）各工厂站点 （2）需要结果的站点：（1）plant-number=X的站点，Aromonk站点；（2）plant-number=Xi的站点，Aromonk站点；（3）Aromonk站点4.1 概述分布式数据库系统中事务的定义、特性、结构和状态，以及分布式事务所特有的性质。分布式数据库系统中的事务是一个分布式操作的序列，被操作的数据分布在不同的站点上，所以称为分布式事务。 分布式事务 分布式数据库系统中的事务是一个分布式操作的序列，被操作的数据分布在不同的站点上，所以称为分布式事务。一个事务的执行可能涉及多个站点上的数据。事务也在多个站点上执行。 分布式事务是集中式事务的扩充，它的ACID特性的保证要比集中式事务复杂得多。因为有多个站点参与执行，其中任何一个站点的故障，或者将这些站点连接起来的任何一条通信链路的故障，都可能导致错误发生。 因此分布式事务的恢复要比集中式事务的恢复要复杂得多。分布式数据库系统中的事务具有ACID特性：原子性（Atomicity）:指事务执行时的不可分割性。即事务的操作要么全部执行, 要么全部不执行，保证分布式数据库一致性状态。一致性（Consistency）:指一个使分布式数据库从一个一致状态转变为另一个一致状态的正确程序。分布式事务执行完毕时，必须以正确的状态退出系统。如果事务不能达到一个正常的结束状态，就必须把分布式数据库退回到该事务执行前的初始状态。持久性（Durability）:指一旦某个事务被提交后，则无论系统发生任何故障，都不会丢失该事务的执行结果。也即，已提交事务对数据库的改变在数据库中应该是持续存在的，这些改变不会因为故障而发生丢失。 隔离性（ Isolation）:指一个正在执行的事务在其提交之前，决不允许把它对共享数据所作改变的结果提供给其他事务使用。也即事务的执行似乎与其他事务相隔离，事务的执行不应受到其他并发事务执行的干扰。虽然可以有多个事务同时执行，但是单个事务的执行不应该感知其他事务的存在，因此事务执行的中间结果应该对其他并发事务隐藏 。 在分布式数据库系统中，全局事务的主事务和子事务全部成功提交，才能改变数据库状态，有一个失败，其他子事务操作都要撤销。为了保证事务的原子性，要求组成这个分布式事务的各个子事务，要么全部提交(成功结束)，要么全部撤销(不成功结束)。如果至少有一个子事务执行失败，该分布式事务所包含的所有子事务，不管它的执行成功与否，一律都被撤销。各站点上的数据库全都回滚到相应子事务开始前的状态，从而使整个分布式数据库仍处于该分布式事务开始前的状态。只有当一个分布式事务所包含的所有子事务，都能成功执行，各站点上的数据库全都进入一个新的一致状态，才能使整个分布式数据库转换为新的一致状态。为保证分布式事务的ACID特性，更需要对各子事务进行协调和控制。结构：分布式数据库系统中事务的结构以begin transaction原语作为一个事务的开始，以commit原语作为一个事务成功完成的结束，而以rollback或abort原语作为事务失败的结束。状态：活动(active): 从事务开始执行的初始状态始， 事务执行中保持该状态。部分提交(partially committed): 事务的最后一个语句执行后进入该状态.失败(failed): 一旦发现事务不能正常执行时进入该状态.回滚/夭折(rollback/aborted): 当事务被回滚后，数据库恢复到事务开始执行前的状态。 提交(committed): 当事务成功执行后.分布式事务独有的特性：大量的数据传送、通信原语和控制报文等。4.2 请用自己的语言描述分布式事务管理的抽象模型和分布式事务执行的控制模型。务管理器与局部事物管理器之间不必要的数据传输。4.3 分布式数据库系统中的事务管理与集中式数据库系统中的事务管理有何不同？分布式与集中式相比，会多遇到一些问题：（1）处理数据项的多个副本；（2）单个站点的故障；（3）通信网络的故障；（4）分布式提交。4.4 什么是事务的提交点？为什么说它们很重要？当事务所有的站点数据库存取操作都已成功执行，并且所有操作对数据库的影响都已记录在日志中时，该事务就到达提交点。事务的提交点：当事务T所有的站点数据库存取操作都已成功执行，并且 所有操作对数据库的影响都已记录在日志中时，该事务就到达提交点。提交点后事务就成为已提交的事务，并假定其结果已永久记录在数据库中(事务的永久性)。事务在日志中写入提交记录commit，T。在系统发生故障时，需要扫描日志，检查那些已在日志中写入start_transaction，T，但没有写入commit，T的所有事务T。恢复时必须回滚这些事务以取消它们对数据库的影响。此外，还必须对日志中记录的已提交子事务的所有写操作进行恢复，这样它们对数据库的作用才可根据这些记录重做Redo。4.5 日志、档案库和检查点的作用是什么？典型的日志包含哪些内容？为什么要“先写日志”？日志的作用是为了能够从故障状态中恢复有影响的事务，系统维护一个 日志来保存所有影响数据库项的值的事务操作的信息，这些信息可以用于故障时的恢复。档案库的作用是为了防止因介质故障而破坏数据库，要定期将整个数据库的全部内容转储到档案库中去。存放数据库的档案存储设备称为数据库档案库(DB archive)检查点的作用是为了便于恢复，在日志中设定一种周期性(时间/容量)操作点，称为检查点，以标识检查点前已执行完的事务是正确的。典型的日志包含了每个改变数据项值的写操作记录。日志Log记录项 : start_transaction, T：表示事务T开始执行； write_item, T, x, 旧值, 新值：表示事务T已将数据项X的值从旧值改为新值。 read_item, T, x：表示事务T已读取数据项X的值。 commit, T：表示事务T已成功完成，其结果已被提交(永久记录) 给数据库。 abort, T：表示事务T已被撤销。 Log：记录长度及用于恢复过程的辅助信息，如指向本事务前一 日志记录的指针，检查点记录等。先写日志：因为系统崩溃时主存中的内容可能丢失，所以恢复时只能考虑已写回磁盘的日志内容。因此，在事务到达提交点以前，还未写到磁盘的日志的任何部分，必须被写入磁盘，即“先写日志”。4.6 列出分布式数据库系统中可能出现故障类型。哪些故障也可能出现在集中式数据库系统中？事务故障、系统故障、介质故障、站点故障、通信故障。事务故障、系统故障、介质故障也可能出现在集中式数据库系统中。4.7 请用自己的语言描述两阶段提交过程。 两阶段提交协议基本思想 将本地原子性提交行为的效果扩展到分布式事务, 保证了 分布式事务提交的原子性, 并在不损坏日志的情况下, 实现快速故障恢复, 提高DDB系统的可靠性。 两阶段提交协议把事务的提交过程分为两个阶段： 第一阶段：表决阶段，即形成一个共同的决定。 第二阶段：执行阶段，目的是实现这个决定 表决阶段 目的是形成一个共同的决定 首先，协调者在日志中写入一条开始提交记录，再给所有参与者发送“准备”消息，进入等待状态。 其次当参与者收到“准备”消息后，检查是否能够提交本地事务。 如能提交，参与者在日志中写入一条开始提交的记录，并给协调者发送“建议提交”消息，然后进入就绪状态； 否则，参与者写入撤销记录，并给协调者发送“建议撤销”消息。 如果某个站点作出“建议撤销”提议，由于撤销决定具有否决权(即单方面撤销)，该站点可以忽略这个事务。 第三，协调者收到所有参与者的消息后，他就做出是否提交事务的决定。 只要有一个参与者投了反对票(建议撤销)，协调者从整体上撤销整个事务，发送“全局撤销”消息给所有参与者，进入撤销状态； 否则，它写入提交记录，给所有参与者发送“全局提交”消息，然后进入提交状态。 执行阶段 实现表决阶段的决定，提交或者撤销。 根据协调者的指令，参与者或者提交事务，或者撤销事务，并给协调者发送确认消息。 协调者在日志中写入一条事务结束记录并终止事务。4.8 为什么说两阶段提交协议在不丢失运行日志信息的情况下，可以从从任何故障恢复？因为在执行过程中维护了事务日志，记录了执行恢复所需要的信息。4.9 在分布式数据库系统中对多副本数据的更新通常采用什么方法？快照方法的优点和缺点是什么？多站点数据更新法、主文本更新法、快照方法。快照方法的优缺点： 快照方法不考虑数据的辅助副本,只关心每一数据的主文本和在这些主文本上定义的任意多个快照。 快照与视图一样，可以定义为一个或多个主文本的部分拷贝或/和全部拷贝。 采用快照方法可以完成复杂的查询, 但又不阻止更新，因为其中数据被暂时“凝固”，不受更新操作的影响，所以不会妨碍其他事务对有关数据的更新操作。 为了与主文本保持同步，当主文本被更新时，需要刷新快照。 快照方法既避免了某些并发控制的开销，又便于复杂查询的完成，是提高系统可用性的有效方法。 快照是一个只读关系，其中数据只能读而不能写。即对查询操作可使用快照，也可使用主文本，对更新操作还是在主文本上进行。4.10 为什么说分布式事务增强了数据库的一致性？第五章51 为什么说分布式数据并发控制比集中并发控制要复杂得多？ 5.2 描述分布式事务的可串行化理论的一些定义:事务、冲突操作、并发调度、串行调度、一致性调度、两个调度等价、可串行化调度。 1.事务的定义一个事务是一个偏序集：Ti=i,i，其中：（1）i：操作符集合，包含Rix,Wix/x为数据项UAi,Ci，Ai,Ci是i中最后一个操作符，且只能出现其中之一个；Ai为撤销(abort),Ci为提交(commit)；i：排序关系，即(冲突)操作有先后次序执行。（2）如果Rix,Wixi，则它们必满足Ri(x)iWi(x)或Wi(x)iRi(x)。（3）Rix,Wix，Ai，Ci或公式的每一个都是事务Ti操作符序列中的一个操作。这是对事务的简单定义，实际上事务中还可能包含其他操作如封锁、通信原语等。 2. 冲突动作 如果有两个操作P和Q对同一个数据A进行操作，其中有一个是写操作W(A)，则 P和Q称为冲突操作。 一个调度事务的一个操作序列称为一个调度，一般用S表示。比如，S：R1(x), R2(y), W2(y), R2(x), W1(x), W2(x)3. 并发事务的一个调度(简称并发调度)定义令T= T1,T2,Tn 是一组并发执行事务。T上的调度 S 是具有如下顺序关系 T 的偏序集，即 S= T , T :(1) T = Ti (2) T i (3) 对任意两个冲突操作 p,q S, 存在 p q 或 q p关系。 第一种情况简单地说明了调度的域是每个事务域的并集。第二种情况定义排序关系为每个事务排序关系的超集，这保证了每一个事务内部的操作的顺序。最后一种情况定义了冲突操作的执行顺序。 4. 串行调度如果一个调度S中的任意两个事务Ti 和 Tj，i j，若i=1i j=1j 或者 j=1j i=1i 则称调度S为串行调度。即一个事务的第一个动作是在另一个事务的最后一个动作完成后开始。即一个调度中不同事务的各个操作不会互相交叉, 每个事务是相继 执行的。 5. 一致性调度如果执行一个调度S，可以使得数据库从一个一致性状态转变为 另一个一致性状态，则称调度S为一致性调度。显然，串行调度是一致性调度。 6.调度等价调度S1与S2是等价的充分条件是：对于两个有冲突的操作Oi和Oj, 若 Oi, OjS1, 且OiOj在S1中也成立, 则Oi, OjS2, 且也有OiOj 在S2中也成立。 7. 可串行化调度如果一个调度等价于某个串行调度，则该调度称为可串行化调度。也就是说，该调度可以通过一系列非冲突动作的交换操作使其成 为串行调度。5.5 什么是两阶段封锁协议？它如何保证可串行性？为什么人们经常更愿意采用严格两阶段封锁和严酷两阶段封锁？答：所谓两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁：1. 在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁。2. 在释放一个封锁之后，事务不再申请和获得任何其他封锁。因此保证可串行性。由于实现基本2PL协议要锁管理器必须要知道事务的锁点位置；保守2PL要事先声明续集和写集，这都是难以实现的。严格2PL和严酷2PL容易实现。严格2PL的实现方法是：事务在提交或者撤销之前，绝对不释放任何一个写锁；事务结束时（提交或者撤销），同时释放所有的锁。严酷2PL的实现方法是：事务T在提交或撤销之前，不能释放任何一个锁（写锁或者读锁），因此它比严格2PL更容易实现。 如果一个事务所有的封锁操作(读封锁和写封锁)都放在第一个解锁操作 之前，那么就说该事务遵守2PL协议。 事务的执行中Lock的管理分成两个阶段： 第一阶段是扩张阶段或成长阶段：事务只能获得新的数据项锁，而 不能释放任何已持有的锁。 第二阶段是收缩阶段或衰退阶段：事务只能释放已经持有的锁，而 不能获得任何的新锁。 一个很有名的理论Eswaran et al.,1976是：遵循了两段锁规则的并发控制算法锁产生的调度都是可串行化的。 可以证明，如果调度中的每个事务都遵守两阶段封锁协议，就可以 保证该调度是可串行化的，不再需要检测调度的可串行性。 实施两阶段封锁规则的封锁机制，也就实施了调度的可串行性。 两阶段封锁限制了一个调度中可以发生的并发事务的数量，原因： 如果事务T稍后必须封锁数据项Y，那么在它使用完数据项X之后， 获得数据项Y之前，不可以释放数据项X上的锁；或者，反过来说，事务T必须在它需要数据项Y上的锁之前就封锁Y。以便它可以释放 X上的锁。 因此，T 必须一直持有 X上的锁，直到该事务需要读或写的所有 数据项都被它自己封锁，然后T才可以释放X上的锁。同时，即使T 已经使用完X，另一个要访问X的事务也可能会被强制等待。 相反，如果事务T在需要数据项Y之前就封锁了它，那么即使T不是 正在使用数据项Y，其他想要访问Y的事务也被强制等待。这正是 不必检测调度本身就能保证所有调度可串行性的代价。5.6 描述死锁预防中的占先权方法和非占先权方法，比较它们的异同。描述检测分布式死锁的三种基本方法。答：等待-死亡模式(非占先权)的方法：如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年老时（TiTj），则Ti被终止并带有同一时间戳重新启动。这个方法的理论基础是：最好总是重新启动较年轻的事务，允许较年老的事务去等待已持有资源的较年轻的事务，但不允许较年轻的事务去等待较年老的事务。受伤-等待模式(占先权) 的方法是：如果Ti对已被Tj封锁的一数据项请求封锁的话，则只有在Ti比Tj年轻时（TiTj），才允许Ti等待。否则，Ti比Tj年老（TiTj），则Tj被终止并带有同一时间戳重新启动,而Ti得锁执行。这个方法的理论基础是：只有年轻的等待年老的。集中式死锁检测方法：选择一个站点负责整个系统的死锁检测,死锁检测器放到这个站点。每个站点的锁管理器周期性地将本站点的LWFG传送给死锁检测器, 死锁检测器构造GWFG, 并在其中寻找回路；或者，其它每个站点上的锁管理器周期性地把记录本站点上事务的开始时间，对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点，由它维护一张全局封锁动态表，形成GWFG, 并在其中寻找回路。如果至少包含一条回路，它会选择一个或者多个事务，把它们取消并恢复，释放资源，使得其它事务继续进行。选择的标准是尽可能使撤销并恢复的代价最小，如撤销年轻的事务，撤销占有较少资源的事务，撤销具有最短运行时间的事务，撤销具有最长运行时间的事务等，使系统情况而定。层次式死锁检测方法：树叶是各站点的局部死锁检测器，在本站点建立局部等待图。本站点的死锁检测器找出本站点局部等待图中的任何回路，并把有关潜在全局回路的信息发送给上一层死锁检测器。每个非本地死锁检测器只对它所涉及的紧挨下层进行死锁检测，合并这些接收到的有关潜在全局回路的信息，并找出任何回路。如果还有上层死锁检测器，将经过简化的有关潜在全局回路的信息发送给它上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路。这样，逐层检测，直到最高层。分布式死锁检测方法：使用局部信息建造LWFG, 该LWFG包含EX节点。对每次接收到的信息, 执行如下对LWFG的修改。对报文中的每个事务, 若LWFG中不存