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

第4章关系数据库理论4.1第一范式4.2函数依赖4.3模式分解4.4第二范式4.5第三范式4.6BC范式4.7第四范式4.8范式小结习题在前面几章，对数据库系统的一般概念、数据库概念模型、关系数据库的基本概念以及关系数据库操作的标准语言SQL进行了介绍。了解了这些概念和技术之后，需要解决如何为一个具体应用设计出合适的数据模式。针对关系型数据库来说，就是要确定关系模型中的各个关系以及关系中包含的属性，这个过程是由关系数据库逻辑设计阶段来完成的。关系模型的建立过程本质上是关系模型分解和规范化的过程。因此，在本章，首先学习函数依赖、模式分解等基本概念，然后学习如何通过模式分解和关系规范化理论得到满足要求的关系。4.1第一范式在关系数据库中，关系模式的好坏用范式(NF，NormalForms)来评价。范式有很多，但对关系模式评价最常用也是最有用范式主要是1NF、2NF、3NF和BCNF，特别是3NF和BCNF。

定义4.1

设R是一个关系模式，r是R的一个关系。如果r的每个属性值都是不可再分的(或原子的)值，那么称关系模式R是第一范式的模式。只有满足第一范式的模式才是规范关系。第一范式的定义表明，一个规范关系只有行和列，不存在表中套表(子表)的情况。表4.1(a)所示的关系不满足第一范式的定义，不是规范关系，因为其包含有子表店长(姓名，任职年月)；表4.1(b)所示的关系满足第一范式的定义，是规范关系，因为其所有的行和列都不可再分了。另外，对于表的某个属性，对于一个元组，如果存在多值情况，为了达到规范关系，应将该元组分成多个元组进行存储。例如，如果一个门店有多个“联系电话”，那么需要为每个联系电话用一个元组进行存放。表4.1非规范关系与规范关系4.2函数依赖在现实世界中，实体的各属性之间存在依赖关系。例如，知道了某个地区的邮政编码，就可以找到该地区的名称；知道了某个学生的学号，就可以查到该学生的姓名。这种属性之前的依赖关系，就是函数依赖(FD，FunctionDependency)。4.2.1基本概念定义4.2

设R(P)是一个关系模式，P是R的属性集，X、Y都是P的子集。如果，对于R的任意两个元组t1和t2，如果t1在X上的取值t1[X] 与t2在X上的取值t2[X] 相等，即t1[X] = t2[X]，那么t1和t2在Y上取值也相等，即t1[Y] = t2[Y] 成立。这时，称Y函数依赖于X，记为FD：X→Y在关系模式R(P)上成立。“X→Y”可以读作“X函数决定Y”或“Y函数依赖于X”。定义4.2表明，在一个关系模式R(P)中，如果FD：X→Y成立，那么，对于R(P)的任意一个关系r的任意两个元组，如果它们在X上的值相同，则也要求它们在Y值上也相同。也就是说，Y的值由X来决定。表4.2所示的商品定价销售关系满足函数依赖(商品代码)→(价格)。当然，从该关系可以看出，函数依赖与关系的码是不同的，例如第一元组和第三元组的“商品代码”都是“010001”，它们对应的价格都是12.00，所以是不违反“商品代码→价格”这一函数依赖，但显然“商品代码”不是这个关系的码。表4.2函数依赖实例由上面的讨论可知，利用函数依赖可以对关系中数据的正确性进行验证，从而使关系的实现和存储更加有效。但同时也要注意到，在商品销售关系中，如果采用商品代码→价格这个函数依赖，那么，该关系就不是存放异价商品的销售数据了。因为，一件商品会有不同的销售价格，不满足商品代码→价格。因此，函数依赖也会导致一些信息无法存放到关系中。针对关系模式R(P)上的FD：X→Y，根据X和Y之间的包含关系，可将函数依赖X→Y分成以下3种类型：

(1)如果Y⊆X，那么称FD：X→Y为平凡的函数依赖；

(2)如果Y至少有一个属性不在X中，那么称FD：X→Y为非平凡的函数依赖；

(3)如果X∩Y = ，那么称FD：X→Y是完全非平凡的函数依赖。定义4.3

设X→Y是关系模式R(P)上的一个函数依赖，如果不存在X '⊂Y使得X '→Y成立，则称X→Y是完全函数依赖或Y完全函数依赖于X。如果存在X '⊂Y使得X '→Y成立，则称X→Y是部分函数依赖或Y部分函数依赖于X。例如，表4.2所示的商品定价销售关系中，函数依赖(商品代码)→(价格)是完全函数依赖，而(商品代码，营业员工号，交易日期)→(价格)是部分依赖。定义4.4在关系R(P)上，如果有非平凡函数依赖X→Y，但X不函数依赖于Y，Y→Z成立，那么则称X→Z为传递函数依赖或Z传递函数于X。4.2.2函数依赖集及闭包在一个关系模型R(P)上的一个或多个FD组合的集合F，称为函数依赖集。一般地，把带有FD集的关系模式记为R(P，F)，P是R的属性集，F是P中属性满足的FD集。可以通过已知的FD集得到未知的FD或判断某FD是否成立。这类问题称为逻辑蕴涵问题。定义4.5

设R(P，F)为一个关系模式，X和Y是P的子集。如果对于R(P，F)的任何一个关系r，函数依赖X→Y都成立，那么称F逻辑蕴涵X→Y或称X→Y为F所逻辑蕴涵。F逻辑蕴涵的全体函数依赖的集合，称为函数依赖集F的闭包，记为F+。定义4.5表明，针对关系模式R(P，F)，如果要根据F得到未知函数依赖，只要将F逻辑蕴涵的所有FD推导出即可。如果判断给定的某个FD是否成立，只是判断F是否逻辑蕴涵该FD。这里，给出R(P，F)中FD的推导规则Armstrong公理系统。

