第5章
规范化设计





本章介绍关系数据库的规范化设计理论(即“模式设计理论”)。这个理论主要包括三个方面的内容： 数据依赖、范式和模式设计方法。其中数据依赖起着核心作用，数据依赖研究数据之间的联系，范式是关系模式的标准。
规范化设计理论对关系数据库结构的设计起着重要的作用。
本章介绍最重要的一种数据依赖——函数依赖，关系模式分解的两大特性——无损分解和保持依赖以及范式、模式分解方法，最后介绍模式进一步规范化的内容。
5.1关系模式的设计问题
5.1.1关系模型的外延和内涵

一个关系模型包括外延(Extension)和内涵(Intension)两个方面的内容。
外延就是通常所说的关系、表或当前值。由于用户经常对关系进行插入、删除和修改操作，因此外延是与时间有关的，随着时间的推移在不断变化。
内涵是对数据的定义以及数据完整性约束的定义。对数据的定义包括对关系、属性、域的定义和说明。对数据完整性约束的定义涉及面较广，主要包括以下两个方面。
静态约束： 涉及数据之间的联系(称为“数据依赖”（Data Dependences)）、主键和值域的设计。
动态约束： 定义各种操作(插入、删除、修改)对关系值的影响。一般，把内涵称为关系模式，所以关系模式应包括这些内容。
5.1.2泛关系模式与数据库模式
本章讨论问题的框架如图5.1所示。
对于一个现实问题，它有一个属性集U，其中每个属性Ai对应一个值域，而不同的属性可以有相同的值域。现实问题的所有属性组成的关系模式记为R(U)。关系r是关系模式R(U)

的当前值，是元组的集合。这样的关系模式和关系一般称为泛关系模式(Universal Relation Schema)和泛关系(Universal Relation)。

图5.1泛关系模式与数据库模式


但在实际使用时，往往R(U)和r不是恰当的形式，而必须用一个关系模式的集合ρ={R1，R2，…，Rk}代替R(U)，其中每个Ri的属性是U的子集。有时就用Ri表示其属性集，因此有R1∪R2∪…∪Rk＝U。这里ρ称为数据库模式(Database Schema)。对数据库模式的每一个关系模式Ri赋予一个当前值，就得到数据库实例(简称为数据库)。
因此，在计算机中数据并不是存储在泛关系r中，而是存储在数据库σ中。
本章主要介绍如何把泛关系模式分解成规范的、较优的数据库模式。


5.1.3关系模式的冗余和异常问题
在数据管理中，数据冗余一直是影响系统性能的大问题。数据冗余是指同一个数据在系统中多次重复出现。在文件系统中，由于文件之间没有联系，引起一个数据在多个文件中出现。数据库系统克服了文件系统的这种缺陷，但对于数据冗余问题仍然应加以关注。如果一个关系模式设计得不好，仍然会出现像文件系统一样的数据冗余、异常、不一致等问题。
【例5.1】设有一个关系模式R(SNO，CNO，CNAME，TNAME)，其属性分别表示学生学号、选修课程的课程号、课程名、任课老师姓名，具体实例如图5.2所示。


图5.2关系模式R的实例



虽然这个模式只有四个属性，但在使用过程中会出现以下问题。
① 数据冗余。如果一门课程有多个学生选修，那么在关系中要出现多个元组，也就是这门课程的课程名和任课老师姓名要重复多次。
② 操作异常。由于数据的冗余，在对数据操作时会引起各种异常。
 修改异常。例如C4课程有三个学生选修，在关系中就会有三个元组。如果这门课程的教师改为CHEN老师，那么这三个元组的教师姓名都要改为CHEN老师。若有一个元组的教师姓名未改，就会造成这门课程的任课老师不唯一，产生不一致现象。
 插入异常。如果需安排一门新课程(C8，DELPHI，CHEN)，在尚无学生选修时，要把这门课程的数据值存储到关系中去时，在属性SNO上就会出现空值。在数据库技术中空值的语义是非常复杂的，对带空值元组的检索和操作也十分麻烦。
 删除异常。如果在图5.2中要删除学生S8选课元组，那么就要把这门课程的课程名和教师姓名一起删除，这也是一种不合适的现象。
因此，关系模式R的设计不是一个合适的设计。
在例5.1中，关系模式R存在数据冗余和操作异常现象。如果用下面两个关系模式R1和R2代替R： R1(SNO，CNO)和R2(CNO，CNAME，TNAME)，其关系实例如图5.3所示。


图5.3关系模式R2的实例



这样分解后，例5.1中提到的冗余和异常现象基本消除了。每门课程的课程名和教师姓名只存放一次，即使这门课程还没有学生选修，其课程名和教师姓名也可存放在关系R2中。
但是将R分解成R1和R2两个模式是否是最佳分解，也不是绝对的。如果要查询学生所学课程的任课教师，就要对两个关系做连接操作，连接的代价是很大的。而在原来模式R的关系中，就可直接找到上述结果。到底什么样的关系模式是最优的，标准是什么，如何实现，都是本章要讨论的问题。
5.1.4本章的符号规定
为了便于阅读，本章对使用的符号有如下规定： 
(1) 英文字母表首部的大写字母“A，B，C，…”表示单个的属性。
(2) 英文字母表尾部的大写字母“…，U，V，W，X，Y，Z”表示属性集。
(3) 大写字母R表示关系模式，小写字母r表示其关系。为叙述方便，有时也用属性名的组合写法表示关系模式。若模式有A、B、C三个属性，就用ABC表示关系模式。
(4) 属性集{A1，A2，…，An}简写为A1A2…An。属性集X和Y的并集X∪Y简写为XY。X∪{A}简写为XA或AX。
5.2函 数 依 赖
在数据库中，数据之间存在着密切的联系。在数据库技术中，把数据之间存在的联系称为“数据依赖”。设计人员的一个职责就是要把数据依赖找出来。在数据库规范化设计中，数据依赖起着关键的作用。其中，函数依赖是基本的一种依赖，它是关键码概念的推广。
5.2.1函数依赖的定义
在数据库中，属性值之间会发生联系。例如每个学生只有一个姓名，每门课程只有一个任课教师，每个学生学一门课程只能有一个总评成绩等。这类联系称为函数依赖，其形式定义如下。
定义5.1设有关系模式R(U)，X和Y是属性集U的子集，函数依赖(Functional Dependency，FD)是形为X→Y的一个命题，只要r是R的当前关系，对r中任意两个元组t和s，都有t［X］=s［X］蕴涵t［Y］=s［Y］，那么FD X→Y在关系模式R(U)中成立。
这里t［X］表示元组t在属性集X上的值，其余类同。X→Y读作“X函数决定Y”，或“Y函数依赖于X”。FD是对关系模式R的一切可能的关系r定义的。对于当前关系r的任意两个元组，如果X值相同，则要求Y值也相同，即有一个X值就有Y值与之对应，或者说Y值由X值决定。因而这种依赖称为函数依赖。
【例5.2】有一个关于学生选课、教师任课的关系模式： 

