第3章
关系数据库设计理论




本章要点
 关系数据库设计理论概述。
 范式和规范化。
 数据依赖的公理系统。
数据库设计需要理论指导，关系数据库规范化理论是数据库设计的重要理论基础，应用该理论可针对一个给定的应用环境，设计优化的数据库逻辑结构和物理结构，并据此建立数据库及其应用系统。在本章中，介绍关系数据理论概述、规范化、数据依赖的公理系统等内容。

3.1关系数据库设计理论概述
关系数据库设计理论最早由数据库创始人E.F.Codd提出，后经很多专家学者作了深入的研究与发展，形成了一整套有关关系数据库设计的理论。
关系数据库设计的关键是关系模式的设计，一个合适的关系数据库系统的设计重点是关系数据库模式，即应构造几个关系模式，每个模式有哪些属性，怎样将这些相互关联的关系模式组建成一个适合的关系模型。
关系数据库的设计必须在关系数据库设计理论的指导下进行。关系数据库设计理论有3个方面的内容： 函数依赖、范式和模式设计。函数依赖起核心作用，它是模式分解和模式设计的基础，范式是模式分解的标准。
例3.1~例3.4（从第一范式到第三范式）就是举例说明好的关系模式的设计过程。
【例3.1】设计一个学生课程数据库，其关系模式SDSC(Sno，Sname，Age，Dept，DeptHead，Cno，Grade)，各属性含义为学号、姓名、年龄、系、系主任姓名； 课程号、成绩。根据实际情况，这些属性语义规定如下。
(1) 一个系有若干学生，一个学生只属于一个系。
(2) 一个系只有一个系主任。
(3) 一个学生可以选修多门课程，一门课程可被多个学生选修。
(4) 每个学生学习每门课程有一个成绩。
关系模式SDSC在某一时刻的一个实例，即数据表，如表3.1所示。


表3.1SDSC表



SnoSnameAgeDeptDeptHeadCnoGrade


141001刘星宇22电子工程李建明10194

141001刘星宇22电子工程李建明20492



续表


SnoSnameAgeDeptDeptHeadCnoGrade

141001刘星宇22电子工程李建明90195

141002王小凤20电子工程李建明10176

141002王小凤20电子工程李建明20474

141002王小凤20电子工程李建明90184

142001杨燕21计算机应用程海涛20487

142001杨燕21计算机应用程海涛90182


142004周培杰21计算机应用程海涛20490

142004周培杰21计算机应用程海涛90192


从上述语义规定和分析表中数据可以看出，(Sno，Cno)能唯一标识一个元组，所以，(Sno，Cno)为该关系模式的主码，但在进行数据库操作时，会出现以下问题。
(1) 数据冗余。
当一个学生选修多门课程时就会出现数据冗余，导致姓名、性别和课程名属性多次重复存储，系名和系主任姓名也多次重复。
(2) 插入异常。
如果某个新系没有招生，由于没有学生，则系名和系主任姓名无法插入，根据关系实体完整性约束，主码(Sno,Cno)不能取空值，此时Sno、Cno均无值，所以不能进行插入操作。
另外，学生未选修课程，则Cno无值，其学号、姓名和年龄无法插入，因为实体完整性约束规定，主码(Sno，Cno)不能部分为空，也不能进行插入操作。

(3) 删除异常。
当某系学生全部毕业还未招生时，要删除全部记录，系名和系主任姓名也被删除，而这个系仍然存在，这就是删除异常。
(4) 修改异常。
如果某系更换系主任，则属于该系的记录都要修改DeptHead的内容，若有不慎，会造成漏改或误改，造成数据的不一致性，破坏数据完整性。
由于存在上述问题，SDSC不是一个好的关系模式。为了克服这些异常，将S关系分解为学生关系S(Sno，Sname，Age，Dept)，系关系D(Dept，DeptHead)，选课关系SC(Sno，Cno，Grade)，这3个关系模式的实例如表3.2~表3.4所示。


表3.2S表



SnoSnameAgeDept

141001刘星宇22电子工程

141002王小凤20电子工程

142001杨燕21计算机应用

142004周培杰21计算机应用



表3.3D表



DeptDeptHead

电子工程李建明
计算机应用程海涛



表3.4SC表



SnoCnoGrade

14100110194

14100120492

14100190195

14100210176

14100220474

14100290184

14200120487

14200190182

14200420490

14200490192

可以看出，首先是数据冗余明显降低。当新增一个系时，只需在关系D中增加一条记录。当某个学生未选修课程时，只需在关系S中增加一条记录，而与选课关系SC无关，这就避免了插入异常。当某系学生全部毕业时，只需在关系S中删除全部记录，不会影响到系名和系主任姓名等信息，这就避免了删除异常。当更换系主任时，只需在关系D中修改一条记录中的属性DeptHead的内容，这就避免了修改异常。
但是，一个好的关系模式不是在任何情况下都是最优的。例如，查询某个学生的系主任姓名和成绩，就需要通过3个表的连接操作完成，需要的开销较大。在实际工作中，要以应用系统功能与性能需求为目标进行设计。


3.2规范化
规范化设计关系模式，将结构复杂的关系模式分解为结构简单的关系模式，使不好的关系模式转变为较好的关系模式。
在第2章中，已学习关系模式可以形式化地表示为一个五元组。

R(U, D, DOM, F)


其中，R是关系名； U是组成该关系的属性名集合； D是属性所来自的域； DOM是属性向域的映像集合； F是属性间的数据依赖关系集合。
由于D和DOM对设计好的关系模式作用不大，一般将关系模式简化为一个三元组

R<U, F>


有时还可简化为R(U)。
数据依赖(Data Dependency)是一个关系内部属性与属性之间的约束关系，是数据内在的性质，是语义的体现。
数据依赖有多种类型，以下主要介绍函数依赖(Functional Dependency，FD)、多值依赖(Multivalued Dependency，MVD)和连接依赖(Join Dependency，JD)。