Armstrong公理系统设P为关系模式R的属性总体，F是P上的一个函数依赖集。对于关系模式R(P，F)有下列三条推理规则：

(1)自反性规则：若Y⊆X⊆P，则F逻辑蕴涵X→Y；

(2)增广性规则：若X→Y为F所逻辑蕴涵，且Z⊆P，则XZ→YZ；

(3)传递性规则：若X→Y，Y→Z都为F所逻辑蕴涵，则X→Z为F所逻辑蕴涵。

定理4.1Armstrong公理系统是正确的。证明利用函数依赖的定义(定义4.2)来证明：

(1)自反性规则：很显然，自反性规则是正确的。因为在R的一个关系r上不可能存在两个元组，它们在属性集X的值相等，而在X的某个子集上的值不相等。

(2)增广性规则：设r是R的某个关系，t1和t2是r的两个元组，它们在X上的值相同，t1[X] = t2[X]。假设t1和t2在XZ上的值相同，t1[XZ] = t2[XZ]，而在YZ上的值不相同，t1[YZ] ≠ t2[YZ]，导致这个不等式成立条件是t1[Y] ≠ t2[Y]或t1[Z] ≠ t2[Z]。由FD：X→Y可知t1[Y] = t2[Y]，那么只有t1[Z] ≠ t2[Z] 成立才能使t1[YZ] ≠ t2[YZ] 成立。由t1[XZ] = t2[XZ] 得到t1[X] = t2[X]及t1[Z] = t2[Z]。这样，t1[Z] ≠ t2[Z] 不成立。因此，增广性规则成立。

(3)传递性规则：假设r是R的某个关系，t1和t2是r的两个元组，它们在X上的值相同t1[X] = t2[X] 但t1[Z] ≠ t2[Z]。由FDX→Y可得t1[Y] = t2[Y]，再由Y→Z得t1[Z] = t2[Z]，这与题设t1[Z] ≠ t2[Z] 相矛盾。因此，传递性规则成立。在Armstrong公理系统的基础上，可得到以下几个导出规则：

(1)合并规则：若X→Y，Y→Z都为F所逻辑蕴涵，则X→YZ为F所逻辑蕴涵。

(2)分解规则：若X→V为F所逻辑蕴涵，且属性集Z⊆V，则X→Z为F所逻辑蕴涵。

(3)伪传递规则：若X→Y，VY→Z为F所逻辑蕴涵，则XV→Z为F所逻辑蕴涵。

证明

(1)合并规则：假设r是R的某个关系，t1和t2是r的两个元组，它们在X上的值相同，t1[X] = t2[X]，由FD：X→Y得到t1[Y] = t2[Y]，由Y→Z得到t1[Z] = t2[Z]，故t1[YZ] = t2[YZ]。因此，X→YZ在R(P，F)成立。

(2)分解规则：设Z⊆V，由自反性规则可知V→Z成立，而X→V为F所逻辑蕴涵，由传递性规则可知X→Z成立。

(3)伪传递规则：由增广性规则和X→Y得到VX→VY，而VY→Z，由传递性规则可知XV→Z为F所逻辑蕴涵。根据合并规则和分解规则，很容易证明下列定理：

定理4.2

如果P1，P2，…，Pn是关系模式R的属性集，那么X→P1，P2，…，Pn的充分必要条件是X→Pi

(1≤i≤n)。4.2.3属性集的闭包

Armstrong公理系统是有效的、完备的。Armstrong公理系统的有效性指的是：在关系模式R(P，F)上，根据Armstrong公理系统推导出来的任意函数依赖一定为F所逻辑蕴涵的函数依赖，它保证了推导出来的所有函数依赖是正确的；Armstrong公理系统的完备性指的是：对于所逻辑蕴涵的任意函数依赖，必定在R(P，F)上可以根据Armstrong公理系统推导出来，它保证了所有被蕴涵的函数依赖都能被推出。

Armstrong公理系统的有效性和完备性的证明需要引入属性的闭包概念。定义4.6设R(P，F)是一个关系模式，X是P的子集，那么X关于函数依赖集F的闭包(记为)是运用FD推理规则得到F+ 中所有X→Y的属性Y组成的集合：

= {Y | X→Y在F+

中}根据定理4.2和定义4.6，可以发现判断函数依赖X→Y是否能由Armstrong公理系统推得F+，也就是要判断Y是否是的子集。下面的定理能够帮助快速判断X→Y是否在F+中。

定理4.3

设R(P，F)是一个关系模式，X、Y⊆P。X→Y能由Armstrong公理系统推导的充分必要条件是Y ⊆。利用定理4.2和定义4.6，定理4.3很容易得到证明。这里，不再给出详细描述，读者可自行证明。定理4.2表明，要判断Y是否是的子集，首先要求得。分析表明，运用Armstrong公理系统推得F+ 是指数级时间。这里，介绍一种求的有效算法。算法4.1

求R(P，F)的属性集X关于函数依赖集F的闭包。输入：关系模式R的属性集P，P上的FD集F，X⊆P。输出：。过程：result←X；

for对于FD集F中的每个FDW→Z do

ifW ⊆resultthen

result←result∪W；

until(result不再变化或等P)；

returnresult例4.1已知关系模式R(P，F)，P = (ABCDE)，F = {A→BC，CD→E，B→D，E→A}试求 。计算步骤：

Step1.result={A}；

Step2.针对FD：A→BC，因为{A}⊆result，故result = {A} ∪ {BC}={ABC}；

Step3.针对FD：CD→E，因为{CD}不在result中，故result保持不变；

Step4.针对FD：B→D，因为 {B}⊆result，故result = result∪{D} = {ABCD}；

Step5.针对FD：E→A，因为A已在result中，故result保持不变；

Step6.重新查检F，由FDCD→E，{CD}⊆{ABCD}，result = result∪{E} = {ABCDE}；

Step7.  result已包含全部属性，返回result。根据计算结果可知，本题中的= (ABCDE)。