R(SNO, SNAME, CNO, GRADE, CNAME, TNAME, TAGE)

属性分别表示学生学号、姓名、选修课程的课程号、成绩、课程名、任课教师姓名和年龄等意义。
如果规定，每个学号只能有一个学生姓名，每个课程号只能决定一门课程，那么可写成下列FD形式： 

SNO→SNAME

CNO→CNAME

每个学生每学一门课程，有一个成绩，那么可写出下列FD： 

(SNO, CNO)→GRADE

还可以写出其他一些FD： 

CNO→(CNAME, TNAME, TAGE)

TNAME→TAGE

【例5.3】设关系模式R(ABCD)，在R的关系中，属性值间有这样的联系： A值与B值有一对多联系，即每个A值有多个B值与之联系，而每个B值只有一个A值与之联系； C值与D值之间有一对一联系，即每个C值只有一个D值与之联系，每个D值只有一个C值与之联系。试根据这些规则写出相应的函数依赖。
【解】从A值与B值有一对多联系，可写出函数依赖B→A。
从C值与D值有一对一联系，可写出两个函数依赖C→D和D→C。
5.2.2FD的逻辑蕴涵
由于函数依赖是用命题形式定义的，因此函数依赖之间存在着逻辑蕴涵的关系。比如A→B和B→C在关系模式R中成立，那么A→C在R中是否成立？这个问题就是FD之间的逻辑蕴涵问题。
定义5.2设F是在关系模式R(U)上成立的函数依赖集，X和Y是属性集U的子集。如果从F推导出X→Y也在R(U)上成立，那么称F逻辑蕴涵X→Y，记为FX→Y。
定义5.3设F是函数依赖集，被F逻辑蕴涵的函数依赖全体构成的集合，称为函数依赖集F的闭包(Closure)，记为F+。即： 
F+={X→Y|FX→Y}
5.2.3FD的推理规则
从已知的一些FD，可以推导出另外一些FD，这就需要一系列推理规则。FD的推理规则最早出现在1974年W.W.Armstrong的论文里，这些规则常被叫作“Armstrong公理”。下面的推理规则是他人于1977年提出的改进形式。
设U是关系模式R的属性集，F是R上成立的只涉及U中属性的函数依赖集。FD的推理规则有以下三条： 
A1(自反性，Reflexivity)： 若YXU，则X→Y在R上成立。
A2(增广性，Augmentation)： 若X→Y在R上成立，且ZU，则XZ→YZ在R上成立。
A3(传递性，Transitivity)： 若X→Y和Y→Z在R上成立，则X→Z在R上成立。
定理5.1FD推理规则A1、A2和A3是正确的。也就是，如果X→Y是从F用推理规则导出，那么X→Y在F+中。
证明： 根据FD的定义和使用反证法来证明。
(1) A1是显然的。因为不可能在一个关系中存在两个元组在X上是相等的，而在X的某个子集Y上不相等。
(2) 假设R的某个关系r中存在两个元组t和s违反XZ→YZ，即t［XZ］=s［XZ］，但t［YZ］≠s［YZ］。
从t［YZ］≠s［YZ］可知t［Y］≠s［Y］或t［Z］≠s［Z］。如果t［Y］≠s［Y］，则与已知的X→Y矛盾； 如果t［Z］≠s［Z］，则与假设的t［XZ］＝s［XZ］矛盾。因此，假设不成立，从而得出A2是正确的。
(3) 假设R的某个关系r中存在两个元组t和s违反X→Z，即t［X］=s［X］，但t［Z］≠s［Z］。
如果t［Y］≠s［Y］，则与已知的X→Y矛盾； 如果t［Y］＝s［Y］，则与已知的Y→Z矛盾。因而A3是正确的。
【例5.4】已知关系模式R(ABC)，F={A→B，B→C}，求F+。
根据FD的推理规则，可推出F的F+有43个FD。
例如，据规则A1可推出A→(表示空属性集)，A→A，…据已知的A→B及规则A2可推出AC→BC，AB→B，A→AB，…据已知条件及规则A3可推出A→C等。读者可自行推出这43个FD。
定义5.4对于FD X→Y，如果YX，那么称X→Y是一个“平凡的FD”； 否则称为“非平凡的FD”。
正如名称所示，平凡的FD并没有实际意义，根据规则A1就可推出。人们感兴趣的是非平凡的FD。只有非平凡的FD才和“真正的”完整性约束条件相关。
已经证明，{A1，A2，A3}是函数依赖的一个正确的和完备的推理规则集。推理规则的正确性是指“从FD集F使用推理规则集推出的FD必定在F+中”，完备性是指“F+中的FD都能从F集使用推理规则集导出”。也就是正确性保证了推出的所有FD是正确的，完备性保证了可以推出所有被蕴涵的FD。这就保证了推导的有效性和可靠性。
除了上述A1、A2、A3三条规则外，FD还有几个实用的推理规则，这些规则可从上面三条规则导出。这些规则如下： 
A4(合并性，Union)： {X→Y，X→Z}X→YZ。
A5(分解性，Decomposition)： {X→Y，ZY}X→Z。
A6(伪传递性)： {X→Y，WY→Z}WX→Z。
A7(复合性，Composition)： {X→Y，W→Z}XW→YZ。
A8 {X→Y，W→Z}X∪(W－Y)→YZ。
其中A8是1992年由Darwer提出的，称为“通用一致性定理”(General Unification Theorem)。
从A4和A5，立即可得到下面的定理。
定理5.2如果A1A2…An是关系模式R的属性集，那么X→A1A2…An成立的充分必要条件是X→Ai(i=1，2，…，n)成立。
5.2.4FD和关键码的联系
有了FD概念后，可以把关键码和FD联系起来。实际上，函数依赖是关键码概念的推广。
定义5.5设关系模式R的属性集是U，X是U的一个子集。如果X→U在R上成立，那么称X是R的一个超键。如果X→U在R上成立，但对于X的任一真子集X1都有X1→U不成立，那么称X是R上的一个候选键。本章的键都是指候选键。
【例5.5】在学生选课、教师任课的关系模式中： 

