2006-2007(2)数据库系统原理试题(A)参考答案及评分标准

2006-2007（2）数据库系统原理试题(A)参考答案及评分标准一、填空题（本大题共10小题，每题1空，每空2分，总计20分）1 串行的 隔离的（或独立的）2 非主属性（或非键属性）3 BC4 稀疏5 代数操作6 实体完整性约束7 数据描述语言(或数据定义语言)8 关系运算（或数据操作）9 无损连接性二、单选题（本大题共10小题，每题1分，总计10分）1A 2A 3B 4A 5C 6A 7C 8C 9D 10C三、简答题（每题4分，总计16分）1、 什么是事务的调度？如何判断一个调度是不是冲突可串行的？答：N个事务的一个调度S是N个事务的所有操作的一个序列，表示这些操作的执行顺序，并且满足对于N个事务中的每个事务T，如果操作i在T中先于操作j执行，则在S中操作i也必须先于操作j执行。（2分）构造调度S的前趋图，如果前趋图有回路，则S不是冲突可串行的；如果前趋图不包含回路，则S是冲突可串行的。（2分）2、 简述逻辑数据库设计的步骤。答： 形成初始关系数据库模式，关系模式规范化，关系模式优化，定义关系上的安全性和完整性约束，子模式定义，性能估计。以上6步答对4步给4分，每步1分。3、 什么是数据库？什么是数据库管理系统？答：数据库是相互关联的数据集合。（2分）数据库管理系统是一个通用的软件系统，由一组计算机程序构成。数据库管理系统能够对数据库进行有效的管理，包括存储管理、安全性管理、完整性管理等。（2分）4、 投影操作要求结果去重或不去重时，算法的磁盘读写块数分别是多少？答：设投影关系为R，BR表示R的磁盘块数，L是投影结果元组的字节数，b是一个数据块所包含的字节数。结果不去重时存取的磁盘块数是O(BR +nL/b)。（2分）结果去重时存取的磁盘块数至多为O(BR + nL/b logM(nL/b) + nL/b)。（2分）四、综合题（一） （8分）现有关系数据库如下：学生(学号，姓名，性别，专业，奖学金)课程(课号，课名，学分) 学习(学号，课号，分数) 用关系代数实现下列查询： 1 检索“国际贸易”专业中获得奖学金1000元的学生信息，包括学号、姓名、课名和分数； 用SQL语句实现下列查询：2 检索没有任何一门课程成绩在80分以下的学生的信息，包括学号、姓名和专业； 3 对成绩得过满分(100分)的学生，如果没有获得奖学金的，将其奖学金设为1000元。 答：（答案不唯一）1学号，姓名，课名，分速(专业=国际贸易奖学金=1000(学生) 课程 学习) （3分）2. SELECT 学号，姓名，专业 FROM 学生 EHERE NOT EXITS (SELECT * FROM 学习 WHERE 学习.学号学生.学号 AND 学习.分数80) （3分）2 UPDATE 学生 SET 奖学金=1000 WHERE 奖学金 IS NULL and （EXITS SELECT * FROM 学习 WHERE 分数=100 and 学习.学号=学生.学号）（2分）（二）（12分）现有如下关系模式： R(A，B，C，D，E) ，R上的函数依赖集F=ABE，BC，CD 。1. 该关系模式最高满足第几范式并说明原因。2. 如果将关系模式R分解为R1(A，B，E)和R2(B，C，D)，指出关系模式R2的码，并说明该关系模式最高满足第几范式?。 3. 判断2中的分解是否具有无损连接性。4. 将关系模式R分解成具有无损连接性的BCNF。 答：1. 该关系模式的候选键为AB。因为BC，所以非键属性C部分依赖于候选键AB，所以该关系模式不是2NF，最高是1NF。（3分） 2. F在R2上的投影为BC，CD，候选键是B。不存在非键属性对候选键的部分依赖，但是有BC，CD，且C B，因此非键属性D传递依赖于键B，因此R2不是3NF，最高满足2NF。（3分）3. 设U1和U2分别是R1和R2的属性集合。U1U2B，U1U2AE，BAE不属于F+，U2U1CD，BCD属于F+，所以有U1U2U2U1，所以分解具有无损连接性。（3分）4. 因为BC，决定因素B不是键，因此把R分解成R1(BC)和R2(ABDE)。其中R1上的函数依赖集合F1=BC，候选键是B，因此是BCNF。R2上的函数依赖集合F2ABE，候选键为ABD，非BCNF，进一步分解为R21(ABE)和R22(ABD)。R21上的函数依赖集合F21= ABE ，候选键是AB，是BCNF。R22的候选键是全键，函数依赖依赖集合为空集，也是BCNF。因此原关系模式R分解成R1、R21、R22。（3分，此题的分解方法不唯一）（三）（10分）一个图书借阅数据库系统要求提供下述服务：可随时查询书库中现有书籍的名称、品种、数量与存放位置，所有各类书籍均可由书号唯一标识；可随时查询书籍借还情况。包括借书人单位、姓名、借书证号、借书日期和还书日期。约定：任何人可借多种书，任何一种书可为多个人所借，借书证号具有唯一性；当需要时，可通过数据库中保存的出版社电报编号、电话、邮编及地址等信息向有关书籍的出版社增购有关书籍。约定：一个出版社可出版多种书籍，同一本书仅为一个出版社出版，出版社名具有唯一性。 1根据上述语义画出ER图，要求在图中画出属性并注明联系的类型。（6分，其中实体2分、联系2分、属性2分）2将ER模型转换成关系模型，并指出每个关系模式的主键和外键。（共4分，每个完整的关系模式1分，若关系模式的属性描述正确但主键或外键有错误时适当给分）NM1N书籍出版社借书人借阅名称品种数量存放位置书号姓名借书证号单位还书日期借书日期出版邮编地址出版社名 电话电报编号 书籍（书号，名称，品种，数量，存放位置，出版社名） 出版社名为外键出版社（出版社名，电报编号，电话，邮编，地址） 无外键借书人（借书证号，姓名，单位）无外键借阅（书号，借书证号，借书日期，还书日期） 书号和借书证号都是外键其中下划线表示主键（或把出版联系单独形成一个关系模式，即5个关系模式）（四）（12分）设文件F具有10000个记录，每个记录50字节，其中10字节用来表示文件的键值。每个磁盘块大小1000字节，指向磁盘块的指针占5字节，不允许记录跨两个块。1 存放整个文件需要多少个磁盘块？如果F是顺序文件，查找一个记录需要多少次磁盘I/O？如果F无序，查找一个记录需要多少次磁盘I/O？2 如果为文件F建立主索引，索引文件占用多少磁盘块？利用这个主索引查询需要多少次磁盘I/O？答：1. 每个磁盘块能存放记录数：1000/5020个。整个文件占用的磁盘块数：10000个记录/20个每块500块。(2分) 如果F是顺序文件，查找一个记录需要的磁盘I/O数：log25009块。(2分) 如果F无序，查找一个记录需要的磁盘I/O数：500/2=250块。(2分)2. 每个磁盘块能存放记录数：1000/5020个。整个文件占用的磁盘块数：10000个记录/20个每块500块。因为主索引为稀疏索引，数据文件的每个磁盘块对应一个索引项，因此主索引共有500个索引项。每个索引项存放一个键值指针对，共10+5=15字节。每个磁盘块能存放索引项个数为1000/1566个。因此索引文件占用的磁盘块数为500/668块。（3分）利用主索引查询，需要读索引文件log28=3块，数据块1块，因此利用这个主索引查询某记录需要3+1=4次磁盘I/O。（3分）（五）（12分）设教学数据库有三个关系：学生关系：S(S#, SNAME, AGE, SEX)选课关系：SC(S#,C#,GRADE)课程关系：C(C#,CNAME,TEACHER)数据库上的一个查询为“检索男同学选修课程的课程名和任课教师名”。1 写出该查询的初始关系代数表达式。2 画出初始关系代数表达式对应的查询树。3 使用启发式代数优化规则对该查询进行优化，画出优化的过程和最后结果。1 初始关系代数表达式：(3分)CNAME,TEACHERsSEX=男AND S.S#=SC.S# AND SC.C#=C.C#(SSCC)2 初始关系代数表达式对应的查询树：(3分，若初始关系代数有误且查询树与其对应，若查询树正确则给满分)SCSCCNAME,TEACHERsSEX=男AND S.S#=SC.S# AND SC.C#=C.C#3 优化的过程及结果（共6分，其中过程3分，结果3分。过程只需要画出1棵树，过程对应的查询树不唯一）sSEX=男s S.S#=SC.S#SCSCCNAME,TEACHERs SC.C#=C.C#选择下移S#S.S#=SC.S#sSEX=男SC.C#SCSCCNAME,TEACHER最后结果SC.C#=C.C#C#, S#