汇编语言：第7章 关系数据库规范化理论

第7章关系数据库规范化理论

7.1关系规范化的作用7.2函数依赖7.3关系模式的规范化7.4多值依赖和第四范式7.5关系的规范化程度7.6函数依赖公理与模式分解7.7小结7.1关系规范化的作用

所谓规范化,就是用形式更为简洁、结构更加规范的关系模式取代原有关系的过程。例1有三个属性的工资表（姓名,级别,工资）关系模式。对应此模式建立的表如表7-1所示工资表

姓名级别工资周诚106500刘老师106500陈头76800胡院86650任老师116300犀利哥116300

7.1.1存在的问题

1.数据冗余度大表7-1中,工资是从级别推导出的,但却重复存放。数据在数据库中的重复存放称为数据冗余。冗余度大,不仅浪费存储空间,重要的是在对数据进行修改时,又易造成数据的不一致性。

如10级的工资变化时,如果表中有K个职工的工资为10级,就需要修改K次,一旦遗漏就使数据不一致。2.插入与删除异常无法插入某部分信息或删除掉不应删除的信息称为插入或删除异常。例如,9级工资为6600元的信息无法插入表。因为该表的码是姓名,而目前无职工工资级别为9级,表中不能插入码为空值的记录。姓名级别工资周诚106500刘老师106500陈头76800胡院86650任老师116300犀利哥116300

即:在插入一行时,此关系模式强迫同时增加关于两个实体的数据。

又如:要删除陈头记录时,又将7级工资的信息一起删去了。即在删除一行时,删除了关于两个实体的数据。

7.1.2解决方法上述现象的产生,是由于关系模式不合理。

如果一个关系中,存储了两个或两个以上实体的数据,一般应将它分解为多个关系,使每个关系只有一个实体。

将表7-1分解为两个模式表达：

职工级别（姓名,级别）,

级别工资（级别,工资）,

如表7-2、表7-3所示。表7-2职工级别表7-3级别工资姓名级别周诚10刘老师10陈头7胡院8任老师11犀利哥11级别工资1065007680086650116300

改进后,有如下好处：

(1)数据量减少

设有n个职工,m个工资级别,则表7-1有3n个数据,表7-2和表7-3共有2n+2m个数据,显然后者的数据量要少。

(2)表达能力强

表7-1中无法进入的信息（如9级工资）,而在采用改进后的两个模式表达时则可加入；当删除职工犀利哥时,也不会丢失11级工资信息。

(3)修改方便

改进后,修改某一级别工资时只要修改一处。

改进后的关系模式存在另外一个问题,当查询某个职工的工资时,需要将两个关系连接后进行查询,而关系的连接代价是很大的。

什么样的关系模式需要分解？

分解关系模式的理论依据又是什么？

分解后能完全消除上述三种问题吗？回答这些问题需要理论的指导。下面将加以讨论。7.2函数依赖

7.2.1属性间的关系前面章节讲到客观世界的事务间有着错综复杂的联系。实体联系：实体与实体之间的联系；

实体内部各属性间的联系。

在数据库建模（E-R）中主要讨论了前一类联系,现在讨论第二类联系。

属性间的联系可分为以下三类：

1.一对一关系（1∶1）以职工模式为例：职工（职工号,姓名,职称,部门）,如果该企业（或单位）中职工无重名,则属性职工号与姓名之间是1∶1关系。一个职工号唯一地决定一个姓名,一个姓名也可决定唯一的职工号。设X、Y是关系R的两个属性（集）。如果对于X中的任一具体值,Y中至多有一个值与之对应,且反之亦然,则称X、Y两属性间是一对一关系。

2.一对多关系（1∶m）职工模式中,职工号和职称间是一对多关系。一个职工号只对应一种职称（如周诚老师只能对应实验师）,但一种职称却可对应多个职工号（如实验师可对应多名老师）。设X、Y是关系R的两个属性（集）。如果对于X中的任一具体值,Y中至多有一个值与之对应,而Y中的一个值却可以和X中的n个值（n≥0）相对应,则称Y对X是一对多关系。

3.多对多关系（m∶n）在职工模式中,职称和部门之间是多对多关系。一种职称可分布在多个部门中（如每一个部门中均可有工程师）,而一个部门中也可有多个职称。设X、Y是关系R的两个属性（集）。如果对于X中的任一具体值,Y中有m（m≥0）个值与之对应,而Y中的一个值也可以和X中的n个值（n≥0）相对应,则称Y对X是多对多关系。

上述属性间的三种关系实际上是属性值之间相互依赖又相互制约的反映,称为属性间的数据依赖。数据依赖是现实世界属性间相互联系的抽象,是世界内在的性质,是语义的体现。数据依赖共有三种：函数依赖（FunctionalDependency,简称FD）多值依赖（MultivaluedDependency,简称MVD）连接依赖（JoinDependency,简称JD）其中最重要的是函数依赖和多值依赖。

7.2.2函数依赖

函数依赖是属性之间的一种联系。假设给定一个属性的值,就可以唯一确定（查到）另一个属性的值。例如,知道职工号的值,可以得出其对应的职称的值。如果这种情况成立，就可以说职称函数依赖于职工号。