定理4.4Armstrong公理系统是有效的、完备的。

Armstrong公理系统的有效性是很显然的。只需证明Armstrong完备性。对于F所逻辑蕴涵的任意函数依赖，必定在R(P，F)上可以根据Armstrong公理系统推导出来。通过证明完备性的逆否命题可以完成完备性的证明，即证明若FD：X→Y不能由F从Armstrong公司导出，那么它必然不为F所逻辑蕴涵。设有一个FD：X→Y不能由F利用Armstrong公理系统推出。现要证明X→Y不在F+

中，即X→Y在R的某个关系r上不成立。分两步：

(1)证明F中的每个FD：V→W在r上均成立。分两种情况：V⊆或V未在中。如果V⊆，由定理4.3可知X→V。再由传递性规则可得X→W成立。再利用定理4.3，可知W⊆。这样，V⊆和W⊆同时成立，故V→W在r上也成立。如果V未在中，即V有些属性不在中。此时，关系r中有两个元组在V值上不相等，因此，V→W也在r上成立。

(2)证明X→Y在r上不成立。因此X→Y不能从F上利用Armstrong公理系统推导出，根据定理4.3，可知Y不在中。反映在关系r上，表现为存在两个元组在X值上相等，在Y值不相等，这与X→Y相矛盾。由(1)、(2)证明可知，若X→Y不能从F上利用Armstrong公理系统推出，那么，X→Y就不被F所蕴涵。这样，Armstrong公理系统的完备性得以证明。4.2.4最小覆盖由函数依赖，引入函数依赖集的覆盖和极小覆盖的概念。定义4.7设在关系R上存在两个函数依赖集F和G。如果F+

= G+，那么称函数依赖集F覆盖G(或函数依赖集G覆盖F)，或F和G等价。根据Armstrong公理系统，要判断函数依赖集F是否包含于G+，只需针对F中每个FD：X→Y，考查Y⊆是否成立即可。下面的定理提供了一个判断两个函数依赖集等价的可行算法。定理4.5

关系R上的两个函数依赖集F和G，F+

= G+

的充分必要条件是F⊆G+且G⊆F+。证明先证明必要性。已知，F⊆F+，G⊆G+，因为F+

= G+

，很显然F⊆G+

且G⊆F+成立。再证明充分性。针对某一属性集X，如果F⊆G+，则⊆。设X→Y是F+

中的任意一个FD，则有Y∈⊆。因此，X→Y包含在G+

中，即F+⊆G+

成立。同理可证，G+⊆F+。故F+

= G+。定义4.8F是关系R上的一个函数依赖集，如果F满足以下条件，就称F为一个极小函数依赖集，也称极小依赖集或最小覆盖：

(1) F中所有函数依赖X→A，A中仅含有一个属性；

(2) F中的任意函数依赖X→A，都不满足F和F－(X→A)等价；

(3) F中的任意函数依赖X→A，不存在X ‘⊂X，使得F和F － (X→A)∪(X '→A)成立。例4.2在商品定价销售关系S(P)，P = (商品代码，营业员工号，价格，销售数量，交易时间)上有两个函数依赖集F和G：

F = {商品代码 → 价格，(商品代码，营业员工号，交易时间) → 销售数量}

G = {商品代码 → 价格，(商品代码，营业员工号，交易时间) → 销售数量，(商品代码，营业员工号，交易时间) → 价格}不难看出，F是最小覆盖，而G不是最小覆盖。因此，由商品代码 → 价格可推导出(商品代码，营业员工号，交易时间) → 价格。根据最小覆盖的定义，采用“极小化处理”可证明以下定理：

定理4.6每一个函数依赖集F均等价一个极小函数依赖集Fmin，Fmin称为F的最小依赖。算法4.2求关系模式R(P，F)的函数依赖集F的等价最小依赖集。输入：关系模式R(P，F)的函数依赖集F。输出：F的最小依赖集。过程：

Step1.对F中的每个FD，将其右边分解成只有一个属性，如将X→A1A2…Ak(k>2)分解成X→Aj，j < k；

Step2.检查每个X→Aj，令G = F － (X→Aj)。若Aj∈，则从F中去掉此函数依赖；

Step3.对F中的每个FD：X→A，将其左侧表示为B1B2…Bm，对每个Bi进行判断，如果A∈，则用X－Bi替代X。最后得到的F就是Fmin。例4.3设F是关系模式R(ABC)上的函数依赖集：F = (A→BC，B→C，A→B，AB→C)求F的最小依赖集Fmin。计算步骤：

Step1.将各个FD的右侧都化为只有一个属性，A→BC化为A→B，A→C；

Step2.令G = F - (A→C，A→B) = (B→C，A→B，AB→C)， = (ABC)，故BC都在中。这样，F = G = (B→C，A→B，AB→C)；

Step3.对于F中的函数依赖AB→C，而 = (ABC)，故C∈，用A→C替换AB→C，但A→C又能从(B→C，A→B)利用传递性规则推出，因此Fmin = (B→C，A→B)。注意：F的最小依赖可能有多种情况，它与对各函数依赖及X→A中X各属性顺序有关。4.3模式分解4.3.1基本分解定义前面介绍了函数依赖及其相关特征。通常情况下，为了建立合适的关系模式往往需要将一个大的关系模式分解成几个小的关系，这就是模式分解。下面给出模式分解的形式化定义。

定义4.9

设有关系模式R(P，F)及P的子集P1P2…Pn满足条件且没有Pi⊆Pj，1≤i，j≤n，F1F2…Fn是函数依赖集F在P1P2…Pn上的投影(即Fi是F+

中在Pi上成立的函数依赖集)，那么将关系模式R(P, F)(称为泛关系模式)分解成ρ = {R1(P1, F1), R2(P2, F2), …, Rn(Pn, Fn)}的过程，称为R(P, F)的模式分解，称ρ为关系模式R(P, F)的一个分解。

例4.4已知关系模式R(P，F)，P = (ABCDE)，F = {A→BC，CD→E，B→D，E→A}，设有ρ1 = {R1，R2，R3}其中R1((ABCD)，(A→BC，B→D))，R2((ABDE)，(B→D，E→A))，R3((ACDE)，(CD→E，E→A))；ρ2 = {R1，R2，R3，R4}其中R1((ABC)，(A→BC))，R2((ABD)，(B→D))，R3((ABE)，(E→A))，R4((CDE)，(CD→E))；ρ3 = {R1，R2，R3}其中R1((ABCD)，(A→BC，B→D))，R2((ABD)，(B→D))，R3((ACDE)，(CD→E，E→A))。由定义4.8可知，ρ1，ρ2是R(P，F)的分解，而ρ3

不是R(P，F)的分解，因为R2的属性集(ABD)是R2的属性集(ABCD)的子集。关系模式的分解需要具有“等价性”，目前，对模型分解的“等价性”定义有以下3种：

(1)具有“无损连接性”；

(2)具有“保持函数依赖性”；

(3)既具有“无损连接性”，又具有“保持函数依赖性”。4.3.2无损连接分解简单地说，关系的“无损连接性”指一个关系在分解前后具有相同的数据。如果一个模式分解具有“无损连接性”，那么这个分解就称为“无损连接分解”。

定义4.10设ρ = {R1(P1，F1)，R2(P2，F2)，…，Rn(Pn，Fn)}是R(P，F)的一个分解，如果对R(P，F)的任何一个关系r均有r

=

为r在Pi上的投影)，那么称将关系模式R(P，F)分解成ρ = {R1(P1，F1)，R2(P2，F2)，…，Rn(Pn，Fn)}是无损连接分解。例4.5

