第6章　关系数据理论

1理解并给出下列术语的定义：

函数依赖、部分函数依赖、完全函数依赖、传递依赖、候选码、主码、外码、全码、1NF、2NF、3NF、BCNF、多值依赖、4NF。

答：（1）函数依赖：设R（U）是属性集U上的关系模式。X，Y是属性集U的子集。若对于R（U）的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作X→Y。（即只要X上的属性值相等，Y上的值一定相等。）

（2）部分函数依赖：若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：

（3）完全函数依赖：在R（U）中，如果X→Y，并且对于X的任何一个真子集X′，都有X→Y，则称Y对X完全函数依赖，记作

（4）传递依赖：在R（U）中，如果X→Y，（Y⊈X），Y↛X，Y→Z，Z∉Y，则称Z对X传递函数依赖，记为：

（5）候选码：设K为R<U，F>中的属性或属性组合，若，则K为R的候选码。

（6）主码：若候选码多于一个，则选定其中的一个为主码。

（7）外码：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，也称外码。

（8）全码：整个属性组是码，称为全码。

（9）1NF：关系模式R的每一个分量是不可再分的数据项。

（10）2NF：关系模式R∈1NF，且每一个非主属性完全函数依赖于码。

（11）3NF：关系模式R<U，F>中不存在这样的码X、属性组Y及非主属性Z（Z不是Y的子集）使得X→Y，Y↛X，Y→Z成立。

（12）BCNF：关系模式R<U，F>∈1NF，X→Y且Y不是X的子集时，X必含有码。

（13）多值依赖：设R（U）是属性集U上的一个关系模式。X，Y，Z是U的子集，并且Z＝U－X－Y。关系模式R（U）中多值依赖x→→y成立，当且仅当对R（U）的任一关系r，给定的一对（x，z）值，有一组y的值，这组值仅仅决定于X值而与Z值无关。

（14）4NF：关系模式R<U，F>∈1NF，如果对于R的每个非平凡多值依赖X→→Y（Y不是X的子集，Z＝U－X－Y不为空），X都含有码。

2建立一个关于系、学生、班级、学会等诸信息的关系数据库。

描述学生的属性有：学号、姓名、出生年月、系名、班号、宿舍区；

描述班级的属性有：班号、专业名、系名、人数、入校年份；

描述系的属性有：系号、系名、系办公室地点、系人数；

描述学会的属性有：学会名、成立年份、地点、学会会员人数。

有关语义如下：一个系有若干专业，每个专业每年只招一个班，每个班有若干学生。一个系的学生住在同一宿舍区。每个学生可参加若干学会，每个学会有若干学生。学生参加某学会有一个入会年份。

请给出关系模式，写出每个关系模式的极小函数依赖集，指出是否存在传递函数依赖，对于函数依赖左部是多属性的情况讨论函数依赖是完全函数依赖，还是部分函数依赖。

指出各关系的候选码、外部码，是否有全码存在。

答：（1）关系模式如下：

学生：S（Sno，Sname，Sbirth，Dept，Class，Rno）

班级：C（Class，Pname，Dept，Cnum，Cyear）

系：D（Dept，Dno，Office，Dnum）

学会：M（Mname，Myear，Maddr，Mnum）

（2）每个关系模式的最小函数依赖集如下：

①学生S（Sno，Sname，Sbirth，Dept，Class，Rno）的最小函数依赖集如下：

Sno→Sname，Sno→Sbirth，Sno→Class，Class→Dept，DEPT→Rno。

传递依赖如下：

由于Sno→Dept，而Dept→Sno，Dept→Rno（宿舍区），所以Sno与Rno之间存在着传递函数依赖；由于Class→Dept，Dept→Class，Dept→Rno，所以Class与Rno之间存在着传递函数依赖；由于Sno→Class，Class→Sno，Class→Dept，所以Sno与Dept之间存在着传递函数依赖。

②班级C（Class，Pname，Dept，Cnum，Cyear）的最小函数依赖集如下：

Class→Pname，Class→Cnum，Class→Cyear，Pname→Dept。