定义1：

所谓函数依赖是指在关系R中,X、Y为R的两个属性或属性组,如果对于R的所有关系r都存在：对于X的每一个具体值,Y都只有一个具体值与之对应,则称属性Y函数依赖于属性X。或者说,属性X函数决定属性Y,记作X→Y。其中X叫决定因素,Y叫被决定因素。

此定义可简单表述为：如果属性X的值决定属性Y的值,那么属性Y函数依赖于属性X。换一种说法是,如果知道X的值,就可以获得Y的值。

(1)若Y函数不依赖于X,记作X→Y。

(2)若X→Y,Y→X,记作X

Y。前面讨论的属性间的三种关系,并不是每一种关系中都存在函数依赖。

(1)如果两属性集X、Y间是1∶1关系,则存在函数依赖：X

Y。如职工关系模式中，如果不允许同名职工存在,则有：职工号姓名。

(2)如果两属性集X、Y间是1∶m关系,则存在函数依赖：X→Y。如：职工号→职称。

(3)如果两属性集X、Y间是m∶n关系,则不存在函数依赖。如职称与部门之间即如此。

关系模式学生课程属性间的函数依赖：

学生课程（学号,课程号,成绩,教师,教师办公室）

该关系中,成绩要由学生号和课程号共同确定,但教师和教师办公室由课程号决定,关系中包含了以下四种函数依赖关系：

（学号,课程号）→成绩；课程号→教师；教师→教师办公室;课程号→教师办公室；

注意：属性间的函数依赖不是指R的某个或某些关系满足上述限定条件,而是指R的一切关系都要满足定义中的限定。只要有一个具体关系r不满足定义中的条件,就破坏了函数依赖,使函数依赖不成立。

7.2.3码的定义已对码进行了直观的定义,下面用函数依赖的概念对码作出较为精确的形式化的定义。定义2设K是关系模式R（U,F）中的属性或属性组,K′是K的任一真子集。若K→U,而不存在K′→U,则K为R的候选码（CandidateKey）。若候选码多于一个,则选定其中的一个为主码（PrimaryKey）包含在任一候选码中的属性,叫主属性（PrimeAttribute）不包含在任何码中的属性称为非主属性（NonprimeAttribute）或非码属性（Non―keyAttribute）关系模式中,最简单的情况,单个属性是码,称为单码（SingleKey）最极端的情况,整个属性组是码,称为全码（All―Key）

有关演员、制片公司、电影的关系模式如下：

签约（演员名,制片公司名,电影名）该关系模式反映了某个演员为某部电影与某制片公司的签约情况。一个制片公司可以为一部电影和多个演员签约一个演员可以和多个制片公司签约饰演多部电影中的角色一部电影可由不同的制片公司制作

所以此关系模式的码为？

（演员名,制片公司名,电影名）,即全码。

定义3设有两个关系模式R和S,X是R的属性或属性组,并且X不是R的码,但X是S的码（或与S的码意义相同）,则称X是R的外部码（ForeignKey）,简称外码。设有如下两个关系模式：职工（职工号

,姓名,性别,职称,部门号）部门（部门号

,部门名,电话,负责人）其中部门号不是职工表的码,但是部门表的码,所以部门号在职工表中称为外码。关系间的联系可通过同时存在于两个或多个关系中的主码和外码的取值来建立。主码和外部码提供了一个表示关系间联系的途径。

7.2.4函数依赖和码的唯一性码是由一个或多个属性组成的可唯一标识元组的最小属性组。码在关系中总是唯一的,即一个码函数唯一地决定一行。如果码的值重复,则整个元组都会重复。否则,违反实体完整性规则。

与码的唯一性不同,函数依赖的决定因素可能是唯一的,也可能不是唯一的。如果我们知道A决定B,且A和B在同一关系中,但我们仍无法知道A是否能决定除B以外的其他所有属性，所以无法知道A在关系中是否是唯一的。看关系模式：

学生课程（学生号,课程号,成绩,教师,教师办公室）关系中包含的四种函数依赖为：（学生号,课程号）→成绩；课程号→教师；课程号→教师办公室；教师→教师办公室其中,课程号是决定因素,但它不是唯一的。因为它能决定教师和教师办公室,但不能决定属性成绩。但决定因素（学生号,课程号）除了能决定成绩外,当然也能决定教师和教师办公室,所以它是唯一的。

关系的码应取（学生号,课程号）。

函数依赖性是一个与数据有关的事物规则的概念。如果属性B函数依赖于属性A,那么,若知道了A的值,则完全可以找到B的值。这并不是说可以导算出B的值,而是逻辑上只能存在一个B的值。例如,在人这个实体中,如果知道某人的唯一标识符,如身份证号,则可以得到此人的性别、身高、职业等信息,所有这些信息都依赖于确认此人的唯一标识符。通过非主属性如年龄,无法确定此人的身高从关系数据库的角度：身高不依赖于年龄。意味着码是实体实例的唯一标识符。因此,在以人为实体来讨论依赖性时,如果已经知道是哪个人,则身高、体重等等就都知道了。码指示了实体中的某个具体实例。