R(SNO, SNAME, CNO, GRADE, CNAME, TNAME, TAGE)

如果规定： 每个学生每学一门课只有一个成绩，每个学生只有一个姓名，每个课程号只有一个课程名，每门课程只有一个任课教师，那么根据这些规则，可以知道(SNO，CNO)能函数决定R的全部属性，并且是一个候选键。虽然(SNO，SNAME，CNO，TNAME)也能函数决定R的全部属性，但相比之下，只能说是一个超键，而不能说是候选键，因为其中含有多余属性。
5.2.5属性集的闭包
在实际使用中，经常要判断能否从已知的FD集F推导出FD X→Y，那么可先求出F的闭包F+，然后再看X→Y是否在F+中。但是从F求F+是一个复杂且困难的问题(NP完全问题，指数级问题)。下面引入属性集闭包概念，将使判断问题化为多项式级时间问题。
定义5.6设F是属性集U上的FD集，X是U的子集，那么(相对于F)属性集X的闭包用X+表示，它是一个从F集使用FD推理规则推出的所有满足X→A的属性A的集合： 

X+={属性A|X→A在F+中}
从属性集闭包的定义，立即可得出下面的定理。
定理5.3X→Y能用FD推理规则推出的充分必要条件是YX+。
从属性集X求X+并不太难，花费的时间与F中全部依赖的数目成正比，是一个多项式级时间问题。
【例5.6】属性集U为ABCD，FD集为{A→B，B→C，D→B}。据属性集闭包的定义，可求出A+=ABC，(AD)+=ABCD，(BD)+=BCD，等。
5.2.6FD集的最小依赖集
如果关系模式R(U)上的两个函数依赖集F和G，有F+=G+，则称F和G是等价的函数依赖集。
函数依赖集F中的FD很多，应该从F中去掉平凡的FD、无关的FD、FD中无关的属性，以求得F的最小依赖集Fmin。形式定义如下： 
定义5.7设F是属性集U上的FD集。如果Fmin是F的一个最小依赖集，那么Fmin应满足下列四个条件： 
(1) F+min=F+； 
(2) 每个FD的右边都是单属性； 
(3) Fmin中没有冗余的FD(即F中不存在这样的函数依赖X→Y，使得F与F-{X→Y}等价)； 
(4) 每个FD的左边没有冗余的属性(即F中不存在这样的函数依赖X→Y，X有真子集W使得F－{X→Y}∪{W→Y}与F等价)。
显然，每个函数依赖集至少存在一个最小依赖集，但并不一定唯一。
【例5.7】设F是关系模式R(ABC)的FD集，F={A→BC，B→C，A→B，AB→C}，试求Fmin。
【解】① 先把F中的FD写成右边是单属性形式： 

F={A→B，A→C，B→C，A→B，AB→C}
显然多了一个A→B，可删去。得F={A→B，A→C，B→C，AB→C}。
② F中A→C是冗余的，可删去。得F={A→B，B→C，AB→C}。
③ F中AB→C可从B→C推出，因此AB→C也可删去。最后得F={A→B，B→C}，即所求的Fmin。
5.3关系模式的分解特性
5.3.1模式分解问题

定义5.8设有关系模式R(U)，R1，R2，…，Rk都是R的子集(这里把关系模式看成是属性的集合)，U=R1∪R2∪…∪Rk。关系模式R1，R2，…，Rk的集合用ρ表示，ρ={R1，R2，…，Rk}。用ρ代替R的过程称为关系模式的分解。这里ρ称为R的一个分解，ρ也称为数据库模式。
实际上，这个定义已在图5.1中表示。在5.1节中已提到，R分解成ρ的目的是为了消除数据冗余和操作异常现象。那么σ和r是否表示同一个数据库？如果两者表示不同的内容，那么这个分解就没有什么意义了。
可以从两个角度来考虑分解。
(1) σ和r是否等价，即是否表示同样的数据。这个问题用“无损分解”特性表示。
(2) 在模式R上有一个FD集F，在ρ的每一个模式Ri上有一个FD集Fi，那么{F1，F2，…，Fn}与F是否等价。这个问题用“保持依赖”特性表示。
5.3.2无损分解
【例5.8】设有关系模式R(ABC)，分解成ρ={AB，AC}。
① 图5.4(a)是R上的一个关系r，图5.4(b)、图5.4(c)是r在模式AB和AC上的投影r1和r2。显然，此时有r1r2=r。也就是在r投影、连接以后仍然能恢复成r，即未丢失信息，这正是大家所希望的。这种分解称为“无损分解”。


图5.4未丢失信息的分解



② 图5.5(a)是R上的一个关系r，图5.5(b)和图5.5(c)是r在模式AB和AC上的投影r1和r2，图5.5(d)是r1r2。此时r1r2≠r。也就是r在投影、连接以后比原来r的元组还要多(增加了噪声)，把原来的信息丢失了。这种分解是我们不希望产生的。这种分解称为“损失分解”。


图5.5丢失信息的分解


定义5.9设R是一个关系模式，F是R上的一个FD集。R分解成数据库模式ρ={R1，R2，…，Rk}。如果对R中满足F的每一个关系r，都有

r=πR1(r)πR2(r)…πRk(r)

那么称分解ρ相对于F是“无损连接分解”(Lossless Join Decomposition)，简称为“无损分解”，否则称为“损失分解”(Lossy Decomposition)。其中符号πRi(r)表示关系r在模式Ri属性上的投影。r的投影连接表达式πR1(r)…πRk(r)用符号mρ(r)表示，即mρ(r)=Ki=1πRi(r)。
r和mρ(r)之间的联系有下面三个性质。
设ρ={R1，R2，…，Rk}是关系模式R的一个分解，r是R的任一关系，ri=πRi(r)(1≤i≤k)，那么有下列性质： 
(1) rmρ(r)； 
(2) 若s= mρ(r)，则πRi(s)=ri； 
(3) mρ(mρ(r))=mρ(r)，这个性质称为幂等性(Idempotent)。
上述三个性质可用图5.6表示。