由于Class→Pname，Pname→Class，Pname→Dept，所以C1ass与Dept之间存在着传递函数依赖。

③系D（Dept，Dno，Office，Dnum）的最小函数依赖集如下：

Dept→Dno，Dno→Dept，Dno→Office，Dno→Dnum。

Dept与Office，Dept与Dnum之间不存在传递依赖。

④学会M（Mname，Myear，Maddr，Mnum）的最小函数依赖集如下：

Mname→Myear，Mname→Maddr，Mname→Mnum。

该模式不存在传递依赖。

（3）各关系模式的候选码、外部码，全码如下：

①学生S候选码：Sno；外部码：Dept、Class；无全码。

②班级C候选码：Class；外部码：Dept；无全码。

③系D候选码：Dept或Dno；无外部码；无全码。

④学会M候选码：Mname；无外部码；无全码。

3试由Armostrong公理系统推导出下面3条推理规则：

（1）合并规则：若X→Z，X→Y，则有X→YZ；

（2）伪传递规则：由X→Y，WY→Z，有XW→Z；

（3）分解规则：X→Y，Z⊆Y，有X→Z。

答：（1）已知X→Z，由增广律知XY→YZ，又因X→Y，可得XX→XY→YZ，根据传递律得X→YZ。

（2）已知X→Y，由增广律知XW→WY，又因WY→Z，可得XW→WY→Z，根据传递律得XW→Z。

（3）已知Z⊆Y，由自反律知Y→Z，又因X→Y，所以由传递律可得X→Z。

4关于多值依赖的另一种定义是：

给定一个关系模式R（X，Y，Z），其中X、Y、Z可以是属性或属性组合。

设x∈X，y∈Y，z∈Z，xz在R中的像集为Y_xz＝{r.Y|r.X＝x∧r.Z＝z∧r∈R}；

定义R（X，Y，Z）当且仅当Y_xz＝Y_xz′，对于每一组（x，z，z′）都成立，则Y对X多值依赖，记作X→→Y。这里允许Z为空集，当Z为空集时，称为平凡的多值依赖。

请证明这里的定义和讲义中定义等价的。

答：设Y_xz＝Y_xz′对于每一组（x，z，z′）都成立，现证其能推出讲义中定义的条件：

设s，t是关系r中的两个元组，s[X]＝t[X]，由新定义的条件可知对于每一个z值，都对应相同的一组y值。这样一来，对相同的x值，交换y值后所得到的元组仍然属于关系r，即讲义中多值依赖的条件成立。

如果讲义定义的条件成立，则对相同的x值，交换y值后所得的元组仍属于关系r，由于任意性及其对称性，可知每个z值对应相同的一组y值，所以Y_xz＝Y_xz′对于每一组（x，z，z′）都成立。

综上可知，两者是等价的。

5试举出3个多值依赖的实例。

答：（1）关系模式MSC（M，S，C）中，M表示专业，S表示学生，C表示该专业的必修课。假设每个专业有多个学生，有一组必修课。设同专业内所有学生选修的必修课相同，实例关系如下。按照语义对于M的每一个值Mi，S有一个完整的集合与之对应而不论C取何值，所以M→→S。由于C与S的完全对称性，必然有M→→C成立。

（2）关系模式ISA（I，S，A）中，I表示学生兴趣小组，S表示学生，A表示某兴趣小组的活动项目。假设每个兴趣小组有多个学生，有若干活动项目。每个学生必须参加所在兴趣小组的所有活动项目，每个活动项目要求该兴趣小组的所有学生参加。按照语义有I→→S，I→→A成立。

（3）上课（学号，教师工号，教室），一个学生可由多个教师来教，一个学生可在多教室上课，而且一个教师可在多个教室上课，一个教室可由多个教师上课。所以存在如下多值依赖：学号→→教师工号和学号→→教室。

6试证明书上给出的关于FD和MVD公理系统的A₄、A₆和A₈。

