数据库试题
目录
1. 九八年秋季试题 ............................................................. 5
1.1. 概念题 .............................................................. 5
1.1.1. 比较半连接方法和枚举法的优缺点。 ................................. 5 1.1.2. 2PL协议的基本思想。 .............................................. 5 1.1.3. WAL协议的主要思想。 .............................................. 5 1.1.4. SSPARC三级模式体系结构。 ......................................... 6 1.1.5. 设计OID的数据结构时应考虑哪些问题。 .............................. 6 1.2. 某个大学中有若干系，且每个系有若干个班级和教研室，每个教研室有若干个教员，其中教授、副教授每个人带若干名研究生。每个班有若干名学生，每个学生可选修若干门课程，每门课程可由若干学生选修。完成下列各种要求： ................... 7 1.3. 下面是某学院的一个学生档案数据库的全局模式： ........................ 9
1.3.1. 将全局模式进行分片，写出分片定义和分片条件。 ..................... 9 1.3.2. 指出各分片的类型，并画出分片树。 ................................. 9 1.3.3. 假设要求查询系号为1的所有学生的姓名和成绩，写出在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询树，请依次进行全局优化和分片优化，画出优化后的查询树。要求给出优化变换过程。 ................. 10 1.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），并说明理由。 ....................... 11
1.4.1. 局部分别是可串行化，而全局是不可串行化的 ........................ 11 1.4.2. 局部和全局都是可串行化的。要求按照严格的2PL协议，加上适当的加锁和解锁命令，（注意，用rl(x)表示加读锁，wl(x)表示加对x加写锁，ul(x)表示解锁） 12 1.5. 试述面向对象的数据库系统中页面服务器和对象服务器两种Client/Server体系结构的主要特点, ........................................................... 12 2. 九九年春季试题 ............................................................ 13
2.1. DBMS解决了信息处理技术中的哪些挑战？ ............................... 13 2.2. 在关系数据库应用设计中，为什么要对数据库模式进行规范化？ ........... 13 2.3. 简述ACID特性。 ..................................................... 15 2.4. 长事务处理有哪些特性，如何解决？ ................................... 15 2.5. 数据库系统体系结构有哪几类，每种类型的特点是什么，关键技术有哪些？ . 16 2.6. 决策支持类应用与OLTP应用对于数据库系统的要求有哪些不同，支持前者的关键
3
技术有哪些，并简述之。 .................................................... 17 2.7. 面向对象的数据库是如何产生的，其基本原理是什么？有哪些创新特性？ ... 18 2.8. ri?rj一定等于rj? ri吗？在什么条件下ri?rj= rj? ri成立? ......... 18 2.9. 为了设计一个健壮的分布式系统，你必须知道可能发生哪种类型的失败。 ... 18
2.9.1. 请列出在分布式系统中可能的失败类型： ............................ 18 2.9.2. 在你列出的失败类型中，哪些也可能发生在集中式系统中？ ............ 19 2.9.3. 对于每一种失败类型，在失败发生情况下，两段提交机制如何保证事务的原子性？ 19
3. 九九年秋季试题 ............................................................ 19
3.1. 问答题 ............................................................. 19
3.1.1. 分布式数据库系统在系统结构、模式结构、功能模块等方面有何特点？ .. 19 3.1.2. 给出两种2PL协议，并比较它们的优点缺点？ ......................... 20 3.1.3. 解释为什么对象类的多继承存在二义性，并通过例子加以说明。 ........ 20 3.1.4. 对于下述情况，哪种并行性（查询间并行性、操作间并行性、操作内并行性）有助于正加系统的吞吐量： ............................................... 20 3.2. 下面是某个公司人事数据库的两个全局关系 ............................. 20
3.2.1. 将全局模式进行分片，写出分片定义和分片条件。 .................... 20 3.2.2. 指出各分片的类型，并画出分片树 .................................. 21 3.2.3. 进行全局优化，画出优化后的全局查询树。 .......................... 21 3.2.4. 进行分片优化，画出优化后的分片查询树。 .......................... 22 3.3. 对3个关系R,S和T的分布式连接，已知有如下的剖视图： .................. 25
3.3.1. 按照SDD-1半连接优化算法，逐步求出半连接优化集和最终执行场地； ... 25 3.3.2. 对以上结果做相应的优化处理。 .................................... 30 3.4. 用下面的关键字值的集合构造一颗B+树：（2,3,5,7,11,17,19,23,29,31）。假定树开始是空的，且关键字的值是以升序插入到B+树中去的，B+树每个节点中含的指针数为4。 32
3.5. 考虑关系r1(A,B,C)，r2(C,D,E)，r(E,F)，假设不存在主关键字。设V(C, r1)=900， ................................................................. 32 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)。 ............................................... 32 4. 二零年春季试题 ............................................................ 32
4.1. ...................................................................... 32
4.1.1. 分布库管理系统有哪些主要功能模块及其作用. ....................... 32 4.1.2. 半连接方法和枚举法各适用于何种查询优化情况. ..................... 32 4.1.3. 分布式事务有哪些基本性质. ....................................... 32 4.1.4. 什么是2PL协议 ................................................... 32 4.2. 下面是某个公司的人事关系数据库的全局模式： ......................... 33
4.2.1. 将全局模式进行分片，写出分片定义和分片条件。 .................... 33 4.2.2. 指出分片的类型，并画出分片树。 .................................. 34 4.3. 对题4.2所确定的分片模式，要求查询级别高于“6”的所有职员的姓名和工资，写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询树。 34
4.3.1. 进行全局优化，画出各步优化后的全局查询树。 ...................... 34 4.3.2. 进行分片优化，画出各步优化后的分片查询树。 ...................... 35 4.4. 下面是一个数据库系统出现故障是，日志文件中记录的信息； ............. 36
4.4.1. 找出发生故障时系统中的活动事务，确定出反做和重做事务集。 ........ 36 4.4.2. 用C或其他语言定义出数据库记录（D记录）和检查点记录（K记录）的数据结构。 36
4.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），并说明理由 ......................... 36
4.5.1. 局部分别是可串行化，而全局是不可串行化的 ........................ 37 4.5.2. 局部和全局都是可串行化的。 ...................................... 37 4.5.3. 要求按照严格的2PL协议，加上适当的加锁和解锁命令，（注意，用rl(x)表示加读锁，wl(x)表示加对x加写锁，ul(x)表示解锁） .......................... 37
5. 二零年秋试题 .............................................................. 38
5.1. 概念题 ............................................................. 38
5.1.1. 解释对象数据库系统中面向对象的相关概念 .......................... 38 5.1.2. 从概念上比较对象数据库模型与对象关系模型 ........................ 38 5.1.3. 利用左深树、右深树、浓密树来进行查询优化的各自特点 .............. 38 5.1.4. 试解释影响并行数据库系统中并行算法性能的三个因数 ................ 39 5.1.5. 简述用爬山算法进行查询优化的基本思想 ............................ 39 5.2. 下面是某个公司一个人事关系数据库的全局模式： EMP={ENO*,ENAME,POSITION,PHONE} PAY={POSITION*,SALARY} ENO为职员号，POSITION为岗位。SALARY表示岗位对应的工资，*对应的属性表示主关键字。该公司分布在两个场地上，其中，在场地1经常处理所有职员数据，而场地2只处理工资低于1000的职员数据，为了节省磁盘空间和增大处理局部性： .............................. 40
5.2.1. 将以上全局关系进行分片设计，写出分片定义和分片条件。 ............ 40 5.2.2. 指出分片的类型，并画出分片树。 .................................. 40 5.2.3. 给出分配设计。 .................................................. 40 5.3. 对题二所确定的分片模式，要求查询岗位为“salesman”的所有职员的姓名和工资，写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询树。假设“salesman”的工资为800元。要求给出中间转换过程。 ............. 41
5.3.1. 进行全局优化，画出优化后的全局查询树。 .......................... 41 5.3.2. 进行分片优化，画出优化后的分片查询树。 .......................... 41 5.4. 按如下给出的条件，求出半连接优化计划和执行场地，并作后优化处理 ..... 42 5.5. 下面是当一个数据库系统出现故障时，日志文件中的信息 ................. 47
5.5.1. 画出对应的事务并发执行图。 ...................................... 48 5.5.2. 找出发生故障时系统中的活动事务，确定出反做和重做事务集。 ........ 48 5.5.3. 指出需要undo的和redo的数据记录。 ................................ 49 5.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)表示。对任何数据的加锁可在事务开始后立即进行）。 ........................... 49
5.6.1. 局部是不可串行化的。 ............................................ 49 5.6.2. 局部是可串行化的，而全局是不可串行化的。 ........................ 49 5.6.3. 局部是可串行化的，全局也是可串行化的。 .......................... 50 5.7. 设计一种满足下列要求的索引结构。 ................................... 51
5.7.1. 被索引的数据集合为有序集 ........................................ 51 5.7.2. 在有序集上的查询操作都是基于位置来进行的 ........................ 51 5.7.3. 当往有序集中插入或删除一个元素时，与该元素相关的后续元素的位置均要发生变化 ............................................................... 51 5.7.4. 元素的类型可为任意类型（这一个小问题的解决需要考虑语言的特征） .. 51
6. 二零一春季试题 ............................................................ 51
6.1. ...................................................................... 51
6.1.1. 讨论集中式数据库和分布式数据库各自的优缺点。 .................... 51 6.1.2. 讨论在局域网和广域网两种情况下分布库设计的区别。 ................ 51 6.1.3. 解释分片透明性、复制透明性和位置透明性等三级透明性的区别。 ...... 51 6.1.4. 解释2PC协议如何在故障情况下保证事务的原子性的 ................... 52 6.1.5. 解释严格2PL协议与基本2PL协议的区别 .............................. 53 6.2. 下面是某个公司一个人事关系数据库的全局模式： EMP={ENO*,ENAME,POSITION,PHONE} PAY={POSITION*,SALARY} ENO为职员号，POSITION为岗位。SALARY表示岗位对应的工资，*对应的属性表示主关键字。该公司分布在两个场地上，其中，在场地1经常处理所有职员数据，而场地2只处理工资低于1000的职员数据，为了节省磁盘空间和增大处理局部性： .............................. 53
6.2.1. 将以上全局关系进行分片设计，写出分片定义和分片条件。 ............ 53 6.2.2. 指出分片的类型，并画出分片树。 .................................. 53 6.2.3. 给出分配设计。 .................................................. 54 6.3. 对题二所确定的分片模式，要求查询岗位为“salesman”的所有职员的姓名和工资，写出的在全局模式上的SQL查询语句，并要求转换成相应的关系代数表示，画出全局查询树。假设“salesman”的工资为1500元。要求给出中间转换过程。 ............ 54
6.3.1. 进行全局优化，画出优化后的全局查询树 ............................ 54 6.3.2. 进行分片优化，画出优化后的分片查询树。 .......................... 55 6.4. 下面是当一个数据库系统出现故障时，日志文件中的信息 ................. 56
6.4.1. 画出对应的事务并发执行图。 ...................................... 57 6.4.2. 找出发生故障时系统中的活动事务，确定出反做和重做事务集。 ........ 57 6.4.3. 指出需要undo的和redo的数据记录。 ................................ 57 6.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)表示。对任何数据的加锁可在事务开始后立即进行）。 ........................... 58
6.5.1. 局部是不可串行化的。 ............................................ 58 6.5.2. 局部是可串行化的，而全局是不可串行化的。 ........................ 58 6.5.3. 局部是可串行化的，全局也是可串行化的。 .......................... 59
1. 九八年秋季试题
1.1. 概念题
1.1.1.比较半联接方法和枚举法的优缺点。
半联接技术缩减了连接操作的操作数，以降低通信费用。枚举法适用于缩减局部代价的情况。
评估查询操作的代价需要综合考虑局部代价和传输代价。侧重哪一个方面，需根据系统组成环境确定。如侧重传输代价，局部代价可以忽略不计时，采用半联接技术较好；相反，如果侧重局部代价时，采用直接连接比采用半连接技术优越。因为直接连接技术实现简单，枚举法是基于直接连接的实现方法，此时应采用枚举法。 半连接优点：传输代价低。
半连接缺点：没有考虑局部代价；当“选择度”交低时，半连接技术才可行。
1.1.2. 2PL协议的基本思想。 2PL协议的基本思想。
并发控制是分布式事务管理的基本任务之一。其目的是保证分布式数据库系统中多个事务的高效正确的执行。有两种模型来实现：其中之一是以“锁”方式为基础的形式模型，一种是以时间印方式为基础的时间模型。
锁方式的基本思想是：事务对任何数据的操作必须先申请数据项的锁，只有申请到了锁之后，即加锁成功以后，才可以对数据项进行操作。操作完成了以后，要释放已经申请的锁。通过锁的共享和排斥的特性，实现事务的可串行化调度。
“锁”又可分为“读锁”和“写锁”：
“读锁”是对数据项进行读操作时要加的锁。由于读操作是可共享操作，所以“读锁”也称为共享锁。
“写锁”是对数据进行写入操作时要加入的锁。写操作是不可共享的锁，因此也叫“排它锁”。
2PL(两阶段锁)协议是并发控制算法中的重要算法。其主要内容是并发执行的多个事务，在对数据进行操作以前要进行加锁，并且每个事务中的所有加锁操作都得在第一个解锁操作以前执行。因此，每个事务中的加锁操作和解锁操作分布在两个部分中，所以此协议称为2PL协议。 在分布式数据库系统中，如果全部的分布式事务均以2PL协议加锁，则系统中各个场地上的局部调度是可串行化的。因为对每个局部场地而言，其上执行的操作只是全局操作的一部分，而全局操作采用2PL协议加锁，显然局部操作也遵循2PL协议。
1.1.3. WAL协议的主要思想。 系统的故障恢复是以日志文件为基础完成的，因此，要求事务在执行过程中满足先写日志协议（WAL）（Write_ahead logging）。当系统发生故障时，可有效地采用重做（redo）和反做（undo）两个基本恢复操作进行恢复。
先写日志协议（WAL）含义：
（1） 在外存数据库被更新之前，应将日志文件中的反做信息写入外存文件； （2） 事务提交之前，日志文件中的有关重做信息应在外存数据库更新之前写入外存文件。