7.3关系模式的规范化

7.3.1非规范化的关系

当一个关系中的所有分量都是不可分的数据项时,该关系是规范化的。表7-4

有组合数据项,表7-5

具有多值数据项,

不是规范化的表工号姓名职称系名系办公地学历毕业年份001陈头教授软件工程501本科研究生8083002周诚讲师数字媒体516本科90

7.3.2第一范式（1NF）

定义4如果关系模式R中属性具有原子性（不可分）,则R满足第一范式,简称1NF（FirstNormalForm）,记作R∈1NF。

1NF是对关系的最低要求,不满足1NF的关系是非规范化关系,如表7-4、表7-5所示。非规范化关系转化为1NF的方法很简单,当然也不是唯一的。对表7-4、表7-5分别进行横向和纵向展开,可分别转化为如表7-6、表7-7所示的符合1NF的关系。表7-6

消除组合数据项后的表

表7-7

消除多值数据项后的表关系数据库中的关系要满足第一范式。class(classID，className，classmate，monitor)满足第一范式？工号姓名职称系名办公地学历毕业年份001陈头教授软件工程501本科80001陈头教授软件工程501研究生83002周诚讲师数字媒体516本科90职工号姓名基本工资职务工资工龄工资

7.3.3第二范式（2NF）表7-7

虽然已符合1NF的要求,但表中存在大量的数据冗余和潜在的数据更新异常。

原因是该关系的码是（职工号,学历）,但姓名、职称、系名、系办公地址却与学历无关,即它们只与码的一部分有关。

码？PF

定义5设X、Y是关系R的两个不同的属性或属性组,且X→Y。

如果存在X的某一个真子集X′,使X′→Y成立,则称Y部分函数依赖于X,记作XY。反之,则称Y完全函数依赖于X,记作XY。

定义6如果一个关系R属于1NF,且它的所有非主属性都完全函数依赖于R的任一候选码,则R属于第二范式,记作R∈2NF。

例如,对于关系模式：

职工信息（职工号,姓名,职称,项目号,项目名称,项目排名）该模式存储了职工的信息和职工所参加的项目信息,码为（职工号,项目号）。函数依赖有：

因为：职工号→姓名,所以：

（职工号,项目号）姓名；

同样有：（职工号,项目号职称,

（职工号,项目号）项目名称；（职工号,项目号）项目排名因此非主属性姓名、职称、项目名称并不完全依赖于码,它不符合2NF的定义。PPPF不符合2NF定义的关系模式,会产生以下几个问题：

(1)插入异常。假如要插入一职工,但该职工还未参加任何项目,可插？根据实体完整性约束规则,关系中元组的主码属性不能为空,项目号(为空)是主属性,因此,该职工信息无法插入。

(2)删除异常。

假设有一职工,只参加了一个项目,现在,又从这个项目中退出来了，该职工的此项目记录将被删除,由于项目号是主属性,该记录只能被全部删除,该职工的其他信息也随着被删除。这样就删除了不该删除的信息,即出现了删除异常。

(3)修改异常。

当某个项目的项目名称发生变化时,必须修改多个元组,造成了修改的复杂化,一旦有遗漏,将破坏数据库中数据的一致性。可把模式分解，使其符合2NF：

职工信息（职工号,姓名,职称,项目号,项目名称,项目排名）

职工（职工号

,姓名,职称）排名（职工号,项目号

,项目排名）项目(项目号,项目名称)

同样,对于表7-7所示的关系模式：职工信息（职工号

,姓名,职称,系名,系办公地址,学历,毕业年份）由于也包含了部分函数依赖,不符合2NF的定义,可将其分解为下面两个关系模式（如何分？）：

职工信息（职工号

,姓名,职称,系名,系办公地址）学历（职工号,学历

,毕业年份）

推论：如果关系模式R∈1NF,且它的每一个候选码都是单码,则R∈2NF。（???）

7.3.4第三范式（3NF）

符合第二范式的关系模式仍可能存在数据冗余、更新异常等问题。如前面从表7-7分解出的职工信息关系模式：职工信息（职工号

,姓名,职称,系名,系办公地址）如果一个系有100位职工,那么系办公地址就要重复存储100次,存在着较高的数据冗余。原因是此关系模式的码是职工号,而系办公地址通过系名函数依赖于职工号,即职工号→系名,系名→系办公地址,是一个传递依赖的过程。

定义7在关系R中,X、Y、Z是R的三个不同的属性或属性组,如果X→Y,Y→Z，但Y→X且Y不是X的子集,则称Z传递依赖于X。再看表7-1的关系模式,它之所以存在着数据冗余、插入或删除异常,就是因为其中存在着传递函数依赖：姓名→级别,级别→工资

定义8如果关系模式R属于2NF,且它的每一个非主属性都不传递依赖于任何候选码,则称R是第三范式,记作R∈3NF。

推论1

如果关系模式R∈1NF,且它的每一个非主属性既不部分依赖、也不传递依赖于任何候选码,则R∈3NF。

推论2

不存在非主属性的关系模式一定为3NF。上述职工关系：职工信息（职工号