将关系模式R(ABC)分解成ρ = {(AB)，(AC)}。表4.3给出了R的一个关系r分解成ρ的两个关系r1和r1及r1

r2的值。从表中可知，r1

r2≠r，由无损连接定义可知该分解不具无损连接性。表4.3不具备无损连接性的模式分解定义4.10表明，判断一个模式分解是否为无损连接分解，只要检查分解后的各个关系的自然连接与分解前的泛关系是否相等即可。但多数情况下直接根据无损连接分解的定义去判断一个模式分解的无损连接性是非常困难的。算法4.3是一个鉴别无损连接分解的常用方法。

算法4.3

判断某一模式分解是否为无损连接分解。输入：关系模式R的属性集P = (A1A2…An)及P上的函数依赖集F、R的一个分解

ρ = {R1(P1，F1)，R2(P2，F2)，…，Rn(Pn，Fn)}输出：给出ρ是否为R的一个无损连接分解的判断。判断过程如下：

Step1.构建一张n列m行的表格，表格的每一列(如列j )对应R的一个属性Aji(1≤j≤n)，每一行(如行i )对应ρ中的一个关系Ri (1≤i≤m)。对表格中第i行，第j列的值这样来确定：如果Aj在Pi中，则取值为aj；否则，取值为bij。

Step2.对每个关系Ri的函数依赖集Fi中的每个函数依赖X→Y，做如下操作：将表格中所有X分量上相等的行的Y分量的所有列值都改为相等：如果存在某行Y分量的某列Aj上的取值为aj值，那么将其他X分量相等的Aj列值也改为aj；如果不存在某行Y分量的某列Aj上的取值为aj，那么将其他分量相等的Aj列值也改为该列已有的下标i较小的bij值。重复这一过程，直到表格不能修改为止。

Step3.修改结束后，若在最后的表格中，有一行的值全部是a，即a1a2…an，那么，ρ 就是R的一个无损连接分解。例4.6已知关系模式R(P，F)，P = (ABCDE)，F = {A→BC，CD→E，B→D，E→A}分解为ρ = {R1，R2，R3}，其中R1((ABC)，(A→BC))，R2((ABD)，(B→D))，R3((CDE)，(CD→E))，试判断ρ是否为R的一个无损连接分解。计算过程如下：

Step1.构建初始表，见表4.4(a)。

Step2.利用R1中的函数依赖集A→BC，因为第1行和第2行的A值都等于a1，而第1行的C值为a3，因此，将b23改为a3；由R2中的函数依赖B→D，因为第1行和第2行的B值都等于a2，而第2行的D值为a4，故将b14改为a4，修改后的表格见表4.4(b)。在表4.4(b)所示的表格上，利用R3上的函数依赖集CD→E，发现表格的全部三行在C和D属性上的取值都分别是a3和a4，而第3行的E值为a5，因此，将第1、2行的E值改为a5，修改后的表格见表4.4(c)；

Step3.观察表4.4(c)，发现第1、2行所有列上取值都为a。因此ρ是R的一个无损连接分解。如果将一个关系模式R(P，F)分解成两个关系ρ = {R1(P1，F1)，R2(P2，F2)}，可以利用以下定理进行快速判断该分解是否为无损连接分解。

定理4.7