3.2.1函数依赖、码和范式
1. 函数依赖

函数依赖是关系数据库规范化理论的基础。
定义3.1设R(U)是属性集U上的关系模式，X、Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作X→Y，称X为决定因素，Y为依赖因素。若Y不函数依赖于X，则作为X→/ Y。若X→Y，Y→X，则记作XY。
例如，关系模式SDSC(Sno，Sname，Age，Dept，DeptHead，Cno，Grade)，有
U={Sno，Sname，Age，Dept，DeptHead，Cno，Grade}
F={Sno→Sname，Sno→Age，Sno→Dept，Dept→DeptHead，Sno→DeptHead，(Sno，Cno)→Grade}
一个Sno有多个Grade的值与之对应，Grade不能函数依赖于Sno，即Sno→/ Grade。
同理，Cno→/ Grade，但Grade可被(Sno，Cno)唯一确定，所以，(Sno，Cno)→Grade。

注意： 函数依赖是指R的所有关系实例都要满足的约束条件，不是针对某个或某些关系实例满足的约束条件。
函数依赖和别的数据之间的依赖关系一样，是语义范畴的概念，人们只能根据数据的语义来确定函数依赖。
函数依赖与属性之间联系的类型有关： 
(1) 如果X和Y之间是1∶1关系(一对一关系)，则存在函数依赖XY。例如，学生没有重名时，SnoSname。
(2) 如果X和Y之间是1∶n关系(一对多关系)，则存在函数依赖X→Y。例如，学号和姓名、部门名之间都有1∶n关系，则Sno→Age，Sno→Dept。
(3) 如果X和Y之间是m∶n关系(多对多关系)，则X和Y之间不存在函数依赖。例如，学生和课程之间是m∶n关系，因此，Sno和Cno之间不存在函数依赖关系。
由于函数依赖与属性之间联系的类型有关，可以从分析属性之间的联系入手，确定属性之间的函数依赖。
定义3.2若X→Y是一个函数依赖，且YX，则称X→Y是一个平凡函数依赖，否则称为非平凡函数依赖。例如，(Sno，Cno)→Sno，(Sno，Cno)→Cno都是平凡函数依赖。
注意： 若不特别声明，本书讨论的都是非平凡函数依赖。
定义3.3设R(U)是属性集U上的关系模式，X、Y是U的子集。设X→Y是一个函数依赖，并且对于任何X的一个真子集 X’，X’→Y都不成立，则称X→Y是一个完全函数依赖(Full Functional Dependency)。即Y函数依赖于整个X，记作XfY。
定义3.4设R(U)是属性集U上的关系模式，X、Y是U的子集。设X→Y是一个函数依赖，但不是完全函数依赖，则称X→Y是一个部分函数依赖(Partial Functional Dependency)，或称Y函数依赖于X的某个真子集，记作XpY。
例如，关系模式SDSC中，因为Sno→/ Grade，Cno→/ Grade，所以，(Sno，Cno)fGrade。因为Sno→Age，所以，(Sno，Cno)pAge。

定义3.5设R(U)是一个关系模式，X、Y、Z是U的子集，如果X→Y(YX)，Y→/ X，Y→Z成立，则称Z传递函数依赖(Transitive Functional Dependency)于X，记为XtZ。
注意： 如果有Y→X，则 XY，此时称Z对X直接函数依赖，而不是传递函数依赖。
例如，关系模式SDSC中，Sno→Dept，但Dept→/ Sno，又Dept→DeptHead，所以SnotDeptHead。

2. 码
定义3.6设K为R<U，F>中的属性或属性组，若KfU，则K为R的候选码(或候选键或候选关键字，Candidate Key)。若有多个候选码，则选定其中的一个作为主码(或称主键，Primary Key)。
包含在任何一个候选码中的属性称为主属性(Prime Attribute)。不包含在任何候选码中的属性称为非主属性(Nonprime Attribute)或非码属性(Nonkey Attribute)。最简单的情况，单个属性是码。最极端的情况，整个属性组是码，称为全码(Allkey)。
例如，在关系模式S(Sno，Age，Dept)中，Sno是码，而在关系模式SC(Sno，Cno，Grade)中属性组合(Sno，Cno)是码。
在后面的章节中，主码和候选码都简称为码，读者可从上下文加以区分。

定义3.7关系R中的属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码(Foreign Key)，也称外码。
例如，在关系模式SC(Sno，Cno，Grade)中，Sno不是主码，但Sno是关系模式S(Sno，Sname，Age，Dept)主码，所以，Sno是关系模式SC的外码。同理，Cno也是关系模式SC的外码。
主码与外码提供了一个表示关系间的联系手段，例如关系模式S与SC的联系就是通过Sno这个在关系模式S中是主码而在关系模式SC中是外码实现的。

3. 范式
规范化的基本思想是尽量减小数据冗余，消除数据依赖中不合适的部分，解决插入异常、删除异常和更新异常等问题，这就要求设计出的关系模式要满足一定条件。在关系数据库的规范化过程中，为不同程度的规范化要求设立的不同标准或准则称为范式。满足最低要求的称为第一范式，简称1NF。在第一范式基础上满足进一步要求的成为第二范式2NF，以此类推。
1971—1972年，E.F.Codd系统地提出了1NF、2NF、3NF的概念，讨论了关系模式的规范化问题。 1974年，Codd和Boyce又共同提出了一个新范式，即BCNF。1976年有人提出了4NF，后又有人提出了5NF。
各个范式之间的集合关系可以表示为5NF4NFBCNF3NF2NF1NF，如图3.1所示。


图3.1各范式之间的关系



一个属于低一级范式的关系模式，通过模式分解可以转换成若干个满足高一级范式要求的关系模式的集合，该过程称为规范化。


3.2.21NF
定义3.8在一个关系模式R中，如果R的每一个属性都是不可再分的数据项，则称R属于第一范式1NF，记作R∈1NF。
第一范式是最基本的范式，在关系中每个属性都是不可再分的简单数据项。
【例3.2】第一范式规范化举例。
表3.5所示的关系R不是1NF。将关系R转化为1NF的结果，如表3.6所示。