,姓名,职称,系名,系办公地址）不属于3NF

因为：职工号→系名,系名→系办公地址,传递依赖可把它分解如下,使其符合3NF：

职工（职工号

,姓名,职称,系名）系（系名

,系办公地址）

7.3.5改进的3NF——BCNF

第三范式的修正形式是Boyee―Codd范式（简称BCNF）,是由Boyee与Codd提出的。定义9设关系模式R（U,F）∈1NF,若F的任一函数依赖X→Y中X都包含了R的一个码,则称R∈BCNF。换言之,在关系模式R中,如果每一个决定因素都包含码,则R∈BCNF。

职工（职工号

,姓名,职称,系名）∈?NF

由BCNF的定义可以得到以下推论：如果R∈BCNF,则

R中所有非主属性对每一个码都是完全函数依赖;

R中所有主属性对每一个不包含它的码,都是完全函数依赖;

R中没有任何属性完全函数依赖于非码的任何一组属性。

定理：如果R∈BCNF,则R∈3NF一定成立。

证明：用反证法。如果R∈BCNF,但不是3NF,则R中一定存在传递函数依赖。即R中必定存在候选码X,非主属性A,属性组Y,其中A

X,A

Y,X→Y,使得X→Y→A成立。Y不是R的码,但Y是R的决定因素,根据BCNF的定义,R不是BCNF,与假设相矛盾。所以假设不成立。下面是一个BCNF的例子：职工（职工号

,姓名,职称,系名）

在该关系中,假定职工无重名,则候选码为职工号或姓名,除了职工号和姓名以外没有其他决定因素,即符合BCNF的定义,故该关系是BCNF的。该关系中的非主属性（职称或系名）对这两个码不存在部分函数依赖和传递函数依赖,因此是3NF的。

再看职工关系∈BCNF？

职工（职工号

,姓名,职称,系名,系地址）存在：系名→系地址是trivial（平凡的，FD左边不包含码）

再看职工关系∈3NF？存在：职工号→系名→系地址（传递依赖）

如果R∈3NF,R未必属于BCNF。3NF比BCNF放宽了一个限制,即允许决定因素不包含码。请看下面两个例子：例7.1通讯（城市名,街道名

,邮政编码）该关系的码是（城市名,街道名）

根据语义其函数依赖集为：

F={（城市名,街道名）→邮政编码,邮政编码→城市名}3NF?BCNF?

非主属性邮政编码完全函数依赖于码,且无传递依赖,属于3NF。

邮政编码也是一个决定因素,它没有包含码,所以该关系不属于BCNF。

例7.2授课（学生,教师,课程）假设该校规定：一个教师只能教一门课,每门课可由多个教师讲授。学生一旦选定某门课,教师就相应地固定。根据语义关系的函数依赖集为：

F={教师→课程,（学生,课程）→教师,

（学生,教师）→课程}

该关系的候选码为（学生,课程）或（学生,教师）,因此三个属性都是主属性,由于不存在非主属性,该关系一定是3NF的。

由于决定因素教师没包含码,该关系不属于BCNF。

不属于BCNF的关系模式,仍然存在数据冗余问题。如例7.2中如果有100个学生选定了某一门课,则教师与该课程的关系就要重复存储100次。可分解为如下两个BCNF的关系模式,消除此种冗余：教师（教师,课程）学生（学生,教师）

一个关系模式如果达到了BCNF,那么在函数依赖范围内,它已实现了彻底的分离,消除了数据冗余、插入和删除异常。规范化程度还可有更高的范式：4NF、5NF。例：建立一个数据库来描述学生的借书情况，有这样一些属性： 借书证号（S#）

姓名（SN）

所在系（SD）

电话（PHONE） 借阅的图书号（B#）

借阅图书名（BN）

借阅日期（DATE）用一个关系模式S（S#,SN,SD,PHONE,B#,BN,DATE）表示。坏的数据库设计中的异常S#SNSDPHONEB#BNDATE200713001王铭CS87654321B001数据结构20090403200713001王铭CS87654321B002数据库20090403200713001王铭CS87654321B003离散数学20090406200713001王铭CS87654321B004操作系统20090406200713001王铭CS87654321B005心理学20090420200713001王铭CS87654321B006人工智能20090420200612001李力MA12345678C001哲学20090501200712002张成MA12345678B001数据结构20090503主键为（S#，B#）“王铭”转系一个学生借多本书新生注册但没借书还掉了借的所有书更新异常插入异常删除异常冗余太大

解决方法:

将该模式分解下列成三个模式：

S（S#,SN,SD,PHONE），

B（B#,BN），

SB（S#,B#,DATE）总结：函数依赖是一种语义上的概念，不能仅由表中的元组集合归纳出来；函数依赖、部分函数依赖的定义。1NF,2NF,3NF,BCNF

