e028数据库原理及应用教学第4章关系化理论

第四章关系规范化理论本章内容函数依赖4.2范式和规范化方法4.3数据依赖的公理系统4.4关系模式的分解4.5

规范问题的提出4.1

小结4.6教学目的

掌握函数依赖的概念掌握1NF、2NF、3NF和BCNF范式掌握模式分解的方法教学要求

牢记有关概念，掌握关系模式规范化的方法教学重点规范化问题的存在的原因函数依赖、完全函数依赖、传递依赖规范化过程概念回顾关系关系模式关系数据库关系数据库的模式

规范问题的提出4.1关系数据库逻辑设计针对具体问题，如何构造一个适合于它的数据模式数据库逻辑设计的工具──关系数据库的规范化理论

规范问题的提出4.14.1.1规范化理论的主要内容规范化理论研究了关系模式中各属性之间的依赖关系及其对关系模式性能的影响，探讨好的关系模式应该具备的性质，以及达到好的关系模式的方法。规范化理论为我们提供了判断关系模式好坏的理论标准，帮助我们预测可能出现的问题。关系数据库的规范化理论主要包括3方面的内容：函数依赖、范式（NormalForm）和规范化方法。其中函数依赖起着核心作用，是模式分解和模式设计的基础；范式是模式分解的标准。

为了讨论关系数据库规范化理论，先分析下面一个实例。

【例4-1】以学生选课为背景，设计一个关系模式SCS。设计关系模式SCS如下：

SCS(Sno,Sname,Ssexk,Sdept,Cno,Cname,Sorce)

其中，Sno、Sname、Ssex、Sdept、Cno、Cname、Sorce是属性名，分别表示学号、学生姓名、学生性别、学院、课程号、课程名、成绩，加下划线的属性为主键。表4-1是关系模式SCS的一个实例，即一个具体关系。4.1.2不合理的关系模式存在的数据冗余和异常现象表4-1关系SCSSnoSnameSsexSdeptCnoCnameScore100101100101100101120102120102130103姜珊姜珊姜珊陈默陈默孙浩女女女女女男信电学院信电学院信电学院管理学院管理学院外语学院C150110C150101C150103C150102C150103C150100离散数学数据结构数据库操作系统数据库计算机基础787085688272从表4-1中不难看出，关系模式SCS存在以下问题：（1）数据冗余。当一个学生选修多门课程时，就会导致姓名、性别、学院名等多次重复存储；每一门课程名均对选修该门课程的学生重复存储，因而造成数据冗余。（2）操作异常。由于存在数据冗余，就可能导致数据库操作过程中出现异常，这主要表现在以下几个方面。

①插入异常。如果某个学生还没有选课，学生的有关信息就不能插入。同样，没有被学生选修的课程信息也无法存入数据库。从表4-1中不难看出，关系模式SCS存在以下问题：

②删除异常。如果关系中某位同学因某种原因退学或转学，那么就需要将其信息从关系中删除。但如果某课程只有该同学一个人选修，则在删除该生信息的同时，也把相应课程的信息删除了。那么，一旦查询所开课程信息时，就不会出现被删除课程的信息，就会认为没有开设该课程，可实际情况并非如此。因此，这也是该数据库的一种功能缺陷，称为删除异常。

③修改异常。由于数据的冗余，当修改数据库中的某些数据项时，可能一部分修改了，而另一部分没有修改，造成存储数据的不一致性。例如，某个学生从信电学院转到管理学院，那么与该学生相关的所有记录都需要逐一修改属性Sdept的值，如有遗漏，就会造成SCS中数据的不一致。结论

SCS关系模式不是一个好的，合理的模式。“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少原因：是因为该关系模式没有设计好，使得某些属性之间存在着“不良”的依赖关系，导致数据冗余。解决方法：通过分解关系模式来消除其中不合适的数据依赖

如果将SCS分解为：

S(Sno,Sname,Ssex,Sdept)C(Cno,Cname)SC(Sno,Cno,Score)

就不会出现上述异常，数据冗余也得到较好控制。

规范化理论正是用来改造关系模式，通过把一个较大的关系模式分解成两个或多个关系模式，在分解的过程中消除关系模式中不合适的问题，解决数据冗余、插入异常、删除异常、修改异常等问题，其中，函数依赖是规范化理论的基础。函数依赖4.2