设将关系模式R(P，F)分解成两个关系ρ = {R1(P1，F1)，R2(P2，F2)}，ρ是R的无损连接分解的充分必要条件是(P1∩P2)→(P1

－ P2)或(P1∩P2)→(P2

－ P1)。利用算法4.3可以证明这个定理。请读者自己证明。表4.4利用算法4.3判断无损连接分解用到的表格4.3.3保持依赖“等价”分解的第二种含义是分解后能否保持函数依赖集，保持函数依赖就是保证分解后的各关系中的数据语义完整性不受破坏。定义4.11设关系模式R(P，F)的一个分解为ρ = {R1(P1，F1)，R2(P2，F2)，…，Rn(Pn，Fn)}，若，则R的分解ρ保持函数依赖。定义4.8给出一个判断分解是否保持函数依赖的方法，逐个验证F中的函数依赖是否被所蕴涵，这种方法是可行的。例4.7将加盟门店((门店编号，门店名称，店长工号，任职年月)，(门店编号→门店名称，门店编号→店长工号，店长工号→任职年月))分解成两关系：门店信息((门店编号，门店名称)，(门店编号→门店名称))和店长信息((店长工号，任职年月)，(店长工号→任职年月))试判断该分解是否保持函数依赖。通过分析，不难发现，在分解前的加盟门店的关系中存在函数依赖“门店编号→店长工号”不能从分解后的两个关系模式的函数依赖集中导出。因此，此分解不保持函数依赖。保持函数依赖的分解，只要能够保证保存在每个分解后的关系中的数据满足各个关系各自的函数依赖集，那么所有数据也满足分解前的泛关系模式中的函数依赖集。这样，就保证了分解前后数据语义的一致性。“等价”的第三种含义是“既具有‘无损连接性’，又‘保持函数依赖’”。要判断关系模式的一个分解是属性这种“等价”分解，可以利用算法4.3判断该分解是否是无损连接分解，再利用定义4.11判断该分解是否保持函数依赖。4.3.4模式信息冗余至此，了解了模式分解的定义及什么是分解的无损连接性和保持函数依赖。但为什么要进行模式分解？判断一个分解好坏的标准是什么？要得到一个关系模式的合理分解，必须先回答这两个问题。本节先回答第一个问题。下面通过一个例子来说明模式分解的重要性。表4.5所示是分解前的关系，它是用来存放5个商品的库存信息。在这个关系中，(商品代码，进货批次，商品名称，库存量，生产厂家，厂家所在城市)是其属性集，这些属性之间存在函数依赖集(商品代码→商品名称，商品代码→生产厂家名称，生产厂家→厂家所在城市，(商品代码，进货批次)→库存量)，(商品代码，进货批次)是该关系的主码。现在来分析这个模式中存在哪些问题：

(1)数据冗余。如果对某个厂家生产的某种商品进货多次，这个商品的商品名称、生产厂家及厂家所在城市就需要重复存放多次。例如，在关系中，商品代码为“01001”的“东北大米”进货两次，对应的商品名称、生产厂家、厂家所在城市都重复存放了2遍。表4.5分解前的商品库存表

(2)修改异常。数据冗余会导致数据修改产生问题。由于商品代码为“01001”商品在该关系中重复存放了两次，如果生产厂家搬迁到其他城市，必须对所有该生产厂家所在的元组的“厂家所在城市”进行修改。如果由于疏漏导致某一个元组没有修改成功，就会造成该厂家有多个城市与其相对应，这就产生了修改异常。

(3)删除异常。数据库的数据经常需要进行清理，避免不了对表中的数据进行删除操作。例如，在表4.5所示的关系中，想删除商品代码为“020015”商品的库存数据，包括商品代码、进货批次、商品名称、库存量。如果删除整个元组，就会把不应删除数据(如生产厂家，厂家所在城市)也删除了，这种删除操作显然是不适合的。

(4)插入异常。有的时候，针对一个生产厂家，在库存关系中并不一定存在该厂家生产的商品，也就是说，需要把某个生产厂家和厂家所在城市插入到关系中。由于缺少商品信息对应的属性值，所以一种可能的方法就是将对应的属性值置为空。但置空也产生问题，一是空值难于理解，再者在该关系中，商品代码和批次是主属性，是不允许取空值的。根据上面的分析，可以说表4.5所示关系对应的关系模式，不是一个“好”的关系模式。如果将该关系分解成表4.6所示的3个关系：商品关系(商品代码，商品名称，生产厂家名称)、生产厂家关系(生产厂家名称、厂家所在城市)及进货关系(商品代码，进货批次，库存量)，那么就不会产生前面提到的数据冗余、数据插入、数据删除和数据修改等异常现象。表4.6商品库存关系的一种分解上述分析表明，模式分解对保证数据库的数据正确性是十分重要的，这回答了为什么要进行模式分解的问题。但是否只要将“大”关系分解成“小”关系就一定不会产生异常了吗？显然不是。那又如何判断一个模式分解的好坏呢？为了解决这个问题，提出关系的“规范化”理论。也就是说，一个关系分解后的关系应该达到一定的标准才不会产生异常。这些标准称为关系的“范式(NF)”。范式有多种，常用的有4.1节定义的第一范式(1NF)，以及下面即将介绍的第二范式(2NF)、第三范式(3NF)、BC范式(BCNF)和第四范式(4NF)。4.4第二范式第一范式告诉我们，一个规范关系是由行与列组成的二维表，不存在表中套表(或称复合列)的情况，这是关系型数据库中的关系应满足的最基本的条件。但仅仅满足第一范式是远远不够的，在4.3节例子中的商品库存关系说明了这个问题。因此，要建立一个适合的关系模式必须满足更加严格的条件。为了更好地说明问题，从函数依赖角度对候选码进行定义。定义4.12设关系模式R(P，F)，其中P = (A1A2…An)是R的属性集，F是P上成立的函数依赖集。如果F+ 存在X⊆P使得X→A1A2…An成立，并且X中不存在真子集X '⊂X，使得X '→A1A2…An在F+ 中成立。那么，称X为关系R(P，F)的一个候选码。主码是候选码之一，通常是指数据库中正在使用的候选码。下文中所说的码，如不加专门说明，就是指的“候选码”。定义4.13