规范化是关系数据库逻辑设计的一种方法；一个不好的数据库设计存在更新异常：插入异常、删除异常、更新异常(修改复杂)和数据冗余；导致异常的原因是：在一个关系模式中存在某些函数依赖。规范化就是将一个关系模式分解成多个模式，使得这些函数依赖不出现在同一个关系模式中的过程；使用规范化方法设计数据库的逻辑结构时，并不是要求数据库模式都达到最高范式，而是还需要平衡查询效率和更新代价。课堂练习1．现有如下关系模式：R(A，B，C，D，E),其中：A,B组合为码,R上存在的函数依赖有A,B→E，B→C，C→D，试问：(1)该关系模式满足2NF吗?为什么?(2)如果将关系模式R分解为：

R1(A，B，E)，R2(B，C，D)

指出关系模式R2的码，并说明该关系模式最高满足第几范式(在1NF～BCNF之内)?7.4多值依赖和第四范式

7.4.1多值依赖（MultivaluedDependency）在属性之间的数据依赖中,除了函数依赖,还有多值依赖。在讨论多值依赖之前,请先看一个例子,见表7-8。表7-8教师开课一览表

从表中可以得到如下信息：哪门课由哪些教师开,由哪些班级开设了这门课。因此,我们可以从已知的元组推出表中一定存在的其他元组。例如,如果已知表中存在元组：（网络技术,王宝钢,98级本科）（网络技术,张丽萍,99级大专）那么表中应该有元组：（网络技术,王宝钢,99级大专）（网络技术,张丽萍,98级本科）将表7-8转化为规范化的表7-9：教师开课表。表7-9教师开课表：CTC

这种依赖关系称为多值依赖。与函数依赖不同,函数依赖是属性值之间的约束关系,而多值依赖是元组值之间的约束关系。

定义10

设R（U）是属性集U上的一个关系模式,X、Y、Z是U的子集,且Z=U-X-Y。如果对R（U）的任一关系r,给定一对（x,z）值,都有一组Y值与之对应,这组Y值仅仅决定于x值而与z值无关。称Y多值依赖于X,或X多值决定Y,记作X→→Y。

在表7-9中,对于一对（x,z）值（数据结构,00级本科）有一组Y值{王晓萍,陈保乐,刘彤彤}与之对应,这组值仅决定于课程“数据结构”。对于另一个（x,z）值（数据结构，00级辅修）,对应的仍是这组Y值{王晓萍,陈保乐,刘彤彤}。因此,课程→→教师。

多值依赖的另一个等价的形式化定义为：设关系模式R（U）,X、Y、Z是U的子集,Z=U-X-Y,r是R的任意一个关系,t1、t2是r的任意两个元组。如果t1[X]=t2[X],在r中存在元组t3,使得

t3[X]=

t1[X],t3[Y]=t1[Y],t3[Z]=t2[Z]

成立,则X→→Y。上述定义中,由于t1、t2的对称性,实际隐含着关系r中还存在着另一个元组t4,t4满足：

t4[X]=t1[X],t4[Y]=

t1[Y],t4[Z]=t2[Z]

换句话说,如果r有两个元组在X属性上的值相等,则交换这两个元组在Y上的属性值,得到的两个新元组也必是r中的元组。定义中如果Z=Ф（即Z为空集）,则称X→→Y为平凡的多值依赖,否则为非平凡多值依赖。例：

关系模式：供应（项目,供应商,零件）,假设一个项目可由不同的供应商供应该项目所需要的多种零件,一个供应商可为多个项目供应多种零件,如表7-10所示。表7-10供应

对于项目中的每一个Ii,都有一完整的供应商集合与之对应,同时交换供应商和零件的值所得的新元组必在原关系中。因此有：项目→→供应商,项目→→零件。

多值依赖具有以下性质：

(1)多值依赖具有对称性。若X→→Y,则X→→Z,其中Z=U-X-Y。(Y=U-X-Z)

如上例中,对于项目中的每一个Ii,都有一完整的零件集合与之对应。因此,项目→→零件。

(2)多值依赖具有传递性：若X→→Y,Y→→Z,则X→→Z-Y。

(3)若X→→Y,X→→Z,则X→→YZ。

(4)若X→→Y,X→→Z,则X→→Y∩Z。

(5)若X→→Y,X→→Z,则X→→Y-Z,X→→Z-Y。

一般来讲,当关系至少有三个属性,其中的两个是多值,且它们的值只依赖于第三个属性时,才会有多值依赖。即对于关系R（A,B,C）,如果A决定B的多个值,A决定C的多个值,B和C相互独立,这时才存在多值依赖。

在具有多值依赖的关系中,如果随便删去一个元组而破坏了其对称性,那么,为了保持多值依赖关系中数据的“多值依赖”性,必须删去另外的元组以维持其对称性。这个规则称为“多值依赖的约束规则”,这种规则只能由设计者在软件设计中加以体现,目前的RDBMS不具有维护此规则的能力。

函数依赖可看成是多值依赖的特例,即函数依赖的一定是多值依赖；多值依赖是函数依赖的概括,即存在多值依赖的关系,不一定存在函数依赖。

7.4.2第四范式（4NF）

定义11如果关系模式R∈1NF,对于R的每个非平凡的多值依赖X→→Y,X含有码,则称R是第四范式,即R∈4NF。

一个关系模式如果属于4NF,则一定属于BCNF,但一个BCNF的关系模式不一定是4NF的,R中所有的非平凡多值依赖实际上是函数依赖。