答：A₄：若X→→Y，V⊆W⊆U，则XW→→YV。设Z＝U－X－Y，已知X→→Y，设r是R上的任一关系，s、t∈r，且t[X]＝s[X]，则存在元组p、q∈r，使p[X]＝q[X]＝t[X]，而p[Y]＝t[Y]，p[Z]＝s[Z]，q[Y]＝s[Y]，q[Z]＝t[Z]。设t[XW]＝s[XW]，我们以上构造的元组p和q，是某部分属性在s和t上翻转而成，所以p[W]＝q[W]，可知p[XW]＝q[XW]，同理p[YV]＝t[YV]（由V⊆W知t[V]＝s[V]），q[YV]＝s[YV]，p[U－YV－XW]＝s[U－YV－XW]（因为U－YV－XW⊆Z），q[U－YV－XW]＝t[U－YV－XW]。所以XW→→YV。

A₆：若X→→Y，Y→→Z则X→→Z－Y。由Y→→Z容易证得Y→→Z－Y。设R₁＝U－X－Y，R₂＝U－Y－Z，R₃＝U－X－Z＋Y。已知X→→Y，设r是R上的任一关系，s，t∈r，且t[X]＝s[X]，则存在元组p，q∈r，使p[X]＝q[X]＝t[X]，而p[Y]＝t[Y]，p[R1]＝s[R1]，q[Y]＝s[Y]，q[R₁]＝t[R₁]。对元组t、p，已知t[Y]＝p[Y]，t[X]＝p[X]，由Y→→Z－Y知：存在元组m∈r，使m[Z－Y]＝p[Z－Y]，m[R₂]＝t[R₂]。因为（Z－Y）⊆R₁，又p[R₁]＝s[R₁]，所以m[Z－Y]＝s[Z－Y]。因为元组p和s在除属性Y之外的属性上值相等，所以m[R₂]＝t[R₂]，另外元组m是由元组t和p交换某些属性上的值而产生的，而t和p在属性X上值相等，显然m[X]＝t[X]，所以m[U－（Z－Y）]＝t[U－（Z－Y）]，即m[R₃]＝t[R₃]。对元组s、q，同理可知s[Y]＝q[Y]，存在元组n，使n[Z－Y]＝t[Z－Y]，即n[R₃]＝s[R₃]。综上所述，对t、s∈r，t[X]＝s[X]，存在元组m、n∈r，使m[X]＝n[X]＝t[X]，而m[Z－Y]＝s[Z－Y]，m[R₃]＝t[R₃]，n[Z－Y]＝t[Z－Y]，n[R₃]＝s[R₃]。

A₈：若X→→Y，W→Z，W∩Y＝Φ，Z⊆Y，则X→Z。设r是R上的任一关系，对任意s，t∈r，若t[X]＝s[X]，设R₁＝U－X－Y，则根据X→→Y知：存在元组p，q∈r，使p[X]＝q[X]＝t[X]，而p[Y]＝t[Y]，p[R₁]＝s[R₁]，q[Y]＝s[Y]，q[R₁]＝t[R₁]。因为W∩Y＝Φ，所以s[W]＝p[W]，又W→Z，所以s[Z]＝p[Z]；因为Z⊆Y，且p[Y]＝t[Y]，所以p[Z]＝t[Z]；所以可得t[Z]＝s[Z]，即X→Z。

7设关系模式为R（U，F），X，Y为属性集，X，Y∈U。

证明：（1）X⊆X_F^＋

（2）（X_F^＋）_F^＋＝X_F^＋

（3）若X⊆Y，则X_F^＋⊆Y_F^＋

（4）U_F^＋＝U

答：（1）因为X→X，所以X⊆X_F^＋。

（2）任意A⊆（X_F^＋）_F^＋，存在B⊆X_F^＋，使B→A能由F根据Armstrong公理导出，从而B⊆X_F^＋能由F根据Armstrong公理导出，根据公理中的传递律可知，X→A能由F根据Armstrong公理导出，所以A⊆X_F^＋，因此（X_F^＋）_F^＋＝X_F^＋。

（3）对任意A⊆X_F^＋，可知X→A能由F根据Armstrong公理导出，因为X⊆Y由自反律可知Y→X，由传递律可知Y→A，所以A⊆X_F^＋，所以X_F^＋⊆Y_F^＋得证。