设关系模式R的候选码为X，那么X中的所有属性称为主属性。反之，不在X中的所有属性称为非主属性。回过头来再分析表4.5中的商品库存关系。显然该关系的主码是由(商品代码，进货批次)组成的复合码。其他属性如商品名称、库存量、生产厂家、厂家所在城市都依赖于这个主码，也即函数依赖(商品代码，进货批次)→商品名称，在该关系上成立。同时，由题设可知，函数依赖(商品代码→商品名称)也在该关系中成立。根据函数依赖的定义(定义4.3)，得出(商品名称)与主码(商品代码，批次)之间是部分依赖。这种非主属性对主码的部分依赖会导致数据冗余(如一个商品的名称存在多次)、数据插入异常(当有新商品需要存放在关系中，但并没进货，无批次信息就法存放)、数据修改异常(同一商品代码的商品名称发生修改，应该修改与该商品代码相同的所有元组的商品名称属性，否则，会造成数据不一致)、数据删除异常(删除某次进货信息，同时也将商品名称也删除了)。同样的情况，还发生在(生产厂家)与主码之间的部分依赖上。如果将关系中的非主属性对主码的部分依赖消除掉，又会怎样呢？在表4.7中，将原商品库存关系分解成两个关系：商品表和进货表。其中，商品关系的属性集是(商品代码，商品名称，生产厂家名称，厂家所在城市)，进货关系的属性集是(商品代码，进货批次，库存量)。在这两个关系中都不存在非主属性对主码的部分依赖，把这类关系称为满足第二范式(2NF)的关系。表4.7满足2NF的关系实例4.4.1定义定义4.14

设关系模式R满足第一范式，如果R的每个非主属性都不局部依赖于候选码，那么称R是第二范式的关系模式，记为R∈2NF。如果一个数据库的所有关系都是第二范式的关系，那么，这个数据库就称为第二范式的数据库。在表4.7所示的两个关系中，在商品关系表(表4.7(a))中，由于其候选码是单属性(商品代码)，因此，不存在非主属性对主属性的局部依赖问题。所以，该关系模式是第二范式的关系模式。同样，在进货关系表(表4.7(b))中，只有非主属性——库存量，它是完全依赖于候选码(商品代码，进货批次)的，因此，进货表也是第二范式的关系模式。这样，由这两个关系组成的数据库就是第二范式的数据库。从以上的分析可得出，第二范式的关系模式消除了由于非主属性对候选码的部分依赖造成的数据冗余和数据的插入、删除和修改异常。但如何才能得到第二范式关系呢？4.4.2分解算法算法4.4

保持无损连接和函数依赖的第二范式关系模式集的分集。输入：R(P，F)，其中P = {A1A2…An}是R的属性集，F是P上成立的函数依赖集。输出：R(P，F)的一个分解ρ = {R1(P1，F1)，R2(P2，F2)，…，Rn(Pn，Fn)}，其中每个关系模式Ri

(Pi，Fi)均为第二范式的关系模式。分解过程如下：

Step1.求R的候选码，记为K。

Step2.针对R中的每个主属性(设为A)，求，并设结果集为ρ = {}。

Step3.对F中的每个函数依赖FDi：X→Y，做如下操作：如果X属于某个主属性A的闭包，那么，生成关系Ri((XY)，(X→Y))，Ri的候选码为X，并检查ρ中的关系，如果存在某个关系(设为Rj)的候选码是X，那么将作为非主属性加入到Rj中；如果不存在这个关系Rj，那么，ρ = ρ∪Ri。

Step4.删除R中与ρ中所有关系的非主属性相同的非主属性，并将ρ = ρ∪R。

Step3.输出满足第二范式的分解ρ。下面用实例来说明算法4.4计算过程。例4.8已知关系模式R(P，F)，P = (ABCDE)，F = {A→BC，B→E，A→C}，试将R(P，F)分解成满足第二范式的关系模式集。计算过程如下：

Step1.求关系R(P，F)的候选码K = (AD)。

Step2. R的主属性的闭包：= (ABCE)，

= (D)ρ = {}。针对函数依赖A→BC，因为A⊂，故产生关系R1((ABC)，(A→BC))，其主码是(A)。这样，ρ = {R1}。针对函数依赖A→C，因为A⊂，故产生关系R2((AC)，(A→C))，其主码是(A)。因为ρ中R1的主码也是(A)，将R1和R2合并为新的R1((ABC)，(A→BC，A→C))，其主码为{A}。针对函数依赖B→E，而A→B，故有A→E。因为A⊂，故产生关系R3((AE)，(A→E))，其主码是(A)。因为ρ中R1的主码也是A，将R1和R3合并为新的R1((ABCE)，(A→BC，A→C，B→E))，其主码为{A}。

Step3.检查R中的非主属性，发现BCE也是R1的非主属性。因此，需要将BCE从R中删除，这样，R(AD)。

Step4.这样，求得R(P，F)满足第二范式的分解ρ = {R1((ABCE)，(A→BC，A→C，B→E))，R2(AD)}。很容易利用判断无损连接算法和保持函数依赖的定义来证明算法4.4得到的关系模式集满足无损连接和保持函数依赖。这里，不再详细描述证明过程了。4.5第三范式4.5.1定义在2NF的关系模式中，不存在非主属性对候选码的部分依赖，在一定程序上消除了数据冗余和数据的插入、删除、修改可能产生的异常。但满足2NF的关系模式仍然还存在一些问题。在表4.7(a)所示的商品关系表中，此关系只有一个主属性，因此肯定是2NF的。但仔细分析后会发现该关系仍存在数据冗余及数据的插入、删除和修改异常。

(1)数据冗余。例如有两种商品产自“上海光明乳业集团”，因此，该生产厂家的信息重复存了两遍。如果某生产厂家供应N种商品，那么该生产厂家的信息就要重复存N次，这会造成大量数据冗余。

(2)插入异常。如果有新的生产厂家的信息需要存在放到该关系中，但该生产厂家还未供应任何商品，因为(商品代码)是主码，因此无法插入。

(3)修改异常。如果某个生产厂家的信息发生变化了，必须修改该厂家所有商品对应的元组，否则就造成数据的不一致。