图5.6r的投影连接变换示意图


应注意，上述性质有一个先决条件，即r是R的一个关系。也就是在先存在r(泛关系)的情况下，再去谈论分解，这是关系数据库理论中著名的“泛关系假设”(Universal Relation Assumption)。在存在泛关系情况下，泛关系的投影连接变换的示意图可修改为图5.7。


图5.7泛关系假设下的示意图


如果谈论模式分解时，先不提泛关系r的存在性，而先说存在一个数据库实例σ〈r1，r2，…，rk〉，再设Ki=1πri(r)=s，那么πRi(s)就未必与ri相等了。示意图见图5.8。原因就是ri中可能有“悬挂”元组(Dangling Tuple，破坏泛关系存在的元组)。下面以例5.9为例对这种情况进行说明。


图5.8无泛关系假设时的示意图


【例5.9】设关系模式R(ABC)分解成ρ={AB，BC}。图5.9(a)和图5.9(b)分别是模式AB和BC上的值r1和r2，图5.9(c)是r1r2的值。显然πBC(r1r2)≠r2。这里r2中元组(b2c2)就是一个悬挂元组，由于它的存在，使得r1和r2不存在泛关系r。


图5.9关系r1和r2不存在泛关系




模式分解能消除数据冗余和操作异常现象，并能使数据库中存储悬挂元组，即存储泛关系中无法存储的信息。但是分解以后，检索操作需要做笛卡儿积或连接操作。这将付出时间代价。一般认为，为了消除冗余和异常现象，对模式进行分解是值得的。
5.3.3无损分解的测试方法
在把关系模式R分解成ρ以后，如何测试分解ρ是否是无损分解？已有人提出一个“追踪”(Chase)算法，用于测试一个分解是否是无损分解。
算法5.1无损分解的测试。
输入： 关系模式R=A1A2…An，F是R上成立的函数依赖集，ρ={R1，R2，…，Rk}是R的一个分解。
输出： 判断ρ相对于F是否具有无损分解特性。
方法： (1) 构造一张k行n列的表格，每列对应一个属性Aj(1≤j≤n)，每行对应一个模式Ri(1≤i≤k)。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上bij。
(2) 把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改方法如下： 
对于F中一个FD X→Y，如果表格中有两行在X值上相等，在Y值上不相等，那么把这两行在Y值上也改成相等的值。如果Y值中有一个是aj，那么另一个也改成aj； 如果没有aj，那么用其中一个bij替换另一个值(尽量把下标ij改成较小的数)。一直到表格不能修改为止(这个过程称为chase过程)。
(3) 若修改的最后一张表格中有一行是全a，即a1a2…an，那么称ρ相对于F是无损分解，否则称损失分解。
【例5.10】设关系模式R(ABCD)，R分解成ρ={AB，BC，CD}。如果R上成立的函数依赖集F1={B→A，C→D}，那么ρ相对于F1是否是无损分解？如果R上成立的函数依赖集F2={A→B，C→D}呢？
【解】
① 相对于F1，chase过程的示意图如图5.10所示。


图5.10相对于F1,chase过程的示意图



据B→A，可把b21改成a1； 据C→D，可把b24改成a4。此时第二行已是全a行，因此相对于F1，R分解成ρ是无损分解。
② 相对于F2，chase过程的示意图如图5.11所示。
据C→D，可把b24改成a4； 据A→B，不能修改表格。此时表格没有一行是全a行，因此相对于F2，R分解成ρ是损失分解。


图5.11相对于F2，chase过程的示意图



在chase过程中，如果把b改成a，则表示从其他模式和已知的FD使得该模式可以增加一个属性。如果改成另一个bij，表示模式相应关系中该属性值虽然还没有，但其值应与其他关系中的值相等。
当最后一张表格中存在一行全a时，这行表示的模式中可以包含R的所有属性，也就回到原来的表格，即mρ(r)=r。因此，分解是无损分解。
当最后一张表格中不存在全a行时，也就是回不到原来的表格，即mρ(r)≠r。因此，分解是损失分解。
当ρ中只包含两个关系模式时，存在一个较简单的测试定理。
定理5.4设ρ={R1，R2}是关系模式R的一个分解，F是R上成立的FD集，那么分解ρ相对于F是无损分解的充分必要条件是： 

(R1∩R2)→(R1-R2)或(R1∩R2)→(R2-R1)
这个定理的证明可以用算法5.1的chase过程来实现。
5.3.4保持函数依赖的分解
分解的另一个特性是在分解的过程中能否保持函数依赖集，如果不能保持FD，那么数据的语义就会出现混乱。
定义5.10设F是属性集U上的FD集，Z是U的子集，F在Z上的投影用πZ(F)表示，定义为： 

πZ(F)={X→Y|X→Y∈F+，且XYZ}
定义5.11设ρ={R1，R2，…，Rk}是R的一个分解，F是R上的FD集，如果有∪Ki=1πRi(F)F，那么称分解ρ保持函数依赖集F。
从定义5.10可知F∪Ki=1πRi(F)，从定义5.11可知∪Ki=1πRi(F)F，因此，在分解ρ保持函数依赖情况下有∪Ki=1πRi(F)+=F+。
根据定义5.11，测试一个分解是否保持FD，比较可行的方法是逐步验证F中每个FD是否被∪Ki=1πRi(F)逻辑蕴涵。
如果F的投影不蕴涵F，而用ρ={R1，R2，…，Rk}表达R，很可能会找到一个数据库实例σ满足投影后的依赖，但不满足F。对σ的更新也有可能使r违反FD。下面的例子说明了这种情况。
【例5.11】设关系模式R(WNO，WS，WG)的属性分别表示职工的工号、工资级别和工资数目。FD有WNO→WS，WS→WG。
R分解成ρ={R1，R2}，其中R1={WNO，WS}，R2={WNO，WG}，可以验证这个分解是无损分解。
R1上的FD是WNO→WS，R2上的FD是WNO→WG。但从这两个FD推导不出在R上成立的FD WS→WG，因此分解ρ把WS→WG丢失了，即ρ不保持F。图5.12(a)和图5.12(b)是两个关系r1和r2，图5.12(c)是r1r2。r1和r2分别满足πR1(F)和πR2(F)。但r1r2违反了WS→WG。