函数依赖（FunctionalDependency）是数据依赖的一种。数据依赖是指一个关系中属性值之间的相互联系，它是现实世界属性间相互联系的体现，是数据之间的内在性质，是语义的体现。现在已经提出了多种类型的数据依赖，其中最重要的是函数依赖和多值依赖。函数依赖是关系规范化的理论基础。函数依赖4.24.2.1函数依赖的定义

定义4.1：设R(U)是一个关系模式，U是R的属性集合，X和Y是U的子集。如果对于R(U)的任意一个可能的关系r，t、s是r中的任意两个元组，由t[X]=s[X]可以推导出t[Y]=s[Y]，则称X函数决定Y或Y函数依赖于X，记作X→Y。定义中t[X]、t[Y]分别是元组t在属性集X、Y上的分量；s[X]、s[Y]是元组s在X、Y上的分量。由定义可知，如果元组t和与元组s在X上的分量相等，则t、s在Y上的分量也相等，则称X、Y间存在函数依赖关系，X属性集函数决定Y属性集。

说明所有关系实例均要满足语义范畴的概念数据库设计者可以对现实世界作强制的规定4.2.1函数依赖的定义

对于函数依赖的讨论，有一些相关的概念：（1）如果X→Y，且YX，则称X→Y是平凡的函数依赖。（2）如果X→Y，但YX，则称X→Y是非平凡的函数依赖。【注意】在任一关系模式中，平凡的函数依赖都是必然成立的，其自身语义不言自明且不含其他语义。下面的讨论如果没有特别说明，均是讨论非平凡的函数依赖。4.2.1函数依赖的定义

（3）如果X→Y，则称X为决定因素（Determinant），称Y

为依赖因素（Dependent）。（4）如果X→Y且Y→X，则记作X←→Y。（5）如果Y不函数依赖于X，则记作XY。

需要注意的是，函数依赖不是指关系模式R的某个或某些关系满足的约束条件，而是指R的一切关系均要满足的约束条件。4.2.2完全函数依赖和部分函数依赖

定义4.2：在关系模式R(U)中，U是R的属性集合，X和Y是U的子集。如果X→Y，并且对于X的任何一个真子集X′，都有X′Y，则称Y完全函数依赖（FullFunctionalDependency）于X，记作XY；若X→Y，但Y不完全函数依赖于X，则称Y部分函数依赖（PartialFunctionalDependency）于X，记作XY。

【例4-2】在关系SC(Sno,Cno,Cname,Score)中，SnoScore且CnoScore，关系中有(Sno,Cno)Score。而Cno→Cname，所以(Sno,Cno)Cname。该关系中(Sno,Cno)是候选键。Cno单独决定Cname。所以关系中的函数依赖(Sno,Cno)Cno是部分函数依赖。由定义及上例可知，当函数依赖中的决定因素是组合属性时，讨论部分函数依赖才有意义；当决定因素是单属性时，该函数依赖是完全函数依赖。4.2.3传递函数依赖

定义4.3：在关系模式R(U)中，U是R的属性集合，X和Y是U的子集。如果X→Y，Y→Z，且YX，YX，则称Z传递函数依赖（TransitiveFunctionalDependency）于X，记作XZ；否则称Z非传递函数依赖于X。

【例4-3】在关系S(Sno，Sname,Ssex,Sdept,Dean)中，有函数依赖关系SnoSname，由于SnoSdept，SdeptDean，有SnoDean。

由函数依赖的定义可以知道，如果Z传递依赖于X，则Z必然函数依赖于X，如果Z传递依赖于X，说明Z是间接依赖于X，从而表明X和Z之间的关联较弱，表现出间接的弱函数依赖，因而亦是产生数据冗余的原因之一。4.2.4超键、候选键、主键1．超键和候选键定义4.4设K为R（U）的属性或属性组合，若K→U，则K为关系R的超键（Superkey）。如果K→U在R上成立，但对K的任一真子集K'⊂K，都有K'U，则称K为R的候选键（Candidatekey）。

超键是可以唯一地标识一个元组的属性或属性集合。超键包含了候选键，但超键含有多余属性，不是候选键。候选键是去掉了多余属性的超键，是最小的超键。超键的超集仍然是超键。超键和候选键都具有唯一性，而候选键具有最小性。4.2.4超键、候选键、主键【例4-4】在关系模式S(Sno,Sname,Sage,Ssex,BP)中，存在函数依赖关系Sno→Sname，Sno→Sage，Sno→Ssex，Sno→BP及Sno→Sno。关系模式S中所有属性都函数依赖于Sno，即有Sno→U，Sno是超键。Sno是单属性，无多余属性，故Sno是候选键。另一方面，关系模式S中也存在函数依赖关系(Sno,Sname)→U，(Sno,Sname)能够在关系中唯一地标识一个元组，是S的一个超键，但它有多余属性，不是候选键。4.2.4超键、候选键、主键2．主键和主属性

