《数据库原理与应用》课件第5章

第5章关系数据库理论5.1关系模式的一般表示及设计中的问题5.2函数依赖5.3函数依赖的公理系统5.4关系模式规范形式5.5关系模式的规范化小结关系数据库是以关系模型为基础的数据库，它利用关系描述现实世界。关系模式是用来定义关系的，一个关系数据库包含一组关系，定义这组关系的关系模式的全体就构成了该关系数据库的模式。关系数据库模式设计归根到底是如何构造关系，即如何把具体的客观事物划分为几个关系，而每个关系又由哪些属性组成。在我们构造关系时，经常会发现数据冗余和更新异常等现象，这是由关系中各属性之间的相互依赖性和独立性造成的。前面我们已经讨论了关系模式的一般概念，但是，当使用关系模式设计数据库时，还面临一个关系模式的选择问题，如何挑选一个“好”的模式，这就需要对关系模式的一些性质做更深入的研究。

关系数据库设计理论主要包括：数据依赖、范式和关系模式的规范化处理等三方面的内容。

本章主要介绍了函数依赖、函数依赖的公理系统、关系模式的各种范式及关系模式的规范化。学习内容：

(1)函数依赖的定义。

(2)

Armstrong公理系统。

(3)关系模式的规范化形式。

(4)关系模式的规范化处理。

随着时间的不断变化，在不同的时刻，关系模式的关系也会有变化，但是现实世界的许多已知的事实，却限定了关系模式的所有可能的关系必须满足一定的约束。这些约束或者通过对属性取值范围的限定，如小学生的年龄要求大于等于6岁并且小于18岁；或者通过数据间的互相关联反映出来。5.1关系模式的一般表示及设计中的问题后者称为数据依赖。数据依赖是数据库理论中最主要的组成部分，是数据库模式的理论基础。数据依赖是现实世界属性间相互联系的抽象，它表示数据间存在的一种限制或制约关系。人们已经提出了许多种类型的数据依赖，如函数依赖、多值依赖、连接依赖等，其中最重要的是函数依赖，所以函数依赖是数据库模式设计中的关键所在。

首先介绍什么是数据库模式？设任一关系模式用Ri表示，X=R1∪R2∪…∪Rn，则Ω={R1，R2，…，Rn}就是X上的一个数据库模式。并不是任意一个数据库模式都是好的模式。我们研究函数依赖，其目的之一就是要从理论上找到判断好的数据库模式的标准。

函数依赖普遍地存在于现实生活中。例如，描述一个在校大学生所在学院及学习情况会涉及一些属性：学号sno、姓名sname、所属学院名dname、院长姓名dmn、课程编号cno、课程名称cname和成绩grade，其属性集合表示为U={sno，sname，dname，dmn，cno，cname，grade}。由现实世界的已知事实可以得出上述属性间包含有以下联系：

·学生的姓名可能有重名现象，但每名学生的学号是唯一的；

·一名学生只隶属于一个学院，但一个学院可以接收若干名学生；

·一个学院只有一名院长；

·每门课程的课程号是唯一的；

·一名学生可以选修多门课程，每门课程也可以有若干名学生选修；

·每名学生所学的每门课程都有一个成绩。图5.1在校大学生属性之间的函数依赖关系图根据上述情况，我们至少可以给出以下两种关系数据库模式：

(1)

Ω1={R1}

其中：

关系模式R1={sno,sname,dname,dmn,cno,cname,grade}。

(2)

Ω2={R1,R2,R3,R4}

其中：

关系模式R1={sno,sname,dname}

关系模式R2={dname,dmn}

关系模式R3={cno,cname}

关系模式R4={sno,cno,grade}

虽然它们都是符合定义的数据库模式，但使用起来的实际效果却大不相同。

下面我们先来看Ω1。假设r是R1上的一个关系，如表5.1所示。表5.1关系r针对这个关系r，存在以下一些弊病：

(1)数据冗余大。如果某个学生选修多门课程，则他的姓名、所在学院信息均要被重复保存。例如，学号为“20080101”的学生的姓名、所在学院信息在关系r中被4个元组重复记载，这显然是一种冗余。

(2)插入异常。如果有一门新增课程，课程号为c08，课程名为“健美操”，但因为目前还未有学生选修，构不成一个元组，所以无法插入到关系r中去，也即存在有计划开设的课程因为暂时没有学生上，就无法将这些课程号和课程名等信息保存到数据库中的现象，这就产生了插入异常。

(3)删除异常。如果学号为“20080101”的学生考“c05”课程时违纪，则成绩作废，我们应在关系r中删去对应的这个元组。但这个元组其实还包含课程号为“c05”，课程名为“离散数学”等信息，因删除只能删除整个元组，所以因学号为“20080101”的学生的“c05”课成绩作废，而把课程号为“c05”对应课程名为“离散数学”的信息也给“冤枉”地删除掉了。事实上，不管目前有无学生学习“离散数学”这门课程，这门课程的相关信息均应能保留在数据库中，上述这种关系模式则不能保证做到这一点，它可能产生删除异常。在数据库模式Ω1中，针对关系模式R1的某一关系r为什么会存在上述弊端呢？怎样才能在同一个属性集U上给出没有这些弊端的数据库模式呢？为了解决这些问题，我们先讨论几个重要的概念。

在现实世界中，最广泛存在的一种数据依赖是函数依赖。

例如，关系模式R1={sno,sname,dname,dmn,cno,cname,grade}中存在的函数依赖有：cname函数依赖于cno；dmn函数依赖于dname；sname函数依赖于sno；grade函数依赖于(sno，cno)等。下面给出相关概念的定义。5.2函数依赖5.2.1函数依赖的概念

1．函数依赖(FunctionalDependency，简称FD)

定义5.1

设R(U)是属性集U上的一个关系模式，X、Y

U。若对R(U)中任意一个可能关系r，r中不可能有两个元组在X的属性分量值相等，而在Y的那些属性分量值不相等，则称“X函数决定Y”，或“Y函数依赖于X”，记作X→Y。X称为决定因子，或称为函数依赖的左部，Y称为函数依赖的右部。

另一种定义为：设R(U)是属性集U上的一个关系模式，X、Y

U。对R(U)中任意一个可能关系r中的任意两个元组t和s，若有t[X]=s[X]，则有t[Y]=s[Y]，就称“X函数决定Y”，或“Y函数依赖于X”。

对函数依赖，我们需要强调几点：