表3.5关系R



SnoSnameCname

141001刘星宇数字电路，英语

141002王小凤数字电路，英语

142001杨燕数据库系统，英语

142004周培杰数据库系统，英语



表3.6关系R转化为1NF



SnoSnameCname

141001刘星宇数字电路

141001刘星宇英语

141002王小凤数字电路

141002王小凤英语

142001杨燕数据库系统


142001杨燕英语

142004周培杰数据库系统

142004周培杰英语


3.2.32NF
定义3.9对于关系模式R∈1NF，且R中每一个非主属性都完全函数依赖于任意一个候选码，则该关系模式R属于第二范式，记作R∈2NF。

第二范式的规范化指将1NF关系模式通过投影分解，消除非主属性对候选码的部分函数依赖，转换成2NF关系模式的集合过程。
分解时遵循“一事一地”原则，即一个关系模式描述一个实体或实体间的联系。如果多于一个实体或联系，则进行投影分解。
【例3.3】第二范式规范化举例。
在例3.1的关系模式SDSC(Sno，Sname，Age，Dept，DeptHead，Cno，Grade)中，各属性含义分别为“学号”“姓名”“年龄”“系”“系主任姓名”“课程名”“成绩”，(Sno，Cno)为该关系模式的候选码。
该模式属于第一范式，函数依赖关系如下。
(Sno，Cno)fGrade
Sno→Sname，(Sno，Cno)pSname
Sno→Age，(Sno，Cno)pAge
Sno→Dept，(Sno，Cno)pDept，Dept→DeptHead
SnotDeptHead，(Sno，Cno)pDeptHead
以上函数依赖关系可用函数依赖图表示，如图3.2所示。



图3.2SDSC中函数依赖图



可以看出，Sno、Cno为主属性，Sname、Age、Dept、DeptHead、Grade为非主属性。由于存在非主属性Sname对候选码(Sno，Cno)的部分依赖，所以，SDSC2NF。
在SDSC中，既存在完全函数依赖，又存在部分函数依赖和传递函数依赖，导致数据冗余、插入异常、删除异常、修改异常等问题，这在数据库中是不允许的。
根据“一事一地”原则，将关系模式SDSC分解为以下两个关系模式。

SD(Sno, Sname, Age, Dept,DeptHead)

SC(Sno, Cno, Grade)

分解后的函数依赖图如图3.3和图3.4所示。


图3.3SD中函数依赖图




图3.4SC中函数依赖图



分解后的关系模式SD的候选码是Sno，关系模式SC的候选码是(Sno，Cno)，非主属性对候选码都是完全函数依赖的，从而消除了非主属性对候选码的部分函数依赖，所以，SD∈2NF，SC∈2NF，它们之间通过SC中的外键Sno相联系，需要时进行自然连接，恢复原来的关系，这种分解不会损失任何信息，具有无损连接性。
注意： 如果R的候选码都是单属性，或R的全体属性都是主属性，则R∈2NF。

3.2.43NF
定义3.10如果关系模式R∈2NF，且R中所有非主属性对任何候选码都不存在传递函数依赖，则称R属于第三范式，记作R∈3NF。
第三范式具有以下性质。
(1) 如果R∈3NF，则R也属于2NF。
(2) 如果R∈2NF，但R不一定属于3NF。
2NF的关系模式解决了1NF中存在的一些问题，但2NF的关系模式SD在进行数据操作时，仍然存在以下问题。
(1) 数据冗余。每个系名和系主任名存储的次数等于该系的学生人数。
(2) 插入异常。当一个新系没有招生时，有关该系的信息无法插入。
(3) 删除异常。当某系学生全部毕业没有招生时，删除全部学生记录的同时也删除了该系的信息。
(4) 修改异常。更换系主任时需要更动较多的学生记录。
存在以上问题，是因为在SD中存在非主属性对候选码的传递函数依赖，消除传递函数依赖就可转换为3NF。
第三范式的规范化指将2NF关系模式通过投影分解，消除非主属性对候选码的传递函数依赖，转换成3NF关系模式的集合过程。
分解时遵循“一事一地”原则。 
【例3.4】第三范式规范化举例。
将属于2NF的关系模式SD(Sno，Sname，Age，Dept，DeptHead)分解为： 

S(Sno, Sname, Age, Dept)，

D(Dept,Dept Head)


分解后的函数依赖图如图3.5和图3.6所示。


图3.5S中函数依赖图




图3.6D中函数依赖图


分解后的关系模式S的候选码是Sno，关系模式D的候选码是Dept，不存在传递函数依赖，所以，S∈3NF，D∈3NF。
关系模式SD由2NF分解为3NF后，函数依赖关系变得更简单，既无非主属性对候选码的部分函数依赖，又无非主属性对候选码的传递函数依赖，解决了2NF存在的4个问题，3NF的关系模式S和D特点如下。
(1) 降低了数据冗余度。系主任名存储的次数与该系的学生人数无关，只在关系D中存储一次。
(2) 不存在插入异常。当一个新系没有招生时，该系的信息可直接插入到关系D中，与学生关系S无关。
(3) 不存在删除异常。删除全部学生记录仍然保留该系的信息，可以只删除学生关系S中的记录，不影响关系D中的数据。
(4) 不存在修改异常。更换系主任时，只需修改关系D中一个相应元组的DeptHead属性值，不影响关系S中的数据。
由于3NF只限制了非主属性对码的依赖关系，未限制主属性对码的依赖关系。如果发生这种依赖，仍然可能存在数据冗余、插入异常、删除异常、修改异常，需要对3NF进一步规范化，消除主属性对码的依赖关系，转换为更高一级的范式，这就是下一节要介绍的BCNF范式。