候选键多于一个时，从候选键中选择一个作为主键（PrimaryKey）。主键的选择是任意的。

关系模式中包含在任何一个候选码中的属性称为主属性（Primeattribute），不包含在候选码中的属性称为非主属性（Nonprimeattribute）或非码属性（Non-keyattribute）。【例4-5】在关系模式SC(Sno,Cno,Score)中，(Sno,Cno)为候选键，其中的属性Sno、Cno是主属性，Score是非主属性（非码属性）。主属性和非主属性的概念在下面规范化问题的讨论中常会用到。

范式和规范化方法4.3

范式（NormalForms，NF）的概念是E.F.Codd在1971年提出的。1971—1972年，E.F.Codd提出了1NF、2NF与3NF。1974年，Codd与Boyce又共同提出了BCNF。1976年，Fagin提出了4NF，后来又有人提出了5NF，这些范式是关系规范化的理论基础。虽然规范化理论中还有新的范式出现，在这些范式中，最重要的是3NF和BCNF，它们是关系规范化的主要目标。范式和规范化方法4.3

一个质量良好的关系模式必须满足一定的规范化要求，对于不同的规范化程度可用范式来衡量。范式是满足一定要求的关系模式的集合，是衡量关系模式规范化程度的标准，满足不同程度要求的为不同范式。目前主要有6种范式：第一范式（1NF）第二范式（2NF）第三范式（3NF）

BC范式（BCNF）第四范式（4NF）第五范式（5NF）范式和规范化方法4.3

范式的级别越高，条件越严格。满足基本规范化要求的关系模式称为第一范式，简称为1NF；在第一范式基础上进一步满足一定要求的范式为第二范式，简称为2NF；其余以此类推。各种范式之间存在联系：

1NF⊃2NF⊃3NF⊃BCNF⊃4NF⊃5NF

通常把某一关系模式R为第n范式简记为R∈nNF。一个满足低级范式的关系模式通过模式分解可以转换为若干个高级范式的关系模式的集合，这个过程称为关系模式的规范化。范式和规范化方法4.34.3.1第一范式（1NF）

定义4.5：如果关系模式R的每个属性都是不可分解的基本数据项，则称R属于第一范式，记为R∈1NF。第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。但是满足第一范式的关系模式并不一定是一个好的关系模式如表4-2所示的关系模式是一个非规范化的关系模式，因为表中的数据项“高级职称人数”不是基本的数据项，它是由两个基本数据项组成的复合数据项。将非第一范式的关系模式转换成满足第一范式的关系模式，只需将所有数据项都分解为不可再分的最小数据项即可。由表4-2转换后的满足第一范式的表如表4-3所示。

表4-2非第一范式的表

学院名称高级职称人数

教授副教授信电学院315管理学院526外语学院3124.3.1第一范式（1NF）学院名称教授副教授信电学院315管理学院526外语学院312表4-3满足第一范式的表4.3.1第一范式（1NF）4.3.2第二范式（2NF）

定义4.6：如果关系模式R∈1NF，且每个非主属性都完全函数依赖于主键，则称R属于第二范式，记为R∈2NF。由定义可知，如果某个1NF的关系的主键只由一个属性组成或关系的全体属性均为主属性，那么这个关系就是2NF。如果主键是由多个属性列共同构成的复合主键，并且存在非主属性对主属性的部分函数依赖，则这个关系就不是2NF。

【例4-6】对于关系S(Sno,Sname,Ssex,Sdept,Dean,Cno,Cname,Sorce)，主键为(Sno,Cno)。由于存在非主属性姓名（Sname）、性别（Ssex）、课程名（Cname）部分函数依赖于(Sno,Cno)，因此S不属于2NF。不满足2NF的关系模式存在冗余及操作异常，需要进一步规范化。可以通过模式分解将非2NF的关系模式分解为多个满足2NF的关系模式。分解步骤如下：

（1）首先用组成主键的属性集合的每个子集作为主键构成若干关系，对于关系S分解为如下3个子关系：

S1(Sno,…)，Sno为主键

S2(Cno,…)，Cno为主键

S3(Sno,Cno,…)，(Sno,Cno)为主键4.3.2第二范式（2NF）

（2）对于每个子关系，将依赖于此主键的属性放置到此关系中，则有：