(1)当我们确定关系模式R中的某个函数依赖时，是指R的所有可能关系r都必须满足这个函数依赖；反之，如果R中只要有一个关系r不满足这个函数依赖，我们就认为R不存在这个函数依赖。

(2)在确定一个关系模式中的函数依赖时，我们只能从属性含义上去加以说明，而不能在数学上加以证明。

(3)只有数据库设计者才能决定是否存在某种函数依赖。这就使得数据库系统可以根据设计者的意图来维护数据库的完整性。例如，关系模式R1={sno,sname,dname,dmn,cno,cname,grade}中的函数依赖可表示为

sno→sname

sno→dname

dname→dmn

cno→cname

(sno,cno)→grade

等等。

2．函数依赖模式

定义5.2

设关系模式R(U)，F是关于R的函数依赖集合(即若X→Y∈F，则X、Y

U)，则称(R,F)为一个函数依赖模式。5.2.2几种特定的函数依赖

1．非平凡函数依赖和平凡函数依赖

定义5.3

设有关系模式R(U)，X、Y

U，如果X→Y，且Y不是X的子集，则称X→Y为非平凡的函数依赖；如果X→Y，且Y

X，则称X→Y为平凡的函数依赖。

说明：对于任何一个关系模式，平凡函数依赖总是必然成立的。所以如果不是特别声明，我们总是讨论非平凡函数依赖。

2．完全函数依赖和部分函数依赖

定义5.4

设有关系模式R(U)，X、Y

U，如果X→Y，并且对于X的任何一个真子集Z，Z→Y都不成立，则称Y完全函数依赖于X；若X→Y，但对于X的某一个真子集Z，有Z→Y成立，则称Y部分函数依赖于X。

上述完全函数依赖和部分函数依赖定义可以用图5.2表示。

例如，关系模式R1={sno,sname,dname,dmn,cno,cname,grade}中存在sno→sname，说明sname完全函数依赖于sno；又因为其存在sno→sname,(sno,cno)→sname，所以sname部分函数依赖于(sno,cno)。图5.2完全函数依赖和部分函数依赖定义的图形表示

(a)完全函数依赖；(b)部分函数依赖

3．传递函数依赖

定义5.5

设有关系模式R(U)，X

U，Y

U，Z

U，如果X→Y，Y→Z成立，但Y→X不成立，且Z

-

X、Z

-

Y和Y

-

X均不空，则称X→Z为传递函数依赖。

上述传递函数依赖定义可以用图5.3表示。

例如，关系模式R1={sno,sname,dname,dmn,cno,cname,grade}中存在sno→dname，dname→dmn，但不存在dname→sno，则dmn传递函数依赖于sno。图5.3传递函数依赖定义的图形表示又例如，关系模式R={A,B,C,D}，其上的函数依赖集F={A→B,B→C,A→C,AB→D},则A→C为传递函数依赖。

注：在函数依赖中还有两种特殊的函数依赖：X→ф、ф→Y，它们对于任意关系都是成立的，在后面的介绍中我们不考虑这样的函数依赖。5.2.3逻辑蕴涵

我们在讨论函数依赖时，有时需要从一些已知的函数依赖去判断另一些函数依赖是否成立。这个问题称为逻辑蕴涵问题。

1．F逻辑蕴涵X→Y

定义5.6

设有关系模式R(U)，X、Y

U，F是关于R的函数依赖集合。又设X→Y为R中的一个函数依赖，

若对R的每一个关系r，满足F中每一个依赖，则r也必须满足X→Y，我们就说F逻辑蕴涵X→Y，或称X→Y是从F推导出来的或称X→Y逻辑蕴涵于F。例如，设R(U)是一个关系模式，A∈U，B∈U，C∈U，又假定在R中有函数依赖集F={A→B，B→C}，则称R中有函数依赖A→C，即F逻辑蕴涵A→C。

又例如，关系模式R1={sno,sname,dname,dmn,cno,cname,grade}，R1上的函数依赖集合F1={sno→sname，sno→dname，dname→dmn，cno→cname，(sno,cno)→grade}，则称R1中有函数依赖sno→dmn，即F1逻辑蕴涵sno→dmn。

2．函数依赖集合F的闭包

定义5.7

所有被F逻辑蕴涵的那些函数依赖组成的集合称为F的闭包，记为F+。

例如，设有关系模式R(U)，U={A,B,C},F={AB→C,C→B}是R(U)上的一组函数依赖，则有

F+={A→A,AB→A,AC→A,ABC→A,B→B,AB→B,BC→B,ABC→B,C→C,AC→C,BC→C,ABC→C,AB→AB,ABC→AB,AC→AC,ABC→AC,BC→BC,ABC→BC,ABC→ABC,AB→C,AB→AC,AB→BC,AB→ABC,C→B,C→BC,AC→B}

在关系模式的规范化处理过程中，只知道一个给定的函数依赖集合是不够的，我们需要知道由给定的函数依赖集合所蕴涵的所有函数依赖的集合。如果从一个函数依赖集合出发，用一个公理系统推出的每个依赖都被该依赖集合所蕴涵，则称这个公理系统是“有效的”；若该依赖集合所蕴涵的全部依赖都可以从该集合出发用这个公理系统推出，则称这个系统是“完备的”。Armstrong公理系统就是这样一个系统。该公理系统是W.W.Armstrong于1974年提出的。5.3函数依赖的公理系统5.3.1Armstrong公理系统

1．Armstrong公理系统的三条推理规则

设有关系模式R(U)，X、Y、Z、W

U，F是R的一个函数依赖集合，则Armstrong公理系统包含如下三条推理规则：

(1)自反律(reflexivity)，若Y

X

U，则F蕴涵X→Y。

(2)增广律(又称外延性，augmentation)，若F蕴涵X→Y，Z

U，则F蕴涵XZ→YZ。

(3)传递律(transitivity)，

若F蕴涵X→Y和Y→Z，

但不存在F蕴涵Y→X，则F蕴涵X→Z。

Armstrong公理系统提供一整套推理规则，它能从F推导出F+中的所有依赖(所谓完备性)，从F推不出任何不属于F+的依赖(所谓正确性)。

例如，有关系模式R(CITY,ST,ZIP)，其中CITY表示城市，ST表示城市的街道，ZIP表示街道所在地区的邮政编码，函数依赖集合F={(CITY,ST)→ZIP,ZIP→CITY}，证明

{ST,ZIP}和{CITY,ST}是候选键。

证明：因为ZIP→CITY(由给定条件得出)，所以

(ST,ZIP)→(CITY,ST)(由增广律得出)