3.2.5BCNF
定义3.11对于关系模式R∈1NF，若X→Y且YX时X必含有码，则R∈BCNF。
即若R中的每一决定因素都包含码，则R∈BCNF。
由BCNF的定义可以得到如下结论，一个满足BCNF的关系模式有如下性质。
(1) 所有非主属性对每一个码都是完全函数依赖。
(2) 所有主属性对每一个不包含它的码也是完全函数依赖。
(3) 没有任何属性完全函数依赖于非码的任何一组属性。
若R∈BCNF，按定义排除了任何属性对码的部分函数依赖和传递函数依赖，所以R∈3NF。但若R∈3NF，则R未必属于BCNF。
BCNF的规范化指将3NF关系模式通过投影分解转换成BCNF关系模式的集合。

【例3.5】BCNF范式规范化举例。
设有关系模式SCN(Sno，Sname，Cno，Grade)，各属性含义为“学号”“姓名”“课程名”“成绩”，并假定姓名不重名。
可以看出，SCN有两个码(Sno，Cno)和(Sname，Cno)，其函数依赖如下。
SnoSname
(Sno，Cno)pSname
(Sname，Cno)pSno
唯一的非主属性Grade对码不存在部分依赖和传递依赖，所以SCN∈3NF。但是，由于SnoSname，即决定因素Sno或Sname不包含码，从另一个角度看，存在主属性对码的部分依赖： (Sno，Cno)pSname，(Sname，Cno)pSno，所以SCNBCNF。
根据分解的原则，将SCN分解为以下两个关系模式。

S(Sno, Sname)

SC(Sno, Cno, Grade)

S和SC的函数依赖图如图3.7和图3.8所示。


图3.7S中函数依赖图




图3.8SC中函数依赖图


对于S，两个候选码为Sno和Sname，对于SC，主码为(Sno，Cno)。在上述两个关系模式中，主属性和非主属性都不存在对码的部分依赖和传递依赖，所以，S∈BCNF，SC∈BCNF。
关系SCN转换为BCNF后，数据冗余度明显降低，学生姓名只在关系S中存储一次，学生改名时，只需改动一条学生记录中相应Sname的值即可，不会发生修改异常。
【例3.6】设有关系模式STC(S，T，C)，其中，S表示学生，T表示教师，C表示课程，语义假设是每一位教师只教一门课，每门课有多名教师讲授，某一学生选定某一门课程，就对应一名确定的教师。
由语义假设，STC的函数依赖是： 
(S，C)fT，(S，T)pC，TfC
其中，(S，C)和(S，T)都是候选码。
函数依赖图如图3.9所示。


图3.9STC中函数依赖图 


由于STC没有任何非主属性对码的部分依赖和传递依赖(因为STC没有非主属性)，所以STC∈3NF。但不是BCNF，因为有T→C，T是决定因素，而T不包含候选码。
非BCNF关系模式分解为ST(S，T)和TC(T，C)，它们都是BCNF。

3.2.6多值依赖与4NF
函数依赖表示关系模式中属性间“一对一”或“一对多”的联系，不能表示属性间“多对多”的联系。本节讨论属性间“多对多”的联系即多值依赖问题，以及第四范式。
1. 多值依赖
为了说明多值依赖的概念，见下面的例题。
【例3.7】设一门课程可由多名教师讲授，他们使用相同的一套参考书，可用如图3.10所示的非规范关系CTR表示课程C、教师T和参考书R间的关系。


图3.10非规范关系CTR


转换成规范化的关系CTR(C，T，R)如图3.11所示。


图3.11规范后关系CTR


关系模式CTR(C，T，R)的码是(C，T，R)，即全码(Allkey)，所以CTR∈BCNF。但存在以下问题。
(1) 数据冗余。课程、教师和参考书都被多次存储。
(2) 插入异常。当某一门课程“数据库原理与应用”增加一名讲课教师“周丽”时，必须插入多个元组： (数据库原理与应用，周丽，数据库系统概念)，(数据库原理与应用，周丽，数据库系统概论)，(数据库原理与应用，周丽，SQL Server数据库教程)。
(3) 删除异常。当某一门课程“数学”要去掉一本参考书“数学分析”时，必须删除多个元组： (数学，罗燕芬，数学分析)，(数学，陈诗雨，数学分析)。
分析上述关系模式，发现存在一种称之为多值依赖(MultiValued Dependency，MVD)的数据依赖。
定义3.12设R(U)是属性集U上的一个关系模式，X、Y、Z是U的子集，且Z=U-X-Y。如果R的任一关系r，对于给定的(X，Z)上的每一对值，都存在一组Y值与之对应，且Y的这组值仅仅决定于X值而与Z的值不相关，则称Y多值依赖于X，或X多值决定Y，记为X→→Y。
若X→→Y，而Z＝，则称X→→Y为平凡的多值依赖，否则称X→→Y为非平凡的多值依赖。
在上例的关系模式CTR(C，T，R)中，对于给定的(C，R)的一对值(数据库原理与应用，数据库系统概念)，对应的一组T值为{刘俊松，李智强}，这组值仅仅决定于C值。对于另一个(数据库原理与应用，SQL Server数据库教程)，对应的一组T值仍为{刘俊松，李智强}，尽管此时参考书R的值已改变。所以，T多值依赖于C，记为C→→T。

2. 4NF
定义3.13设关系模式R<U，F>∈1NF，如果对于R的每个非平凡多值依赖X→→Y(YX)，X都含有码，则称R<U，F>∈4NF。
由定义可知： 
(1) 根据定义，4NF要求每一个非平凡的多值依赖X→→Y，X都含有码，则必然是X→Y，所以4NF允许的非平凡多值依赖实际上是函数依赖。
(2) 一个关系模式是4NF，则必是BCNF。而一个关系模式是BCNF，不一定是4NF。所以4NF是BCNF的推广。
例3.7的关系模式CTR(C，T，R)是BCNF，分解后产生CTR1(C，T)和CTR2(C，R)，因为C→→T，C→→R都是平凡的多值依赖，已不存在非平凡的非函数依赖的多值依赖，所以CTR1∈4NF，CTR2∈4NF。
函数依赖和多值依赖是两种最重要的数据依赖。如果只考虑函数依赖，则属于BCNF的关系模式规范化程度已达到最高； 如果只考虑多值依赖，则属于4NF的关系模式规范化程度已达到最高。在数据依赖中，除函数依赖和多值依赖外，还有其他数据依赖，如连接依赖。函数依赖是多值依赖的一种特殊情况，而多值依赖又是连接依赖的一种特殊情况。如果消除了属于4NF的关系模式中存在的连接依赖，则可进一步达到5NF的关系模式，这里就不再进行讨论了。