S1(Sno,Sname,Ssex,Sdept,Dean)，Sno为主键

S2(Cno,Cname)，Cno为主键

S3(Sno,Cno,Sorce)，(Sno,Cno)为主键

模式分解后，消除了原关系S中的部分函数依赖，即S1、S2、S33个关系模式都不存在部分函数依赖，S1、S2、S3都属于2NF。分析一下S1存在的问题：（1）数据冗余。每个学院都有多名学生，都要存储学院名和院长名，会出现数据冗余。（2）插入异常。学院刚成立，无在校学生，无法插入该学院信息。（3）删除异常。假设某学院的全部学生都毕业了，则该学院的信息也会丢失。（4）修改复杂。若某学院更换了院长，需要修改所有学生的Dean属性值。由此可见，满足第二范式的关系模式仍然可能出现数据冗余和操作异常。这是因为第二范式没有排除传递函数依赖。因此，还需要对满足第二范式的关系模式进行进一步分解。4.3.3第三范式（3NF）

定义4.7：如果关系模式R∈2NF，且所有非主属性都不传递函数依赖于任何候选键，则R∈3NF。

【例4-7】分解例4-6中的关系S1，使其满足3NF的要求。解：在关系S1中，院长（Dean）传递函数依赖于学号（Sno），即SnoDean，所以S1不属于3NF。将关系S1(Sno,Sname,Ssex,Sdept,Dean)进一步分解，消除传递依赖。分解步骤如下：（1）对于不是候选键的每个决定因素，从关系中删除依赖它的所有属性。在关系S1中，学院（Sdept）不是候选键，但却是决定因素，从关系S1中删除依赖它的属性院长（Dean），得到新的关系S11(Sno,Sname,Ssex,Sdept)。（2）新建一个关系，该关系中包含原关系中不是候选键的决定因素以及所有依赖该决定因素的属性，并将决定因素作为该关系的主键。对于关系S1，新建的关系为S12(Sdept,Dean)，主键为Sdept。关系S1分解后消除了传递函数依赖，因此S11和S12都满足3NF。

由于3NF关系模式中不存在非主属性对主键的部分依赖和传递依赖，因而在很大程度上消除了数据冗余和操作异常，因此在通常的数据库设计中，一般要求达到3NF。3NF只是规定了非主属性对键的依赖关系，而没有限制主属性对键的依赖关系。若存在主属性对键的部分函数依赖和传递函数依赖关系，同样会出现数据冗余、插入异常、删除异常以及修改异常问题。【例4-8】假设有关系CSC(City,Street,Code)，其中各属性分别代表城市、街道和邮政编码，其语义为：城市和街道可以决定邮政编码，邮政编码可以决定城市。因此有：(City,Street)→Code,Code→City其候选键为(City,Street)和(Code,Street)，此关系模式中不存在非主属性，故CSC∈3NF。

现在分析一下此关系模式存在的问题。假设取(City,Street)为主键，则当插入数据时，如果没有街道信息，则一个邮政编码所属城市这样的信息就无法保存到数据库中，因为Street不能为空。由此可见，即使是满足3NF的表，也有可能存在异常。4.3.4BCNF

在3NF关系模式中存在异常的原因主要是3NF并没有排除主属性对候选键的部分依赖和传递依赖。如在此例中，Code→City，Code是决定因素，但不是候选键。CSC中存在主属性City对候选键(Code,Street)的部分依赖。在此情况下产生了BCNF。

1974年，Boyce和Codd等人从另一个角度研究了范式，发现函数依赖中的决定因素和键之间的联系与范式有关，从而创立了另一种第三范式，称为Boyce-Codd范式，简称BCNF，但其条件比3NF更苛刻。通常认为BCNF是修正的第三范式。4.3.4BCNF4.3.4BCNF

定义4.8：设关系模式R∈1NF，如果对于R的任意一个函数依赖X→Y，X必为候选键，则R∈BCNF。等价于：每个决定属性集（因素）都包含（候选）码。

BCNF的关系模式都具有如下3个性质。（1）所有非主属性都完全函数依赖于每个候选键。（2）所有主属性都完全函数依赖于每个不包含它的候选键。（3）没有任何属性完全函数依赖于非候选键的任何一组属性。4.3.4BCNF若R∈BCNF

所有非主属性对每一个码都是完全函数依赖所有的主属性对每一个不包含它的码，也是完全函数依赖没有任何属性完全函数依赖于非码的任何一组属性R∈BCNFR∈3NF