(4)删除异常。正如前面提到的，如果要删除商品代码为“20015”的商品，要么将该商品对应的整条元组删除，要么将商品代码和商品名称设为空值。但在多数情况下，需要保留厂家信息供以后使用，这表明删除整条元组是不适合的。如果将商品代码和商品名称设为空值，由于商品代码是该关系的主属性，如果设为空，就造成了删除异常。分析表4.7(b)中所示的进货关系，发现该关系无数据冗余，也不会发生数据的插入、删除和修改异常。那么，为什么在商品关系中存在数据冗余及异常产生，而在进货关系中却没有呢？要回答这个问题，需要考察这两个关系模式中存在的函数依赖。在进货关系(商品代码，进货批次，库存量)中，非主属性只有库存量，它直接依赖于主码(商品代码，进货批次)。也就是说，库存量只取决于商品代码和进货批次。因此，该关系中无数据冗余，也不会产生插入、修改、删除异常。再看看表4.7(a)商品关系(商品代码，商品名称，生产厂家名称，生产厂家所在城市)，该关系的主码是(商品代码)，因此，其他非主属性都依赖于(商品代码)，即(商品代码)→(商品名称，生产厂家名称，厂家所在城市)。但非主属性对主码的依赖之外，在非主属性之间还存在函数依赖：(生产厂家名称→生产厂家所在城市)。这样，(生产厂家所在城市)就传递依赖于主码(商品代码)。正是由于这个非主属性对候选码(主码)的传递依赖导致了数据冗余和异常的产生。要消除传递依赖带来的数据冗余以及数据插入、数据修改和数据删除异常，必须使关系满足第三范式(3NF)。定义4.15

设R是一个1NF的关系模式，K是R的候选码，A是R的一个非主属性，如果所有A都不传递依赖于K，那R就是第三范式(3NF)的关系模式。如果一个数据库里的所有关系模式都是3NF的，那么该数据库也是3NF的。定义4.15表明，在3NF的关系模式中，消除了非主属性对候选码的传递依赖，而定义4.14告诉2NF的关系模式消除了非主属性对候选码的局部依赖。那么3NF的关系模式与2NF的关系模式究竟存在什么关系呢？定理4.8

如果关系模式R是3NF的，那么它一定是2NF的。证明：可采用反证法。设关系R是3NF，但不是2NF的。由于R不是2NF的，因此必存在某个非主属性(设为A)局部依赖于候选码K，即存在K '⊂K，使得K '→A成立。因为K '⊂K，所以K→K '，这样A就传递依赖于K，从而得出R不是3NF的。因此，与题设相矛盾。在实际应用中，一般将关系变换成3NF或更高级别的范式，这个过程称为“模式的规范化”。局部依赖和传递依赖是造成数据冗余和数据操纵异常的两个重要原因。模式的规范化的目标就是要尽可能地消除这些函数依赖。前面的例子表明，由于1NF、2NF关系模式自身的弱点，一般不宜做数据库模式。4.5.2分解算法

3NF的关系模式消除了非主属性对候选码的传递依赖，在一定程度减小了关系中数据冗余和降低异常的产生。那么，如何将一个泛关系分解成满足3NF的关系集，并且保持函数依赖性和具有无损连接性？算法4.5

将关系模式在保持函数依赖且无损连接的情况下分解成3NF关系模式集。输入：R(P，F)，其中P = {A1A2…An}是R的属性集，F是P上成立的函数依赖集。输出：R(P，F)的一个分解ρ = {R1(P1，F1)，R2(P2，F2)，…，Rn(Pn，Fn)}，其中每个关系模式Ri(Pi，Fi)均为3NF的关系模式，且ρ保持函数依赖性和具有无损连接性。计算过程如下：

Step1.求R的候选码，并设结果集ρ = ()。

Step2.对于F中的每个函数依赖X→Y，如果ρ中每个模式都不包含XY，那么将XY组成一个关系模式，并加入ρ，即ρ = ρ∪(XY)。

Step3.如果ρ中的所有关系均不包含的一个候选码，那么，将R的一个候选码作为一个关系加入到ρ中。

Step4.返回结果集ρ。从算法描述中可知，对于FD集中的每个函数依赖均生成了一个关系，因此，很明显该分解能保持函数依赖，并且每个关系都是3NF的。第4步保证了候选码在关系中存在。利用算法4.3很容易验证该分解具有无损连接性。

例4.9已知关系模式R(P，F)，P = (ABCDE)，F = (A→BC，B→E，D→C)，试将R(P，F)分解成满足第三范式的关系模式集。计算过程如下：

Step1.  R的候选码为(AD)，并设结果集=()。

Step2.对于FD：A→BC，组成关系R1 = {ABC}，由于R1不在ρ中，故ρ = {R1}；同理将R2 = (BE)，R3 = (DC)加入ρ，即ρ = {R1，R2，R3}。

Step3.由于ρ中任何一个关系模式都不包含候选码(AD)，故将(AD)作为一个关系

R4 = {AD}并加入到ρ中。

Step4.返回ρ = {(ABC)，(BE)，(CD)，(AD)}。我们讲过，第三范式的关系模式消除了非主属性对候选码的传递依赖，并未讲它消除了主属性对候选码的传递依赖，这就意味着有时即使达到3NF的关系模式，仍然会造成数据冗余和异常产生。4.6BC范式4.6.1BC范式的定义

3NF消除了非主属性对候选码的传递依赖，并没有考虑主属性对候选码的传递依赖。那么，如果关系模式符合3NF，但却存在主属性对候选码的传递依赖，又会产生什么问题呢？下面仍然通过一个例子来说明。例4.10设有关系模式R((ABC)，(A→B，BC→A))，不难求得R的候选码为(BC)或(AC)。这样，关系模式R的所有属性都是主属性，表明R是3NF的关系模式。表4.8给出R的一个关系r，可以看出关系r中仍存在大量的数据冗余，从而会造成数据插入、数据修改和数据删除异常。造成这一问题的根源是主属性(如B)传递依赖于候选码(BC)。如果将R分解成R1((AB)，(A→B))和R2(AC)，那么可以大大减少数据冗余和异常的产生。但同时也带来了一新问题，分解丢失了函数依赖BC→A，这个问题将在下一节讨论。上述R1((AB)，(A→B))和R2(BC)相较R((ABC)，(A→B，BC→A))来说性能较好，是因为它们消除了所有属性对候选码的传递依赖，即满足BC范式(BCNF)。表4.8满足3NF但不满足BC范式的关系定义4.16