3.2.7规范化小结
关系模式规范化的目的是使结构更合理，消除插入异常、删除异常和更新异常，使数据冗余尽量小，便于插入、删除和更新。
关系模式规范化遵从概念单一化“一事一地”原则，即一个关系模式描述一个实体或实体间的一种联系。规范化的实质就是概念的单一化。方法是将关系模式投影分解为两个或两个以上的模式。
一个关系模式只要其每一个属性都是不可再分的数据项，则称为1NF。消除1NF中非主属性对码的部分函数依赖，得到2NF。消除2NF中非主属性对码的传递函数依赖，得到3NF。消除3NF中主属性对码的部分函数依赖和传递函数依赖，得到BCNF。消除BCNF中非平凡且非函数依赖的多值依赖，得到4NF。规范化过程如图3.12所示。


图3.12规范化过程



3.3数据依赖的公理系统
数据依赖的公理系统是函数分解算法的理论基础。下面介绍的Armstrong公理系统，是一个有效且完备的数据依赖公理系统。

3.3.1Armstrong公理系统
定义3.14对于满足一组函数依赖F的关系模式R<U，F>，其任何一个关系r，若函数依赖X→Y都成立(即r中任意两元组t、s，若t［X］=s［X］，则t［Y］=s［Y］)，则称F逻辑蕴涵X→Y，或称X→Y是F的逻辑蕴涵。
怎样从一组函数依赖求得蕴涵的函数依赖？怎样求得给定关系模式的码？问题的关键在于已知一组函数依赖F，要问X→Y是否是F的逻辑蕴涵。这就需要一组推理规则，这组推理规则就是Armstrong公理系统。
Armstrong公理系统(Armstrongs Axiom)设U为属性集总体，F是U上的一组函数依赖，有关系模式R<U，F>，对于R<U，F>来说有以下推理规则。
(1) 自反律(Reflexivity Rule)。如果YXU，则X→Y为F所蕴涵。
(2) 增广律(Augmentation Rule)。如果X→Y为F所蕴涵，且ZU，则XZ→YZ为F所蕴涵。
(3) 传递律(Transitivity Rule)。如果X→Y及Y→Z为F所蕴涵，则X→Z为F所蕴涵。
提示： 由自反律得到的函数依赖都是平凡的函数依赖，自反律的使用并不依赖于F。

注意： XZ表示X∪Z，YZ表示Y∪Z。
定理3.1Armstrong推理规则是正确的。
证明： 
(1) 设YXU，
对于R<U，F>的任一个关系中任意两元组t、s： 
若t［X］=s［X］，因为YX，有t［Y］=s［Y］，
所以X→Y。
(2) 设X→Y为F所蕴涵，且ZU，
设R<U，F>的任一个关系中任意两元组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→Z为F所蕴涵，
对于R<U，F>的任一个关系中任意两元组t、s： 
若t［X］=s［X］，因为X→Y，有t［Y］=s［Y］，
由Y→Z，有t［Y］=s［Y］，
所以X→Z为F所蕴涵。

注意： t［X］表示元组t在属性组X上的分量，等价于t.X。
根据(1)(2)(3)这3条推理规则，可得以下3条推理规则。
(4) 合并规则(Union Rule)。如果X→Y，Y→Z，则X→YZ。
(5) 分解规则(Decomposition Rule)。如果X→Y，ZY，则X→Z。
(6) 伪传递规则(Preudotransitivity Rule)。如果X→Y，WY→Z，则XW→Z。
由合并规则和分解规则可得： 
引理3.1X→A1A2…Ak成立的充要条件是X→Ai成立(i=1，2，…，k)。
【例3.8】设有关系模式R，A、B、C、D、E、F是它的属性集的子集，R满足的函数依赖为{A→BC，CD→EF}，证明函数依赖AD→F成立。
证明： 
A→BC题中给定
A→C引理3.1
AD→CD增广律
CD→EF题中给定
AD→EF传递律
AD→F引理3.1

3.3.2闭包及其计算
定义3.15在关系模式R<U，F>中，为F所逻辑蕴涵的函数依赖的全体称为F的闭包(Closure)，记为F+。
把自反律、增广律和传递律称为Armstrong公理系统。Armstrong公理系统是有效的、完备的。其有效性是指： 由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中； 其完备性是指： F+中的每一个函数依赖必定可以由F出发根据Armstrong公理推导出来。
定义3.16设F是属性集U上的一组函数依赖，X、YU，X+F={A|X→A能由F根据Armstrong公理推导出}，X+F称为属性集X关于函数依赖集F的闭包。
由引理3.1可得出由引理3.2。
引理3.2设F是属性集U上的一组函数依赖，X、YU，X→Y能由F根据Armstrong公理推导出的充分必要条件是YX+F。
这样，判定X→Y能否由F根据Armstrong公理推导出的问题转化为求出X+F，判定Y是否为X+F的子集问题，该问题可由算法3.1解决。
算法3.1求属性集X(XU)关于U上的函数依赖集F的闭包X+F。
输入： X、F
输出： X+F
步骤： 计算属性集序列X(i)(i=0，1，…)
(1) 令X(0)=X，i=0。
(2) 求B，B={A|(V)(W)(V→W∈F∧VX(i)∧A∈W)}。即在F中寻找尚未用过的左边是X(i)的子集的函数依赖： Yj→Zj(j=0，1，…，k)，其中YjX(i)。再在Zj中寻找X(i)中未出现过的属性构成属性集B。
(3) X(i+1)=B∪X(i)。
(4) 判断X(i+1)=X(i)是否成立，若不成立则转(2)。
(5) 输出X(i)，即为X+F。
对于(4)的计算停止条件，以下4种方法是等价的。
 X(i+l)=X(i)。
 当发现X(i)包含了全部属性时。
 在F中的函数依赖的右边属性中，再也找不到X(i)中未出现过的属性。
 在F中未用过的函数依赖的左边属性集已没有X(i)的子集。