4.3.4BCNF

【例4-9】分析关系模式T(Tno,Tname,Tsex)中，各属性分别代表教师号、教师姓名、性别。

解：T只有一个主键Tno，没有任何属性对Tno部分依赖或传递依赖，所以T∈3NF。同时Tno是T中唯一的决定因素，所以T∈BCNF。

4.3.4BCNF

【例4-10】分析关系模式STC(S,T,C)中，S表示学生，T表示教师，C表示课程。每一教师只教一门课。解：每门课程有若干教师，某一学生选定某门课程，就对应一个固定的教师。由语义可得到函数依赖，如图4-1所示：(S,C)→T,(S,T)→C,T→C

4.3.4BCNF

该关系模式中，(S,C)和(S,T)都是候选键。

因为没有任何非主属性部分依赖和传递依赖于候选键所以STC∈3NF。但STC不是BCNF关系，因为T是决定因素，但它不是候选键。

STC可以分解为ST(S,T)与TC(T,C)，它们都是BCNF。

3NF和BCNF是对以函数依赖为基础的关系模式规范化程度的衡量标准。3NF与BCNF的关系

R∈BCNFR∈3NF如果R∈3NF，且R只有一个候选码

R∈BCNFR∈3NF

如果一个关系数据库中的所有关系模式都属于BCNF，那么在函数依赖范畴内，它已实现了模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删除异常。至此，分别讨论了1NF、2NF、3NF和BCNF，其中1NF是关系模式所隐含的，2NF只具有历史意义，最重要、应用最广泛的是BCNF和3NF，因为它们能满足一般应用的数据处理需求。4.3.5多值依赖与第四范式1．多值依赖定义4.9：设有关系模式R(U)，X、Y、Z是U的子集，且Z=U−X−Y。当且仅当R的任一关系r在（X、Z）上的每一个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关时，称Y多值依赖于X，记作X→→Y。

如果X→→Y，但Z=U−X−Y=Ф，则称X→→Y为平凡的多值依赖，否则为非平凡的多值依赖。4.3.5多值依赖与第四范式

【例4-11】某大学某一门课程由多个教师讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。用关系模式Teach(C,T,B)表示，其中C表示课程，T表示教师，B表示参考书。表4-4表示了关系模式Teach的一个关系实例。表4-4关系模式Teach的一个关系实例课程C教师T参考书B数据库原理及应用数据库原理及应用数据库原理及应用数据库原理及应用数据库原理及应用数据库原理及应用数据结构与算法数据结构与算法数据结构与算法数据结构与算法数据结构与算法数据结构与算法周晓明周晓明周晓明程羽姗程羽姗程羽姗程羽姗程羽姗程羽姗王宏伟王宏伟王宏伟数据库系统概论SQLServer2000离散数学数据库系统概论SQLServer2000离散数学数据结构与算法数据结构离散数学数据结构与算法数据结构离散数学4.3.5多值依赖与第四范式Teach∈BCNFTeach具有唯一候选键(C，T，B)，即全键Teach模式中存在的问题(1)数据冗余度大(2)插入操作复杂(3)删除操作复杂

经过分析可以发现，在关系模式Teach中，每个(C,B)上的值对应一组T值，而且这种对应与B无关。如与(C,B)对应的两个元组(数据库原理与应用,数据库系统概论)和(数据库原理与应用,离散数学)在B属性上的值不同，但它们对应同一组T值{周晓明,程羽姗}，由此得出T多值依赖于C，即C→→T。也就是关系模式Teach中存在的这种多值依赖的数据依赖，造成了上述问题的存在。存在多值依赖4.3.5多值依赖与第四范式多值依赖具有以下性质：（1）替代性。若X→Y，则X→→Y，即X→Y是X→→Y的特例。（2）对称性。若X→→Y，则X→→U−X−Y。（3）传递性。若X→→Y，Y→→Z，则X→→Z−Y。（4）合并性。若X→→Y，X→→Z，则X→→YZ。（5）若X→→Y，X→→Z，则X→→Y∩Z。（6）若X→→Y，X→→Z，则X→→Y-Z，X→→Z–Y。4.3.5多值依赖与第四范式2．第四范式（4NF）定义4.10：关系模式R∈1NF，如果对于R的每个非平凡多值依赖X→→Y（YX），X都含有候选键，则称R属于第四范式，记为R∈4NF。

