S'= S?T=P1(在场地S2上执行) S''= S'?R=P2(在场地S2上执行) R'= R? S''=P3(在场地S1上执行) 如果在场地S1上执行
因为：P3在场地S1上执行，可以从策略集合中消去P3 所以：P'={P1,P2} 因此：
总代价=Cost(S1)+Cost(P1)+Cost(P2)
= Cost(S1)+Size(T)*Card(T)+Size(R)*Card(R) =22.75K+50*5+1000*10=33K
如果在场地S2上执行
因为：P1,P2在场地S2上执行，可以从策略集合中消去P1,P2。 所以：P'={P3}
因此：总代价=Cost(S1)+Cost(P3) ==Cost(S1)+Size(S'')*Card(S'') =22.75K+1500*10=37.75K
所以最终选择在“总代价”最低的场地S1上执行。 S'=S?T S''=S'?R R'=R? S'' 如图
R S T
S'
S
''
R
'
33
3.4. 用下面的关键字值的集合构造一颗B+树：（2,3,5,7,11,17,19,23,29,31）。假定
树开始是空的，且关键字的值是以升序插入到B+树中去的，B+树每个节点中含的指针数为4。
3.5. 考虑关系r1(A,B,C)，r2(C,D,E)，r(E,F)，假设不存在主关键字。设V(C, r1)=900， V(C, r2)=1100，V(E, r2)=50,V(E, r3)=100。设r1有1000 个元组，r2有1500个元组，r3有750个元组。估算r1? r2? r的大小，并给出一种有效的执行策略。
3.6. 假设一个存储块中仅能存放一个记录且在内存中最多只有三个页框。请出在排序
合并算法中每遍形成的Runs,排序属性为第一个属性：（kangaroo,17），(wallaby,21)，(emu,1)，(wombat,13)，(platypus,3)，(lion,8)，(warthg,4)，(zebra,11)，(meerkat,6)，(hornbill,2)，(baboon,12)。
4. 二零年春季试题
4.1.
4.1.1.分布库管理系统有哪些主要功能模块及其作用.
答：分布式数据库管理系统式对数据库进行管理和维护的一组软件，式分布式数据库系统的重要组成部分，是用户与分布式数据库系统的接口。它有三个组成部分。 全局数据库管理系统（GDBMS）：负责分布式数据库（DDB）中的全局数据库的连接、定位,策略面向全网的恢复能力。 局部数据库管理系统（LDBMS）：是各场地的数据库管理系统。 通信管理程序（CM）：保证分布式数据库系统中场地健信息传送的部分。 4.1.2.半连接方法和枚举法各适用于何种查询优化情况.
半联接技术缩减成连接操作的操作数，以降低通信费用。枚举法适用于缩减局部代价的情况。
查询操作的代价评估，需要综合考虑局部代价和传输代价。侧重于哪一方面，需根据系统组成环境确定。如侧重传输代价，局部代价可以忽略不计时，采用半联接技术较好；相反，如果侧重局部代价时，采用直接连接比采用半连接技术优越。因为直接连接技术实现简单，枚举法是基于直接连接的实现方法，此时应采用枚举法。 半连接优点：传输代价低。
半连接缺点：没有考虑局部代价；当选择“度交低”时，半连接技术才可行。
4.1.3.分布式事务有哪些基本性质. 原子性(Atomicity)、可串行性（一致性Consistency）、隔离性（Isolation）、持久性（Durability）。
这四个性质称为ACID性质，还有
执行特性：由一个控制进程（协调进程），协调各子事务的操作。 操作特性：通信原语，控制原语。 控制报文
4.1.4.什么是2PC协议
答：为了实现分布式数据库事务的正确提交，一般采用两阶段提交协议（2PC）。2PC
协议的基本思想是为全部的参与者做出提交或终止全部局部子事务的唯一决定。如果有一个参与者不能提交其子事务。则全部局部子事务终止。 2PC协议由两个阶段组成，第一阶段做出提交或终止全部子事务的决定，称为决定阶段；第二阶段实现第一阶段的决定，称为执行阶段。在日志部分丢失的情况下，2PC协议可以从多数故障中恢复出来。
协调者：在日志中写入“预提交”命令
发送“预提交”命令给所有参与者且开始计时 参与者：等待“预提交”命令 if 参与者可提交 then
begin
在日志中写入子事务记录 在日志中写入“准备提交” 向协调者发“准备提交”信息 end else begin
在日志中写入“abort” 向协调者发“abort”信息 end
协调者：等待接收所有参与者的应答信息并检查限时。 If 超时或收到至少一个夭折 then Begin
在日志中记入“全部夭折” 向所有子事务发“夭折”命令 end else begin
在日志中记入“全局提交” 向所有参与者发“提交”命令 end
参与者 等待协调者的命令
根据命令在日志中记入“夭折或提交”向协调者发送“执行”信息，
然后执行“提交”或“夭折”命令。
协调者 等待接收所有场地的“执行”信息 在日志中记入“完成”
4.2. 下面是某个公司的人事关系数据库的全局模式： EMP={ENO,ENAME,ADDR,POSITION,RANK,SAL,PHONE}
ENO表示职员号，ENAME表示职员姓名，ADDR表示住址，POSITION表示职务，RANK表示级别，SAL表示工资，PHONE表示电话号码，根据需要，要求将职工的个人信息（ENAME,ADDR,PHONE）与工资信息（POSITION,RANK,SAL）分别存放在场地1和场地2，但是，对于级别不低于“5”的工资信息，需另外存放在场地3。根据上述要求，
4.2.1.将全局模式进行分片，写出分片定义和分片条件。
答： EMP1=П
SAL1=П
ENO,ENAME,ADDR,PHONE,RANKPOSITION,RANK,SALEMP
EMP
SAL11=δSAL12=δ
RANK??\5\RANK?\5\SAL1
SAL1
将EMP分成EMP1，SAL11，SAL12
Site EMP1(1) SAL11(3) SAL12(2) 4.2.2.指出分片的类型，并画出“分片树”。
EMP(ENO,ENAME,ADDR,POSITION,RANK,SAL,PHONE)(V)EMP1(ENO,DNEMAE,ADDR,PHONE)Site(1)HSAL1(POSITION,RANK,SAL)HSAL11(POSITION,RANK,SAL)RANK>=5Site 3SAL12(POSITION,RANK,SAL)RANK<5Site 2
4.3.对题4.2所确定的分片模式，要求查询级别高于“6”的所有职员的姓名和工资，写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询树。
4.3.1.进行全局优化，画出各步优化后的全局查询树。 答： SELECT ENAME,SAL
FROM EMP
WHERE RANK>“6”
用关系代数表示： δRANK?\6\ (П
ENAME,SALEMP)
全局查询树如下
δRANK?\6\
П
|
ENAME,SAL
| EMP
优化后的全局查询树如下
П
δ
ENAME,SAL
|
RANK?\6\
| EMP
4.3.2.进行分片优化，画出各步优化后的分片查询树。 答：“分解树”化简 如图：
EMPEMP1SAL1SAL11去掉图中 SAL12。
П
ENAME,SALSAL12
| δRANK?\6\
| ? rank?rank
EMP1(ENO,ENAME,ADDR,PHONE,RANK)Site1
按C1、C2准则转换将一元操作下移。
ПENAME,SAL
SAL11(POSITION,RANK,SAL)Site3
|
?