1、高级数据库系统作业答疑,2016.1,1,第一次作业,1. 用自己语言定义下列分布式数据库系统中的术语。 全局/局部数据、全局/局部DBMS、 全局外/概念模式等（第一章）2. 分布式数据库系统分类？P6-83.分布式DBMS具有哪些集中式DBMS不具备的功能？（P15，34） (见课本),2,第二次作业,已知有如下两种段分配: A R1在Site1, R2在Site2, R3在Site3. B R1和R2在Site1, R2和R3在Site3.另已知有如下应用(所有应用的频率相同) A1: 在Site1上发出, 读5个 R1记录, 5个 R2记录 A2: 在Site3上发出, 读5个R3记录
2、 , 5个R2记录 A3: 在Site2上发出, 读10个R2记录.问: 1. 如果以本地应用为主要设计目标, 那个分配较优?2. 假定A3改为要修改10个R2记录, 并仍以本地应用为其设计目标, 则那个分配方案较优?,3,第二次作业,解：首先完善模型如下：假定：本地读写的代价可忽略不计； 异地读写操作的代价均相等，记为1故可知，第1个问题，A、B两种分配方案代价相等。 第2个问题，A分配方案较优。,4,分别写回site1和site3(保持数据一致性),从site1或者site3读取,A R1在Site1, R2在Site2, R3在Site3.B R1和R2在Site1, R2和R3在Sit
3、e3. A1: 在Site1上发出, 读5个 R1记录, 5个 R2记录 A2: 在Site3上发出, 读5个R3记录 , 5个R2记录 A3: 在Site2上发出, 读10个R2记录.,第二次作业,2.2 分布式数据库设计的主要目标？ P412.6 数据分片基本原则？数据分片基本类型和方法？P44 （见课本）2.9 COMPANY关系数据库：表EMPLOYEE 、DEPARTMENT 、P67DEPT-LOCATION 、PROJECT、WORKS-ON 、DEPENDENT ; 站点B(部门2)、C(部门3)：频繁访问EMPLOYEE表的NAME,ESSN,SALARY和SUPERSSN属
4、性和PROJECT表 站点A(总部门1)：经常存取DEPENDENT、定期访问所有雇员和项目信息 考虑分片和分布。解： (1) 所有表存放于站点A： 部门1要经常访问所有雇员和项目信息 (2) 因为站点B和C分别属于部门2和3，所以先对DEPARTMENT按DNO水平分片， 取DNO=2、3 分别得到部门2和3的数据存放于站点B和C (3)将EMPLOYEE、PROJECT以及DEPT_LOCATION分别和部门2和3的DEPARTMENT 数据在DNO属性上半连接，得到部门2和3上的EMPLOYEE、PROJECT以及 DEPT_LOCATION数据,5,第二次作业,(4) 对水平分片后的E
5、MPLOYEE进行垂直分片，得到只含有 NAME,ESSN,SALARY,SUPERSSN,DNO的片段 (5) WORKS-ON 与 EMPLOYEE和PROJECT都相关，既可以用员工E工作的部门也 可以用管辖项目P的部门来对WORKS-ON水平分片，或者分片更细一些， 先用员工E工作的部门划分，再用管辖项目P的部门来划分,6,第三次作业,7,第三次作业,3.6解：R JN S = R JN S JN T =,8,第三次作业,3.6(续)RS SR ST T SR T 、TR 为空,9,第三次作业,10,第三次作业,3.8解：1）将Boce站点上的副本传至Toronto站点；2）在New
6、York站点上求平均工资，传至Toronto站点；3）Toronto, Edmonton, Vancouver, Montreal求最高工资，传至Toronto汇总；,11,第三次作业,习题: 假定全局关系和分段模式如下：全局关系 Doctor (D#, Name, Dept) Patient (P#, Name, Dept, Treat, D#) Care (P#, Drug, QTY)分段模式 Doctor1 = SLDEPT=Surgery(Doctor) Doctor2 = SLDEPT=Pediatrics(Doctor) Doctor3 = SLDEPT Surgery and D
7、EPT Pediatrics(Doctor) Patient1 = SLDEPT=Surgery and treat=intensing(Patient) Patient2 = SLDEPT=Surgery and treat intensing(Patient) Patient3 = SLDEPT Surgery (Patient) Care1 = Care SJ p#=p# Patient1 Care2 = Care SJ p#=p# Patient2 Care3 = Care SJ p#=p# Patient3使用变换准则，将下面的全局查询变化为分段查询，并对它们加以简化。当需要时用限定
8、关系代数消除查询中不用的段。 (a) 列出在Care中使用Aspirin的Patient 名字； (b) 列出给病人开出接受精细护理的医生名字。,12,第三次作业,(a) 全局关系上的查询表达式(列出在Care中使用Aspirin的Patient 名字),13,全局关系转化为分段关系,第三次作业,(a),14,上推UN下推PJ 和 SL,第三次作业,(a),15,第三次作业,(b)全局关系上的查询表达式,D1 与P3 JN为空,P2 无符合条件的元组,D2 与P1 JN为空,D3 与P1 JN为空,16,第四次作业,17,第四次作业,18,第四次作业,3.7如果习题中的三个关系R,S,T分别位
9、于三个不同的站点X,Y,Z。若采用基于半连接的算法计算RST,请选择使得传输代价最小的连接执行站点和确定半连接序列,19,X,Y,Z,第四次作业,假设每个属性域长度均为1B，考虑所有的半连接a),选择得益最高的P2进行优化，并对受到影响的的方案重新计算得益和费用,20,在有益方案中选择得益最高的或者费用最少的方案进行优化,b),选择收益更高的P4进行优化，对受影响的半连接重新计算费用和得益c),选择P1进行优化,S = SR,T = TS,2*2,2*2,21,d) 选择p3继续进行优化 最终得到的关系如下： R(站点X) S(站点Y) T(站点Z),R = RS,22,S = S T,所以选
10、择各站点做连接的代价为： X站点代价=2*3+2*3=12 Y站点代价=3*4+2*3=18 Z站点代价=3*4+2*3=18故选择X站点作为收集站点代价最低,23,由简化过程得知半连接过程为：S = SR (R.B 和R.C从X-Y) 将S传送给T,做半连接TS得到T (S.D从Y-Z ) 将S传送给R,做半连接RS得到R (S.D从Y-X ) 将T 传送给S，做半连接S T (T.D从Z-Y ) 最终将S和T传到R,做连接得到结果即:(R(SR) (SR)(T(SR) (T(SR),24,S,T,T,R,S,第五次作业,1.假设两个事务T 和 U 的 log 记录如下所示: , 如果系统故
11、障时, 磁盘上记录的Log记录如下, 请描述数据库恢复管理器的动作. a) b) c) d) ,25,第五次作业,1(a)undo U, undo T （不能是undo T，undo U ） (b)undo T, redo U (c)undo T, redo U (d)redo T, redo U (见课本),26,1. Undo是逆向完成2. Redo是顺序完成3. 必须先Undo 后Redo,1.假设两个事务T 和 U 的 log 记录如下所示: , 如果系统故障时, 磁盘上记录的Log记录下, 请描述数据库恢复管理器的动作. a) b) c) d) ,第六次作业,27,第六次作业,一个冲
12、突等价调度如下：S1=W2(x),W1(x),R1(x),R3(x),C1,W2(y),R3(z),C3,R2(x),C2S2=R3(z),R2(z),R3(y),W2(y),W1(x),R3(x),W1(x),R1(x),C1,C2,C3 S3=W2(x),W2(y),R2(z),C2,R3(z),R3(x),R3(y),C3,R1(x),W1(x),C1S4=W2(x),W2(y),C2,W1(x),R1(x),A1,R3(z),R3(x),R3(z),R3(y),C3,非冲突动作的交换可得到一个等价调度,28,第六次作业,2. 上题S1-S4中, 哪个是可串调度? 解：,P(S1),T1
13、,T2,T3,P(S2),T1,T2,T3,P(S3),T1,T2,T3,P(S4),T1,T2,T3,先序图,29,S3和S4为可串调度,第七次作业,3. 有如下的等待图, 用分布式检测算法检测其是否有死锁(给出检测过程),T2T1,Site1,T1 T3,Site2,Site3,30,第七次作业,3. LWFG,31,第七次作业,1） 将site3的LWFG传给site1 (EX E3 E1),32,检测到包含有EX的LOOP,存在潜在的死锁,第七次作业,33,2） 将site1上修改过的LWFG传给site2，得到GWFG,(EX T3 T1 T2）,检测到不包含有EX的LOOP,存在全
14、局死锁,第七次作业,4.已知有事务如例5-1(p.111), 并且T1的TS是20, T2的TS是25重启动间隔是5, 给出按基本T/O方式执行的过程(调度).,34,第七次作业,4.,20 25,35,对X的读操作的时戳只需要与WTM(x) 比较，若小于WTM(x)则拒绝,对X的写操作的时戳需要与WTM(x)和RTM(x) 比较，若小于WTM(x) 或 RTM(x)则拒绝,第八次作业,6.10这里我们选择最常用的三种方法：ROWA方法，Gifford方法和集中式协议的主副本封锁法来进行分析。（1）ROWA方法首先分析ROWA方法下系统对这12个事务的可用性。由于写操作要求对所有副本加锁，所以
15、对于任何一种网络分割情况，事务19都不可能申请全部的锁，因此它们都不能执行，而事务1012是只读事务，它们只要求锁定一个副本，所以它们可以在出现网络分割时，在各自所在的网络组内执行（如果存在这样的网络组）。,36,下图表示了对于每个事务和每种网络分割情况来说，某事务可在其内执行的网络组。只读事务10，11和12与事务10，11和12相同，但是对他们不要求一致性。在ROWA方法中，读副本不必考虑数据的一致性，只锁定一个副本，并从中读出数据。事实上，数据项多副本的一致性是由写锁全部副本来保证的，当无故障发生时，更新必然是对全部副本进行；当发生故障时使得有些副本无法加锁，从而导致更新事务不能执行更新操作，所以副本的一致性得以保证，故读出数据是一致的。,第九次作业,具有许可证级别C的用户看到的视图：带有许可证级别C的用户更新“Jack”的Sal值：,43,允许更新Sal,谢 谢！,44,