又因为(CITY,ST)→ZIP(由给定条件得出)，所以

(CITY,ST)→(CITY,ST,ZIP)(由增广律得出)

(ST,ZIP)→(CITY,ST,ZIP)(由传递律得出)

并且，ST→(CITY,ST,ZIP)和ZIP→(CITY,ST,ZIP)均不成立，所以(ST,ZIP)是候选键。

同理可证(CITY,ST)也是候选键。证毕。

2．Armstrong公理的三个推论

由Armstrong公理可得到下面三个推论：

(1)合并规则，若X→Y，X→Z，则X→YZ。

(2)分解规则，若X→Y且Z

Y，则X→Z。

(3)伪传递规则，若X→Y，YZ→W，则XZ→W。

3．Armstrong公理系统的正确性和完备性

在证明Armstrong公理系统的正确性和完备性之前，有必要引入一个定义和两个引理。

(1)属性集合X关于函数依赖集F的闭包，记为XF+。

定义5.8

设有关系模式R(U)，U={A1,A2,…,An}，Ai∈U，X

U，

X+={Ai|X→Ai能由F根据Armstrong公理系统导出，且Ai∈U}，则称

X+是属性集合X关于函数依赖集F的闭包。

例如，设有关系模式R(U)，U={A,B,C,D,E}，F={A→BC,CD→E,B→D,E→A}，则BF+={B,D}，AF+={A,B,C,D,E}。

算法5.1

计算属性集X的闭包X+。

输入：属性集X和函数依赖集F。

输出：关于F的X的闭包X+。

方法：

①令X(0)=X，i=0。

②令X(i+1)=X(i)∪{A|V

X(i)，V→W∈F,A∈W}。

③若已经没有V→W∈F，能使X(i+1)≠X(i)，则X+=X(i)，输出X+，算法结束；否则，令i=i+1，转去执行第②步。

例5.1

设关系模式R(U)上的函数依赖集为F,U={A,B,C,D,E,I}，F={A→D，AB→E，BI→E，CD→I，E→C}，试计算(AE)+。

解：令X(0)=AE，i=0。

在F中找出左边是AE子集的函数依赖，因A→D，所以X(1)=AED；因E→C，所以X(2)=AEDC；

因CD→I，所以X(3)=AEDCI；因已没有V→W∈F，能使X(3+1)≠X(3)，所以X+=X(3)，即(AE)+={A，C，D，E，I}。

(2)引理5.1

设有关系模式R(U)，U={A1,A2,…,An}，Ai∈U，X

U，X→A1A2…An成立的充分必要条件是X→Ai(i=1,2,…,n)都成立。根据合并规则和分解规则，很容易得到这个引理的证明。留给读者自己证明。

(3)引理5.2

设F是关系模式R(U)上的函数依赖集，X、Y

U，X→Y能由F根据

Armstrong公理系统导出的充分必要条件是Y

XF+。

证明：设Y=A1A2…An

(A1,A2,…,An为属性)。

假设Y

XF+，根据XF+的定义，对所有i=1,…，n,X→Ai可用Armstrong公理系统从F推出。根据合并规则，X→Y也能被从F推出。反之，假设X→Y能用Armstrong公理系统推出。根据分解规则，对于所有i=1,2,…，n,X→Ai成立。根据X+的定义有Ai

XF+，故有A1A2…An

XF+，即Y

XF+。证毕。

(4)定理5.1Armstrong公理系统是正确的和完备的。

证明：[正确性]

设r是关系模式R(U)上的任一关系，t1，t2是r的任意元组，X、Y、Z

U。

①若t1[X]=t2[X]，则X的任意子集在t1，

t2上的属性值也相等，因Y

X，即有t1[Y]=t2[Y]，根据函数依赖的定义，则X→Y成立。

②设t1[XZ]=t2[XZ]，则有t1[X]t1[Z]=t2[X]t2[Z]，则t1[X]=t2[X]，t1[Z]=t2[Z]，由X→Y可知，t1[Y]=t2[Y]。因此有t1[YZ]=t1[Y]t1[Z]=t2[Y]t2[Z]=t2[YZ]，

根据函数依赖的定义，XZ→YZ成立。

③设X→Y，Y→Z，则若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成立。

[完备性]

(设关系模式R(U)上的函数依赖集为F，我们采用证明完备性的逆否命题来证明完备性，即如果函数依赖X→Y不能由F根据Armstrong公理导出，它必然不为F蕴涵。)设关系模式R(U)上的函数依赖集为F。函数依赖X→Y不包含在F+中，给出R上的一个关系r，该关系满足要求F+但不满足X→Y。据此，须证明两点：r不满足X→Y；r满足F中的所有的函数依赖。

设关系模式R(U)中，U={A1,A2,…,An}，

Ai∈U，且ai、bi是Ai域中的两个不同元素，1≤i≤n。假设关系r中仅有两个元组t1和t2。元组t1=(a1,a2,…,an)；元组t2被定义为

先证明r不满足X→Y。

若t1[X]=t2[X]，假定t1[Y]=t2[Y]，那么t2[Y]必全部为ai，并且Y

X+。但由于X→X+∈F+，通过投影可得X→Y在F+中，这一结果与X→Y不包含在F+中的假设矛盾，因此，t1[Y]=t2[Y]不成立，即r不满足X→Y。

再证明r满足F中的所有的函数依赖。

设W→Z是F中任一函数依赖。W在r中有两种情况：W是X+的子集和W不是X+的子集。

若是，则根据属性闭包的定义，有X→W，又因W→Z，由函数依赖的传递性，则有X→Z，所以根据引理5.2知，Z

X+，即W

X+

和Z

X+同时成立。由r的构造可知，W→Z在r上是成立的。若不是，则在r中，t1[W]≠t2[W]，从而W→Z在r上总是成立的。证毕。

Armstrong公理系统的正确性和完备性说明了“通过F推导出的函数依赖”与“F所蕴涵的函数依赖”两种说法是完全等价的。所以，F+也可以说成是由F出发经Armstrong公理系统导出的函数依赖集合。

(5)定理5.2

合并规则、分解规则、伪传递规则是正确的。

证明：①若X→Y，根据增广律得XX→XY，即X→XY；若X→Z，根据增广律得XY→YZ，根据传递律得X→YZ。

②若Z

Y，根据自反律得Y→Z，又已知X→Y，根据传递律得X→Z。

③若X→Y，根据增广律得XZ→YZ，又已知YZ→W，根据传递律得XZ→W。证毕。5.3.2函数依赖集合F的极小函数依赖集

