2003硕士复试数据库试题（开卷）
准考证号（最后4位）4068 姓名 刘瑜 成绩 _________
一、简要回答下述问题（18分）
1、 简述DBMS的主要功能。
答：DBMS的主要功能为
1） 数据库的定义功能，它提供数据定义语言（DDL）来定义数据库的三级结构。
2） 数据库的操纵功能，它提供数据操纵语言（DML）实现对数据库的操作。
3） 数据库的保护功能，它是通过数据库的并发控制，数据库的恢复，数据完整性控制，数据安全性控制这四个子系统实现的
4） 数据库的维护功能，它包含数据库的初始数据载入，转换，转储，数据库的改组以及性能监视，分析等功能。
5） 数据字典，它管理着数据库三级结构的定义
2、 试述数据库系统的三级模式结构，并指出DBTG和IMS系统中与之相应关系。
答：数据库系统的三级模式结构是指数据库系统是由外模式，模式和内模式构成。
模式也称逻辑模式，是数据库全体数据的逻辑结构和特征描述，是所有用户的公共数据视图。
外模式也称子模式，是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图。
内模式也称存储模式，是数据物理结构和存储方式的描述，是数据在数据库内部的表示方法。
在DBTG和IMS系统中与之相应分别为 模式，子模式，物理模式

3、 什么是系值选择？为什么要有系值选择？在DBTG中如何定义系值选择？
答：系值选折主要是DBTG（网状模型）的主要问题，它是指选择两个结点之间一条路径即确定两个实体之间一种联系。
因为在网状模型中两个结点之间存在不同的路径这就有必要选择一条路径，以确定两个实体间的联系。
在DBTG中选择两个结点之间最短路径作为两个实体之间的联系。
4、对如下关系R，指出是否存在多值依赖C→→HR？为什么？

C T H R S G
C-1 T-1 H1 R1 S1 G1
C1 T-1 H2 R2 S1 G1
C1 T1 H1 R1 S2 G2
解：不存在多值依赖C→→HR,因为当属性C的取值确定以后，属性H，R的取值确定了T，S，G的取值。即H，R的取值与T，S，G的取值相关。所以对于C的每一个值C-1或C1，当T，S，G的取值不同时，H，R不存在一个完整的集合与之对应。
5、简述关系系统的分类。
答：关系系统可分为最小关系系统，关系完备的系统和全关系系统
最小关系系统仅仅支持关系数据结构和三种关系操作----选择，投影和连接运算
关系完备系统支持关系数据结构和所有的关系代数操作
全关系系统不仅是关系上完备的而且支持数据结构中域的概念，支持实体完整性和参照完整性。

6、简述利用日志文件恢复事务的过程。
答：系统恢复的步骤为
1） 向扫描文件日志即从最后向前扫描日志文件，查找该事务的更新操作
2） 对该事务的更新操作执行逆操作。即将日志记录中“更新前的值”写入数据库。这样，如果记录中是插入操作，即相当与做删除操作；若记录中是删除操作，则作插入操作；若是修改操作，则相当于用修改前的值代替修改后的值。
3） 继续反向扫描日志文件，查找该事务的其他更新操作，并作同样处理。
4） 如此处理下去，直至读到此事务的开始标记，事务恢复就完成了。

二、试述ER模型向网状、层次、关系模型的转换方法。（6分）
答：ER模型向网状模型的转换：若实体间联系是1 ：1或1 ：N可以直接转换，用接点表示记录类型，用箭头表示从箭尾的记录类型到箭头的记录类型间联系是1 ：1或1 ：N。若实体间联系是M ：N 的，则把两个实体间的联系也看作是一个实体，但是一个复合型实体。即把一个M ：N联系拆分成两个1 ：N联系。
ER模型向层次模型的转换：若实体间联系是1 ：1或1 ：N同样可以直接转换，用接点表示记录类型，用箭头表示从箭尾的记录类型到箭头的记录类型间联系是1 ：1或1 ：N。若实体间联系是M ：N 时
分别用两个1 ：N的联系表示。比如S→C是一个M ：N型（S，C为实体），则可用层次模型表示为两个1 ：N型S→C，C→S（S，C为结点）。
ER模型向关系模型的转换：对于不同的联系类型，不同的情况有不同的处理方法
1） 若实体间联系是1 ：1的，可以在两个实体类型转换成两个关系模式中任意一个关系模式的属性中加入另一个关系模式的键和联系类型的属性。
2） 若实体间的联系是1 ：N的，则在N端实体类型转换成的关系模式中加入1端实体类型转换成的关系模式的键和联系类型的属性。
3） 若实体间联系是M ：N 的，则将联系类型也转换成关系模式，其属性为两端实体类型的键加上联系类型的属性，而键为两端实体键的组合。