在前面的供应关系中,项目→→供应商,项目→→零件,且都是非平凡的多值依赖。

但该关系的码是全码（项目,供应商,零件）,而项目没有包含码（只是码的一部分）,所以该关系模式属于BCNF而不属于4NF。如将其分解为两个关系,可达到4NF：

需求（项目,零件）供应（项目,供应商）这两个关系中,项目→→零件,项目→→供应商,它们均是平凡多值依赖(Z={})。即关系中已不存在非平凡、非函数依赖的多值依赖,所以它们均是4NF。

一般地,如果关系模式R（X,Y,Z）满足X→→Y,X→→Z,那么可将它们分解为关系模式R1（X,Y）和R2（X,Z）。在一般应用中,即使作数据存储操作,也只要达到BCNF就可以了。因为应用中具有多值依赖的关系较少,因此需要达到4NF的情况也就比较少。

如果只考虑函数依赖，属BCNF规范化程度已最高如果考虑多值依赖，属4NF规范化程度是最高在理论上,还有与数据依赖中的连接依赖（JD）有关的第五范式（5NF）,这里就不再介绍了。7.5关系的规范化程度

各种规范化之间的关系为：

5NF

4NF

BCNF

3NF

2NF

1NF。关系规范化的目的是解决关系模式中存在的数据冗余、插入和删除异常、更新繁琐等问题。其基本思想是消除数据依赖中的不合适部分,使各关系模式达到某种程度的分离,使一个关系描述一个概念、一个实体或实体间的一种联系。

因此,规范化的实质是概念的单一化。

一般来说,规范化程度越高,分解就越细,所得数据库的数据冗余就越小,且更新错误也可相对减少。但是,如果某一关系经过数据大量加载后,主要用于检索,那么,即使它是一个低范式的关系,也不要去追求高范式而将其不断进行分解。因为在检索时,又会通过多个关系的自然连接才能获得全部信息,从而降低了数据的检索效率。即,数据库设计满足的范式越高,其数据处理的开销也越大。图7―1范式递进过程示意图关系规范化的递进过程如图所示：

所以,规范化的基本原则是：由低到高,逐步规范,权衡利弊,适可而止。通常,以满足第三范式为基本要求。把一个非规范化的数据结构转换成第三范式,一般经过以下几步：

(1)把该结构分解成若干个属于第一范式的关系。

(2)对那些存在组合码,且有非主属性部分函数依赖的关系必须继续分解,使所得关系都是属于第二范式。

(3)若关系中有非主属性传递依赖于码,则继续分解之,使得关系都属于第三范式。

关系模式的规范化过程是通过投影分解实现的,即用投影运算把一个模式分解成若干个高一级的关系模式。这种投影分解不是唯一的。在分解时应注意满足以下三个条件：

(1)分解是无损连接分解,分解后既不丢失又不增加信息。

(2)分解所得的所有关系都是高一级范式的。

(3)分解所得关系的个数最少。7.6*函数依赖公理与模式分解

在前面的规范化过程中,在进行模式分解时,并没有给出分解的算法。实际上,在规范化理论中,模式分解以及判断分解是否等价是有一定算法的。函数依赖的公理系统是模式分解算法的基础,它可以从已知的函数依赖,推导出其他函数依赖。下面首先讨论函数依赖的一套推论规则,这套规则是1974年由Armstrong提出来的,常被称为Armstrong公理系统。7.6.1

函数依赖公理

Armstrong公理系统设有关系模式R（U,F）,X,Y,Z

U,则对R（U,F）有：

·A1（自反律）：若Y

X,则X→Y；

·A2（增广律）：若X→Y,则XZ→YZ；

·A3（传递律）：若X→Y,Y→Z,则X→Z。

这些规则是保真的,它们不会产生错误的函数依赖。说明：XZ表示X∪Z。

引理7.1Armstrong公理是正确的。即如果函数依赖F成立,则由F根据Armstrong公理所推导的函数依赖总是成立的。证明：设t1、t2是关系R中的任意两个元组。

A1：

如果t1［X]=t2［X],则因为Y

X,所以有t1［Y]=t2［Y],故X→Y成立。

A2：

如果t1［XZ]=t2［XZ],则有t1［X]=t2［X]、

t1［Z]=t2［Z]。

A1（自反律）：若Y

X,则X→Y；

A2（增广律）：若X→Y,则XZ→YZ；

A3（传递律）：若X→Y,Y→Z,则X→Z。又已知X→Y,因此得t1[Y]=t2[Y]。

可知t1[YZ]=t2［YZ],故XZ→YZ成立。A3：如果t1[X]=t2[X],则t1[Y]=t2[Y]；

如果t1[Y]=t2[Y],则t1[Z]=t2[Z]。

可得：如果t1[X]=t2[X],则t1[Z]=t2[Z],即X→Z成立。

A1（自反律）：若Y

X,则X→Y；

A2（增广律）：若X→Y,则XZ→YZ；

A3（传递律）：若X→Y,Y→Z,则X→Z。定理7.1Armstrong公理是正确的、完备的。由Armstrong公理系统,可以得到以下三个推论：·

