DDBS期末复习.doc

DDBS课程期末复习提纲单选题 填空题 综合题 第一章1、 什么是DDB、DDBS、DDBMS？ DDS: 数据库系统 DDBS:分布式数据库系统 DDBMS：分布式数据库管理系统2、 理解局部应用和全局应用 访问本地银行数据：局部应用 通兑业务、转账业务：全局应用DB1DB1DB1计算机1计算机1计算机1通讯网络北京重庆上海银行系统访问本地银行数据：局部应用通兑业务、转账业务：全局应用3、 DDBS分哪三类？如何区分这三类？同构同质型DDBS：各个场地都采用同一类型的数据模型（譬如都是关系型）， 并且是同一型号的DBMS。同构异质型DDBS：各个场地采用同一类型的数据模型，但是DBMS的型号不同，譬如DB2、ORACLE、SYBASE、SQL Server等。异构型DDBS：各个场地的数据模型的型号不同，甚至类型也不同。随着计算机网络技术的发展，异种机联网问题已经得到较好的解决，此时依靠异构型DDBS就能存取全网中各种异构局部库中的数据。4、 什么是GDD、LDD？ 全局数据字典（GDD）：提供全局数据的描述和管理的相关信息，如数据的结构定义，分片、分布处理、授权、事务恢复等必要信息。 局部数据字典（LDD）：提供局部数据的描述和管理的相关信息5、 数据分片有哪三类？（1）水平分片：按一定的条件把全局关系的所有元组划分成若干不相交的子集，每个子集为关系的一个片段。（2）垂直分片：把一个全局关系的属性集分成若干子集，并在这些子集上作投影运算，每个投影称为垂直分片。（3）混合分片：以上两种方法的混合。可以先水平分片再垂直分片，或先垂直分片再水平分片，或其他形式，但他们的结果是不相同的。6、 数据分布有哪四种方式？（1）集中式：所有数据片段都安排在同一个场地上。（2）分割式：所有数据只有一份，它被分割成若干逻辑片段，每个逻辑片段被指派在一个特定的场地上。（3）全复制式：数据在每个场地重复存储。也就是每个场地上都有一个完整的数据副本。（4）混合式：这是一种介乎于分割式和全复制式之间的分配方式。7、 什么是数据透明性？ 数据透明性：分布式数据库系统的用户不必知晓有关数据如何存储以及存储在哪里的细节的程度。8、 DDBS的优缺点分别是？ DDBS的优点：具有灵活的体系结构；适应分布式的管理和控制机构；经济性能优越；系统的可靠性高、可用性好；局部应用的响应速度快；可扩展性好，易于集成现有的系统。DDBS的缺点：系统开销较大，主要花在通信部分 ；复杂的存取结构（如辅助索引、文件的链接技术），在集中式DBS中是有效存取数据的重要技术，但在分布式系统中不一定有效；数据的安全性和保密性较难处理。第二章1、 DDBS的设计方法有哪两种？ “从上至下”重构法和“从下至上”组合法2、 分布式数据库系统的设计目标有哪些？1) 本地性和近地性 2) 控制数据的适当冗余3) 工作负荷分布4) 存储的能力和费用3、 分片、分段、分配（分布）分别指什么？“分片”是指：将全局对象分解成为数据片段的过程；“片段”是指：分配和存储的逻辑单位。“分配”是指：将分片好的片段映射到一个或者多个站点的过程。4、 分片准则是什么？（设R=R1，R2，R3，Rn）1.完整性如果某个数据aR，则必有a Ri，i=1,2,3 n2.可重构条件R=Ri（水平分片）或者R= Ri（垂直分片）3.不相交条件Ri Rj= 空集，ij，i，j=1,2,.ij . n（水平分片）Ri Rj=主键属性 i，j=1,2,.ij . n （垂直分片）5、 水平分片分哪两类？它们之间有何不同？ 分成为初级水平分片和导出水平分片两种类型。1）初级水平分片 执行选择操作，将关系分片成为若干不相交的片段。例子1：设s(sno,sname,sex,age)按照性别进行分片；Select * from s where sex=M（校验分片的基本原则）2）导出分片全局关系的导出式水平分片不是以其自身的属性性质为基础的，而是从另一个关系的属性性质或水平片段推导出来的。6、 如何理解“最小的”和“完整的”（见例题PPT16）？ 设s(sno,sname,sex,age,sdept,sage,blood)如果分片的方式是： blood=A,B,O,AB，sex=M,F假定经常查询的内容是：血型是B型的男同学。请列举1、不完整的片段，写出查询语句，并说明原因。2、完整的、最小的片段，写出查询语句，并说明原因。3、完整的但不是最小的片段，写出查询语句，并说明原因。Select * from s where sex=M 就是不完整的。应用仅仅查询B型成分，B型的查询概率必然大于其他血型的概率；Select * from s where sex=M and blood=B 这是正确的并且是完整的；按照这个分片逻辑就可以分成为8个片段:男同学对应4种血型，女同学对应4种血型，它们是互斥且不相交的；对于这8个片段，每一片段中的任意两个元组被访问的频率是相同的。Select * from s where sex=M and blood=B and age20 是完整的，但是不是最小的，因为age20与应用无关。7、两个案例案例：（1）某路桥工程公司因拓展业务在北京设立总部，上海和广州设立分公司；即共有3个计算机站点。图形见下。基本的全局关系表为：员工表（员工编号，姓名，性别，生日，家庭住址，部门编号，部门编号，加入公司时间，薪水）部门表（部门编号，部门所在地编号，经理执行时间，部门名称）部门所在地表（部门所在地编号，地理名称）项目表（项目编号，项目名称，项目所在地，所属部门编号）工作考核表（员工编号，项目编号，工作时间）员工职务表（员工编号，部门编号，开始职务时间，终止职务时间，职务，终止职务原因）（2）连锁百货商店具有地域上分散而管理上面集中的特点，往往既要有各个门店的局部控制和分散管理，同时也要有各个组织的全局控制和高层管理，因此需要将这些门店和中央总部通过计算机网络连接起来，组成分布式的数据库系统。根据下面关于连锁百货商店主要信息的需求分析结果，确定为该连锁百货商店设计的分布式数据库分析的解决方案。需求分析如下：1、一个公司总部，多个分布在全国的加盟公司组成。连锁公司各个部门之间交换的数据通过广域网进行连接，各个连锁公司在业务上面独立开展，分别独立开展本公司的具体业务。2、由公司总部负责产生并管理连锁百货公司的整体汇总数据，即各个分公司的明细帐目总表数据表，汇总数据表。3、总部为方便对业务的管理以及比较各个连锁公司的运营和效益情况，要求连锁店将相应的商品归入对应的业务种类和品牌，由总店统一管理并指定连锁商店进行销售。因此，各个加盟商店的销售业务种类和品牌是不能够自行设定的。4、我们通过调研，得到一些加盟商店的数据报表资料如下： 应商表（供应商编号，名称，经营类别）；合同表（合同编号，甲方名称，乙方名称，合同内容，开始时间，截止时间）；商品表（商品编号，名称，业务编号，品牌标号，进货价格，折扣信息）；销售表（销售流水号，供应商编号，商品编号，数量，日期，经手人）；5、整个连锁店的员工信息由总公司负责管理，分公司可以查询本公司员工信息。6、该连锁公司实行会员卡制度进行全国联网消费，会员可以进行异地消费和获取相应的折扣。门店信息（门店编号，所在地，面积）职员信息（职工号，姓名，性别，生日，家庭住址，所属门店）供应商信息（供应商号，公司名称，联系人，电话，所属门店）合同信息（合同号，商品编号，供应商号，数量）商品信息（商品编号，商品名称，单价，所属品牌，所属业种，所属门店）销售信息（销售编号，商品编号，数量，金额，日期）销售汇总（门店编号，总金额）会员信息（会员号，姓名，性别，生日，家庭住址，电话）会员消费明细（消费编号，会员号，商品编号，数量，金额，日期）品牌信息（品牌编号，品牌名称）业种信息（业种编号，业种名称）1、对所有全局关系表分别讨论是否需要分片，如需分片请说明以哪个字段为分片条件，以及分片类型如：门店信息：无需分片职员信息：按“A”字段进行初级分片合同信息：按“B”字段联接“职员信息”表的相应分段进行导出分片2、阐述各站点上各个关系表和分段的分布情况如：总店：门店信息、职员信息、分店1：供应商信息1、分店2：供应商信息2、第三章1、 查询优化的准则涉及哪些方面的内容？在分布式查询处理中这些内容孰轻孰重？ 总代价I/O代价CPU代价通信代价 在基于远程通信网的分布式数据库系统的查询处理中，查询的局部处理时间与通信所需时间相比可以忽略不计，即以减少传输次数和数据量作为优化的重要目标。（熟轻熟重）传送时间T=总传输延迟+总数据量/传输速度P71例3.1数据在网络中传输，如果都以整个关系传输，显然是一种冗余。不参与联接的值或无用的值不必在网络中来回传输。2、 分布式查询分哪三类？ 局部查询：只涉及本地、单个站点上的数据，与集中式数据库查询的优化技术相同远程查询：只涉及单个站点上的数据，尽可能选择最近的站点全局查询：涉及多个站点上的数据3、 全局查询的四项工作是？1) 具体化：副本的选择2) 操作执行的次序：连接操作与并操作3) 操作执行的方法：连接方法4) 执行站点：就近、空闲4、 一道例题、一道作业 （例题）设某公司的雇员关系为employee(eno,name,address,salary,plant-number)，按plant-number水平分片这个关系，每个片段有两个副本：一个副本存放在New York站点，另一个副本存放在工厂站点。请为在Toronto站点提出的下列查询设计一个好的处理策略1、找出Boce厂的所有雇员（假设Boce 站点邻近Toronto站点）2、找出所有雇员的平均工资3、找出在如下每个站点工资最高的雇员姓名：Toronto,Edmonton,Vancouver,Montreal4、找出该公司中工资最低的雇员姓名注：取平均值的函数avg()，取最大值的函数max()，取最小值的函数min()1、将Boce站点上的employee片段副本传送到Toronto站点，呈现给用户2、 1）在New York站点的employee关系上使用函数avg()取得平均工资X 2）将X传送到Toronto站点，呈现给用户3、 1）分别在Toronto,Edmonton,Vancouver,Montreal这四个站点的employee片段副本上使用函数max()取得最高工资X1,X2,X3,X4 2）在四个站点上分别投影出最高工资X1,X2,X3,X4所对应的雇员姓名Y1,Y2,Y3,Y4 3）分别将Y2,Y3,Y4传送到Toronto站点 4）最后在Toronto站点将Y1,Y2,Y3,Y4执行并操作，得到最后结果呈现给用户4、 1）在New York站点的employee关系上使用函数min()取得最低工资X 2）在employee关系上投影出最低工资X所对应的雇员姓名Y 3）将Y传送到Toronto站点，呈现给用户（作业）关系：employee(eno,name,address,salary,plant-number)主码为eno，关系： machine(machine-number,type,plant-number)主码为machint-number假定关系employee按plant-number水平分片，且每个片段本地存放在它所对应的工厂站点；关系machine没有被分片， 整个关系存放在A站点（整个系统站点的个数等于工厂的个数+1），B是该系统中的子站点，同时B是提出查询和需要结果的站点。1、找出B站点所生产的所有机器的机器号和机器类型。2、找出该工厂所有员工的平均工资1、 1）先在B站点找出plant-number的值，设为X 2）将X传送到存放machine关系的A站点，根据plant-number=X对machine关系进行投影，得到machine-number和type 3）把结果传送到B站点，呈现给用户2、 1）除B站点外的各个工厂站点把存放在该站点上的employee关系的片段传送到B站点 2）在B站点上执行并操作，重构employee关系 3）在重构后的employee关系上使用函数avg()取得平均工资，呈现给用户第四章1、 什么是事务？1 事务是访问或更新各种数据项的最小逻辑工作单位。2 它是一个操作序列3 它可以使数据库从一个一致状态到另外一个一致状态4 事务必须保证数据库的一致性5 事务执行期间数据库可能不一致2、 分布式事务的四个特性是？举例PPT8-PPT11 原子性（Atomicity） 事务的操作要么全部执行, 要么全部不执行 ,保证数据库一致性状态 一致性（Consistency） 事务的正确性，串行性，并发执行的多个事务,其操作的结果应与以某种顺序串行执行这几个事务所得的结果相同. 持久性（Durability） 当事务提交后, 其操作的结果将永久化, 而与提交后发生的故障无关 隔离性（ Isolation） 虽然可以有多个事务同时执行，但是单个事务的执行不应该感知其他事务的存在，因此事务执行的中间结果应该对其他并发事务隐藏 此外，分布式数据库系统中还要考虑数据传送、通信原语和控制报文等。举例:从账号A向账号B转账 $50: 1. read(A) 2. A := A 50 3. write(A) 4. read(B) 5. B := B + 50 6. write(B)一致性要求: 事务执行后A 和 B账号的总金额不变原子性要求: 如果事物在第3步和第6步之间故障, 系统应该保证事务对数据库的修改没有产生,否则将导致不一致性持久性要求: 一旦用户通知说事务已经完成（即$50 转账成功），那么由该事务对数据库的修改就必须保证是永久的，即使是发生故障也如此独立性要求 如果在第 3步和第6步之间, 允许其他事务访问被修改的数据库的中间结果, 那么它将见到一个不一致的数据库 3、 分布式事务的一般结构 Begin Transaction原语：开始一个事务 T1 T2 : 子事务或操作序列 : Tn Commit原语：事务成功完成的结束 Rollback或Abort原语：事务失败的结束4、 什么是进程、总代理（根代理）、事务代理？进程：系统中可以并行执行的一段操作序列，分布式事务中的子事务序列是进程方式完成的 -进程说明：定义进程的行为模式，数据和数据上的操作，功能等 -进行执行：按模式来启动这个进程，执行其中的操作过程：不可并行执行的操作序列 P100事务代理（Agent）：应用在各个Site上执行的若干进程，称作应用在该Site上的代理。代理可以执行应用程序员写的程序，也可以执行系统的原语函数，不同代理间通过报文实现通讯根代理（Root Agent） 应用启动Site上的代理。根代理所在的Site称作原发Site. 一般，根代理负责发系统原语，只有根代理可以请求创建新代理。5、 什么是DTM、LTM？功能有哪些？ DTM:分布式事务管理器 LTM:本地事务管理器DTM功能 1) 保证分布式事务ACID特性l 特别是原子性，使每一站点的子事务都成功执行，或者都不执行。l 通过向各站点发begin-transaction,commit或者abort,create原语来实现的2) 负责协调由该站点发出的所有分布式事务的执行启动分布式事务的执行将分布式事务分解为子事务，并将其分派到恰当的站点上执行决定分布式事务的终止（子事务都提交或者都撤销）3) 支持分布式事务执行位置透明性实现了对网络上各站点的各子事务的监督和管理完成对整个分布式事务执行过程的调度和管理保证分布式数据库系统的高效率LTM功能1 保证本地事务的ACID特性2 维护一个用于恢复的日志，代替DTM把分布事务的执行与恢复信息记入日志3 参与适当的并发控制模式，以协调在该站点上执行的事务的并发执行。接收并遵从本Site上DTM发来的Log原语，记入Log并执行之6、 站点故障有哪三类？ 事务故障；系统故障；介质故障7、 什么是提交点？检查点？事务的提交点：1) 当事务T所有的站点数据库存取操作都已成功执行；2) 所有操作对数据库的影响都已记录在日志中。到达提交点3) 提交点后事务就成为已提交的事务，并假定其结果以永久记录在数据库中4) 事务在日志中写入提交记录commit,T5) 在系统发生故障时，需要扫描日志，检查日志中写入start_transaction,T,但没有写入commit,T的所有事务T6) 恢复时必须回滚这些事务以取消他们对数据库的影响7) 此外，还必须对日志中记录的已提交子事务的所有写操作进行恢复。检查点（Checkpoint）设置一个周期性（时间/容量）操作点a) Log Buffer内容写入Log数据集b) 写检查点Log信息：当前活动事务表, 每个事务最近一次Log记录在Log文件中的位置c) DB Buffer内容写入DBd) 将本次检查点Log项在Log文件中的地址记入“重启动文件”8、 理解两阶段提交协议PPT52 9、一道作业假设两个事务T 和 U 的 log 记录如下所示: , 如果系统故障时, 磁盘上最后记录的Log记录如下, 请描述数据库恢复管理器的动作. 1) 2) 3) 4) 答：1) undo T ,undo U, A还原为初始值 2) undo T ,redo U, A、C还原为初始值,B的取值为20，D的取值为40 3) undo T ,redo U, A、C、E还原为初始值,B的取值为20，D的取值为40 4)redo T, redo U, A的取值为10，B的取值为20，C的取值为30，D的取值为40,E的取值为50第五章1、 什么是冲突动作？调度？ 冲突动作 R1(A) W2(A) W1(A) W2(A) R1(A) W2(A)事务的一个操作序列称为一个调度，一般用S表示比如，S: R1(x),R2(y),W2(y),R2(x),W1(x),W2(x)调度：1) 事务的调度必须包含这些事务的所有操作2) 调度中某个事务的操作顺序必须保持与该事务原有的顺序相同2、 什么是串行化调度？一致性调度？调度等价？可串行化调度？串行调度:个事务的第一个动作是在另一个事务的最后一个动作完成后开始. 即调度中事务的各个操作不会交叉, 每个事务相继执行.一致性调度：度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度调度等价:S1与S2等价, 也就是说, 对于冲突操作, , Oi Oj在S1中成立, 同时 Oi Oj 在S2中也成立可串行化调度1) 如果一个调度等价于某个串行调度，则该调度称为可串行化调度。2) 也就是说，该调度可以通过一系列非冲突动作的交换操作使其成为串行调度3、 区分的调度，一道例题。 五种调度：S1=R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1, R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2S2=R1(x),x=x+10,W1(x), R2(x),x=x-20,W2(x), R1(y),y=y-15,W1(y),C1, R2(y),y=y*2,W2(y),C2S3=R1(x),x=x+10,W1(x), R2(x), x=x-20,W2(x),R2(y),y=y*2,W2(y),C2 ,R1(y),y=y-15,W1(y),C1S4=R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2 ,R1(x),x=x+10,W1(x),R1(y),y=y-15,W1(y),C1S5=R2(x),x=x-20,W2(x), R1(x),x=x+10,W1(x), R2(y),y=y*2,W2(y),C2 ,R1(y),y=y-15,W1(y),C1如果将事务提交延迟到两个事务操作完成之后执行，有：1) 调度S1和S4是串行调度2) 调度S2和S1的冲突操作具有相同的顺序，因此是等价调度；S2是可串行化调度，也是一致性调度3) 调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度4) 调度S5和S4等价，所以S5是一致调度，也是可串行化调度有以下推论：一个可串行化调度必定与某个串行调度等价，且是一致性调度一致性调度不一定是可串行化调度同一事务集几个可串行化调度，他们的结果未必相同4、 用优先图判断可串行化调度，一道例题，一道作业。 考虑如下3个事务： T1: Read(x); Write(x); Commit; T2: Write(x); Write(y); Read(z); Commit; T3: Read(x); Read(y); Read(z); Commit; 这3个事务的一个调度：S=W2(x),W2(y),R2(z),C2,R1(x),W1(x),C1,R3(x),R3(y),R3(z),C3 优先图： 无环， S是串行调度。另外一个调度S:S=W2(x), R1(x),W1(x),C1,R3(x), W2(y), R3(y), R2(z), C2,R3(z),C3 优先图：无环，是可串调度。用优先图分别判别下面的4个调度是否为可串行化调度，是可串行化调度的还要写出其等价串行调度。S1= W2(x),W1(x),R3(x),R1(x),C1,W2(y), R3(z),C3,R2(x),C2S2= R3(z),R3(y),W2(y),R2(z),W1(x),R3(x),W1(x),R1(x),C1,C2,C3S3=R3(z),W2(x),W2(y),R1(x),R3(x),R2(z),R3(y),C3,W1(x),C2,C1S4=R3(z),W2(x),W2(y),C2,W1(x),R1(x),C1,R3(x),R3(z),R3(y),C35、 什么是锁的粒度？ 锁的粒度:1) 锁定数据项的范围2) 数据项层次一条数据库记录数据库记录中的一个字段值一个磁盘块（页面）一个完整的文件整个数据库6、 什么是共享锁？什么是排他锁？什么是意向锁？ 意向锁：如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁；对任一节点封锁时，必须先对它的上层节点加意向锁意向共享锁(IS)：指示在其后代节点上将会请求共享锁，即如果对某个对象加IS锁，表示它的后代节点拟加共享锁意向排它锁(IX)：指示在其后代节点上将会请求排他锁，即如果对某个对象加IX锁，表示它的后代节点拟加排他锁共享意向排它锁(SIX)：指示当前节点处在共享方式的封锁中，但是在它的某些后代节点中将会请求排他锁。即如果对一个数据对象加SIX锁,表示对它加共享锁，再加IX锁（SIX=S+IX）。例如：对某个表加SIX锁，则表示该事务要读整个表（加S锁），同时会更新个别元组（加IX锁） 7、 分布式死锁检测算法，一道例题，一道作业。（例）如下的等待图, 用分布式检测算法检测其是否有死锁(给出检测过程)解：将site3的LWFG传给site1和site2将site1的信息传给site2，得到GWFG，其中存在不含EX的循环，故存在死锁（作业）用分布式检测算法检测该等待图是否存在死锁传递顺序：EX T1 T2将site1的LWFG传给site2 存在不含EX的循环，故存在死锁8、 基本时标法，一道作业。 对数据库中的某个数据项x，已知RTM（x）=120，WTM（x）=110。(或)表示事务T在x项上具有TS时间戳的读申请(或写申请)，给出下列申请序列的满足基本时间戳算法的执行动作。 ，解：RTM（x）=120，WTM（x）=1101、 表示事务T在x项上具有 TS 为 115 的读申请。此时 TSWTM(x),执行操作，设置 RTM(x) = maxRTM(x), TS 1202、 表示事务T在x项上具有 TS 为 80 的读申请。此时TSWTM（x），拒绝该操作, 事务重新启动3、 表示事务T在x项上具有 TS 为 112 的写申请。此时TSRTM(x)，拒绝该操作, 事务重新启动4、 表示事务T在x项上具有 TS 为 118 的写申请。此时TSRTM(x)，拒绝该操作, 事务重新启动5、 表示事务T在x项上具有 TS 为 135 的读申请。此时 TSWTM(x),执行操作，设置 RTM(x) = maxRTM(x), TS 1356、 表示事务T在x项上具有 TS 为 125 的写申请。此时TSRTM(x)，拒绝该操作, 事务重新启动7、 表示事