图5.12丢失FD的分解



如果某个分解能保持FD集，那么在数据输入或更新时，只要每个关系模式本身的FD约束被满足，就可以确保整个数据库中数据的语义完整性不受破坏。显然这是一种良好的特性。
5.3.5本节小结
本节讨论的关系模式分解的两个特性实际上涉及两个数据库模式的等价问题，这种等价包括数据等价和依赖等价两个方面。数据等价是指两个数据库实例应表示同样的信息内容，用“无损分解”衡量。如果是无损分解，那么对泛关系反复的投影和连接都不会丢失信息。依赖等价是指两个数据库模式应有相同的依赖集闭包。在依赖集闭包相等的情况下，数据的语义是不会出差错的。违反数据等价或依赖等价的分解很难说是一个好的模式设计。
但是要同时达到无损分解和保持FD的分解也不是一件容易的事情，需要认真对待。下面的例子表示关系模式R(ABC)在不同函数依赖集上即使对同样的分解也会产生不同的结果。
【例5.12】设关系模式R(ABC)，ρ={AB，AC}是R的一个分解。试分析分别在F1={A→B}，F2={A→C，B→C}，F3={B→A}，F4={C→B，B→A}情况下，ρ是否具有无损分解和保持FD的分解特性。
【解】
① 相对于F1={A→B}，分解ρ是无损分解且保持FD的分解。
② 相对于F2={A→C，B→C}，分解ρ是无损分解，但不保持FD集。因为B→C丢失了。
③ 相对于F3={B→A}，分解ρ是损失分解但保持FD集的分解。
④ 相对于F4={C→B，B→A}，分解ρ是损失分解且不保持FD集的分解。
从上例可以看出分解的无损分解与保持FD的分解两个特性之间没有必然的联系。
5.4关系模式的范式
关系模式的好与坏，用什么标准衡量？这个标准就是模式的范式(Normal Forms，NF)。范式有1NF、2NF、3NF、BCNF等多种。范式的种类与数据依赖有着直接的联系。
5.4.1第一范式
定义5.12如果关系模式R的每个关系r的属性值都是不可分的原子值，那么称R是第一范式(First Normal Form，1NF)的模式。
满足1NF的关系称为规范化的关系，否则称为非规范化的关系。关系数据库研究的关系都是规范化的关系。例如关系模式R(NAME，ADDRESS，PHONE)，如果一个人有两个电话号码(PHONE)，那么在关系中至少要出现两个元组，以便存储这两个号码。
1NF是关系模式应具备的最起码的条件。
5.4.2第二范式
即使关系模式是1NF，但很可能具有不受欢迎的冗余和异常现象。因此需把关系模式做进一步的规范化。
如果关系模式中存在局部依赖，就不是一个好的模式，需要把关系模式分解，以排除局部依赖，使模式达到2NF的标准。具体定义如下所述。
定义5.13对于FD W→A，如果存在X  W有X→A成立，那么称W→A是局部依赖(A局部依赖于W)； 否则称W→A是完全依赖。
完全依赖也称为“左部不可约依赖”。
定义5.14如果A是关系模式R的候选键中的属性，那么称A是R的主属性； 否则称A是R的非主属性。
定义5.15如果关系模式R是1NF，且每个非主属性完全函数依赖于候选键，那么称R是第二范式(2NF)的模式。如果数据库模式中每个关系模式都是2NF，则称数据库模式为2NF的数据库模式。
【例5.13】设关系模式R(SNO，CNO，GRADE，TNAME，TADDR)的属性分别表示学生学号、选修课程的编号、成绩、任课教师姓名和教师地址等意义。(SNO，CNO)是R的候选键。
R上有两个FD： (SNO，CNO)→(TNAME，TADDR)和CNO→(TNAME，TADDR)，因此前一个FD是局部依赖，R不是2NF模式。此时R的关系就会出现冗余和异常现象。例如某一门课程有100个学生选修，那么在关系中就会存在100个元组，因而教师的姓名和地址就会重复100次。
如果把R分解成R1(CNO，TNAME，TADDR)和R2(SNO，CNO，GRADE)后，局部依赖(SNO，CNO)→(TNAME，TADDR)就消失了。R1和R2都是2NF模式。
在关系模式R中消除非主属性对候选键的局部依赖的方法如下所述。
算法5.2分解成2NF模式集的算法。
设关系模式R(WXYZ)，主键是WX，R上还存在FD X→Z(也就是WX→Z是一个局部依赖)。此时应把R分解成两个模式： 
R1(XZ)，主键是X； 
R2(WXY)，主键是WX，外键是X(REFERENCESR1)。
利用外键和主键的连接可以从R1和R2重新得到R。
如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中每一个关系模式都是2NF为止。
5.4.3第三范式
定义5.16如果X→Y，Y→A，且Y→＼X和AY，那么称X→A是传递依赖(A传递依赖于X)。
定义5.17如果关系模式R是1NF，且每个非主属性都不传递依赖于R的候选键，那么称R是第三范式(3NF)的模式。如果数据库模式中每个关系模式都是3NF，则称其为3NF的数据库模式。
【例5.14】例5.13中的R1(CNO，TNAME，TADDR)是2NF模式。如果R1中存在FD： CNO→TNAME和TNAME→TADDR，那么CNO→TADDR就是一个传递依赖，即R1不是3NF模式。此时R1的关系中也会出现冗余和异常操作。例如一个教师开设五门课程，那么关系中就会出现五个元组，教师的地址就会重复五次。
如果把R1分解成R11(TNAME，TADDR)和R12(CNO，TNAME)后，CNO→TADDR就不会出现在R11和R12中。这样R11和R12都是3NF模式。
在关系模式R中消除非主属性对候选键的传递依赖的方法如下所述。
算法5.3分解成3NF模式集的算法。
设关系模式R(WXY)，主键是W，R上还存在FD X→Y。这样W→Y就是一个传递依赖。此时应把R分解成两个模式： 
R1(XY)，主键是X； 
R2(WX)，主键是W，外键是X(REFERENCESR1)。
利用外键和主键相匹配机制，R1和R2通过连接可以重新得到R。
如果R1和R2还不是3NF，则重复上述过程，一直到数据库模式中每一个关系模式都是3NF为止。
从定义5.13和定义5.16可以知道，局部依赖的存在必定蕴涵着传递依赖的存在。也就是，如果R是3NF模式，那么R也是2NF模式。
局部依赖和传递依赖是模式产生冗余和异常的两个重要原因。由于3NF模式中不存在非主属性对候选键的局部依赖和传递依赖，因此消除了很大一部分存储异常，具有较好的性能。而对于非3NF的1NF、2NF，甚至非1NF的关系模式，由于它们性能上的弱点，一般不宜作为数据库模式，通常需要将它们变换成3NF或更高级的范式，这种变换过程，称为“关系的规范化处理”。
3NF有个等价的定义，如下所述。
定义5.18设F是关系模式R的FD集，如果对F中每个非平凡的FD X→Y，都有X是R的超键，或者Y的每个属性都是主属性，那么称R是3NF的模式。
这个定义表明，如果非平凡的FD X→Y，X不包含超键(并且Y不是主属性)，那么Y必传递依赖于候选键，因此R不是3NF模式。
5.4.4BCNF
在3NF模式中，并未排除主属性对候选键的传递依赖，仍有可能有冗余和异常现象。因此有必要提出更高一级的范式。Boyce和Codd分别在1972年提出了这种范式，故称为“BCNF”
定义5.19如果关系模式R是1NF，且每个属性都不传递依赖于R的候选键，那么称R是BCNF的模式。如果数据库模式中每个关系模式都是BCNF，则称为BCNF的数据库模式。
【例5.15】设关系模式R(BNO，BNAME，AUTHOR)的属性分别表示书号、书名和作者名。如果规定，每个书号只有一个书名，但不同书号可以有相同书名； 每本书可以有多个作者，但每个作者参与编著的书名应该互不相同。这样的规定可以用下列两个FD表示： 