（4）要证明U_F^＋＝U，只要证明U⊆U_F^＋且U_F^＋⊆U。

自反律：Y⊆U，U→Y为F所蕴含，显然U由F根据Armstrong公理的自反律推出的Y仍属于U；

增广律：U→Y为F所蕴含，Z⊆U，则UZ→YZ为F所蕴含，YZ⊆U；

传递律：U→Y和Y→Z为F所蕴含，则U→Z为F所蕴含，所以Z⊆U。

8设关系模式为R（U，F），若X_F^＋＝X，则称X相对于F是饱和的。定义饱和集φ_F＝{X|X＝X_F^＋}，试证明φ_F＝{X_F^＋|X⊆U}。

答：（1）对于任意A∈φ_F，由已知条件的A＝A_F^＋，因为A⊆U，A＝A_F^＋，所以A∈{X_F^＋|X⊆U}。

（2）对任意A∈{A_F^＋|A⊆U}，因为（A_F^＋）_F^＋＝A_F^＋，令B＝A_F^＋，有B_F^＋＝B，所以B∈φ_F，即A_F^＋∈φ_F，A∈φ_F得证。

9图6-1表示一个公司各部门的层次结构。

图6-1　部门层次结构

对每个部门，数据库中包含部门号D#（唯一的）、预算费（BUDGET）以及此部门领导人员的职工号E#（唯一的）信息。

对每一个部门，还存有关于此部门的全部职工、生产与科研项目以及办公室的信息。

职工信息包括：职工号、他所参加的生产与科研项目号（J#）、他所在办公室的电话号码（PHONE#）。

生产科研项目包含：项目号（唯一的）、预算费。

办公室信息包含办公室房间号（唯一的）、面积。

对每个职工，数据库中有他曾担任过的职务以及担任某一职务时的工资历史。

对每个办公室包含此办公室中全部电话号码的信息。

请给出你认为合理的数据依赖，把这个层次结构转换成一组规范化的关系。

答：（1）函数依赖：

语义假设如下：

①一个职工不能同时成为多个部门的领导人；

②一个职工不能同时在多个部门就职；

③一个职工不能同时参加多个生产与科研项目；

④一个职工不能同时在两个不同的办公室办公；

⑤一个职工不能同时拥有两倍或两倍以上的电话；

⑥一个生产与科研项目不能同时分配给多个部门；

⑦一个办公室不能同时分配给多个部门；

⑧部门号、职工号、项目号、办公室号码及电话号码是全局唯一的。

（2）设计一组关系模式，它们都是属于1NF的。

①部门DEPT（DEPT#，DBUDGET，MGR_EMP#），其中DEPT#和MGR_EMP#都是候选码；

②职工EMP（EMP#，DEPT#，PROJ#，OFF#，PHONE#），候选码为EMP#，但有PHONE#→OFF#，OFF#→DEPT#，PROJ#→DEPT#；

③职务JOB（EMP#，JOBN），工资史SALHIST（EMP#，DATE，JOBN，SALARY）；

④生产与科研项目PROJ（PROJ#，DEPT#，PBUDGET）；

⑤办公室OFFICE（OFF#，DEPT#，AREA）；

⑥电话PHONE（PHONE#，OFF#）。

（3）分析可知，JOB的属性包含在SALHIST中，故将EMP#分解为4个3NF的关系模式：

EMP（EMP#，PROJ#，PHONE#）

X（PHONE#，OFF#）

Y（PROJ#，DEPT#）

Z（OFF#，DEPT#）

然而X就是PHONE，Y是PROJ的投影，Z是OFFICE的投影，所以X、Y和Z都可以消去。最后得到如下6个关系模式，它们都是3NF，也是BCNF。

DEPT（DEPT#，DBUDGET，MGR_EMP#）

EMP（EMP#，PROJ#，PHONE#）

SALHIST（EMP#，DATE，JOBN，SALARY）

PROJ（PROJ#，DEPT#，PBUDGET）