由4NF的定义可以知道，4NF限制了关系模式的属性之间不允许出现非平凡且非函数依赖的多值依赖。因为对于每一个非平凡的多值依赖X→→Y，X都含有候选键，所以X→Y，故4NF所允许的非平凡的多值依赖实际上就是函数依赖。如果一个关系模式满足BCNF，但不是4NF，这样的关系模式仍然可能存在问题，还需要继续规范化使其达到4NF。如果一个关系模式满足4NF，则它一定满足BCNF；反之不然。4.3.5多值依赖与第四范式

例4-11的关系模式Teach中，主键是(C,T,B)，即全键。C→→T，C→→B，它们都是非平凡的多值依赖，但C不是候选键，所以Teach不属于4NF。将Teach分解为T(C,T)和B(C,B)，虽然存在C→→T，C→→B，但它们是平凡的多值依赖，所以T∈4NF，B∈4NF，这样关系模式Teach存在的问题得到了较好地解决，如表4-5和表4-6所示。表4-5关系T表4-6关系B课程C教师T课程C参考书B数据库原理及应用数据库原理及应用数据结构与算法数据结构与算法周晓明程羽姗程羽姗王宏伟数据库原理及应用数据库原理及应用数据库原理及应用数据结构与算法数据结构与算法数据结构与算法数据库系统概论SQLServer2000离散数学数据结构与算法数据结构离散数学4.3.5多值依赖与第四范式

函数依赖和多值依赖是两种最重要的数据依赖。如果只考虑函数依赖，则属于BCNF的关系模式规范化程度是最高的；如果考虑多值依赖，则属于4NF的关系模式规范化程度是最高的。实际上，数据依赖中除函数依赖和多值依赖之外，还有其他数据依赖，如连接依赖。函数依赖是多值依赖的一种特殊情况，而多值依赖实际上又是连接依赖的一种特殊情况。但连接依赖不像函数依赖和多值依赖可由语义直接导出，而是在关系的连接运算时反映出来。存在连接依赖的关系模式仍然可能存在数据冗余、操作异常等问题。如果消除了属于4NF的关系模式中存在的连接依赖，则可以进一步达到满足5NF的关系模式。

4.3.6关系模式的规范化

关系数据库的规范化理论是数据库逻辑设计的工具目的：尽量消除插入、删除异常，修改复杂，数据冗余基本思想：逐步消除数据依赖中不合适的部分实质：概念的单一化4.3.6关系模式的规范化一个关系模式的规范化过程如图4-2。图4-2各种范式及规范化过程4.3.6关系模式的规范化不能说规范化程度越高的关系模式就越好在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式上面的规范化步骤可以在其中任何一步终止数据依赖的公理系统4.41．函数依赖集F的逻辑蕴含

定义4.11：对于满足一组函数依赖F的关系模式R(U,F)，其任何一个关系r，若函数依赖X→Y都成立（即r中任意两元组t、s，若t[X]=s[X]，则t[Y]=s[Y]），则称F逻辑蕴含X→Y。例如，关系模式S中存在函数依赖Sno→(Sname,Sage)它蕴含两个函数依赖：Sno→Sname，Sno→Sage。对于关系模式R(U,F)，考虑到F所蕴含的所有函数依赖，就有函数依赖集闭包的概念。4.4.1函数依赖的逻辑蕴含与函数依赖集的闭包4.4.1函数依赖集的闭包2．函数依赖集闭包

定义4.12：所有被一个已知函数依赖集F逻辑蕴含的那些函数依赖的集合称为F的闭包（Closure），记为F+。为了用一套系统的方法求F+，还必须遵循一组函数依赖的推理规则。

1．Armstrong公理系统（Armstrong’saxiom）

对于关系模式R(U,F)，X、Y、Z是U的子集，F是U上的一组函数依赖。对R(U,F)有以下推理规则：（1）A1：自反律。如果YX，则X→Y。

注意：由自反律得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。（2）A2：增广律。如果ZW且X→Y，则XZ→YZ。（3）A3：传递律。如果X→Y且Y→Z，则X→Z。4.4.2函数依赖的推理规则2．其他推理规则

由3条独立推理规则，可得到3条推论

推论1：合并规则若X→Y，X→Z，有X→YZ。

证明：由X→Y，可知X→XY（增广律）；由X→Z，知XY→YZ（增广律），所以X→YZ（传递律）。

推论2：分解规则。若X→Y，ZY，有X→Z。

证明：由ZY，可知Y→Z（自反律），又因为X→Y，所以X→Z（传递律）。

推论3：伪传递规则。若X→Y，WY→Z，有XW→Z。