合成规则：若X→Y,X→Z,则X→YZ；·

分解规则：若X→YZ,则X→Y,X→Z；·

伪传递规则：若X→Y,WY→Z,则XW→Z。

A1（自反律）：若Y

X,则X→Y；

A2（增广律）：若X→Y,则XZ→YZ；

A3（传递律）：若X→Y,Y→Z,则X→Z。引理7.2X→A1A2…Ak成立的充分必要条件是X→Ai成立（i=1,2,…,k）。(1)A→H。由于A→B,B→H,使用传递律可得到A→H。(2)CG→HI。由于CG→H,CG→I,由合成律可得CG→HI。(3)AG→I。由于A→C,CG→I,由伪传递律可推出AG→I。

例7.3设关系模式R（A,B,C,G,H,I）,函数依赖集为

F={A→B,A→C,CG→H,CG→I,B→H},利用规则,可以得到关系中存在那些函数依赖？

7.6.2闭包及其计算

定义12设关系模式R（U,F）,U为R的属性集合,F为其函数依赖集,则称所有用Armstrong公理从F推出的函数依赖X→Ai中Ai的属性集合,为X的属性闭包,记作X+,读作X关于函数依赖集F的闭包。由引理7.2可以推出：引理7.3设关系模式R（U,F）,U为R的属性集合,F为其函数依赖集,X,Y

U,则从F推出X→Y的充要条件是Y

X+。

如果要判断X→Y是否能由F根据Armstrong公理导出,只需求出X+,判断Y是否为X+的子集。这可由算法7.1完成。算法7.1求属性集X关于函数依赖F的属性闭包X+。

输入：关系模式R的全部属性集U,U的子集X,U上的函数依赖集F。输出：X关于F的属性闭包X+。

步骤：设i=0,1,2,…。