在实际应用中，经常需要将一个已知的函数依赖集变换为其他的或更简洁的表示形式。例如，需要把一个大的关系模式分解为几个小的关系模式，这样就需要将相应的函数依赖也投影到分解后的模式上。这就涉及一个函数依赖集的等价问题。下面，从蕴涵(或导出)的概念出发，再引出两个概念。这些概念在关系模式规范化处理中十分重要。

1．两个函数依赖集合F和G等价

定义5.9

设模式R上有两个函数依赖集F和G，如果有F+=G+，则称F和G等价，记作F≡G。若F≡G，则F是G的一个覆盖，同样，G是F的一个覆盖。

定理5.3

设G和F是两个函数依赖集，则F与G等价的充分必要条件是F

G+，且G

F+。

证明：(先证必要性)设G+=F+，由于F

F+，所以有F

G+。同理可得G

F+。

(再证充分性)

设F

G+且G

F+，对于每个X→Y∈F+，则有X→Y由F出发使用Armstrong公理导出。因F

G+，所以X→Y可以由G+使用Armstrong公理导出，所以X→Y∈(G+)+=G+，即X→Y∈G+，从而F+

G+。同理可证G+

F+。所以F+=G+，即F与G等价。

2．函数依赖集F的极小(或最小)函数依赖集(记为F’)

定义5.10

如果函数依赖集F满足下列三个条件：

(1)

F中任一函数依赖的右部仅含有一个属性。

(2)

F中不存在函数依赖X→A，使得F与F-{X→A}等价。

(3)

F中不存在函数依赖X→A，X包括真子集Z使得(F-{X→A})∪{Z→A}与F等价。称此函数依赖集为F的极小(或最小)函数依赖集，记作F’。

注：(1)条件(1)保证了每一个函数依赖的右部都不含有多余的属性；条件(2)保证了在F中不存在多余的函数依赖；条件(3)保证了F中每个函数依赖的左边没有多余的属性。

(2)

F的极小依赖集不一定是唯一的。

例如，设关系模式R(U)上的函数依赖集为F,U={A,B,C,D,E,G}，F={AB→C，BC→D，ACD→B，D→EG，C→A，BE→C，CG→BD，CE→AG}，F1={AB→C，BC→D，D→E，BE→C，CG→D，CE→G，C→A，D→G，CD→B}，则可以验证F1是F的最小函数依赖集。

定理5.4

每个函数依赖集F都与它的极小依赖集F’等价。

证明：采用构造性证明的方法。分三步进行：

(1)逐一对函数依赖集F中的各函数依赖X→Y进行检查，只要有Y=A1A2…Am，m≥2，则用{X→Ai|i=1,2,…,m}来取代X→Y。

(2)依次检查F中各函数依赖X→A，令G=F-{X→A}，若A∈X+G，则从F中删除X→A(根据F与G等价的充分必要条件是A∈X+G)。上述操作循环进行，直到F不再改变为止。

(3)循环检查F中各函数依赖X→A，若X=B1B2…Bn，则逐一考查Bi(i=1,2,…,n)，如果A∈(X-Bi)+F，则用(X-Bi)→A取代X→A(因为F与(F-{X→A})∪{(X-Bi)→A}等价的充分必要条件是A∈(X-Bi)+F)，直到F不再改变为止。

这时得到的就是一个与F等价的极小函数依赖集。

证毕。

算法5.2

计算函数依赖集F的极小依赖集F’。

输入：一个函数依赖集F。

输出：F的一个等价极小依赖集F’。

方法：(1)应用分解规则，使F的每一个函数依赖的右部属性单一化。

(2)去掉各函数依赖左部多余的属性。具体办法是：逐个循环检查F中左边是否是非单属性的依赖X→Y。设X=B1B2…Bn，若Y∈(X-Bi)F+，则以(X-Bi)→Y取代X→Y，直到F不再改变为止。

(3)去掉多余的函数依赖。具体办法是：循环检查F中各函数依赖X→Y，令G=F-{X→Y}，若Y∈XG+，则从F中去掉X→Y；否则，不能去掉X→Y。直到F不再改变为止。

例5.2

设关系模式R(U)上的函数依赖集为F,U={A,B,C,D,E,G}，F={AB→C，BC→D，ACD→B，D→EG，C→A，BE→C，CG→BD，CE→AG}，试求其等价的极小函数依赖集F’。

解：(1)应用分解规则，使F的每一个函数依赖的右部属性单一化。结果为

F1={AB→C,BC→D,ACD→B,D→E,D→G,C→A,BE→C,CG→B,CG→D,CE→A,CE→G}

(2)去掉各函数依赖左部多余的属性。因为CE→A,C→A，

则E是多余的；对于ACD→B,由于(CD)F1+={A,B,C,D,E,G}，则A是多余的。其他函数依赖中无左部多余的属性。删除函数依赖左部多余的函数依赖后的结果为

F2={AB→C,BC→D,CD→B,D→E,D→G,C→A,BE→C,CG→B,CG→D,CE→G}

(3)在F2中去掉多余的函数依赖。对于CG→B，令x=F2

-

{CG→B}由于(CG)+x={A,B,C,D,E,G}，即B∈(CG)+x，因此是多余的。其等价的极小函数依赖集F’的结果为：

F’={AB→C,BC→D,CD→B,D→E,D→G,C→A,BE→C,CG→D,CE→G}

关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。关系模式的规范形式(简称范式)是以函数依赖为基础的。关系模式的常见范式主要有四种，它们是第一范式、第二范式、第三范式和BC范式。除此以外，还有第四范式和第五范式。满足这些范式条件的关系模式可以在不同程度上避免本节开始提到的冗余问题、插入问题和删除问题。其中最有意义的是“第三范式”和“BC范式”，这两个范式基本保证了消除冗余问题和异常情况的发生。5.4关系模式规范形式根据规范化程度的不同，关系模式的范式从低到高有第一范式、第二范式、第三范式、BC范式等。把一个给定关系模式从低一级范式转化为某种较高一级范式的过程称为关系模式的规范化过程，简称为规范化。本节主要介绍关系模式的各种范式的基本概念。关于把一个给定关系模式转化为较好一级范式的规范化算法，将在下节详细介绍。

需要说明的一点是，目前存在很多种关系模式范式的定义，这些定义都是等价的。5.4.1第一范式(1NF)

定义5.11