【例3.9】已知关系模式R<U，F>，其中
U={A，B，C，D，E}，F={AB→C，B→D，C→E，EC→B，AC→B}，求AB+F。
解： 
(1) 设X(0)=AB。
(2) 在F中找出左边是AB子集的函数依赖，其结果是AB→C，B→D，则X(1)=X(0)∪CD=AB∪CD=ABCD，显然X(1)≠X(0)。
(3) 在F中找出左边是ABCD子集的函数依赖，其结果是C→E，AC→B，则X(2)=X(1)∪BE=ABCD∪BE=ABCDE，显然X(2)≠X(1)。
(4) 由于X(2)已等于全部属性的集合，所以AB+F=ABCDE。
【例3.10】设有关系模式R<U，F>，其中U={A，B，C，D，E，G}，函数依赖集F={A→D，AB→E，BG→E，CD→G，E→C}，X=AE，计算X+F。
解： 
(1) 设X(0)=AE。
(2) 在F中找出左边是AE子集的函数依赖，其结果是A→D，E→C，则X(1)=X(0)DC=ACDE，显然X(1)≠X(0)。
(3) 在F中找出左边是ACDE子集的函数依赖，其结果是CD→G，则X(2)=X(1)G=ACDEG。
(4) 虽然X(2)≠X(1)，但F中未用过的函数依赖的左边属性集已没有X(2)的子集，所以不必再计算下去，即X+F=ACDEG。
定理3.2Armstrong公理是有效的、完备的。
Armstrong公理的有效性可由定理3.1得到证明，完备性证明略。
Armstrong公理的完备性及有效性说明“导出”与“蕴含”是两个完全等价的概念。F+也可说成是由F出发根据Armstrong公理导出的函数依赖的集合。

3.3.3确定候选码
设关系模式为R<U，F>，F为函数依赖集，将U中的属性分为以下4类。
 L类属性： 只在F中各个函数依赖的左部出现。
 R类属性： 只在F中各个函数依赖的右部出现。
 LR类属性： 在F中各个函数依赖的左部和右部两边都出现。
 N类属性： 不在F中各个函数依赖中出现。
L类属性集中每一个属性都必定是候选码中的属性； R类和N类属性集中每一个属性都必定不是候选码中的属性； LR类属性集中每一个属性不能确定是否在候选码中。
确定候选码的步骤如下。
(1) 划分属性类别。令X为L类属性集的集合，Y为LR类属性集的集合。
(2) 基于F计算X+。若X+包含了R的全部属性，则X是R的唯一候选码，算法结束。否则，转(3)。
(3) 逐一取Y中单一属性A，与X组成属性组XA。如果(XA)+F=U，则XA为候选码，令Y=Y-{A}，转(4)。
(4) 如果已找出所有候选码，转(5)； 否则，依次取Y中的任意2个、3个……属性，与X组成属性组XZ，如果(XZ)+F=U，且XZ不包含已求得的候选码，则XZ为候选码。
(5) 算法结束。
【例3.11】设R(A，B，C，D，E，F)，G={AB→E，AC→F，AD→B，B→C，C→D}，求R的所有候选码。
解： 
(1) R中L类属性： A，LR类属性： B、C、D。
(2) A+F=A≠U。
(3) 
因为(AB)+F=ABCDEF，所以AB为候选码。
因为(AC)+F=ABCDEF，所以AC为候选码。
因为(AD)+F=ABCDEF，所以AD为候选码。
故R的所有候选码为AB，AC，AD。
3.3.4函数依赖集的等价和最小函数依赖集
从蕴含(或导出)的概念出发，引出两个函数依赖集的等价和最小函数依赖集的概念。
1. 两个函数依赖集的等价
定义3.17如果G+=F+，就说函数依赖集F覆盖G(F是G的覆盖，或G是F的覆盖)，或F和G等价。
引理3.3F+=G+的充分必要条件是FG+和GF+。
证明： 必要性显然，只证充分性
如果FG+，则X+FX+G+，
任取X→Y∈F+，则有YX+FX+G+，
所以X→Y(G+)+G+，即F+G+，
同理可证G+F+，所以F+=G+。
引理3.3给出了判定两个函数依赖集的等价的算法。
要判定FG+，只需逐一对F中的函数依赖X→Y考察Y是否属于G+即可。
【例3.12】设有F和G两个函数依赖集，F={A→B，B→C}，G={A→BC，B→C}，判断它们是否等价。
解： 
首先检查F中的每个函数依赖是否属于G+。
因为A+G=ABC，BA+G，所以A→B∈A+G，
因为B+G=BC，CB+G，所以B→C∈B+G，
故FG+。
同样有GF+。所以两个函数依赖集F和G是等价的。