(1)初始化：i=0,X(i）=X(0)=X。

(2)求属性集A。A是这样的属性：在F中寻找尚未用过的左边是X(i）子集的函数依赖：

Y(i)

X(i),并且在F中有Y(i)→Z(i),则A=Z(1)∪Z(2)∪…∪Z(i)；

(3)X(i+1)=X(i）∪A。

(4)判断以下条件之一是否成立,若有,则转向(5)；否则,i=i+1,转向(2)。

·X(i+1)=X(i）；

·

X(i）中已包含了R的全部属性；

·

在F中的每个函数依赖的右边属性中已没有X(i）中未出现过的属性；

·

在F中未用过的函数依赖的左边属性已没有X(i）的子集。

(5)输出X(i+1）,即为X+。是系统化寻找满足条件A∈X+的属性的方法。

例7.4设关系模式R（U,F）,其中,U={A,B,C,D,E,I},F={A→D,AB→C,BI→C,ED→I,C→E},求（AC）+。解：(1)令X={AC},则X(0)=AC。

(2)在F中找出左边是AC子集的函数依赖：A→D,C→E

(3)X(1)=X(0)∪D∪E=ACDE。

(4)很明显X(1)≠X(0),所以X(i)=X(1),并转向算法中的步骤(2)。

(5)在F中找出左边是ACDE子集的函数依赖：ED→I。

(6)X(2)=X(1)∪I=ACDEI。

(7)虽然X(2)≠X(1),但是F中未用过的函数依赖的左边属性已没有X(2)的子集,所以,可停止计算,输出（AC）+=X(2)=ACDEI。若属性集（X）+包含U，则X为超码，可以继续确定是否为码。

算法7.1可用伪=代码书写如下：输出结果存储在变量result中

result∶=X;WHILE(result发生变化)DOFOREACH函数依赖Y→ZINFDOBEGINIFY

resultTHENresult∶=result∪Z;END

7.6.3函数依赖的覆盖定义13设F和G是关系模式R（U）上的两个函数依赖集,如果F+=G+，则称F和G是等价的,记作F≡G。也可称为F覆盖G,或G覆盖F,或F、G相互覆盖。引理7.4F≡G的充分必要条件是F

G+、G

F+。引理7.5任一函数依赖集总可以为一右边都为单属性的函数依赖集所覆盖。证明：构造G={X→A|X→Y∈F且A∈Y}根据分解规则：G

F+；根据合并规则：F

G+。可得：F+=G+,即F为G所覆盖。证毕。

定义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等价。条件(2)保证了F中不存在多余的函数依赖,条件(3)保证了F中每个函数依赖的左边没有多余的属性。

定理7.2任一函数依赖集F均等价于一个极小函数依赖集Fm。

最小依赖集可由算法7.2计算出来。

算法7.2计算最小依赖集。

输入：一个函数依赖集F

输出：F的一个等价最小依赖集G。

步骤：

(1)应用分解规则,使F的每个函数依赖的右部属性都为单属性。

(2)依次去除F的每个函数依赖左部多余的属性。设XY→A是F的任一函数依赖,在F中求出X的闭包X+。如果X+包含了Y,则Y为多余属性,该函数依赖变为X→A。

(3)依次去除多余的函数依赖。设X→A是F的任一函数依赖,在F-{X→A}中求出X的闭包X+。如果X+包含了A,则X→A为多余的函数依赖,应该去除；否则,不能去除。

例7.5设有函数依赖集F={A→C,C→A,B→AC,D→AC,BD→A}

计算它等价的最小依赖集。解：

(1)化单依赖右边的属性,结果为

F1={A→C,C→A,B→A,B→C,D→A,D→C,BD→A}(2)去除F1的依赖中左边多余的属性。对于BD→A,由于有B→A,所以是多余的。结果为

F2={A→C,C→A,B→A,B→C,D→A,D→C}(3)去除F2中多余的依赖。因为：A→C,C→A,所以A=C。故：B→A、B→C以及D→A、D→C中之一为多余的。取F3={A→C,C→A,B→A,D→A}。在F3中：对于A→C,F3-{A→C}中A+=A；对于C→A,F3-{C→A}中C+=C；对于B→A,F3-{B→A}中B+=B；对于D→A,F3-{D→A}中D+=D；所以,F3中已没有多余的函数依赖。即F的等价最小依赖集为：{A→C,C→A,B→A,D→A}。

注意：函数依赖集的最小集并不是唯一的,本例中还可以有以下几个答案：

{A→C,C→A,B→A,D→A}或

{A→C,C→A,B→C,D→A}

或{A→C,C→A,B→C,D→C}

7.6.4关系模式的分解关系模式经分解后,应与原来的关系模式等价。所谓“等价”是指两者对数据的使用者来说应是等价的。即对分解前后的关系,做相同内容的查询,应产生同样的结果。这是对模式分解的基本要求。历年来,人们对等价的概念形成了三种不同的定义：

·

分解具有“无损连接性”（Losslessjoin）；

·

分解具有“函数依赖保持性”（Preservedependency）；

·

分解既要具有“无损连接性”,又要具有“函数依赖保持性”。

一、无损连接性

所谓无损连接性是指,对关系模式分解时,原关系模式下的任一合法关系实例,在分解之后,应能通过自然连接运算恢复起来。无损连接性有时也称为无损分解。定义15设ρ={R1,R2,…,Rk}是关系模式R（U,F）的一个分解,如果对于R的任一满足F的关系r,都有

则称分解ρ满足函数依赖集F的无损连接。

根据算法7.3可以测试一个分解具有无损连接性（是否为无损分解）。算法7.3检验分解的无损连接性。

输入：关系模式R（A1,A2,…,An）；

R上的函数依赖集F；

R上的分解ρ={R1,R2,…,Rk}。输出：ρ是否具有无损连接性。步骤：

(1)构造一k行n列的表（或矩阵）,第i行对应于分解后的关系模式Ri,第j列对应于属性Aj,如表7-11所示。表7-11构造判断矩阵

(2)对F中的每一个函数依赖进行反复的检查和处理。具体处理为：取F中一个函数依赖X→Y,在X的分量中寻找相同的行,然后将这些行中的Y分量改为相同的符号。即如果其中之一为aj,则将bij改为aj；若其中无aj,则改为bij,如：两个符号分别为b23和b13,则将它们统一改为b23或b13。

表中各分量的值由下面的规则确定：

(3)如此反复进行,直至M无可改变为止。如果发现某一行变成了a1,a2,…,an,则ρ具有无损连接性；否则,ρ不具有无损连接性。例7.6设关系模式R（U,F）中,U={A,B,C,D,E},

F={AB→C,C→D,D→E},R的一个分解ρ={R1（A,B,C）,R2（C,D）,R3（D,E）}。试判断ρ具有无损连接性。

表7-12分解的无损连接判断表

解：(1)首先构造初始表,如表7-12(a)所示。

(2)按下列次序反复检查函数依赖和修改M：

AB→C,属性A、B（第1、2列）中都没有相同的分量值,故M值不变；

C→D,属性C中有相同值,故应改变D属性中的M值,b14改为a4；

D→E,属性D中有相同值,b15、b25均改为a5。结果如表7-12（b）所示。表7-12分解的无损连接判断表

(3)此时第一行已为a1,a2,a3,a4,a5,所以ρ具有无损连接性。说明：在上例步骤后,如果没有出现a1,a2,a3,a4,a5,并不能马上判断ρ不具有无损连接性。而应该进行第二次的函数依赖检查和修改M。直至M值不能改变,才能判断ρ是否具有无损连接性。

【例】已知关系模式R(U)，U={A,B,C,D,E}，R上的函数依赖集F={A→C,B→C,C→D,DE→C,CE→A}，分解ρ={R1({A,D}),R2({A,B}),R3({B,E}),R4({C,D,E}),R5({A,E}),判定ρ是否具有无损连接性。解：(1)首先构造初始表（见表13）。表13ρ={R1({A,D}),R2({A,B}),R3({B,E}),R4({C,D,E}),R5({A,E})(A,D)(A,B)(B,E)(C,D,E)(A,E)

(2)检查A→C，因为R1［A]=R2［A]=R5［A],

修改b13,b23,b53，使其均用b13代替。修改结果如表14。

F={A→C,B→C,C→D,DE→C,CE→A}表14(A,D)(A,B)(B,