1、1第一章 分布式数据库系统概述1.1 请用自己的语言定义下列分布式数据库系统中的术语：（1 ）局部数据: 只提供本站点的局部应用所需要的数据。全局数据：虽然物理上存储在个站点上，但是参与全局应用（2 ）全局/局部用户：局部用户： 一个用户或一个应用如果只访问他注册的那个站点上的数据称为本地或局部用户或本地应用；全局用户： 如果访问涉及两个或两个以上的站点中的数据，称为全局用户或全局应用。全局/局部 DBMS：1） LDBMS(Local DBMS)：局部场地上的数据库管理系统，其功能是建立和管理局部数据库，提供场地自治能力，执行局部应用及全局查询的子查询。（2 ） GDBMS(Global D
2、BMS)：全局数据库管理系统，主要功能是提供分布透明性，协调全局事物的执行，协调各局部 DBMS 以完成全局应用，保证数据库的全局一致性，执行并发控制，实现更新同步，提供全局恢复功能等。（3 ）全局外模式：全局应用的用户视图，也称全局视图。从一个由各局部数据库组成的逻辑集合中抽取，即全局外模式是全局概念式的子集。对全局用户而言，都可以认为在整个分布式数据库系统的各个站点上的所有数据库都如同在本站点上一样，只关心他们自己所使用的那部分数据（4 ）全局概念模式：描述分布式数据库中全局数据的逻辑结构和数据特性，是分布式数据库的全局概念视图。采用关系模型的全局概念模式由一组全局关系的定义(如关系名、关
3、系中的属性、每一属性的数据类型和长度等)和完整性定义 (关系的主键、外键及完整性其他约束条件等 )组成。（5 ）分片模式：描述全局数据的逻辑划分。每个全局关系可以通过选择和投影的关系操作被逻辑划分为若干片段。分片模式描述数据分片或定义片段，以及全局关系与片段之间的映像。这种映像是一对多的。（6 ）分配模式：根据选定的数据分布策略，定义各片段的物理存放站点，即定义片段映像的类型，确定分布式数据库是冗余的还是非冗余的，以及冗余的程度。如果一个片段分配在多个站点上，则片段的映像是一对多的，分布式数据库是冗余的，否则是不冗余的。（7 ）局部概念模式：是全局概念模式的子集。全局概念模式经逻辑划分成一个或
4、多个逻辑片段，每个逻辑片段被分配在一个或多个站点上，称为该逻辑片段在某个站点上的物理映像或称物理片段。对每个站点来说，在该站点上全部物理映像的集合称为该站点上的局部概念模式。或者说，一个站点上的局部概念模式是该站点上所有全局关系模式在该站点上物理映像的集合。（8 ）局部内模式：是分布式数据库中关于物理数据库的描述，描述的内容不仅包含局部本站点的数据的存储描述，还包括全局数据在本站点的存储描述。1.4 什么是分布式数据库系统？它具有哪些主要特点？怎么样区别分布式数据库系统与只提供远程数据访问功能的网络数据库系统？（分布式数据库系统的定义、特点详见课件第 1 章 4.1.课本 P6）分布式数据库系
5、统：物理上分散而逻辑上集中的系统，它使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通常是集中式数据库系统）连接起来，共同组成一个统一的数据库系统。分布式数据库系统可以看成是计算机网络和数据库系统的有机结合。特点：物理分布性、逻辑整体性、站点自治性、数据分布透明性、集中与自治相结合的控制机制、存在适当的数据冗余度、事务管理的分布性。1.6 用自己的语言解析“什么时候需要进行数据分片和数据复制”？（课本第 10,11 页）数据分片又称数据分割、数据分段，局部数据库是由全局数据库分割而成；全局数据库 是由各个局部数据库逻辑组合而成。一个关系描述了某些数据之间的逻辑相关性，
6、不同站点的用户需要该关系中的元组可能不同，需要对这个关系进行分割，并将 分割后得到的各部分元组，称为该关系的逻辑片段，存放在相应的站点上。这样 处理各得其所，可以减少网络上的通信，提高系统的相应效率。数据复制指分布式数据库中的数据根据需要将数据划分成逻辑片段，按某种策略把数据 分片所得的逻辑片段分散地存储在各个站点上。全局数据有多个副本，每个站点都有一个完整的数据副本。系统可靠性高，2响应速度快，数据库恢复也较容易。但要保持各个站点上数据的同步修改，将要付出高昂的代价。1.7 在分布式数据库系统中，为什么要对数据进行分片？什么是关系的片段？关系的片段有哪些主要类型？（课本第 9-10 页。数据
7、分片又称数据分割、数据分段，局部数据库是由全局数据库分割而成；全局数据库 是由各个局部数据库逻辑组合而成。一个关系描述了某些数据之间的逻辑相关性，不同站点的用户需要该关系中的元组可能不同，需要对这个关系进行分割，并将 分割后得到的各部分元组，称为该关系的逻辑片段，存放在相应的站点上。这样 处理各得其所，可以减少网络上的通信，提高系统的相应效率。数据分片是指数据存放单位不是全部关系，而是关系的一个片段。也就是关系的一部分。包括： （1）水平分片：按一定的条件把全局关系的所有元组划分成若干不相交的子集，每个子集为关系的一个片段。 （2）垂直分片：把一个全局关系的属性集分成若干子集，并在这些子集上做
8、投影运算，每个投影为垂直分片。 （3）混合型分片：将水平分片与垂直分片方式综合使用则为混合型分片。 ）1.8 为什么说分布式数据库系统中，数据独立性这一目标比集中式数据库系统更为重要，也更为复杂？（详见课本第 25 页第二段）1.9 概述分布式 DBMS 的参考模型中，用户处理器、数据处理器、全局数据库控制和通信子系统的组成和功能。 （组成（参考模型）：详见课件 5.6；功能：用户处理器课本第 18 页；数据处理器课本第 20 页；全局数据库控制和通信子系统课本第 21 页）用户处理器：用户结果格式化器用户命令翻译器约束实施器用户结果用户命令规范化数据规范化命令外部模式概念模式规范化命令用户处
9、理器用户处理器的功能一是它把数据操纵语言中的用户命令，翻译成规范化命令。 ；二是它把来自数据处理器3的数据，翻译成用户理解的格式。数据处理器：数据处理器负责存取数据库的数据，数据处理器的组成主要包括：规范化命令翻译器、规范化结果格式器和运行时支持处理器。全局数据库控制和通信子系统的组成和功能：全局数据库控制和通信子系统负责通信和控制分布式的执行。由多个处理器组成：1. 分解器：分解器由一个或几个数据处理器组成，主要任务是把来自用户处理器的请求，翻译成一个由若干命令组成的分布式执行策略。2. 合并器：它的任务是在提交给用户处理器之前，把分布式执行策略访问不同站点所得到的结果数据组合起来。3. 分
10、布式执行监视器：负责分布式执行策略的正确执行以及保证分布式环境中事务的原子性。同时还负责提供复制独立性和分布式并发控制。4. 通信子系统：提供站点之间的信息传送。每个站点都有一个通信处理器，与此通信子系统相接口。通信处理器使用一组通信协议来正确利用通信设施和为分布系统提供无错的和可靠的通信。5. 本地执行监视器：负责在本地数据处理器中，执行该分布式执行策略中与本站点有关的部分。当执行策略的某一部分在该数据处理器中完成执行，或出现故障时，就由它来通知全局执行监视器。1.10 分布式数据库系统潜在的优点是什么？存在哪些技术问题？（优点：详见课本第 34-35 页共 6 点；技术问题详见课本第 35
11、-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 概述分布式数据库系统的创建方法、
12、方法特点和适用范围答：创建方法有：组合法、重构法组合法的特点：剖析网络功能；剖析原有数据库系统；解决数据的一致性、完整性和可靠性；难度较大；组合法适用范围：通常是异构或者同构异质 DDBS重构法的特点：根据实现环境和用户需求；按照 DDBS 的设计思想和方法；从总体设计做起，包括LDBS,重新建立一个 DDBS；可有效解决数据一致性、完整性和可靠性问题。重构法的适用范围：通常是同构异质或同构同质 DDBS2.2 分布式数据库设计的主要目标是什么?1. 目标一：分布式数据库的本地性或近地性2. 目标二：控制数据适当冗余43. 目标三：工作负荷分布4. 目标四：存储的能力和费用2.3 概述分布式数
13、据库设计的关键问题及解决方法答：关键问题：1）数据的实际分布情况。访问的多个数据对象是存放在同一站点上还是分布在多个站点所需的时间和费用有很大区别。2）数据对否被复制、复制副本的多少问题3）数据分片、片段如何复制、数据或片段如何分布、分布式数据库管理系统的透明性解决方法：1）分布式数据库遵循本地性或近地性，尽量减少通信次数和通信量，90/10 准则，分片和分布方案（本地和远程访问次数）择优；90%的数据应当在本地站点找到，而只有 10%的数据需要在远程站点上进行访问。也即最有效的设计是确保数据对最大数目的应用具有本地性。可以采用的设计方法是对每一种可供选择的分片方法和片段的分配方法都统计出本地
14、访问和远程访问的次数，然后从其中选择一个最佳的方案。2）控制数据适当冗余，冗余增加了可靠性、可用性，提高了效率，维护数据一致性开销增加。在分布式数据库系统中，为了提高系统的本地性、并发度和可靠性，需要增加数据的副本。这不仅使应用具有高度的可用性和本地性，而且当数据的任何一个副本不能使用时，可方便地使用在另一站点中的该数据的副本进行恢复，从而提高系统的可靠性。3）工作负荷分布分布式计算机系统的一个重要特征是把工作负荷分布在网络中的各个站点上。分布工作负荷的目的是充分利用每个站点计算机的能力和资源，以提高应用执行的平行程度，从而提高系统的性能。4）存储能力和费用数据库的分布会受到各站点的存储能力的
15、影响。在网络中可以有专门用于存储数据的站点，也可以有完全不支持大容量存储的站点。一般，数据存储的费用与 CPU，I /O 及传输的费用相比是不重要的，但是必须考虑各站点可用存储空间的限制。2.4 考虑为局域网设计的分布式数据库系统和为广域网设计的分布式数据库系统由什么区别?这道不会，参考 p42 1.分布式数据库的本地性或近地性2.5 请用自己的语音阐述分布式数据库设计的自顶向下和自底向上设计方法及其适用范围。5答: 自顶向下：(1) 从概念设计到形成形式规格说明设计分布式数据库。从头开始设计分布式数据库。该方法假定设计者理解用户的数据库应用要求，历经概念设计、逻辑 设计和物理设计阶段，并将与
16、计算机系统无关的规格说明逐渐求精成 低级的、与计算机系统有关的规格说明。概念设计和逻辑设计的结果 是数据库的全局模式，包含了数据库的所有数据元素及其使用形式。 专门针对分布式数据库的一个设计阶段称为分布设计，将全局模式映 射成几个可能交叠的子集模式，每一个子模式表示与一个站点有关的 信息子集，然后完成每一单个数据库的设计。(2) 适用范围：通常是同构异质或同构同质 DDBS。自底向上： (1)通过聚集现存数据库设计分布式数据库。假定由于需要互联一些现存数据库以形成一个多数据库系统，或由于对各站点已独立完成了数据库的概念说明，所以各站点上数据库的规格说明已是现存的。需要综合各站点的规格说明，以便
17、得到分布式数据库的全局概念模式。(2)适用范围：通常是异构或者同构异质 DDBS。2.6 数据分片应遵守哪些原则?数据分片要准守的原则：完备性原则：要把所有的数据映射到各个片断中可重构原则：关系分片后的各个片断可重构整个关系不相交原则：关系分片后的各个片断不能重叠数据分片有哪些基本类型和方法?有两种基本的数据分片方法：水平分片方法和垂直分片方法。通过交替水平分片与垂直分片，可以产生混合分片。水平分片 水平分片是对全局关系执行“选择”操作，把具有相同性质的元组进行分组，构成若干个不相交的子集。水平分片的方法可归为初级分片和导出分片两类。垂直分片和垂直群集 一个全局关系的垂直分片是通过“投影”操作
18、把它的属性分成若干组。根据应用以“同样方式”(具有相同的使用频率)访问的属性来进行分组。垂直分片的组必须只在某个键属性上重叠，其他属性不可重叠；垂直群集的组在其他属性上也可以重叠。 2.7 为什么说在关系型分布式数据库中使用导出式水平分片，使关系之间的连接变得更加容易？试举例。答：原因：全局关系的导出式水平分片不是以其自身的属性性质为基础，而是从另一个关系的属性性质或水平片段推导出来的。 确定一方便的导出式水平分片要求确定应用所执行的最重要的结合操作。导出分片可使片段与片段间“连接” 变得更容易。可将连接条件代之以子查询，从而使它变为一般的判别条件。具体实例： 例 2.3 设全局关系SC( S
19、#, 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, SWhere SC.S#=S.S# and SEX=MDefine fragment SC2 as （ Define fragment SF as ）6Select SC.S#, C#, GRADE
20、From SC, SWhere 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 asSelect * From SC Where S# in (Select SM.S from SM)2.8 采用 DATAID-D 方法的分布式数据库设计与传统的集中式数据库设计在步骤和内容上有什么不同？分布要求分析
21、设计位于概念设计阶段之后进行，主要工作：1. 收集用户分布要求信息2. 水平分片的划分谓词3. 每一应用在各站点激活的频率分布设计全局逻辑设计之后进行，主要工作：1. 分布要求和全局逻辑模式作为输入2. 形式为全局数据库模式和逻辑访问表3. 输出为分片模式和分配模式第三章3.1 用自己的语言概述分布式查询优化与集中式查询优化的异同。分布式查询和集中式查询的相同点即在本地的 CPU 和 I/O 代价，不同点为分布式查询比集中式查询多了通讯代价73.2 试述分布式查询优化的层次结构。分布式查询处理按不同层次结构执行，符合分布式 DBMS 的体系结构。分布式查询处理可分为四个层次。 查询分解 将查询
22、问题（SQL）转换成一个定义在全局关系上的关系代数表达式。 本层转换所需要从全局概念模式中获得。 数据本地化 把一个在全局关系上的查询具体化，落实到合适的(使尽可能做到本地化或近地化)片段上的查询。即将全局关系的关系代数表达式变换为相应片段上的关系代数表达式。 这一变换所需要的信息在分片模式和片段的分配模式中 获得。 全局优化 输入的是分片查询，查询优化目标是寻找一个近于最优 的执行策略。 全局优化即是找出分片查询的最佳操作次序，使得代价函数最小。代价函数一般是I/O、CPU 和通信代价之和。 全局优化的一个重要方面是关于连接操作的优化。全局 优化处理层输出是一个优化的、片段上的关系代数查询。
23、 局部优化 局部查询优化由拥有与查询有关的片段的各个站点执行。在每个站点上执行的子查询被称为局部查询。它由该站 点上的 DBMS 进行优化，采用集中式数据库系统中查询 优化的算法。所需信息取自局部模式。83.3 概括基于关系代数等价变换的查询优化算法的基本原理与实现步骤。 基本原理1. 把查询问题转化为关系代数表达式；2. 分析得到查询树；3. 进行全局到片段的变换得到基于片段的查询树；4. 利用关系代数等价变换规则的优化算法，尽可能先执行 选择和投影操作，后执行连接和合并操作；5. 对该查询树进行优化，从而达到查询优化的目的。 优化算法1. 连接操作和合并操作尽可能上提（树根方向） ；2.
24、选择操作和投影操作尽可能下移（叶子方向） ；3. 尽可能先执行选择和投影操作，后执行连接和合并操作。4. 经过选择和投影操作不但可以减少其后操作量，还可以 减少操作次数。 实现步骤和方法 将一个查询问题转换成关系代数表达式。 从关系代数表达式到查询树的变换：对一个关系 代数表达式进行语法分析，可以得到一棵语法树 (或查询树)，即查询树根节点是最终的查询结果，叶子节点是查询涉及的9所有关系或片段，中间节 点是按关系代数表达式中的操作顺序组成的一组 关系操作符。 从全局查询到片段查询的变换：把基于全局关系 的查询树中的全局关系名，用其重构该全局关系 的各个片段名替换，变换成相应片段上的查询树。 利
25、用关系代数等价变换规则优化算法，对片段的 查询树进行优化处理，最后达到优化查询目的。3.4 概述基于半连接算法查询优化的基本原理和适用情形。基本原理：p84p85 适用情形： p85，由此可见那段，第四行的“所以。”开头3.5 概述基于直接连接算法查询优化的基本原理和适用情形。10另一种是自然连接。自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重复的属性去掉。 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 D2 3 5 3 5 6 3 5 65 3 6 3 5 9 3 5 91 6 8 6 8 3 6 8 33 4 6 5 9 6 5 9 65 3 5 4 1 6 4 1 62 6 8 5 8 4 5 8 46、（1）RSTA B C D E I2 3 5 6 6 91 6 8 3 8 95 3 5 6 6 92 6 8 3 8 9（2 ） RSA B C2 3 51 6 85 3 52 6 8SRB C D3 5 63 5 9