2. 最小函数依赖集
定义3.18如果函数依赖集F满足以下条件，则称F为一个极小函数依赖集，也称最小函数依赖集或最小覆盖(Minimal Cover)。
(1) F中的任一函数依赖的右部仅含有一个属性。
(2) F中不存在这样一个函数依赖X→A，X有真子集Z，使得F-{X→A}∪{Z→A}与F等价，即左部无多余的属性。
(3) F中不存在这样一个函数依赖X→A，使得F与F-{X→A}等价，即无多余的函数依赖。
【例3.13】以下3个函数依赖集中哪一个是最小函数依赖集？
F1={A→D，BD→C，C→AD}
F2={AB→C，B→A，B→C}
F3={BC→D，D→A，A→D}
解： 
在F1中，有C→AD，即右部没有单一化，所有F1不是最小函数依赖集。
在F2中，有AB→C，B→C，即左部存在多余的属性，所有F2不是最小函数依赖集。
F3满足最小函数依赖集的所有条件，它是最小函数依赖集。
【例3.14】在关系模式R<U，F>中，U={Sno，Dept，DeptHead，Cno，Grade}。考察下面的函数依赖中，哪一个是最小函数依赖集？
F={Sno→Dept，Dept→DeptHead，(Sno，Cno)→Grade}
F1={Sno→Dept，Sno→DeptHead，Dept→DeptHead，(Sno，Cno)→Grade，(Sno，Dept)→Dept}
解： 
F是最小函数依赖集。
F1不是最小函数依赖集，因为F1-{Sno→DeptHead}与F1等价，F1-{(Sno，Dept)→Dept}与F1等价。
定理3.3每一个函数依赖集F均等价于一个极小函数依赖集Fm，此Fm称为F的最小依赖集。
证明： 
这是一个构造性的证明，分3步对F进行“极小化”处理。
(1) 逐一检查F中各函数依赖FDi，使F中每一函数依赖的右部属性单一化。
X→Y，若Y=A1A2…Ak，k≥2，则用{X→Aj|(j=1，2，…，k)}取代X→Y。
(2) 逐一取出F中各函数依赖FDi，去掉各函数依赖左部多余的属性。
X→A，设X=B1B2…Bm，m≥2，逐一考查Bi(i=1，2，…，m)，若B∈(X－Bi)+F，则以X-Bi取代X。
(3) 逐一检查F中各函数依赖FDi，去掉多余的函数依赖。
X→A，令G=F-{X→A}，若A∈X+G，则从F中去掉此函数依赖。
F的最小函数依赖集不一定是唯一的，它与对各函数依赖FDi及X→A中X各属性的处理顺序有关。
【例3.15】求函数依赖集F={A→B，B→A，B→C，A→C，C→A}的最小函数依赖集。
解： 
下面给出F的两个最小函数依赖集。
Fm1={A→B，B→C，C→A}
Fm2={A→B，B→A，A→C，C→A}

3.4小结
本章主要介绍以下内容。
(1) 关系数据库设计理论有3个方面的内容： 函数依赖、范式和模式设计。函数依赖起核心作用，它是模式分解和模式设计的基础； 范式是模式分解的标准； 关系数据库设计的关键是关系模式的设计。
(2) 函数依赖是关系数据库规范化理论的基础。本章介绍了完全函数依赖、部分函数依赖和传递函数依赖的定义。
(3) 在关系数据库的规范化过程中，为不同程度的规范化要求设立的不同标准或准则称为范式。
一个低一级范式的关系模式，通过模式分解可以转换成若干个高一级范式的关系模式的集合，该过程称为规范化。
关系模式规范化的目的是使结构更合理，消除插入异常、删除异常和更新异常，使数据冗余尽量小，便于插入、删除和更新。
一个关系模式只要其每一个属性都是不可再分的数据项，则称为1NF。消除1NF中非主属性对码的部分函数依赖，得到2NF。消除2NF中非主属性对码的传递函数依赖，得到3NF。消除3NF中主属性对码的部分函数依赖和传递函数依赖，得到BCNF。消除BCNF中非平凡且非函数依赖的多值依赖，得到4NF。
(4) 把自反律、增广律和传递律称为Armstrong公理系统。Armstrong公理系统是有效的、完备的。其有效性是指： 由函数依赖集F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中； 其完备性是指： F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。
在关系模式R<U，F>中，为F所逻辑蕴涵的函数依赖的全体称为F的闭包(Closure)，记为F+。
从蕴含(或导出)的概念出发，引出两个函数依赖集的等价和最小函数依赖集的概念。

3.5规范化理解与应用实验
1. 实验目的及要求
(1) 理解范式和规范化的概念。
(2) 掌握第一范式规范化、第二范式规范化和第三范式规范化的方法，具备使用规范化方法解决应用问题的能力。
2. 验证性实验
(1) 设有关系模式： 运动员信息(代表团编号，地区，运动员编号，运动员姓名，性别，年龄，项目编号，项目名，得分)。
① 分析该模式的主键，写出所有部分函数依赖和传递函数依赖关系。
运动员信息的主键： (运动员编号，项目编号)

部分函数依赖： 
(运动员编号，项目编号)p代表团编号
(运动员编号，项目编号)p地区
(运动员编号，项目编号)p运动员姓名
(运动员编号，项目编号)p性别
(运动员编号，项目编号)p年龄
(运动员编号，项目编号)p项目名
传递函数依赖： 
运动员编号→代表团编号，代表团编号→地区，运动员编号t地区
② 将该关系模式规范化为第二范式。
消除部分函数依赖，该关系模式分解为： 
运动员代表团(运动员编号，运动员姓名，性别，年龄，代表团编号，地区)
项目(项目编号，项目名)
参加比赛(运动员编号，项目编号，得分)
③ 将第二范式规范化为第三范式。
消除传递函数依赖，运动员代表团(运动员编号，运动员姓名，性别，年龄，代表团编号，地区)分解为： 
运动员(运动员编号，运动员姓名，性别，年龄，代表团编号)
代表团(代表团编号，地区)