设R是一个关系模式，如果R的每个属性的值域(更确切地说是R的每一个关系r的属性值域)都是不可分的简单数据项(即是原子)的集合，则称这个关系模式属于第一范式(FirstNormalForm)，简记作R∈1NF。

不满足1NF的关系称为非规范化的关系，满足1NF的关系称为规范化的关系。在任何一个关系数据库系统中，关系至少应该是第一范式。不满足第一范式的数据库模式不能称为关系数据库。在以后的讨论中，我们假定所有关系模式都是1NF的。但注意，第一范式不能排除数据冗余和异常情况的发生。表5.2学生选课关系例如，表5.2描述的学生选课关系不是1NF的，因为课程一列包含多门课，不是原子值，而表5.3所示学生选课1关系是1NF的。

又例如，关系模式R1={sno,sname,dname,dmn,cno,cname,grade}，它的某一关系见表5.1，R1显然属于1NF。表5.3学生选课1关系5.4.2第二范式(2NF)

1．2NF

定义5.12

若关系模式R是1NF的，而且每一个非主属性都完全函数依赖于R的候选键，则R称为第二范式，记作R∈2NF。

2．求出一个关系模式的所有候选键的方法

一个关系模式候选键的定义前面已经给出，但还存在如何求出一个关系模式的所有候选键的问题。下面给出一种方法，供读者参考。

定理5.5

假设有给定的关系模式R(U)及其函数依赖集F，XU，并将其属性分为四类：L类(仅出现在F的函数依赖左部的属性)、R类(仅出现在F的函数依赖右部的属性)、N类(在F的函数依赖左、右两边均未出现的属性)和LR类(在F的函数依赖左、右两边均出现的属性)，则：

(1)若X是L类属性，则X必为R的任一候选键的成员。

(2)若X是L类属性，且X+包含了R的全部属性，则X必为R的唯一候选键。

(3)若X是N类属性，则X必包含在R的任一候选键中。

(4)若X是R类属性，则X不在任一候选键中。

(5)若X是N类和L类组成的属性集，且X+包含了R的全部属性，则X是R的唯一候选键。

例如，描述一个在校大学生所在学院及学习情况涉及一些属性：学号sno、姓名sname、所属学院名dname、院长姓名dmn、课程编号cno、课程名称cname和成绩grade，以及关系模式R={sno,sname,dname,dmn,cno,cname,grade}，其属性之间的函数依赖情况可以用图5.4表示。图5.4中虚线表示部分函数依赖或传递依赖，实线表示完全函数依赖。图5.4关系模式R属性之间的函数依赖关系图

例5.3

针对关系模式R={sno,sname,dname,dmn,cno,cname,grade}，R上的函数依赖集合F={sno→sname，sno→dname，dname→dmn，cno→cname，(sno,cno)→grade，sno→dmn，(sno,cno)→sname，(sno,cno)→dname，(sno,cno)→dmn，(sno,cno)→cname}，考虑如何求出关系模式R1的候选键，并判断R是否属于第二范式。

解：根据F可以将关系模式R的属性分为如下四类：

·L类：sno，cno。

·R类：cname，sname，dmn，grade。

·N类：无。

·LR类：dname。

由定理5.5得出sno、cno一定是主属性。又由于

(sno,cno)+={sno,sname,dname,dmn,cno,cname,grade}

sno+={sno,sname,dname,dmn}

cno+={cno,cname}

即(sno,cno)包含了R的全部属性，所以，(sno,cno)是关系模式R唯一的候选键。

R的主属性有sno和cno；R的非主属性有sname、dname、dmn、cname和grade。

由F可以得出sno→dname，(sno,cno)→dname，即存在非主属性dname部分函数依赖于(sno,cno)，所以R属于第一范式，但不属于第二范式。

以表5.1给出的关系r为例(关系r存在的弊病我们前面已经给出)，如若将关系模式R分解成如下三个关系模式R1、R2和R3：

R1={sno,sname,dname,dmn}

R2={cno,cname}

R3={sno,cno,grade}则我们把它描述为关系数据库模式Ω3={R1,R2,R3}，用图5.5(a)、(b)、(c)分别表示关系模式R1、R2和R3中属性之间的函数依赖情况。图5.5中虚线表示传递依赖；实线表示完全函数依赖。

图5.5关系模式R1、R2和R3中属性之间的函数依赖关系图根据定理5.5可以得出，关系模式R1、R2和R3的候选键分别为sno、cno和(sno,cno)，显然，关系模式R1、R2和R3均属于第二范式。将关系模式R分解为关系模式R1、R2和R3后，关系模式R存在的问题在一定程度上得到了解决。如：

(1)

R1关系中可以插入尚未选修课程的学生信息，减少了由此引起的插入异常问题。

(2)删除学生选课关系只涉及R3关系，不涉及R1中的学生基本信息，减少了由此引起的删除异常问题。

(3)由于学生选课信息与学生基本信息分开存放，不论某学生选修了几门课，dname与dmn的值都只存储一次，减少了数据冗余。

3．2NF的关系模式可能引发的问题及解决办法

从上面例子可以看出，R1属于2NF。现在我们来分析一下R1存在的问题：

(1)插入异常。学院刚成立，无在校学生，无法存入学院信息。

(2)删除异常。假设某学院的全部学生都毕业了，则学院的信息也就丢失了。

(3)修改复杂。当某学院更换了院长时，需要修改所有学生的dmn属性值。

(4)存在数据冗余。每一个学院的学生有多个，都要存放学院院长信息，即院长信息要重复出现。

造成上述问题的主要原因是：非主属性dmn传递函数依赖于候选键sno。

解决办法：将传递函数依赖关系分解出来。5.4.3第三范式(3NF)

定义5.13

如果关系模式R是1NF，而且它的任何一个非主属性都不传递地依赖于任何候选键，则R称为第三范式，记作R∈3NF。

例5.4

证明如果R是3NF的关系模式，则R也是2NF的关系模式。

证明：(思路：关系模式中的非主属性对候选键的部分函数依赖的存在蕴涵着传递依赖的存在。)

设A是R的一个非主属性，K是R的一个候选关键字，且K→A是一个部分依赖，那么，R中必存在某个K’

K，有K’→A成立。由于A是非主属性，因此A∩KK’=ф。从K’

K可知K不函数依赖于K’，但K→K’成立。所以从K→K’和K’→A可知K→A是一个传递依赖。

因而，如果R是3NF的关系模式，则它的任何一个非主属性都不传递地依赖于任何候选键，也就不可能存在它的任何一个非主属性部分依赖于任何候选键，所以R也是2NF的关系模式。

