高级数据库系统作业答疑.ppt

1、高级数据库系统作业答疑,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记录, 并仍以本地应用为其设计目标, 则那个分配方案较优?,第一次作业,解：首先完善模型如下

2、： 假定：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 (

3、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

4、 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不再变化为止,第三次作

5、业,在如下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

6、(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、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; 隐式重引用：a

8、notherMaterial := 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

9、, 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; ,第五次作业,imp

10、lementation 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

11、); 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

12、所在 的面/棱/顶点，进而求出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实例。 删除关系时，方

13、法一中直接删除对应的TR实例，方法二中 只需修改right集合，直到right集合为空时，才需要删除对应的TR 实例。 更新操作由插入删除操作组合而成，不再讨论。 （2）方法一、二的insert操作均需修改，以保证一致性，方法二的 delete操作也需要修改。修改思想上边已说明，具体算法不再给 出。,第六次作业,10.5 解： declare connect : Pipe | Pipe void; refine connect : ConicalPipe | ConicalPipe void; 一个合法的重定义要求： 操作名不变，参数个数不变； 操作的接收者类型是原操作中接收者类型的子类； 操

14、作的返回值类型是原操作返回值的子类； 操作的参数类型是原操作参数类型的超类。 题中的重定义仅满足（1）（2）（3），但违反（4）。ConicalPipe是Pipe 的子类而非超类，故不合法。 考虑下面的程序段： var aPipe, anotherPipe : Pipe; aConicalPipe : ConicalPipe; anotherPipe := aConicalPipe; /可替换性，合法 anotherPipe.connect(aPipe); /编译通过，执行时由于动态绑定，出错,第六次作业,10.6 解： 继承属性的类型是不能重定义的，必须保持原类型。 (1) 子类中继承属性的

15、类型不能是该类型的子类，即特化不合法。 特化举例： 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; /可替换性，合法 anEm

16、p.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

17、:= 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 Ele

18、mType; 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 subst

19、itute(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

20、 : ElemType; i : int; begin i := 0; if (i = 1 ,第七次作业,13.5 Assume a Swiss Knife consists of a blade of a certain length that is able to cut different kind of material. A small scissor that is able to cut paper and a screwdriver are also provided. Last but not least a corkscrew completes it. Every too

21、l has a certain length and provides a certain capability. Model a Swiss knife using multiple inheritance. Try an alternative modeling with single inheritance only where the Swiss knife solely is-a knife, which additionally consists of the other tools. What is the difference? 答案略,第七次作业,14.8 Retrieve

22、all Emps who earn more than their Manager. But note that Managers ara also Emps and may work in their own Dept. select e from e in EMP where e.salary e.worksin.mgr.salary;,第七次作业,14.9 Retrieve all Managers of the R,第七次作业,14.10 List the name and salary of managers who manage more than 10 employees. se

23、lect , m.salary from m in Manager, e in EMP where e.worksin.mgr = m group by having count() 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

24、的实现代码 参见 线形式2PC的实现代码.doc,第九次作业,1. 指出下面的冲突等价调度(忽略提交C和夭折A动作) S1= W2(x),W1(x),R3(x),R1(x),C1,W2(y), R3(z),C3,R2(x),C2 S2= R3(z),R3(y),W2(y),R2(z),W1(x),R3(x),W1(x),R1(x),C1,C2,C3 S3= R3(z),W2(x),W2(y),R1(x),R3(x),R2(z),R3(y),C3,W1(x),C2,C1 S4= R3(z),W2(x),W2(y),C2,W1(x),R1(x),A1,R3(x),R3(z),R3(y),C3,第九

25、次作业,冲突等价调度如下： S1 = W2(x),W1(x),R1(x),R3(x),C1,W2(y),R3(z),C3,R2(x),C2 S2 = 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),C1 S4 = W2(x),W2(y),C2,W1(x),R1(x),A1,R3(z),R3(x),R3(z),R3(y),C3,第九次作业,2. 上题S1-S4中, 哪个是可串调度? S3和S4为可串调度 S1：T1等待T2，T2等待T1（W2(x),W1(x),R2(x)） S2：T3等待T1，T1等待T3（W1(x),R3(x),W1(x) ）,