高级数据库系统作业答疑

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高级数据库系统作业答疑,2007.1,第一次作业,已知有如下两种段分配,:,A R1,在,Site1, R2,在,Site2, R3,在,Site3.,B R1,和,R2,在,Site1, R2,和,R3,在,Site3.,另已知有如下应用,(,所有应用的频率相同,),A1:,在,Site1,上发出,读,5,个,R1,记录, 5,个,R2,记录,A2:,在,Site3,上发出,读,5,个,R3,记录, 5,个,R2,记录,A3:,在,Site2,上发出,读,10,个,R2,记录,.,问,: 1.,如果以本地应用为主要设计目标,那个分配较优,?,2.,假定,A3,改为要修改,10,个,R2,记录,并仍以本地应用为其设计目标,则那个分配方案较优,?,第一次作业,解：首先完善模型如下：,假定：,B,方案中,Site1,上的,R2,和,Site3,上的,R2,是完全相同的，即冗余；本地读写的代价可忽略不计；所有异地读操作的单位记录代价均相等，记为,1,；所有异地写操作的单位记录代价均相等，记为,1,。,1 A,方案,B,方案,2 A,方案,B,方案,A1,代价,5 0 5 0,A2,代价,5 0 5 0,A3,代价,0 10 0 10+10+10,故可知，第,1,个问题，,A,、,B,两种分配方案代价相等。,第,2,个问题，,A,分配方案较优。,第二次作业,习题,:,假定全局关系和分段模式如下：,全局关系,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 DEPT,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,使用变换准则，将下面的全局查询变化为分段查询，并对它们加以简化。当需要时,用限定关系代数消除查询中不用的段。,(a),列出在,Care,中使用,Aspirin,的,Patient,名字；,(b),列出给病人开出接受精细护理的医生名字。,第二次作业,(a),第二次作业,(a),第二次作业,(a),第二次作业,(b),第三次作业,对,R,的另一个简化程序：,R=R SJ S, T = T SJ R, S = S SJ T,计算到,R,不再变化为止,第三次作业,在如下,R, S,的概貌上计算,R JNA=B S,Size(R,)=50,Card(R,)=100,Val(AR,)=50,Size(A,)=3,Size(S,)=5,Card(S,)=50,Val(BS,)=50,Size(B,)=3,R SJA=B S,的选择度, = 0.2,S SJA=B R,的选择度, = 0.8,问,:,1.,使用,SJ,简化程序在,R,得站点执行,JN,2.,使用,SJ,简化程序在,S,得站点执行,JN,3.,使用直接连接在,R,站点执行,JN,4.,使用直接连接在,S,站点执行,JN,那种方案较优,?,第三次作业,解：,1.COST1 = 2C0 + C1(,Size(A)Val(AR,) +,Size(S)Card(S),S,SJ R,),= 2C0 + C1( 350 + 5500.8 ) = 2C0 + 350C1,2.COST2 = 2C0 + C1(,Size(B)Val(BS,) +,Size(R)Card(R),R,SJ S,),= 2C0 + C1( 350 + 501000.2 ) = 2C0 + 1150C1,3.COST3 = C0 + C1Size(S)Card(S),= C0 + C1550 = C0 + 250C1,4.COST4 = C0 + C1Size(R)Card(R),= C0 + C150100 = C0 + 5000C1,所以第三种方案最优。,第四次作业,7.2,解：第三句有问题，左边为,string,类型，右边是,City,类型。,cityOfLA.name,:=,cityOfLA.mayor.spouse.livesIn,;,7.4,解：前一种的输出结果为：,Donald Duck,Mickey Mouse,后一种的输出结果为：,60,60,因为前一种是引用语义，而后一种是复制语义。,第四次作业,7.7,解：,引用：,someMaterial,:=,id88,;,隐式引用：,myCuboid.mat,:=,someMaterial,;,someMaterial.create,;,重引用：,w :=,myCuboid,.,mat,.,specWeight,;,隐式重引用：,anotherMaterial,:=,myCuboid.mat,;,myCuboid.mat.create,;,第四次作业,7.9,解：,(1)(2),执行完毕后，,mary.chilaren,=,joe.children,= ,littleJoe,第四次作业,(3)(4),执行完毕后，,betty.children,= ,jimbo,jim.children,= ,第五次作业,8.8,persistent type,Cuboid,is,public length, width, height, surface, volume, weight, translate, scale, rotate,certer, diagonal,minDistance,;,body v1, v2, v3, v4, v5, v6, v7, v8 :,Vetex,; mat : Material; value : float;,operations,declare surface :,float;,declare scale : Vertex,void,code,scaleCuboid,;,declare center :,Vertex;,declare diagonal:,float;,declare,minDistance,: Vertex,float,code,minDistanceCode,;,第五次作业,implementation,define surface is,return 2.0 * (,self.length,*,self.width,+,self.length,*,self.height,+,self.width,*,self.height,);,define,scaleCuboid(s,) is,begin,self.v1.scale(s);,self.v8.scale(s);,end define,scaleCuboid,;,第五次作业,define center is,var,c : Vertex;,begin,c.create,;,c.x,= 0.5 * (self.v1.x + self.v7.x);,c.y,= 0.5 * (self.v1.y + self.v7.y);,c.z,= 0.5 * (self.v1.z + self.v7.z);,return c;,end define,certer,;,define diagonal is,return self.v1.distance(self.v7);,第五次作业,define,minDistanceCode(v,) is,var,v0;,begin,/,将长方体的,6,个面无限延伸，可将整个空间分为,27,个区域,if (v,在长方体内部或表面上,),return 0;,else begin,根据,v,所在区域，可简单判断出长方体上距,v,最近的点,v0,所在 的面,/,棱,/,顶点，进而求出,v0;,return v.distance(v0);,end else,end,deine,minDistanceCode,;,end type,Cuboid,;,第五次作业,9.1,答：,（,1,）方法一采用,1:1,关系表示,1:N,关系，存在较多冗余；,不考虑索引，已知,left,查询对应的,right,集时，方法二效果明显好 于方法一；已知,right,查询对应的,left,时，方法一效果好于方法二。,当插入新关系,时，两种方法都无法保证一致性，即原关系,1:N,的语义约束可能被违反，需要对,insert,操作做修改，保证每一 个,Tright,实例仅有至多一个对应的,Tleft,实例。,删除关系,时，方法一中直接删除对应的,TR,实例，方法二中 只需修改,right,集合，直到,right,集合为空时，才需要删除对应的,TR,实例。,更新操作由插入删除操作组合而成，不再讨论。,（,2,）方法一、二的,insert,操作均需修改，以保证一致性，方法二的,delete,操作也需要修改。修改思想上边已说明，具体算法不再给 出。,第六次作业,10.5,解：,declare connect : Pipe | Pipe,void;,refine connect :,ConicalPipe,|,ConicalPipe,void;,一个合法的重定义要求：,操作名不变，参数个数不变；,操作的接收者类型是原操作中接收者类型的子类；,操作的返回值类型是原操作返回值的子类；,操作的参数类型是原操作参数类型的超类。,题中的重定义仅满足（,1,）（,2,）（,3,），但违反（,4,）。,ConicalPipe,是,Pipe,的子类而非超类，故不合法。,考虑下面的程序段：,var,aPipe,anotherPipe,: Pipe;,aConicalPipe,:,ConicalPipe,;,anotherPipe,:=,aConicalPipe,; /,可替换性，合法,anotherPipe.connect(aPipe,); /,编译通过，执行时由于动态绑定，出错,第六次作业,10.6,解：,继承属性的类型是不能重定义的，必须保持原类型。,(1),子类中继承属性的类型不能是该类型的子类，即特化不合法。,特化举例：,type Person is,body name : string;,age :,int,;,type Employee,supertype,Person is,body boss : Employee;,type Manager,supertype,Employee is,body refine boss : Manager;,第六次作业,程序段：,var,anEmp,: Employee;,aMgr,: Manager;,aMgr.boss,:=,anEmp,; /,语法错误,anEmp.boss,:=,aMgr,; /,可替换性，合法,anEmp.boss.boss,:=,anEmp,; /,语法检查合法，但有潜在问题,(2),子类中继承属性的类型不能是该类型的超类，即泛化不合法。,Person,和,Employee,的类型定义同上，,Manager,类型定义如下：,type Manager,supertype,Employee is,body refine boss : Person;,程序段：,var,aPerson,: Person;,anEmp,: Employee;,aMgr,: Manager;,anEmp.boss,:=,anEmp,; /,合法,aMgr.boss,:=,anEmp,; /,可替换性，合法,aMgr.boss.boss,:=,anEmp,; /,语法错误,第六次作业,12.3,解：,(1),Polymorph declare member (,ListType,= ) : ,ListType,| ,ElemType,bool,;,define member (t) is,var,item : ,ElemType,;,begin,foreach,(item in self),if (item = t),return true;,return false;,end define member;,第六次作业,(2),Polymorph declare,nthmember,(,ListType,= ) :,ListType,|,int,ElemType,;,define,nthmember,(n) is,var,i :,int,;,item : ,ElemType,;,Begin,if (n ,self.length,| n 1),return null;,i := 0;,foreach,(item in self),begin,i+;,if (i = n),return item;,endfor,end define,nthmember,;,第六次作业,(3),Polymorph declare substitute (,ListType,= ) :,ListType,| ,ElemType, ,ElemType,void;,define,substitute(old, new) is,var,item : ,ElemType,;,begin,foreach,(item in self),begin,if (item = old),begin,self.delete(old,);,self.insert(new,);,endif,endfor,end define substitute;,第六次作业,(4),Polymorph declare,sublist(ListType,= ) :,ListType,|,int,int,ListType,;,define,sublist(m, n) is,var,newlist,: ,ListType,;,item : ,ElemType,;,i :,int,;,begin,i := 0;,if (i = 1 & i = k & k = m & i ,e.worksin.mgr.salary,;,第七次作业,14.9,Retrieve all Managers of the R&D,department(s,), who supervise,Emps,located in the Building called “E1”.,select m,from m in Manager, e in EMP,where m =,e.worksin.mgr,and,m.worksin.name,= R&D,and,e.office.building,= E1;,第七次作业,14.10,List the name and salary of managers who manage more than 10 employees.,select,m.name,m.salary,from m in Manager, e in EMP,where,e.worksin.mgr,= m,group by,m.name,having,count(e.name), 10;,第八次作业,1.,假设两个事务,T,和,U,的,log,记录如下所示,:,如果系统故障时,磁盘上记录的,Log,记录如下,请描述数据库恢复管理器的动作,.,a) ,b) ,c) ,d) ,第八次作业,1,(,a)undo,T, undo U,(,b)undo,T, redo U,(,c)undo,T, redo U,(,d)redo,T, redo U,第八次作业,2.,写出线形式,2PC,的实现代码,参见 线形式,2PC,的实现代码,.doc,第九次作业,1.,指出下面的冲突等价调度,(,忽略提交,C,和夭折,A,动作,),S1=,W,2,(x),W,1,(x),R,3,(x),R,1,(x),C,1,W,2,(y), R,3,(z),C,3,R,2,(x),C,2,S2= R,3,(z),R,3,(y),W,2,(y),R,2,(z),W,1,(x),R,3,(x),W,1,(x),R,1,(x),C,1,C,2,C,3,S3=,R,3,(z),W,2,(x),W,2,(y),R,1,(x),R,3,(x),R,2,(z),R,3,(y),C,3,W,1,(x),C,2,C,1,S4=,R,3,(z),W,2,(x),W,2,(y),C,2,W,1,(x),R,1,(x),A,1,R,3,(x),R,3,(z),R,3,(y),C,3,第九次作业,冲突等价调度如下：,S1 =,W,2,(x),W,1,(x),R,1,(x),R,3,(x),C,1,W,2,(y),R,3,(z),C,3,R,2,(x),C,2,S2 =,R,3,(z),R,2,(z),R,3,(y),W,2,(y),W,1,(x),R,3,(x),W,1,(x),R,1,(x),C,1,C,2,C,3,S3 =,W,2,(x),W,2,(y),R,2,(z),C,2,R,3,(z),R,3,(x),R,3,(y),C,3,R,1,(x),W,1,(x),C,1,S4 =,W,2,(x),W,2,(y),C,2,W,1,(x),R,1,(x),A,1,R,3,(z),R,3,(x),R,3,(z),R,3,(y),C,3,第九次作业,2.,上题,S1-S4,中,哪个是可串调度,?,S3,和,S4,为可串调度,S1,：,T1,等待,T2,，,T2,等待,T1,（,W,2,(x),W,1,(x),R,2,(x),）,S2,：,T3,等待,T1,，,T1,等待,T3,（,W,1,(x),R,3,(x),W,1,(x),）,第九次作业,3.,有如下的等待图,用分布式检测算法检测其是否有死锁,(,给出检测过程,),T2,T1,T2 T3,T1 T3,Site1,Site2,Site3,第九次作业,3. LWFG,第九次作业,3.,将,site3,的,LWFG,传给,site1,和,site2,第九次作业,3.,将,site1,的信息传给,site2,，得到,GWFG,，其中存在不含,EX,的循环，故存在死锁,第十次作业,4.,已知有事务如例,5-1(p.111),并且,T1,的,TS,是,20, T2,的,TS,是,25,重启动间隔是,5,给出按基本,T/O,方式执行的过程,(,调度,).,第十次作业,4.,T1(20),T2(25),T1(30),RTM(x,),WTM(x,),RTM(y,),WTM(y,),Read(x,),Write(x,),Abort,Read(x,),Write(x,),Read(y,),Write(y,),Commit,Read(x,),Write(x,),Read(y,),Write(y,),Commit,20,25,30,0,25,30,0,25,30,0,25,30,第十一次作业,设分布式冗余数据库的数据分布如下：,站点,1,：,x,站点,2,：,x, y,站点,3,：,y,站点,4,：,x, y,(a),给每个站点赋以选票，并给读写操作赋以法定人数,(b),给出网络可能的网络分割分组,(c),对于每种网络分割，说明更新,x,的事务在哪个分组上可以终结,第十一次作业,为,x, y,的每个副本赋予一张选票，则各站点的选票为,V1 = 1,V2 = 2,V3 = 1,V4 = 2;,为数据项,x,y,设定读写法定人数如下：,Vrx,=,Vwx,=,Vry,=,Vwy,= 2;,符合,Gifford,算法的要求：,Vr,+,Vw, V,Vw, V/2,。,(,b)(c,),可能的网络分割分组如下（下划线表示事务可在该分组上终结）：,I,未分割：,(1,2,3,4),II,分割为两组：,(1,2),(3,4) (1,3),(2,4),(1,4),(2,3),(1,2,3),(4),(1,2,4),(3),(1,3,4),(2),(2,3,4),(1),III,分割为三组：,(1,2),(3) (4) (1,3) (2) (4),(1,4),(2) (3),(2,3) (1) (4),(2,4),(1) (3) (3,4) (1) (2),IV,分割为四组：,(1) (2) (3) (4),附,本,PPT,可到：,ftp:/addb:addb06202.38.79.95,下载,谢 谢！,