给定一个1NF的关系模式R，对于R中的所有非平凡函数依赖X→Y，X中一定含有候选码，那么称R是BCNF的关系模式。定义4.16表明BCNF关系模式中，所有非主属性都完全函数依赖于候选码(2NF)，所有主属性完全函数依赖于不包含它的候选码，没有属性完全函数依赖于除候选码之外的属性集(3NF)。因此，BCNF关系模式一定是满足3NF的关系模式。还可以这么说：若一个关系达到了第三范式，并且它只有一个候选码，或者它的每个候选码都是单属性的，则该关系一定满足BCNF。4.6.2分解算法算法4.6

把某关系模式无损连接地分解成BCNF关系模式集。输入：R(P，F)，其中P = {A1A2…Am}是的属性集，F是P上成立的函数依赖集。输出：R(P，F)的一个分解ρ = {R1(P1，F1)，R2(P2，F2)，…，Rn(Pm，Fm)}，其中每个关系模式Ri(Pi，Fi)均为BCNF的关系模式，ρ具无损连接性。计算过程如下：

Step1. ρ = {R}。

Step2.求R的所有候选码。

Step3.针对ρ中的关系模式，做下列循环：(i)若ρ中有某个关系模式Rk(Pk，Fk)不是BCNF的关系模式，那么必能在Rk中找到一个非平凡函数依赖X→Y，且X中不包含Rk的任何候选码，将Rk分解成两个关系Rk((Pk

－ Y)，(Fk

－ (X→Y)))和Rmax+1((XY)，(X→Y))，用Rk和Rmax+1代替Rk，并求Rmax+1的候选码。(ii)若ρ中所有关系模式都是BCNF的，那么停止循环；回到Step3。

Step4.返回ρ。算法4.6的关键步骤是Rk((Pk

－ Y)，(Fk

－ (X→Y)))和Rmax+1(XY，X→Y)，其中Rmax+1表示当前ρ中关系模式的个数加1。利用定理4.7很容易判断该分解是无损连接分解。因此，利用算法4.6分解成的BCNF具有无损连接性。算法4.6不一定能保证分解保持函数依赖。利用算法4.6将例4.10中的关系模式R((ABC)，(A→B，BC→A))分解成BCNF的关系模式集：R1((AB)，(A→B))和R2(AC)，R1和R2中的函数依赖只有(A→B)，丢失了(BC→A)。例4.11设关系模式R(P，F)，P = (ABCDEG)，F = (D→G，CD→E，C→A，A→B)，试将R无损连接地分解成BCNF关系模式集。计算过程如下：

Step1.  R1 = R，ρ = {R1}。

Step2.  R1的候选码为{CD}。

Step 3.在R1中针对FD：D→G得到部分函数依赖候选码{CD}，故将R1分解为R1(ABCDE)和R2(DG)，这时R2已为BCNF，ρ = {R1，R2}；同理，可将R1分解为R1(BCDE)和R3(AC)，分析可知此时R1的候选码{BCD}满足BCNF，R3也满足BCNF。因此，ρ = {R1,R2,R3}。

Step4.返回ρ。从上例的返回可以看出，分解后的关系模式不保持函数依赖(丢失了A→B)。另外，分解后的关系模式集的组成与分解过程中利用函数依赖的顺序有关。4.7第四范式无论是2NF、3NF还是BCNF，都是依据函数依赖对关系模式进行分解的，这些分解消除了由于属性对不包含它的候选码的函数依赖而造成性能不足。现在来考察多值依赖对关系模式的影响。4.7.1多值依赖定义4.17

设关系模式R的属性集为P，X、Y和Z是P的子集，且Z = P - X - Y。如果在R的任一关系r中，给定一对X、Z的取值，都有一组Y值与之对应，并且这组Y值仅取决于值而与值无关，那么称在上存在Y对X多值依赖(MVD)，记为X→→Y。如果X→→Y且Y⊆X或Z = ，那么称X→→Y为平凡的多值依赖。多值依赖定义表明，X与Y是多对一的关联，X与Z也是多对一的关联，但Y和Z之间不直接关联。例4.12

在连锁超市经营管理中，如果规定每个加盟门店可进多种商品、有多名营业员，每个营业员可销售门店内的所有商品。这样，在加盟门店和商品之间是一对多的关联、加盟门店和营业员之间也是一对多的关联，而营业员与商品之间无直接关联(每个营业员跟每个商品都相关)，表明加盟门店与商品、加盟门店与营业员之间存在多值依赖。门店、商品、营业员之间的关系可用表4.9来表示。表4.9存在多值依赖的关系分析表4.9所示的关系发现，该关系的主码(营业员，商品)由所有属性组成(称为复合码)，因而符合BCNF。但通过观察关系中的元组，可以发现这个关系存在很多不足。如果某个加盟门店(如A门店)增加一个营业员，必须插入多个(表中为4个)元组：(A门店，张A，商品M1)、(A门店，张A，商品M2)、(A门店，张A，商品M3)和(A门店，张A，商品M4)，可见有很大的数据冗余；如果要删除某个门店(如A门店)的某个营业员(李B)，也要同时删除多个元组(表中为4个)。造成上述数据冗余及删除麻烦的原因就是因为加盟门店与商品、加盟门店与营业员之间存在多值依赖。如果要克服这些不足，需要对存在多值依赖的关系进行分解，即使关系达到第四范式(4NF)。在讨论什么是4NF之前，先来了解