证明：由X→Y，得到WX→WY（增广律），又因为WY→Z，所以有XW→Z（传递律）。

【例4-12】设有关系模式R(A,B,C,D,E)及其上的函数依赖集F={AB→CD,A→B,D→E}，求证F必蕴含A→E。证明：∵A→B（已知）

∴A→AB（增广律）

∵AB→CD（已知）

∴A→CD（传递律）

∴A→C，A→D（分解规则）

∵D→E（已知）

∴A→E（传递律）

证毕4.4.3属性集的闭包及其算法1．属性集闭包定义4.13:

设有关系模式R(U)，F为属性集U上的一组函数依赖，X包含于U，定义={A|X→A能由F根据Armstrong公理导出}，称为属性集X关于函数依赖集F的闭包。2.F逻辑蕴含的充要条件

定理4.2设F为属性集U上的一组函数依赖，X、YU，X→Y能由F根据Armstrong公理导出的充分必要条件是Y。于是，判定X→Y是否能由F根据Armstrong公理导出的问题，就转化为求，并判定Y是否包含于的问题。该问题可由算法4.1解决。4.4.3属性集的闭包及其算法3．求属性集闭包算法算法4.1求属性集X（XU）关于U上的函数依赖集F的闭包。

输入：属性全集U、U上的函数依赖集F，以及属性集XU。输出：X关于F的闭包。方法：根据下列步骤计算一系列属性集合X(0),X(1),…（1）令X(0)=X，i=0。（2）令X(i+1)=X(i)∪B。其中：B={A|(V)(W)(V→WF∧VX(i)∧AW)}，即B是这样的集合：在F中寻找满足条件VX(i)的所有函数依赖V→W，并记属性W的并集为B。（3）判断X(i+1)是否等于X(i)。（4）若X(i+1)≠X(i)，则用i+1取代i，返回第（2）步。（5）若X(i+1)=X(i)，则X(i)即为，算法终止。该算法中的U、X和F都是有限集，它们的任何子集也是有限集；另外，算法每一步的中间结果均满足X(i)U，BU，从而X(i)不可能无限扩大，即计算过程是有限的，经过有限次循环后，一定有X(i)=X(i+1)=X(i+2)=…。4.4.3属性集的闭包及其算法【例4-13】F{AB→C,C→A,BC→D,ACD→B,D→EG,BE→C,CG→BD

CE→AG}令X=BD，求。

4.4.4候选键的计算

前面曾给出候选键的定义。可以用函数集闭包的概念描述候选键：对于关系模式R(U,F)，X是U的子集，如果X→U，即UX+中，则称X为R的一个超键，若X'是X的任一真子集，而UX'+，则X是R的候选键。4.4.4候选键的计算对于关系模式R(U,F)，属性集合U中的属性可以分为4类。（1）L类：仅出现在F中的函数依赖左边的属性。（2）R类：仅出现在F中的函数依赖右边的属性。（3）N类：F中的函数依赖左右两边都未出现的属性。（4）LR类：在F中的函数依赖两边都出现过的属性。

定理4.3对于给定的关系模式R及函数依赖集F，有如下结论：（1）若X、U是L类属性，则X必定是R的某个候选键的成员。（2）若X、U是L类属性，并且X+包含了U，则X必定是R的唯一候选键。（3）若X、U是R类属性，则X不在任何候选键中。（4）若X、U是N类属性，则X包含在R的任一个候选键中。（5）若X、U是R类和L类属性组成的属性集合，且X+包含了U，则X是R的唯一候选键。4.4.4候选键的计算【例4-14】设有关系模式R(A,B,C,D)，函数依赖集F={D→B,B→D,AD→B,AC→D},求R的所有候选键。

解：在F中，A、C属性是L类，B、D属性是LR类。A、C属性必在R的候选键中。而(AC)+=ABCD，包含了R的全部属性，且U不在A+、C+中。故AC是R的唯一候选键。算法4.2候选键算法