证毕。

由此例可知，若R∈3NF，则R的每一个非主属性既不部分函数依赖于候选键，也不传递函数依赖于候选键。

根据第三范式的定义可得，若X→A(A不包含在X中)违反第三范式的条件，则下列两种情况之一会发生：X是某一个候选键的真子集，或者X是非关键字的真子集。

例5.4

分析前面讲述的关系数据库模式Ω3={R1,R2,R3}中各关系模式是否属于第三

范式。

分析：对于R1，函数依赖集F1={sno→sname，sno→dname，dname→dmn}；sno是R1唯一的候选键；其主属性有sno；其非主属性有sname、dname和dmn。显然不存在任何非主属性对候选键的部分依赖。又因为存在sno→dname，dname→dmn，得出非主属性dmn传递依赖于候选键sno，所以R1不属于第三范式，而属于第二范式。对于R2，函数依赖集F2={cno→cname}；cno是R2唯一的候选键；其主属性有cno；其非主属性有cname。因为只存在函数依赖cno→cname，显然不存在任何非主属性对候选键的部分依赖和传递依赖，所以R2属于第三范式。

对于R3，函数依赖集F3={(sno,cno)→grade}；(sno,cno)是R3唯一的候选键；其主属性有sno和cno；其非主属性有grade。因为只存在函数依赖(sno,cno)→grade，显然不存在任何非主属性对候选键的部分依赖和传递依赖，所以R3属于第三范式。可以将R1分解为关系模式R11和R12：

R11={sno,sname,dname}

R12={dname,dmn}

用图5.6的(a)、(b)分别表示关系模式R11和R12中属性之间的函数依赖情况。

图5.6关系模式R11和R12中属性之间的函数依赖关系图同理可以得出关系模式R11和R12均属于第三范式。

部分依赖和传递依赖是产生数据冗余和插入异常、删除异常的两个主要原因。在3NF中不存在非主属性对候选键的部分依赖和传递依赖，所以满足3NF的关系模式可以消除很大一部分数据的异常和冗余，但是，3NF并没有排除主属性对候选键的传递依赖，因此，仍有可能存在数据的异常现象。

例如，有一个关系模式R(U)，U={S,T,C}，设S表示学生，T表示教师，C表示课程，这些数据的语义描述为：

·一名教师只能教一门课程。

·若干教师可以教授同一门课程。

·一旦某一个学生选定了某门课程，就确定了一个固定的教师。

R中的函数依赖关系如图5.7所示。由此得出R上的函数依赖集合

F={(S,C)→T,(S,T)→C,T→C}

根据定理5.5可以得出：(S,C),(S,T)都是关系模式R的候选键；其主属性有S、C和T；无非主属性。显然，不存在任何非主属性对候选键的部分依赖和传递依赖，但存在主属性C对候选键(S,T)的部分依赖，所以R∈3NF。

图5.7关系模式R中属性之间的函数依赖关系图此关系模式R存在如下一些问题：

(1)数据冗余较大。虽然一个教师只教一门课程，但每个选修该教师教授的这门课程的学生对应的元组都要记录这个教师的信息，从而产生一定的冗余。

(2)插入异常。如果出现某个学生刚刚入校，还未选修课程或某个教师开设了某门课程，但暂时没有学生选修的情况，由于受主属性不能为空的限制，导致有关这个学生或教师的信息无法存入数据库中，造成插入异常。

(3)删除异常。如果选修了某门课程的学生全部毕业了，在删除与这些学生有关的元组的同时，可能将相应教师开设该门课程的信息也同时丢掉了，造成删除异常。5.4.4Boyce-Codd范式(BCNF)

定义5.14

设关系模式R是1NF。如果对于R的每个函数依赖X→Y，X必为候选键，则R是BCNF。

根据BCNF的定义可得，R中没有任何属性传递依赖于R的任一关键字。即属于BCNF的关系模式都具有如下三个性质：

(1)所有非主属性都完全函数依赖于每个候选键；

(2)所有主属性都完全函数依赖于每个不包含它的候选键；

(3)没有任何属性完全函数依赖于非候选键的任何一组属性。

例5.5

分析前面讲述的关系数据库模式Ω2={R1,R2,R3,R4}中各关系模式是否属于BC范式。

分析：关系数据库模式Ω2中的各关系模式如下：

R1={sno,sname,dname}

R2={dname,dmn}

R3={cno,cname}

R4={sno,cno,grade}对于R1:

·函数依赖集F1={sno→sname，sno→dname}。

·sno是R1唯一的候选键。

·其主属性有：sno。

·其非主属性有：sname，dname。

因为只存在函数依赖sno→sname，sno→dname，显然不存在任何非主属性对候选键的部分依赖和传递依赖，也不存在任何主属性对候选键的部分依赖和传递依赖，所以R1属于BC范式。对于R2:

·函数依赖集F2={dname→dmn}。

·dname是R1唯一的候选键。

·其主属性有：dname。

·其非主属性有：dmn。

因为只存在函数依赖dname→dmn，显然不存在任何非主属性对候选键的部分依赖和传递依赖，也不存在任何主属性对候选键的部分依赖和传递依赖，所以R2属于BC范式。

对于R3:

·函数依赖集F3={cno→cname}。

·

cno是R3唯一的候选键。

·其主属性有：cno。

·其非主属性有：cname。

因为只存在函数依赖cno→cname，显然不存在任何非主属性对候选键的部分依赖和传递依赖，也不存在任何主属性对候选键的部分依赖和传递依赖，所以R3属于BC范式。对于R4:

·函数依赖集F4={(sno,cno)→grade}。

·(sno,cno)是R4唯一的候选键。

·其主属性有：sno,cno。

·其非主属性有：grade。

因为只存在函数依赖(sno,cno)→grade，显然不存在任何非主属性对候选键的部分依赖和传递依赖，也不存在任何主属性对候选键的部分依赖和传递依赖，所以R4属于BCNF。

根据以上给出的定义，我们可以看出各种范式之间的联系有BCNF

3NF

2NF

1NF。它们之间的转换方法为：对于1NF，通过消除其中任何非主属性对候选键的部分依赖，可以变成2NF；对于1NF，通过消除其中任何非主属性对候选键的部分依赖和传递依赖，可以变成3NF；对于3NF，通过消除其中任何主属性对候选键的部分依赖和传递依赖，可以变成BCNF。前面已经介绍过，不好的数据库模式中可能存在冗余异常、插入异常、删除异常、修改异常等。产生这些异常的主要原因是因为它们不属于3NF或BCNF。一般说来，如果一个关系数据库中的所有关系模式都属于BCNF，那么在函数依赖范畴内，它已实现了模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删除异常。