BNO→BNAME和(AUTHOR，BNAME)→BNO
R的关键码为(BNAME，AUTHOR)或(BNO，AUTHOR)，因而模式R的属性都是主属性，R是3NF模式。但从上述两个FD可知，属性BNAME传递依赖于关键码(AUTHOR，BNAME)，因此R不是BCNF模式。例如一本书由多个作者编写时，其书名与书号间的联系在关系中将多次出现，带来冗余和操作异常现象。
如果把R分解成R1(BNO，BNAME)和R2(BNO，AUTHOR)，能解决上述问题，且R1和R2都是BCNF。但有可能引起新的问题，例如这个分解把(AUTHOR，BNAME)→BNO丢失了，数据语义将会引起新的矛盾。
从定义5.17和定义5.19可以知道，如果R是BCNF模式，那么R也是3NF模式。
BCNF也有个等价的定义，如下所述。
定义5.20设F是关系模式R的FD集，如果对F中每个非平凡的FD X→Y，都有X是R的超键，那么称R是BCNF的模式。
这个定义表明，如果非平凡的FD X→Y中X不包含超键，那么Y必定传递依赖于候选键，因此R不是BCNF模式。
5.4.5分解成BCNF模式集的方法
这个方法的基本思路如下所述。
对于关系模式R的分解ρ(初始时ρ={R})，如果ρ中有一个关系模式Ri相对于πRi(F)不是BCNF，据定义5.20可知，Ri中存在一个非平凡FD X→Y，有X不包含超键。此时把Ri分解成XY和Ri－Y两个模式。重复上述过程，一直到ρ中每一个模式都是BCNF。
上述方法能保证把R无损分解成ρ，但不一定能保证ρ能保持FD(例5.15说明了这种情况)。
5.4.6分解成3NF模式集的方法
这个方法的基本思路如下所述。
(1) 对于关系模式R和R上成立的FD集F，先求出F的最小依赖集，然后再把最小依赖集中那些左部相同的FD用合并性合并起来。
(2) 对最小依赖集中每个FD X→Y去构成一个模式XY。
(3) 在构成的模式集中，如果每个模式都不包含R的候选键，那么把候选键作为一个模式放入模式集中。
这样得到的模式集是关系模式R的一个分解，并且这个分解既是无损分解，又能保持FD，并且每个模式都是3NF。
【例5.16】设关系模式R(ABCDE)，R的最小依赖集为{A→B，C→D}。从依赖集可知R的候选键为ACE。
先根据最小依赖集，可知ρ={AB，CD}。然后再加入由候选键组成的模式ACE。因此最后结果ρ={AB，CD，ACE}是一个3NF模式集，R相对于该依赖集是无损分解且保持FD。
5.4.7模式设计方法的原则
至此，读者对关系模式的分解有了较全面的了解。关系模式R相对于函数依赖集F分解成数据库模式ρ={R1，R2，…，Rk}，一般应具有三个特性： 
(1) ρ是BCNF模式集，或3NF模式集； 
(2) 无损分解，即对于R上任何满足F的泛关系应满足r=mρ(r)； 
(3) 保持函数依赖集F，即∪Ki=1πRi(F)F。
数据库设计者在进行关系数据库设计时，应作权衡，尽可能地使数据库模式保持最好的特性。一般尽可能设计成BCNF模式集。如果设计成BCNF模式集时达不到保持FD的特点，那么只能降低要求，设计成3NF模式集，以求达到保持FD和无损分解的特点。
模式分解并不单指把泛关系模式分解成数据库模式，也可以把数据库模式转换成另一个数据库模式，分解和转换的关键是要“等价”地分解。一个好的模式设计方法应符合三条原则： 表达性、分离性和最小冗余性。
表达性涉及两个数据库模式的等价问题，即数据等价和语义等价，分别用无损分解和保持依赖来衡量。
分离性是指在关系中只存储有直接联系的属性值，而不要把有间接联系的属性值放在一张表中。应该把有间接联系的属性值放在不同的表中。实际上“分离”就是清除冗余和异常现象。如能达到这个目的，就分离，否则将更糟。分离的基准是一系列范式。在分解成BCNF模式集时，分离与依赖等价有时是不兼容的。
最小冗余性要求分解后的模式个数和模式中属性总数应最少。目的是节省存储空间，提高操作效率，消除不必要的冗余。但要注意，实际使用时并不一定要达到最小冗余，有时带点冗余对提高查询速度是有好处的。
5.5节讨论另外两种对数据库设计有一定用处的数据依赖和范式，但基本的模式设计思想还是这些。
*5.5模式的进一步规范化
前面提到的FD有效地表达了属性值之间的多对一联系，它是现实世界中广泛存在也是最基本的一种数据依赖。但FD还不足以刻画现实世界中属性值之间的一对多联系，本节介绍的多值依赖和联系依赖能刻画一部分一对多联系。与这两种依赖有关的范式是4NF和5NF。
5.5.1多值依赖的定义
【例5.17】模式R(DNAME，TNAME，SNAME)的属性分别表示学校的系名、教师名和学生名，存储每个系里的教师和学生。例如系d1有两个教师t1和t2，三个学生s1、s2和s3，那么在关系中就要出现六个元组，否则数据就不完整如图5.13所示。显然，这里存在着数据冗余和操作异常现象。如果一个系有20个教师和100个学生，那么关系中就要出现2000个元组。