三、供应商--零件-工程项目数据库由以下四个关系模式构成：（15分）
S(S#,SNAME,STATUS,CITY)
P(P#,PNAME,COLOR,WEIGHT,CITY)
J(J#,JNAME,CITY)
SPJ(S#,P#,J#,QTY)
供应商S，零件P和工程项目J分别由供应商（S#），零件号（P#）和工程项目号（J#）唯一标识，供货SPJ是反映由某个工程项目供应某些数量的某种零件。
请用SQL语言完成的工程项目提供的不同零件号。
1、 找出给上海的工程项目提供的不同零件号。
SELECT DISTINCT P#
FROM J，SPJ
WHERE J.J# =SPJ.J# AND J.CITY =‘上海’
2、 将没有供货的所有工程项目从J中删去。
DELETE FROM J
WHERE J# NOT IN
(SELECT J#
FROM SPJ)
3、 查询提供零件的供应商名。
SELECT SNAME
FROM S
WHERE S# IN
(SELECT S#
FROM SPJ)
4、 查询这样的工程项目号：供给该工程项目的零件P1的平均供应量大于供给工程项目J1的任何零件中的最大供应量。
SELECT J#
FROM SPJ
WHERE SPJ.P#=P1
GROUP BY J#
HAVING AVG(QTY)>ALL
(SELECT QTY
FROM SPJ
WHERE SPJ.J# =’J1’)
5、 定义一个视图，它由所有这样的工程项目（工程项目号与所在城市名称）组成：它们由供应商S1供货且使用零件P1。
CREATE VIEW J.CITY
AS SELECT J#, CITY
FROM J
WHERE J.J#=SPJ.J# AND
SPJ.S# =’S1’AND
SPJ.P# =’P1’
四、学生一选课数据库由以下三个关系模式组成：（9分）
S（S#，SNAME，AGE，SEX）
S（S#，C#，GRADE）
G（C#，CNAME，TECHER）
三个关系模式的主码分别为S#，（S#，C#），C#。现有一查询语句；找出至少选修了赵老师一门课程的男学生的学号、姓名、所学课程的课程号，以及成绩，现要求：
1、 试写出该查询的关系代数表达式。
∏S#，SNAME，C#，GRADE（?SEX=‘男’∧TEACHER=‘赵老师’（S∞SC∞C））

2、 画出该表达式的语法树。

∏
S#，SNAME，C#，GRADE
?
TEACHER=‘赵老师’ ∧SEX=‘男’
∏
S#, SNAME，C#，GRADE,AGE,SEX,CNAME,TEACHER,

?
SC.C# =C.C#∧SC.S# =S.S#

S

SC C
3、 用关系代数表达式优化算法对上述语法树进行优化处理，并画出优化后的语法树。
∏S#，SNAME，C#，GRADE((∏S#，C#，GRADE(SC∞∏C#( ?TEACHER=‘赵老师’(C)))) ∞
(∏S#，SNAME(?SEX=‘男’(S)))

优化树：
∏
S#，SNAME，C#，GRADE
?
SC.S# =S.S#

∏ ∏
SC.S#,C#,GRADE S.S#,SNAME
? ?
SC.C# =C.C# SEX=‘男’

S

SC ∏
C.C#
?
TEACHER=‘赵老师’
C

五、试论证SQL语言是完备的关系数据语言。（12分）
选做题、试述ARMSTRONG公理系统及其推理规则——自反律、增广律、传递律，并证明推理规则的正确性。
ARMSTRONG公理系统:设U为属性集总体,F是U上的一组函数依赖,于是关系模式R﹤U，F﹥有以下的推理规则:
1) A1自反律,若Y?X?U,则X→Y为F所蕴含
2) A2增广律, 若X→Y为F所蕴含,且Z?U,则XZ→YZ为F所蕴含
3) A3传递律，X→Y及Y→X为F所蕴含，则X→Z 为F所蕴含
证明：（1）设Y?X?U
对R﹤U，F﹥的任一关系r中的任意两个元组t,s:若t[x]=s[x],由于Y?X，有t[y]=s[y]
所以X→Y成立，自反律得证。
（2）设X→Y为F所蕴含，且Z?U。
R﹤U，F﹥的任一关系r中的任意两个元组t,s:若t[xZ]=s[xZ] 则有t[x]=s[x]和t[Z]=s[Z]
由X→Y，于是t[y]=s[y]，所以t[yZ]=s[yZ]，所以XZ→YZ为F所蕴含增广律得证。
（3）设X→Y及Y→X为F所蕴含
对R﹤U，F﹥的任一关系r中的任意两个元组t,s:若t[x]=s[x],由于Y?X，有t[y]=s[y]再由
Y→Z有t[Z]=s[Z]，所以X→Z为F所蕴含，传递律得证。

证明SQL语言是完备的关系数据语言
证：因为完备关系系统的条件是必须支持关系数据结构和所有的关系代数操作。而SQL语言是基于关系数据模型的数据语言。它支持数据库系统的三级逻辑结构，并且集数据定义语言DDL，数据操纵语言DML，数据控制语言DCL的功能于一体。在功能上完全可以与关系代数等价。也就是所有的关系代数运算---并，差，交，广义笛卡尔积，选择，投影，连接，除均可用SQL语言完成。所以SQL语言满足完备关系系统数据语言的条件。证得SQL语言是完备的关系数据语言。