(2) 设有学生信息关系模式： StudentInfo(StudentNo，Name，Sex，ClassNo，Spiciality，SocietyNo，SocietyName)，其中，StudentNo为学号，Name为姓名，Sex为性别，ClassNo为班级号，Spiciality为专业名，SocietyNo为学会编号，SocietyName为学会名。
① 分析该模式的主键，写出所有部分函数依赖和传递函数依赖关系。
(StudentNo，SocietyNo)为该表的主键。
部分函数依赖： 
(StudentNo，SocietyNo)pName
(StudentNo，SocietyNo)pSex
(StudentNo，SocietyNo)pClassNo
(StudentNo，SocietyNo)pSpiciality
(StudentNo，SocietyNo)pSocietyName
传递函数依赖： 
StudentNo→ClassNo，ClassNo→Spiciality，StudentNotSpiciality
② 将该关系模式规范化为第二范式。
消除部分依赖，将关系模式StudentInfo分解为学生班级模式SIT、学会模式Society、参加学会模式PS： 
SIT(StudentNo，Name，Sex，ClassNo，Spiciality)
Society(SocietyNo，SocietyName)
PS(StudentNo，SocietyNo)
③ 将第二范式规范化为第三范式。
消除学生班级模式SIT(StudentNo，Name，Sex，ClassNo，Spiciality)的传递依赖，分解为学生模式ST、班级模式Class： 
ST(StudentNo，Name，Sex，ClassNo)
Class(ClassNo，Spiciality)
3. 设计性试验
(1) 设有关系模式： 员工信息(员工号，姓名，日期，日营业额，部门名，部门经理)。
① 分析该模式的主键，写出所有部分函数依赖和传递函数依赖关系。
② 将该关系模式规范化为第二范式。
③ 将第二范式规范化为第三范式。
(2) 设有教师信息关系模式TeacherInfo(TeacherNo，Name，SchoolNo，SchoolNo，CourseName，CourseName，Grade)，其中，TeacherNo为教师编号，Name为姓名，SchoolNo为学院编号，SchoolName为学院名，CourseNo为课程号，CourseName为课程名，Grade为学分。
① 分析该模式的主键，写出所有部分函数依赖和传递函数依赖关系。
② 将该关系模式规范化为第二范式。
③ 将第二范式规范化为第三范式。
4. 观察与思考
(1) 什么是函数依赖？什么是部分函数依赖和传递函数依赖？
(2) 简述第二范式规范化和第三范式规范化的步骤。

习题3
一、 选择题
1. 在规范化过程中，需要克服数据库逻辑结构中的冗余度大、插入异常和。

A. 结构不合理B. 删除异常
C. 数据丢失D. 数据的不一致性

2. 关系规范化的插入异常是指。
A. 不该删除的数据被删除B. 应该删除的数据未被删除
C. 不该插入的数据被插入D. 应该插入的数据未被插入

3. 关系规范化的删除异常是指。
A. 不该删除的数据被删除B. 应该删除的数据未被删除
C. 不该插入的数据被插入D. 应该插入的数据未被插入

4. 在关系模式中，如果属性A和B存在1∶1的联系，则说明。
A. A→BB. ABC. B→AD. 以上都不是

5. X→Y，且，称为平凡函数依赖。
A. YXB. XYC. X∩Y=D. X∩Y≠

6. 下列说法中，错误的是。
A. 2NF必然属于1NFB. 3NF必然属于2NF
C. 3NF必然属于BCNFD. BCNF必然属于3NF

7. 当关系模式R(A，B)已属于3NF，下列说法正确的是。
A. 一定消除了插入异常和删除异常B. 仍存在一定的插入异常和删除异常
C. 一定属于BCNFD. A和C都是

8. 设有关系模式R(A，B，C，D)，其数据依赖集F={(A，B)→C，C→D}，则关系模式R的规范化程度最高达到。
A. 1NFB. 2NFC. 3NFD. BCNF

9. 在关系模式S(Sno，Sname，Dept，DeptHead)，各属性含义为学号、姓名、系、系主任姓名，S的最高范式是。
A. 1NFB. 2NFC. 3NFD. BCNF

10. 设关系模式R(A，B，C，D，E)，其数据依赖集F={A→D，B→C，E→A}，则关系模式R的候选码为。

A. ABB. CDC. DED. BE

二、 填空题
1. 关系数据库设计理论有3个方面的内容： 函数依赖、范式和。
2. 在关系数据库的规范化过程中，为不同程度的规范化要求设立的不同称为范式。
3. 一个低一级范式的关系模式，通过可以转换成若干个高一级范式的关系模式的集合，该过程称为规范化。
4. 关系模式规范化目的是使结构更合理，消除插入异常、删除异常和，使数据冗余尽量小。
5. 任何一个二目关系是属于的。
6. 把自反律、和传递律称为Armstrong公理系统。
7. Armstrong公理系统是有效的、的。
8. 若R.A→R.B，R.B→R.C，则。
9. 若R.A→R.B，R.A→R.C，则。
10. 若R.B→R.A，R.C→R.A，则。
三、 问答题
1. 什么是函数依赖？简述完全函数依赖、部分函数依赖和传递函数依赖。
2. 什么是范式？什么是关系模式规范化？关系模式规范化目的是什么？
3. 简述关系模式规范化的过程。
4. 简述Armstrong公理系统的推理规则。
5. 什么是函数依赖集F的闭包？
6. 什么是最小函数依赖集？简述求最小函数依赖集的步骤。
四、 应用题
1. 设关系模式R(A，B，C，D)，其函数依赖集F={CD→B，B→A}。
(1) 说明R不是3NF的理由。
(2) 将R分解为3NF的模式集。
2. 设关系模式R(W，X，Y，Z)，其函数依赖集F={X→Z，WX→Y}。
(1) R属于第几范式。
(2) 如果关系R不属于BCNF，将R分解为BCNF。
3. 设关系模式R(A，B，C)，其函数依赖集F={C→B，B→A}。
(1) 求R的候选码。
(2) 判断R是否3NF，并说明理由。
(3) 如果不是，将R分解为3NF模式集。
4. 设关系模式R(A，B，C，D)，其函数依赖集F={A→C，C→A，B→AC，D→AC，BD→A}。
(1) 计算(AD)+。
(2) 求R的候选码。
(3) 求F的最小函数依赖集。
(4) 将R分解为3NF，使其既具有无损连接性，又保持函数依赖。