图5.13模式R的实例



产生问题的原因是教师和学生没有直接的联系。教师与系有直接的联系，学生与系有直接的联系，但教师与学生之间的联系是间接的联系。把有间接联系的属性放在一个模式中就会产生冗余和异常现象。
在模式R中，一个系有很多教师(一对多联系)，一个系有很多学生(一对多联系)，但教师与学生间没有直接联系。这种属性间的一对多联系称为多值依赖。
多值依赖的形式定义如下。
定义5.21设U是关系模式R的属性集，X和Y是U的子集，Z=R-X-Y，小写的xyz表示属性集XYZ的值。对于R的关系r，在r中存在元组(x，y1，z1)和(x，y2，z2)时，也就存在元组(x，y2，z1)和(x，y1，z2)，那么称多值依赖(Multivalued Dependency，MVD)X→→Y在模式R上成立。
在例5.17中，模式R中的属性值间的一对多联系可用MVD表示： 

DNAME→→TNAME和DNAME→→SNAME
5.5.2关于FD和MVD的推理规则集
关于FD和MVD，已经找到一个完备的推理规则集，这个集合有八条规则，三条是关于FD的(即5.2节中提到的A1、A2、A3规则)，三条是关于MVD的，还有两条是关于FD和MVD相互推导的规则。具体如下： 
设U是关系模式R上的属性集，W、V、X、Y、Z为U的子集，关于FD和MVD的推理规则有以下八条。
A1(FD的自反性)： 若YX，则X→Y。
A2(FD的增广性)： 若X→Y，且ZU，则XZ→YZ。
A3(FD的传递性)： 若X→Y，Y→Z，则X→Z。
A4(MVD的补规则，Complementation)： 若X→→Y，则X→→U－XY。
A5(MVD的增广性)： 若X→→Y，且VW，则WX→VY。
A6(MVD的传递性)： 若X→→Y，Y→→X，则X→→Z－Y。
A7(复制性，Replication)： 若X→Y，则X→→Y。
A8(接合性，Coalescence Rule)： 若X→→Y，W→Z，并且ZY，W∩Y=，那么X→Z。
像A1~A3的证明一样，可以用反证法证明规则A4~A8的正确性。
已经证明，推理规则A1~A8对于FD和MVD是完备的。和FD一样，也存在着平凡的MVD。
定义5.22对于属性集U上的MVD X→→Y，如果YX或者XY=U，那么称X→→Y是一个平凡的MVD，否则称X→→Y是一个非平凡的MVD。
这是因为从YX可根据A1和A7推出X→→Y，从XY=U可根据A1、A7和A4推出X→→Y。
根据规则A1~A8，还可以推出另外的推理规则。
A9(MVD的并规则)： 若X→→Y，X→→Z，则X→→YZ。
A10(MVD的交规则)： 若X→→Y，X→→Z，则X→→Y∩Z。
A11(MVD的差规则)： 若X→→Y，X→→Z，则X→→Y－Z，X→→Z－Y。
A12(MVD的伪传递)： 若X→→Y，WY→→Z，则WX→→Z－WY。
A13(混合伪传递)： 若X→→Y，XY→Z，则X→Z－Y。
在有FD和MVD的情况下，也可以用chase过程来测试关系模式R相对于已知的FD和MVD集分解成ρ是否为无损分解。
另外，也可以用无损分解概念来定义MVD。
定义5.23若U是关系模式R的属性集，X、Y、Z是U的一个分割。若对R的每一个关系r，都有r=πXY(r)πXZ(r)，则称MVD X→→Y在R(U)上成立。
这个定义说明，如果一个模式可以无损分解成两个模式，那么蕴涵着一个多值依赖。
5.5.3第四范式
定义5.24设D是关系模式R上成立的FD和MVD集合。如果D中每个非平凡的MVD X→→Y的左部X都是R的超键，那么称R是4NF的模式。
【例5.18】在例5.17的模式R(DNAME，TNAME，SNAME)中，键是(TNAME，SNAME)，在多值依赖DNAME→→TNAME和DNAME→→SNAME的左部未包含键，因此R不是4NF。若把R分解成R1(DNAME，TNAME)和R2(DNAME，SNAME)以后，则R1和R2都是4NF。
从4NF的定义可知，是4NF的模式肯定是BCNF模式。
5.5.4连接依赖
在定义5.23中，MVD定义为一个模式无损分解为两个模式。类似地，对于一个模式无损分解成n个模式的数据依赖，称为连接依赖，形式定义如下所述。
定义5.25设U是关系模式R的属性集，R1，R2，…，Rn是U的子集，并满足U=R1∪R2∪…∪Rn，ρ={R1，R2，…，Rn}是R的一个分解。如果对于R的每个关系r都有mρ(r)=r，那么称连接依赖(Join Dependency，JD)在模式R上成立，记为*(R1，R2，…，Rn)。
定义5.26如果*(R1，R2，…，Rn)中某个Ri就是R，那么称这个JD是平凡的JD。
【例5.19】设关系模式R(SPJ)的属性分别表示供应商、零件、项目等含义，表示三者之间的供应联系。如果规定，模式R的关系是三个二元投影(SP，PJ，JS)的连接，而不是其中任何两个的连接，如图5.14所示，那么模式R中存在着一个连接依赖*(SP，PJ，JS)。


图5.14关系SPJ是三个二元投影的连接而不是其中任何两个的连接



在模式R存在这个连接依赖时，其关系将存在冗余和异常现象。例如在元组插入或删除时就会出现各种异常(见图5.15)。


图5.15在SPJ中更新问题的例子