OFFICE（OFF#，DEPT#，AREA）

PHONE（PHONE#，OFF#）

10在一个订货系统的数据库中，存有顾客、货物和订货单信息。

每个顾客包含顾客号CUST#（唯一的）、收货地址ADDRESS （一个顾客可有几个地址）、赊购限额CREDLIM、余额BAL以及折扣DISCOUNT。

每个订货单包含订单号ORD#、顾客号CUST#、收货地址ADDRESS、订货日期DATE、订货细则LINE# （每个订货单有若干条）、每条订货细则内容是货物号ITEM#以及订货数量QTYORD。

每种货物包含货物号ITEM#（唯一的）、制造厂商PLANT#、每个厂商的实际存货量QTYOH、规定的最低存货量DANGER和货物描述DESCN。

由于处理上的要求，每个订货单的每一订货细则LINE#中还应有一个未发货量QTYOUT （初始值时为订货数量，随着发货将减为零）。

为这些数据设计一个数据库，如第9题那样，首先给出认为合理的数据依赖。

答：语义假设如下：

（1）任何两个顾客的收货地址都不相同；

（2）每一个订单都有一个唯一的订单号码；

（3）每个订单的订单细则在这个订单里有一个唯一的编号。

函数依赖示意图如下：

关系模式如下：

11设在第10题中实际上只有很少量的顾客（例如1%）有多个收货地址，由于存在这些少数的而又不能忽视的情形，使得不能按一般的方式来处理问题。你能发现第10题答案中的问题吗？能设法改进吗？

答：如果99%的顾客只有一个收货地址，则把地址放在与CUST不同的关系模式中，在实际处理订货过程时的效率是很低的。因此可以对这个问题进行改进。对于每个顾客，指定一个合法收货地址作为主地址，则对于99%的顾客，该地址就是其惟一地址。

关系模式CUST的定义修改如下：

99%的顾客只有一个收货地址，则CUST#（顾客号）→ADDRESS（地址）。

对于有多个收货地址的顾客，建立关系模式SECOND（代替原来的关系模式SHIPTO）：

这样，CUST存放主地址，而SECOND中存放所有的第二地址（和相应的顾客号），这两个关系变量都属于BCNF。

该方法具有以下优点：

（1）对于99%的顾客的处理变得简单有效。

（2）如果输入订单时时把收货地址省略了，则可以用主地址作为默认地址。

综述，把特殊情况分离开来是个有效的方法，它可以充分利用两者的优点，既达到简化处理的目的，又使设计的关系模式达到BCNF。

12下面的结论哪些是正确的？哪些是错误的？对于错误的结论请给出判断理由或给出一个反例说明。

（1）任何一个二目关系是属于3NF的。

（2）任何一个二目关系是属于BCNF的。

（3）任何一个二目关系是属于4NF的。

（4）当且仅当函数依赖A→B在R上成立，关系R（A，B，C）等于其投影R₁（A，B）和R₂（A，G）的连接。

（5）若R.A→R.B，R.B→R.C，则R.A→R.C。

（6）若R.A→R.B，R.A→R.C，则R.A→R.（B，C）。

（7）若R.B→R.A，R.C→R.A，则R.（B，C）→R（A）。

（8）若R.（B，C）→R.A，则R.B→R.A，R.C→R.A。

答：（1）正确。因为关系模式中只有两个属性，所以无传递。

（2）正确。按BCNF的定义，若X→Y，且Y不是X的子集时，每个决定因素都包含码，对于二目关系决定因素必然包含码。

（3）正确。因为只有两个属性，所以无非平凡的多值依赖。

（4）错误。当A→B在R上成立，关系R（A，B，C）等于其投影R₁（A，B）和R₂（A，C）的连接。反之则不然。正确的是当且仅当函数依赖A→→B在R上成立，关系R（A，B，C）等于其投影R₁（A，B）和R₂（A，C）的连接。

（5）正确。

（6）正确。

（7）正确。

（8）错误。反例关系模式SC（S#，C#，G），（S#，C#）→G，但S#↛G，C#↛G。