那么，对于不好的数据库模式，怎样才能消除这些异常呢？其方法就是对存在异常的那些关系模式进行分解。通过对关系模式的分解，可以达到使关系模式变成第三范式或更高级范式的要求。5.4.5多值依赖和第四范式(4NF)

当我们完全在函数依赖的范畴内讨论关系模式的范式问题时，仅仅考虑的是函数依赖这一种数据依赖，关系数据库中的关系模式能达到BCNF我们就认为很完美了。但如果考虑其他数据依赖(如多值依赖)，就可能发现，属于BCNF的关系模式仍可能存在问题。

1．多值依赖

定义5.15

设有关系模式R(U)，X、Y、Z

U，并且Z=U-X-Y。当且仅当R的任一关系r，r在(X,Z)上的每一个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关时，称多值依赖X→→Y成立。注：(1)若X→→Y，而Z=Ф，则称X→→Y为平凡的多值依赖；否则称X→→Y为非平凡的多值依赖。

(2)函数依赖X→Y的有效性仅决定于X和Y这两个属性集的值，与其他属性无关。如果X→Y在属性集W上成立，则X→Y在属性集U(W

U)上必成立。而多值依赖的定义中不仅涉及属性组X和Y，而且涉及U中其余属性Z，所以如果X→→Y在U上成立，则在W(X、Y

W

U)上一定成立；但如果X→→Y在W(W

U)上成立，在U上并不一定成立。例如，设某中学中某一门课程由多个教师讲授，他们都使用一套相同的参考书。我们用关系模式R(U)表示。U={C,T,B}，其中C表示课程，T表示教师姓名，B表示参考书名。表5.4表示了关系模式R的一个关系实例。表5.4关系模式R的一个关系实例关系模式R具有唯一的候选键(C,T,B)，显然R∈BCNF。但关系模式R存在一些问题：

(1)当某一门课程(如数学)增加一名新教师时，需要插入多个(针对数学是四个)元组，增加了插入操作的复杂性；

(2)当某门课(如英语)根据需要，要去掉一本参考书时，也要去掉多个(针对英语是两个)元组，带来删除操作的复杂性；

(3)数据冗余也是很明显的。

存在这些问题的原因是什么呢？经过分析我们发现，在这个关系模式R中，每个(C,B)上的值对应一组T值，而且这种对应与B无关。如与(C,B)对应的两个元组(数学，初等几何)和(数学，初等代数)在B属性上的值不同，但它们对应同一组T值{王辉，张强}，由此得出T多值依赖于C，即C→→T。就是关系模式R中存在的这种多值依赖的数据依赖，造成了上述问题的存在。

多值依赖具有以下性质(设U是一个关系模式R的属性集合，X、Y、Z、V、W都是U的子集合)：

(1)替代性，若X→Y，则X→→Y。

(2)对称性，若X→→Y，则X→→U-X-Y。

(3)多值增广性，若X→→Y，V

W，则WX→→VY。

(4)多值传递性，若X→→Y，Y→→Z，则X→→Z-Y。

(5)聚集性，若X→→Y，Z

Y，W∩Y=ф，W→Z，则X→Z。

(6)多值合并性，若X→→Y，X→→Z，则X→→YZ。

(7)多值伪传递性，若X→→Y，WY→→Z，则WX→→(Z-WY)。

(8)多值分解性，若X→→Y，X→→Z，则X→→Y∩Z，X→→Y-Z，X→→Z-Y。

(9)混合伪传递性，若X→→Y，XY→Z，则X→(Z-Y)。

2．第四范式

定义5.16

如果关系模式R是1NF，且对于R的每个非平凡多值依赖X→→Y(Y不是X的子集，XY未包含R的全部属性)，X都含有R的候选键，则R是第四范式，记为R∈4NF。

如果一个关系模式是4NF，则它一定是BCNF；反之不然。

函数依赖是多值依赖的一种特殊情况，这两种依赖是最重要的数据依赖。事实上，数据依赖中除函数依赖和多值依赖之外，还有一种连接依赖。多值依赖又是连接依赖的一种特殊情况。关于连接依赖的概念在此不再介绍，有兴趣的读者可以参阅有关书籍。

根据需求分析中得到的用户要求，我们可以把关系分为两类：

(1)静态关系，其特点是一旦数据已加载，用户就只能在这个关系上运行查询操作。这种关系的要求是必须属于1NF。

(2)动态关系，其特点是当数据加载后，可经常对数据进行增、删、改操作。这种关系的要求是至少属于3NF。5.5关系模式的规范化一个低级范式的关系模式，通过分解(投影)可转换成多个高一级范式的关系模式的集合，这种过程称为规范化，如图5.8所示。

图5.8规范化过程关系模式的规范化过程是通过对关系模式的分解来实现的。可以把低一级的关系模式分解为若干个高一级的关系模式。这种分解不是唯一的。

一旦关系模式不满足要求，就要对此关系模式进行分解，这是关系模式规范化的主要方法。但问题是，分解后的多个模式是否与原来的模式完全一样呢？即所表示的信息是否与原来的信息一致呢？所表达的函数依赖集是否与原来的函数依赖集等价呢？这就涉及分解的概念和原则。5.5.1关系模式分解的概念

1．关系模式分解

设有关系模式R(U)，U={A1,A2,…,An},F是R(U)上的函数依赖的集合。ρ={R1,R2,…,Rn}，是R的一个分解，使得R1∪R2∪…∪Rn=R,U=U1∪U2∪…∪Un，F在Ri的属性集合Ui上的投影是Fi={X→Y|X→Y∈F+,X,Y∈Ui}

2．关系模式分解的主要目的

关系模式分解的主要目的就是为了解决关系模式中可能存在的插入、删除和修改时的异常情况。

注：一般此工作由数据库设计者来进行。

3．关系模式分解的原则

关系模式分解的原则是分解后产生的模式应与原模式等价。

仅当分解满足下述三种情况之一时，才能保证分解后产生的模式与原模式等价：

(1)分解具有“无损连接性”。

(2)分解具有“保持函数依赖性”。

(3)分解既要“保持函数依赖性”，又要具有“无损连接性”。5.5.2具有无损连接性的关系模式分解

1．分解ρ具有无损连接性