5.5.5第五范式
定义5.27如果关系模式R的每个JD均由R的候选键蕴涵，那么称R是5NF的模式。在有的文献中，5NF也称为投影连接范式(ProjectJoin NF，PJNF)。
这里JD可由R的键蕴涵，是指JD可由键推导得到。如果JD*(R1，R2，…，Rn)中某个Ri就是R，那么这个JD是平凡的JD； 如果JD中某个Ri包含R的键，那么这个JD可用chase方法验证。
【例5.20】在例5.19中提到的R(SPJ)中，*(SP，PJ，JS)是非平凡的JD，因此R不是5NF。应该把R分解成SP、PJ、JS三个模式，这个分解是无损分解，并且每个模式都是5NF，清除了冗余和异常现象。
连接依赖也是现实世界属性间联系的一种抽象，是语义的体现。但是它不像FD和MVD的语义那么直观，要判断一个模式是否5NF也比较困难。
对于JD，已经找到一些推理规则，但尚未找到完备的推理规则集。可以证明，5NF的模式也一定是4NF的模式。根据5NF的定义，可以得出一个模式总是可以无损分解成5NF模式集。
不同级别的范式之间的关系如图5.16所示。


图5.16不同级别的范式间的关系


小结
本章讨论如何设计关系数据库的模式问题。关系模式设计得好与不好，直接影响数据库中数据冗余度、数据一致性等问题。要设计好的数据库模式，必须有一定的理论为基础。这就是模式设计理论。
函数依赖是对关系中属性值之间多对一联系的描述，也是对关系中值的一种约束。它是对关键码概念的扩充。
关系模式在分解时应保持“等价”，有数据等价和语义等价两种，分别用无损分解和保持依赖两个特征来衡量。前者能保证泛关系在投影连接以后仍能恢复回来，而后者能保证数据在投影或连接中其语义不会发生变化，也就是不会违反FD的语义。
范式是衡量模式优劣的标准。范式的级别越高，其数据冗余和操作异常现象就越少。
关系模式的规范化过程实际上是一个“分解”过程： 把逻辑上独立的信息放在独立的关系模式中。
习题5
1. 解释下列名词。
函数依赖 函数依赖的逻辑蕴涵平凡的函数依赖函数依赖集F的闭包F+
最小依赖集无损分解保持函数依赖1NF
2NF3NFBCNF4NF
5NF推理规则的正确性和完备性多值依赖连接依赖
2. 设关系模式R有n个属性，在模式R上可能成立的函数依赖有多少个？其中平凡的FD有多少个？非平凡的FD有多少个？
3. 对函数依赖X→Y的定义加以扩充，X和Y可以为空属性集，用表示，那么X→，→Y，→的含义是什么？
4. 已知关系模式R(ABC)，F是R上成立的FD集，F={A→B，B→C}，试写出F的闭包F+。
5. 设关系模式R(ABCD)，如果规定，关系中B值与D值之间是一对多联系，A值与C值之间是一对一联系。试写出相应的函数依赖。
6. 试举出反例说明下列规则不成立： 
(1) {A→B}{B→A}
(2) {AB→C，A→C}{B→C}
(3) {AB→C}{A→C}
7. 设关系模式R(ABCD)，F是R上成立的FD集，F={A→B，C→B}，则相对于F，试写出关系模式R的关键码。并说明理由。
8. 设关系模式R(ABCD)，F是R上成立的FD集，F={A→B，B→C}。
(1) 试写出属性集BD的闭包(BD)+。
(2) 试写出所有左部是B的函数依赖(即形为“B→？”)。
9. 设关系模式R(ABC)分解成ρ={AB，BC}，如果R上的FD集F={A→B}，那么这个分解是损失分解。试举出R的一个关系r，不满足mρ(r)=r。
10. 试解释数据库“丢失信息”与“未丢失信息”两个概念。“丢失信息”与“丢失数据”有什么区别？
11. 设关系模式R(ABC)，F是R上成立的FD集，F={A→C，B→C}，试分别求F在模式AB和AC上的投影。
12. 设关系模式R(ABC)，F是R上成立的FD集，F={B→A，C→A}，ρ={AB，BC}是R上的一个分解，那么分解ρ是否保持FD集F？说明理由。
13. 设关系模式R(ABC)，F是R上成立的FD集，F={B→C，C→A}，那么分解ρ={AB，AC}相对于F，是否无损分解和保持FD？说明理由。
14. 设关系模式R(ABCD)，F是R上成立的FD集，F={A→B，B→C，A→D，D→C}，ρ={AB，AC，BD}是R的一个分解。
(1) 相对于F，ρ是无损分解吗？为什么？
(2) 试求F在ρ的每个模式上的投影。
(3) ρ保持F吗？为什么？
15. 设关系模式R(ABCD)，R上的FD集F={A→C，D→C，BD→A}，试说明ρ={AB，ACD，BCD}相对于F是损失分解的理由。
16. 设关系模式R(ABCD)，F是R上成立的FD集，F={AB→CD，A→D}。
(1) 试说明R不是2NF模式的理由。
(2) 试把R分解成2NF模式集。

17. 设关系模式R(ABC)，F是R上成立的FD集，F={C→B，B→A}。
(1) 试说明R不是3NF模式的理由。
(2) 试把R分解成3NF模式集。
18. 设有一个记录各个球队队员每场比赛进球数的关系模式

R(队员编号, 比赛场次, 进球数, 球队名, 队长名)

如果规定每个队员只能属于一个球队，每个球队只有一个队长，每个队员每场比赛只有一个进球数。
(1) 试写出关系模式R的基本FD和关键码。
(2) 说明R不是2NF模式的理由，并把R分解成2NF模式集。
(3) 进而把R分解成3NF模式集，并说明理由。
19. 设有关系模式： 

R(职工名, 项目名, 工资, 部门名, 部门经理)

如果规定每个职工可参加多个项目，各领一份工资； 每个项目只属于一个部门管理； 每个部门只有一个经理。
(1) 试写出关系模式R的基本FD和关键码。
(2) 说明R不是2NF模式的理由，并把R分解成2NF模式集。
(3) 进而把R分解成3NF模式集，并说明理由。
20. 设关系模式R(ABC)上有一个MVD A→→B。如果已知R的当前关系存在三个元组(ab1c1)、(ab2c2)和(ab3c3)，那么这个关系中至少还应该存在哪些元组？
21. 试撰写2000字短文，论述泛关系假设、无损分解和保持依赖间的联系。