1. 九八年秋季试题 51.1. 概念题 51.1.1. 比较半连接方法和枚举法的优缺点。 51.1.2. 2PL协议的基本思想。 51.1.3. WAL协议的主要思想。 51.1.4. SSPARC三级模式体系结构。 51.1.5. 设计OID的数据结构时应考虑哪些问题。 61.2. 某个大学中有若干系，且每个系有若干个班级和教研室，每个教研室有若干个教员，其中教授、副教授每个人带若干名研究生。每个班有若干名学生，每个学生可选修若干门课程，每门课程可由若干学生选修。完成下列各种要求： 61.3. 下面是某学院的一个学生档案数据库的全局模式： 71.3.1. 将全局模式进行分片，写出分片定义和分片条件。 71.3.2. 指出各分片的类型，并画出分片树。 81.3.3. 假设要求查询系号为1的所有学生的姓名和成绩，写出在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询树，请依次进行全局优化和分片优化，画出优化后的查询树。要求给出优化变换过程。 81.4. 设数据项x,y存放在S1场地，u,v存放在S2场地，有分布式事务T1和T2,T1在S1场地的操作为R1(x)W1(x)R1(y)W1(y),T2在S1场地的操作为R2(x)R2(y)W2(y);T1在S2场地上的操作作为R1(u)R1(v)W1(u),T2在S2场地上的操作作为W2(u)R2(v)W2(v)。对下述2种情况，各举一种可能的局部历程（H1和H2），并说明理由。 91.4.1. 局部分别是可串行化，而全局是不可串行化的 91.4.2. 局部和全局都是可串行化的。要求按照严格的2PL协议，加上适当的加锁和解锁命令，（注意，用rl(x)表示加读锁，wl(x)表示加对x加写锁，ul(x)表示解锁） 91.5. 试述面向对象的数据库系统中页面服务器和对象服务器两种Client/Server体系结构的主要特点, 102. 九九年春季试题 102.1. DBMS解决了信息处理技术中的哪些挑战？ 102.2. 在关系数据库应用设计中，为什么要对数据库模式进行规范化？ 102.3. 简述ACID特性。 112.4. 长事务处理有哪些特性，如何解决？ 122.5. 数据库系统体系结构有哪几类，每种类型的特点是什么，关键技术有哪些？ 122.6. 决策支持类应用与OLTP应用对于数据库系统的要求有哪些不同，支持前者的关键技术有哪些，并简述之。 122.7. 面向对象的数据库是如何产生的，其基本原理是什么？有哪些创新特性？ 132.8. r r 一定等于r r 吗？在什么条件下r r = r r 成立? 142.9. 为了设计一个健壮的分布式系统，你必须知道可能发生哪种类型的失败。 142.9.1. 请列出在分布式系统中可能的失败类型： 142.9.2. 在你列出的失败类型中，哪些也可能发生在集中式系统中？ 142.9.3. 对于每一种失败类型，在失败发生情况下，两段提交机制如何保证事务的原子性？ 143. 九九年秋季试题 143.1. 问答题 143.1.1. 分布式数据库系统在系统结构、模式结构、功能模块等方面有何特点？ 143.1.2. 给出两种2PL协议，并比较它们的优点缺点？ 143.1.3. 解释为什么对象类的多继承存在二义性，并通过例子加以说明。 153.1.4. 对于下述情况，哪种并行性（查询间并行性、操作间并行性、操作内并行性）有助于正加系统的吞吐量： 153.2. 下面是某个公司人事数据库的两个全局关系 153.2.1. 将全局模式进行分片，写出分片定义和分片条件。 153.2.2. 指出各分片的类型，并画出分片树 153.2.3. 进行全局优化，画出优化后的全局查询树。 163.2.4. 进行分片优化，画出优化后的分片查询树。 163.3. 对3个关系R,S和T的分布式连接，已知有如下的剖视图： 193.3.1. 按照SDD-1半连接优化算法，逐步求出半连接优化集和最终执行场地； 193.3.2. 对以上结果做相应的优化处理。 233.4. 用下面的关键字值的集合构造一颗B+树：（2,3,5,7,11,17,19,23,29,31）。假定树开始是空的，且关键字的值是以升序插入到B+树中去的，B+树每个节点中含的指针数为4。 243.5. 考虑关系r (A,B,C)，r (C,D,E)，r (E,F)，假设不存在主关键字。设V(C, r )=900， 243.6. 假设一个存储块中仅能存放一个记录且在内存中最多只有三个页框。请 出在排序合并算法中每遍形成的Runs,排序属性为第一个属性：（kangaroo,17），(wallaby,21)，(emu,1)，(wombat,13)，(platypus,3)，(lion,8)，(warthg,4)，(zebra,11)，(meerkat,6)，(hornbill,2)，(baboon,12)。 244. 二零年春季试题 244.1. 244.1.1. 分布库管理系统有哪些主要功能模块及其作用. 244.1.2. 半连接方法和枚举法各适用于何种查询优化情况. 254.1.3. 分布式事务有哪些基本性质. 254.1.4. 什么是2PL协议 254.2. 下面是某个公司的人事关系数据库的全局模式： 254.2.1. 将全局模式进行分片，写出分片定义和分片条件。 264.2.2. 指出分片的类型，并画出分片树。 264.3. 对题4.2所确定的分片模式，要求查询级别高于“6”的所有职员的姓名和工资，写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询树。 264.3.1. 进行全局优化，画出各步优化后的全局查询树。 264.3.2. 进行分片优化，画出各步优化后的分片查询树。 274.4. 下面是一个数据库系统出现故障是，日志文件中记录的信息； 274.4.1. 找出发生故障时系统中的活动事务，确定出反做和重做事务集。 274.4.2. 用C或其他语言定义出数据库记录（D记录）和检查点记录（K记录）的数据结构。 284.5. 设数据项x,y存放在S1场地，u,v存放在S2场地，有分布式事务T1和T2,T1在S1场地的操作为R1(x)W1(x)R1(y)W1(y),T2在S1场地的操作为R2(x)R2(y)W2(y);T1在S2场地上的操作作为R1(u)R1(v)W1(u),T2在S2场地上的操作作为W2(u)R2(v)W2(v)。对下述2种情况，各举一种可能的局部历程（H1和H2），并说明理由 284.5.1. 局部分别是可串行化，而全局是不可串行化的 284.5.2. 局部和全局都是可串行化的。 284.5.3. 要求按照严格的2PL协议，加上适当的加锁和解锁命令，（注意，用rl(x)表示加读锁，wl(x)表示加对x加写锁，ul(x)表示解锁） 285. 二零年秋试题 295.1. 概念题 295.1.1. 解释对象数据库系统中面向对象的相关概念 295.1.2. 从概念上比较对象数据库模型与对象关系模型 295.1.3. 利用左深树、右深树、浓密树来进行查询优化的各自特点 295.1.4. 试解释影响并行数据库系统中并行算法性能的三个因数 305.1.5. 简述用爬山算法进行查询优化的基本思想 305.2. 下面是某个公司一个人事关系数据库的全局模式： EMP={ENO*,ENAME,POSITION,PHONE} PAY={POSITION*,SALARY} ENO为职员号，POSITION为岗位。SALARY表示岗位对应的工资，*对应的属性表示主关键字。该公司分布在两个场地上，其中，在场地1经常处理所有职员数据，而场地2只处理工资低于1000的职员数据，为了节省磁盘空间和增大处理局部性： 305.2.1. 将以上全局关系进行分片设计，写出分片定义和分片条件。 305.2.2. 指出分片的类型，并画出分片树。 305.2.3. 给出分配设计。 315.3. 对题二所确定的分片模式，要求查询岗位为“salesman”的所有职员的姓名和工资，写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询树。假设“salesman”的工资为800元。要求给出中间转换过程。 315.3.1. 进行全局优化，画出优化后的全局查询树。 315.3.2. 进行分片优化，画出优化后的分片查询树。 315.4. 按如下给出的条件，求出半连接优化计划和执行场地，并作后优化处理 325.5. 下面是当一个数据库系统出现故障时，日志文件中的信息 365.5.1. 画出对应的事务并发执行图。 375.5.2. 找出发生故障时系统中的活动事务，确定出反做和重做事务集。 375.5.3. 指出需要undo的和redo的数据记录。 375.6. 设数据项x,y存放在S1场地，u,v存放在S2场地，有分布式事务T1和T2。T1在S1场地的操作为R1(x)W1(x)R1(y)W1(y)，T2在S1场地的操作为R2(x)R2(y)W2(y)；T1在S2场地上的操作作为R1(u)R1(v)W1(u)，T2在S2场地上的操作作为W2(u)R2(v)W2(v)。对下述2种情况，各举一种可能的局部历程（H1和H2），如果是可串行化的，指出事务的执行次序。对第3种情况，给出符合基本2PL协议的调度。（T1 加锁命令用L1(X)表示，开锁命令U1(X)表示。对任何数据的加锁可在事务开始后立即进行）。 385.6.1. 局部是不可串行化的。 385.6.2. 局部是可串行化的，而全局是不可串行化的。 385.6.3. 局部是可串行化的，全局也是可串行化的。 395.7. 设计一种满足下列要求的索引结构。 395.7.1. 被索引的数据集合为有序集 395.7.2. 在有序集上的查询操作都是基于位置来进行的 395.7.3. 当往有序集中插入或删除一个元素时，与该元素相关的后续元素的位置均要发生变化 395.7.4. 元素的类型可为任意类型（这一个小问题的解决需要考虑语言的特征） 396. 二零一春季试题 396.1. 396.1.1. 讨论集中式数据库和分布式数据库各自的优缺点。 396.1.2. 讨论在局域网和广域网两种情况下分布库设计的区别。 396.1.3. 解释分片透明性、复制透明性和位置透明性等三级透明性的区别。 396.1.4. 解释2PC协议如何在故障情况下保证事务的原子性的 406.1.5. 解释严格2PL协议与基本2PL协议的区别 406.2. 下面是某个公司一个人事关系数据库的全局模式： EMP={ENO*,ENAME,POSITION,PHONE} PAY={POSITION*,SALARY} ENO为职员号，POSITION为岗位。SALARY表示岗位对应的工资，*对应的属性表示主关键字。该公司分布在两个场地上，其中，在场地1经常处理所有职员数据，而场地2只处理工资低于1000的职员数据，为了节省磁盘空间和增大处理局部性： 416.2.1. 将以上全局关系进行分片设计，写出分片定义和分片条件。 416.2.2. 指出分片的类型，并画出分片树。 416.2.3. 给出分配设计。 416.3. 对题二所确定的分片模式，要求查询岗位为“salesman”的所有职员的姓名和工资，写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询树。假设“salesman”的工资为1500元。要求给出中间转换过程。 416.3.1. 进行全局优化，画出优化后的全局查询树 426.3.2. 进行分片优化，画出优化后的分片查询树。 426.4. 下面是当一个数据库系统出现故障时，日志文件中的信息 436.4.1. 画出对应的事务并发执行图。 446.4.2. 找出发生故障时系统中的活动事务，确定出反做和重做事务集。 446.4.3. 指出需要undo的和redo的数据记录。 446.5. 设数据项x,y存放在S1场地，u,v存放在S2场地，有分布式事务T1和T2,T1在S1场地的操作为R1(x)W1(x)R1(y)W1(y),T2在S1场地的操作为R2(x)R2(y)W2(y);T1在S2场地上的操作作为R1(u)R1(v)W1(u),T2在S2场地上的操作作为W2(u)R2(v)W2(v)。对下述2种情况，各举一种可能的局部历程（H1和H2），如果是可串行化的，指出事务的执行次序。对第3种情况，给出符合基本2PL协议的调度。（T1 加锁命令用L1(X)表示，开锁命令U1(X)表示。对任何数据的加锁可在事务开始后立即进行）。 446.5.1. 局部是不可串行化的。 446.5.2. 局部是可串行化的，而全局是不可串行化的。 456.5.3. 局部是可串行化的，全局也是可串行化的。 45### 研究生分布式数据库参考习题解析#### 1.1.1. 比较半连接方法和枚举法的优缺点。**半连接方法：**- **优点：** - **减少网络传输量：** 半连接方法通过在数据源站点先进行过滤操作，减少了网络上传输的数据量，特别是对于大数据集的连接操作，可以显著提高效率。 - **降低远程站点的计算负担：** 由于过滤操作在本地完成，减轻了远程站点的计算压力。 - **适用于分布式环境：** 半连接特别适合于分布式数据库环境，能够有效利用网络资源。- **缺点：** - **增加本地计算负担：** 半连接操作可能会增加本地站点的计算复杂度，尤其是在处理大规模数据时。 - **可能丢失部分结果：** 如果过滤条件设置不当，可能会错误地排除掉一些本应该被保留的结果。 - **实现复杂度较高：** 相比其他方法，半连接的实现相对较为复杂，需要考虑