设有关系模式R(U)，F是R上的函数依赖集合，ρ={R1,R2,…,Rn}是R的一个分解，如果对R的任一满足F的关系r，下式成立：

则称分解ρ为具有无损连接性或分解ρ为无损连接分解。一般把关系r在分解ρ上的投影连接记为mρ(r)，即

满足无损连接的条件可表示为：

r=mρ(r)

无损连接分解的特性说明关系模式分解后所表示的信息应与原模式等价，即分解后的多个关系再连接得到的新关系不能“丢失”信息。实际上，连接后的关系不会丢失任何元组，而是可能多出一些元组，因与原来的关系不等价，所以是有损的。下面的引理表明了r和mρ(r)间的关系。

引理5.3

设有关系模式R(U)及R上的关系r,ρ={R1,R2,…,Rn}是R的一个分解，则有：

(1) r

mρ(r)

(2) 

(mρ(r))=

(r)

(3) mρ(mρ(r))=mρ(r)

证明：(1)任取t∈r，则

根据自然连接的定义，有所以，t∈mρ(r)，即r

mρ(r)。

证毕。

根据定义直接去鉴别一个分解的无损连接性是不可能的，要通过算法来判定。

2．判定一个分解的无损连接性算法

算法5.3

判定一个分解的无损连接性的算法。

输入：关系模式R(A1,A2,…,An)，R上的分解ρ={R1,R2,…,Rk}，R上的函数依赖集为F。

输出：分解ρ是否具有无损连接性。

方法：

(1)构造一个k行n列的初始表，第i行对应于关系模式Ri，第j列对应于属性Aj。如果Aj∈Ri，则在第i行第j列上填符号ai；否则填符号bij。

(2)逐个检查F中的每一个函数依赖，并修改表中的元素。具体办法为：从函数依赖集F中取一个函数依赖X→Y，在X的分量中寻找相同的行，然后将这些行中Y的分量改为相同的符号，如果其中有aj，则将bij改为aj；否则，改为bij(指用其中的一个bij替换另一个，通常是把下标改为较小的那个数)。

(3)反复进行，如果发现某一行变成了a1,a2,…,an，即存在某一行全为“a”类符号，则分解ρ具有无损连接性；如果F中所有函数依赖都不能再修改表中的内容，且没有发现这样的行，则分解ρ不具有无损连接性。

例5.6

已知关系模式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)首先构造初始表(见表5.5)。表5.5构造的初始表

(2)检查A→C，因为R1[A]=R2[A]=R5[A]，修改b13,b23,b53，使其均用b13代替。修改结果如表5.6所示。表5.6修改的结果(一)

(3)检查B→C，因为R2[B]=R3[B]，修改b13,b33，使其均用b13代替。修改结果如表5.7所示。表5.7修改的结果(二)

(4)检查C→D，因为R1[C]=R2[C]=R3[C]=R5[C]，修改b24,b34,b54，使其均用a4代替。修改结果如表5.8所示。

表5.8修改的结果(三)

(5)检查DE→C，因为R3[DE]=R4[DE]=R5[DE]，修改R3[C]，R5[C]，使其均用a3代替。修改结果如表5.9所示。

表5.9修改的结果(四)

(6)检查CE→A，因为R3[CE]=R4[CE]=R5[CE]，修改R3[A]，R4[A]，使其均用a1代替。修改结果如表5.10所示。

表5.10修改的结果(五)由于此时表中第三行已经成为a1,a2,a3,a4,a5,所以ρ具有无损连接性。

定理5.5

算法5.3能正确判断分解ρ是否是无损连接分解的。

证明：假设算法5.3的输出结果是false，即构造表(设为T)不可能出现全a行。可将算法5.3最后得到的表T看做R上的一个关系r，关系r是满足函数依赖集F的。由表T的构造知，表T中Ri对应行的Ri所含列Aj上应为aj，因此，r在分解ρ中的每一个Ri上投影连接后应有全a的行，但r中没有。这也就是说，mρ(r)≠r，即存在无损连接的反例。所以，分解ρ是连接有损的。假设算法5.3的输出结果是true，即最后得到的表T中有全a行，要证明ρ是无损连接分解，必须证明满足F的任何关系r都满足r=mρ(r)。因为由算法5.3的步骤(2)知，全a行是为满足F中的函数依赖将T中元素替代得到的，即若X→Y∈F，就有ti1,ti2,…,tip∈T(1＜p≤K)，当ti1[X]=ti2[X]=…=tip[X]时，则使ti1[Y]=ti2[Y]=…=tip[Y]。因为ti1[X]，ti2[X]，…，tip[X]是属于不同的Ri的，所以，若对T中的元素赋值，替代的结果相当于作投影连接，因此，全a行所对应的值是mρ(r)中的一个元组。根据算法5.3知，构造表T的结果是满足F的，故对R上满足函数依赖集F的任一关系r，如果给表T中的行赋值，使T的每行赋r中一个元组对应列的值，则赋值后T中的行若是可连接的，连接后的元组ui应属于mρ(r)。又由算法5.3知，元组ui一定与表T中(a1,a2,…,an)所对应的元组值相同，即(a1,a2,…,an)所对应的元组值属于mρ(r)。由于对表T的赋值可以是r中元组的任意组合，因此，不同的赋值可得到mρ(r)中所有的元组。而对表T的赋值是r中的元组，即ui∈r，因此有mρ(r)

r。由引理5.3知，r

mρ(r)，因此有r=mρ(r)。所以最后得到表T中若有全a行，则分解ρ是无损连接的。

证毕。算法5.3可检验任意的分解ρ，如果分解ρ仅含有两个关系模式，则可用定理5.6来检验其是否是无损连接分解的。

定理5.6

设关系模式R的一个分解ρ={R1,R2}，U1、U2和U分别是R1、R2和R的属性集合，F是R上的函数依赖集，则ρ具有无损连接性的充分必要条件是：

(U1∩U2)→(U1-U2)∈F+

或(U1∩U2)→(U2-U1)∈F+

证明：对这个分解应用算法5.3，构造初始表如表5.11所示，但省略了a和b的角标，因为忽略它们不影响证明的正确性。表5.11构造的初始表容易证明，如果在属性A上的分量b能够被修改成a，则属性A属于(U1∩U2)+。也容易利用Armstrong公理导出：如果(U1∩U2)→Y成立，则在Y上的那些b都将改成a。于是，对应R1的行全变成a当且仅当(U2

-

U1)

(U1∩U2)+(或(U1∩U2)→(U2

-

U1))。类似地，对应R2的行全变成a当且仅当(U1

-