输入：关系模式R，属性集U及函数依赖集F。输出：关系模式R的所有候选键。（1）由F，将R的所有属性分为L、R、N和LR类，并用X代表L类和N类，Y代表LR类属性。（2）求X+，若X+包含了R的全部属性，则X即为R的唯一候选键，转（5）否则转（3）。（3）在Y中取一个属性A，求(XA)+，若包含了R的全部属性，则转（4），否则，换一个属性重复这一过程，直到试完所有Y中的属性。（4）如果已经找到所有的候选键，则转（5），否则在Y中依次取2个属性、3个属性…，求它们的闭包，直到其闭包包含R的所有属性。（5）停止，输出结果。4.4.4候选键的计算【例4-15】设有关系模式R(A,B,C,D,E)，函数依赖集F={A→BC,CD→E,B→D,E→A}，求R的所有候选键。解：R中所有属性都是LR类属性，没有L、R、N类属性。根据算法4.2，需要从LR类中依次取出一个属性并分别求它们的闭包：A+=ABCDE，B+=BD，C+=C，D+=D，E+=ABCDE。A+及E+都包含了R的全部属性，A、E分别是R的候选键。下面再从BCD中取两个属性的集合计算闭包：(BC)+=ABCDE，(CD)+=ABCDE，(BD)+=BD。(BC)+和(CD)+都包含了R的全部属性，属性集BC和CD也分别是R的候选键。至此R中不可能存在其他的候选键了，所以R的候选键为A、E、BC、CD。定理4.4：Armstrong公理系统是正确的、完备的。1．正确性证明4.4.5函数依赖推理规则的完备性（1）正确性的概念：Armstrong公理系统是正确的。（2）证明：要证明Armstrong公理系统是正确的，只要证明规则A1、A2、A3是正确的即可。①自反律A1是正确的。证明：设YXU，对R(U,F)的任一关系r中的任意两个元组t、s有：若t[X]=s[X]，由于YX，有t[Y]=s[Y]，所以X→Y成立，自反律得证。②增广律A2是正确的。证明：设X→Y为F所蕴含，且ZU，设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所蕴含，增广律得证。③传递律A3是正确的。证明：设X→Y及Y→Z为F所蕴含，对R(U,F)的任一关系r中的任意两个元组t、s有：若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含，传递律得证。2．完备性证明4.4.5函数依赖推理规则的完备性（1）完备性的概念：F+中的每一个函数依赖，必定可以由F出发，根据Armstrong公理推导出来。即若X→Y属于F+，则X→Y必定可以由F出发，根据Armstrong公理推导出来。（2）证明：证明完备性的逆否命题，即若函数依赖X→Y不能由F从Armstrong公理导出，那么它必然不为F所蕴含，其证明分3步。①若V→W成立，且V，则W。证明：因V，所以X→V成立；于是X→W成立（因为X→V，V→W），所以W。4.4.5函数依赖推理规则的完备性②构成一张二维表r，它由图4-3所示的两个元组构成，可以证明r必是R(U,F)的一个关系，即F中的全部函数依赖在r上成立。rU-t1111…1111...1t2111...1000...0

图4-3二维表r及其元组

若r不是R(U,F)的关系，则必是由于F中有函数依赖V→W在r上不成立所致。由r的构成可知，V必定是的子集，而W不是的子集，与第①步矛盾，所以r必是R(U,F)的一个关系。③若X→Y不能由F从Armstrong公理导出，则Y不是的子集，因此必有Y的子集Y′满足Y′包含于U−，则X→Y在r中不成立，即X→Y必不为R(U,F)所蕴含。4.4.5函数依赖集的等价、覆盖和最小函数依赖集2．最小函数依赖集的定义

定义4.14：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖：（1）F中任一函数依赖的右部仅含有一个属性。（2）F中不存在函数依赖X→A，使得F与F−{X→A}等价。（3）F中不存在函数依赖X→A，X有真子集Z使得F−{X→A}∪{Z→A}与F等价。

上述3个条件的作用分别如下：条件（1）保证每个函数依赖的右部都不会有重复的属性。条件（2）保证F中没有冗余的函数依赖。条件（3）保证每个函数依赖的左部没有冗余的属性。

定义4.15：每一个函数依赖集F均等价于一个极小函数依赖集Fm，此Fm称为F的最小依赖集。3．最小函数依赖集的求解算法【例4-16】F={A→B,B→A,B→C,A→C,C→A}，Fm1={A→B,B→C,C→A}，Fm2={A→B,B→A,A→C,C→A}，这里给出了F的两个最小依赖集Fm1和Fm2。

若改造后的F与原来的F相同，那么就说明F本身就是一个最小依赖集，因此定义4.15的证明给出的极小化过程也可以看成是检验F是否是极小依赖集的一个算法。两个关系模式R1(U,F)和R2(U,G)，如果F与G等价，那么R1的关系一定是R2的关系。反过来，R2的关系也一定是R1的关系。所以在R(U,F)中用与F等价的依赖集G来取代F是允许的。关系模式的分解4.5把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义关系模式的分解4.54.5.1模式分解的定义