CH5 关系数据理论及求精 - 副本

第5章关系数据理论及求精数据库系统原理与设计

(第2版)志存高远，

脚踏实地，

勇于探索！目录范式

5.4问题提出

5.1函数依赖定义5.2函数依赖理论5.3数据库模式求精

模式分解算法5.65.5本章要解决的两个问题如何判断一个数据库模式是“好”的模式如何设计出一个“好”模式？数据冗余导致的问题数据冗余是指同一信息在数据库中存储了多个副本。它可能引起下列问题：冗余存储：信息被重复存储，导致浪费大量存储空间。更新异常：当重复信息的一个副本被修改，所有副本都必须进行同样的修改。因此当更新数据时，系统要付出很大的代价来维护数据库的完整性，否则会面临数据不一致的危险。插入异常：只有当一些信息事先已经存放在数据库中时，另外一些信息才能存入数据库中。删除异常：删除某些信息时可能丢失其它信息。数据冗余关系举例[例5.1]

考虑学生选课关系模式：SCE(studentNo,studentName,courseNo,courseName,score),属性集{studentNo,courseNo}是唯一候选码，也是主码。如果允许一个学生选修多门课程，且一门课程可被多个学生选修，则该关系实例可能出现：冗余存储：学生姓名和课程名被重复存储多次；更新异常：当修改某学生的姓名或某课程的课程名时，可能只修改了部分副本的信息，而其他副本未被修改到；插入异常：如果某学生没有选修课程，或某门课程未被任何学生选修时，则该学生或该课程信息不能存入数据库，因为主码值不能为空；删除异常：当一学生的所有选修课程信息都被删除时，则该学生的信息将被丢失。对课程也是如此。数据冗余关系举例studentNoStudentNamecourseNocourseNamescoreS0700001李小勇C001高等数学98S0700001李小勇C002离散数学82S0700001李小勇C006数据库系统原理56S0700002刘方晨C003计算机原理69S0700002刘方晨C004C语言程序设计87S0700002刘方晨C005数据结构77S0700002刘方晨C007操作系统90S0700003王红敏C001高等数学46S0700003王红敏C002离散数学38S0700003王红敏C007操作系统50图5-1学生选课关系SCE实例冗余问题？数据冗余产生原因及解决方法SCE产生问题的原因：部分函数依赖该模式中某些属性之间存在如下函数依赖关系

studentNo→studentName（即学号决定姓名）courseNo→courseName（即课程编号决定课程名称）{studentNo,courseNo}→score即studentName、courseName部分依赖于关系的主码解决方法：关系模式分解分解为三个关系模式

S(studentNo,studentName)C(courseNo,courseName)E(studentNo,courseNo,score)关系模式的设计问题-另解示例 考虑为管理职工的工资信息而设计一个关系模式有没有问题？关系模式的设计问题问题：信息的不可表示问题(inabilitytorepresentcertaininformation)插入异常：如果没有职工具有8级工资，则8级工资的工资数额就难以插入删除异常：如果仅有职工赵明具有4级工资，如果将赵明删除，则有关4级工资的工资数额信息也随之删除了信息的冗余问题(repetitionofinformation)数据冗余：职工很多，工资级别有限，每一级别的工资数额反复存储多次更新异常：如果将5级工资的工资数额调为2620，则需要找到每个具有5级工资的职工，逐一修改关系模式的设计问题解决之道：分解,分解,再分解!级别工资425005260062700关系模式的设计问题有关学生的关系模式S(S#,SN,SD,DEAN,C#,G)它存在优点和哪些不足？原因：不良的数据依赖函数依赖的问题

模式分解导致的问题

将一个关系模式分解为较小关系模式集可解决冗余问题。但由此可能产生两个新的问题：什么样的关系模式需要进一步分解为较小的关系模式集？根据范式要求决定（后面讨论）是否所有的模式分解都是有益的？实例

模式分解问题举例[例5.2]

设一关系模式STU(studentNo,studentName,sex,birthday,native,classNo),其中，studentNo为主码。假设将STU分解为以下两个子模式：STU1(studentNo,studentName)STU2(studentName,sex,birthday,native,classNo)分解后会发生什么问题？

模式分解问题举例studentNostudnetNamesexbirthdaynativeclassNoS0700005王红男1992-4-26江西省南昌市CS0702S0800005王红女1995-8-10湖北省武汉市CP0802studentNostudnetNameS0700005王红S0800005王红studnetNamesexbirthdaynativeclassNo王红男1992-4-26江西省南昌市CS0702王红女1995-8-10湖北省武汉市CP0802studentNostudnetNameSexbirthdaynativeclassNoS0700005王红男1992-4-26江西省南昌市CS0702S0700005王红女1995-8-10湖北省武汉市CP0802S0800005王红男1992-4-26江西省南昌市CS0702S0800005王红女1995-8-10湖北省武汉市CP0802图5-2有损分解举例

模式分解问题举例模式分解存在的问题有损分解：两个分解后的关系通过连接运算还原得到的信息与原来关系的信息不一致。如果能够通过连接分解后所得到的较小关系完全还原被分解关系的所有实例，称之为无损分解(losslessdecomposition)，也称该分解具有无损连接特性。丢失依赖关系sex、birthday、age、native、classNo等与属性studentNo依赖关系也就不再存在。如果被分解关系模式上的所有依赖关系都在分解得到的关系模式上保留，称该分解为依赖保持

(dependencypreserving)分解。小结一个“好”的关系模式应该是：数据冗余应尽可能少不发生插入异常、删除异常、更新异常等问题。模式分解时，分解后的模式应具有无损连接、保持依赖等特性。目录范式

5.4问题提出

5.1函数依赖定义

5.2函数依赖理论5.3数据库模式求精

模式分解算法5.65.5函数依赖定义

函数依赖(functionaldependency,简称FD)是一种完整性约束,是现实世界事物属性之间的一种制约关系，它广泛地存在于现实世界之中。定义5.1

设r(R)为关系模式，R，R。对任意合法关系r及其中任两个元组ti和tj，ij，若ti[]=tj[]，则ti[]=tj[]，则称函数确定，

或函数依赖于，记作。图5-3函数依赖图函数依赖举例[例5.3]

图5-4所示的是满足函数依赖ABC的关系模式r(A,B,C,D)的一个关系实例。对于任意两个在属性集{A,B}上取值相同的元组，它们在属性C上的取值也相同。ABCDa1b1c1d1a1b1c1d2a1b2c1d1a2b1c3d1图5-4满足函数依赖ABC的一个关系实例如果在图中再增加一个元组(a1,b1,c2,

d1)，ABC

还成立吗？20函数依赖检验：A→C？C→A？AB→D？辨识（说明之一）满足依赖的关系：依赖在模式的某个关系实例上成立模式上成立的依赖：依赖在模式的所有关系实例上都成立ABCDa1b1c1d1a1b2c1d2a2b2c2d2a2b3c2d3a3b3c2d4函数依赖说明对于函数依赖，需做如下说明：函数依赖不是指关系模式r(R)的某个或某些关系实例满足的约束条件，而是指关系模式r(R)的所有关系实例均要满足的约束条件。函数依赖是语义范畴的概念，只能根据数据的语义来确定函数依赖，是不能够被证明的。数据库设计者可以对现实世界作强制的规定。码约束是函数依赖的一个特例。码属性(集)相当于定义5.1中的，关系中的所有属性相当于定义5.1中的。平凡与非平凡函数依赖

定义5.2

在关系模式r(R)中，R，R。若，但，则称是非平凡函数依赖。否则，若,则称是平凡函数依赖。对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义。(a)非平凡函数依赖(b)平凡函数依赖图5-5非平凡及平凡函数依赖图完全函数依赖和部分函数依赖

定义5.3

在关系模式r(R)中，R，R，且。若对任意的，都不成立，则称是完全函数依赖，简称完全依赖。否则，若存在非空的，且成立,则称是部分函数依赖，简称部分依赖。图5-6部分依赖的依赖图完全函数依赖和部分函数依赖举例当是单属性时，则完全函数依赖总是成立的。例如，在关系SCE中完全依赖：studentNo

studentNamecourseNo

courseName{studentNo,courseNo}score部分依赖：{studentNo,courseNo}studentName{studentNo,courseNo}courseName部分函数依赖会导致数据冗余和插入、删除、更新异常！传递函数依赖定义5.4

在关系模式r(R)中，R，R，R，且,。若，，则必存在函数依赖，并称是传递函数依赖，简称传递依赖。注意条件：和。与部分依赖一样，传递依赖也可能会导致数据冗余及产生各种异常。图5-7传递依赖的依赖图传递函数依赖举例[例5.4]

在关系模式SCI(studentNo,classNo,className,institute)中，属性studentNo决定属性classNo，属性classNo决定className和institute。因此，关系模式SCI中存在下列传递函数依赖：studentNo

classNoclassNo

classNameclassNo

institutestudentNo

classNamestudentNo

instituteSCI中存在传递依赖studentNoclassName、institute，因此可能导致数据冗余、更新异常、插入异常及删除异常。函数依赖小结函数依赖是指关系模式中属性之间存在的一种约束关系。这种约束关系既可以是现实世界事物或联系的属性之间客观存在的约束，也可以是数据库设计者根据应用需求或设计需要强加给数据的一种约束。但不论是那种约束，一旦确定，进入数据库中的所有数据都必须严格遵守。正确了解数据的意义及确定属性之间的函数依赖关系，对设计一个好的关系模式是十分重要的。平凡/不平凡，完全/非完全，传递函数依赖目录范式

5.4问题提出

5.1函数依赖定义5.2函数依赖理论5.3数据库模式求精

模式分解算法5.65.5函数依赖集闭包

对于给定关系模式r(R)及其函数依赖集F，有时只考虑给定的函数依赖集是不够的，而需要考虑在r(R)上总是成立的所有函数依赖。[例5.5]

给定关系模式r(R)=r(A,B,C)及函数依赖集F={AB,BC}，证明AC成立。

证明：假设对于关系实例r中的任意两个元组ti,tj,ij，满足ti[A]=tj[A]。由于存在AB，则可推出ti[B]=tj[B]。又由于BC，则又可推出ti[C]=tj[C]。因此，ti[A]=tj[A]

ti[C]=tj[C]。按定义5.1有AC。证毕。函数依赖集闭包定义5.5

若给定函数依赖集F，可以证明其他函数依赖也成立，则称这些函数依赖被F逻辑蕴涵。定义5.6

令F为一函数依赖集，F逻辑蕴涵的所有函数依赖组成的集合称为F的闭包，记为F+。函数依赖集F的闭包计算方法Armstrong公理的推理规则32逻辑蕴涵定义F+?示例R(X,Y),F={XY}F+={X，XX，XY，XXY， Y，YY

XY，XYX，XYY，XYXY}Armstrong公理及推论Armstrong公理

自反律(reflexivityrule)：若存在，则有增补律(augmentationrule)：若存在，则有传递律(transitivityrule)：若存在且，则有Armstrong公理三个推论合并律(unionrule)：若有且，则有分解律(decompositionrule)：若有，则有和伪传递律(pseudotransitivityrule)：若有且，则有34Armstrong公理系统Armstrong公理

X，Y，Z是属性集，自反律(reflexivity)：若YX，则XY增广律(augmentation)：若XY，则XZYZ传递律(transitivity)：若XY，YZ，则XZ35Armstrong公理系统关于Armstrong公理正确性按函数依赖定义r是R<U,F>上的任一关系，t，sr}t[X]=s[X]YXt[Y]=s[Y]XY自反律36Armstrong公理系统t[XZ]=s[XZ]t[X]=s[X]XY}t[Y]=s[Y]t[XZ]=s[XZ]t[Z]=s[Z]}t[YZ]=s[YZ]XZYZ增广律37Armstrong公理系统}XYt[X]=s[X]t[Y]=s[Y]}YZt[Z]=s[Z]XZ传递律38Armstrong公理系统由Armstrong公理导出的推理规则合并律(unionrule)若XY，XZ，则XYZ分解律(decompositionrule)若XY’，Y’=YZ且则XY，XZ伪传递律(pseudotransitivityrule)若XY，WYZ，则WXZ39Armstrong公理系统}XY增广律}XXY合并律}XZ增广律XYYZ传递律XYZ40Armstrong公理系统}ZY’自反律Y’=YZ}Y’Z分解律XY’传递律XZ41Armstrong公理系统}XY增广律}WXWYWYZ传递律WXZ伪传递律42Armstrong公理系统示例

R<U,F>,U=(A,B,C,G,H,I),F={AB,AC,CGH,CGI,BH},AH？CGHI？AGI？函数依赖集闭包计算举例[例5.6]

令r(R)=r(A,B,C,G,H,I)，函数依赖集F={AB,AC,CGH,CGI,BH}。我们可列出F+中的几个依赖：由传递律可得AH，因为AB且BH；由合并律可得CGHI，因为CGH，CGI；由伪传递律可得AGI，因为AC且CGI。还可以使用上述规则推导出更多的函数依赖，读者可自行推导。属性集闭包如果想要判断一个给定的函数依赖是否在函数依赖集F的闭包中，不用计算F+就可以判断出来。定义5.7

令r(R)为关系模式，F为函数依赖集，AR，则称在函数依赖集F下由A函数确定的所有属性的集合为函数依赖集F下属性集A的闭包，记为A+。属性集闭包的计算算法：

closure:=A;repeatuntil(closure没有变化)do

foreach

inFdo

if

closureclosure:=closure

图5-8计算F下A+算法

属性集闭包计算举例[例5.7]

r(R)=r(A,B,C,G,H,I)，F={AB,AC,CGH,CGI,BH}，计算(AG)+。

算法第一次循环的执行步骤：

步骤

FD

closure

1．初值AG2．

ABABG3．ACABCG4．CGHABCGH5．CGIABCGHI6．BHABCGHI算法第二次循环的结果仍为closure=ABCGHI，没有变化，算法终止。

结果为：closure=ABCGHI。

最后结果为：(AG)+＝ABCGHI。46闭包的计算示例3

R<U,F>,U=(A,B,C,D,E,G),F={AE,BEAG,CEA,GD},计算

所用依赖

AE ABE

BEAG ABEG GD ABEGD =ABEGD计算属性集闭包的作用计算属性集闭包的作用可归纳如下：验证是否在F+中：看是否有

+。判断是否为r(R)的超码：计算

+，看其是否包含R的所有属性。如(AG)+＝ABCGHI，则AG为r(R)的超码。判断是否为r(R)的候选码：若是超码，可检验包含的所有子集的闭包是否包含R的所有属性。若不存在任何这样的属性子集，则是r(R)的候选码。计算F+。对于任意R，可通过找出+，对任意的S

+，可输出一个S。判断属性集是否为候选码举例[例5.8]

r(R)和F见例5.7，判断AG是否为r(R)的候选码。例5.7已计算出(AG)+＝ABCGHI,则还要进一步分别计算A+和G+。经计算得，A+=ABCH、G+=G，它们都不包含R的所有属性。因此，AG为r(R)的候选码。

对于一个给定的关系模式r(R)及函数依赖集F，如何找出它的所有候选码？这是基于函数依赖理论和范式概念判断该关系模式是否是“好”模式的基础；也是对一个“不好”的关系模式进行分解的基础。

判断属性集是否为候选码给定关系模式r(R)及函数依赖集F，找出它的所有候选码的一般步骤如下：

找出函数依赖集F中在所有函数依赖右方都没有出现的属性集X，属性集X中的属性都一定是候选码中的属性。找出F中在所有函数依赖右方出现但左方没有出现的属性集Y，属性集Y中的属性都不可能是候选码中的属性。如果X非空，则基于F计算X+，并开始发现所有候选码：如果X+=R，则X是关系r(R)的唯一候选码；如果X+≠R，则如果X为空，则从F中的每一个函数依赖u开始(先从函数依赖左边是一个属性的开始)：首先，试着发现是否能够通过增加1个属性与X联合起来构成候选码,例如，若存在R-X-Y，使(X{})+=R，则(X{})是关系r(R)的一个候选码；继续试着增加另一个属性，若存在R-X-Y-{}，使(X{})+=R，则(X{})是关系r(R)的另一个候选码；……。记找到的所有属性的集合为Z，即Z，使(X{})+=R。接下来，还可以试着发现是否能够通过增加2个或多个属性与X联合起来构成候选码，例如,若存在{,}R-X-Y-Z，使(X{,})+=R;则(X{,})也是关系r(R)的一个候选码；……。如果+=R，则是关系r(R)的一个候选码；如果+≠R，类似地，试着发现是否能够通过增加1个属性与联合起来构成候选码；再试着发现是否能够通过增加2个或多个属性与联合起来构成候选码。判断属性集是否为候选码举例[例5.9]

给定关系模式r(R)=r(A,B,C,D)，函数依赖集F={BC,DA}，找出r(R)的所有候选码。属性集BD没有在函数依赖的右部出现，故BD为候选码的一部分；由于(BD)+=BDCA=R，所以BD为关系模式r(R)的唯一候选码。判断属性集是否为候选码举例[例5.10]

给定关系模式r(R)=r(A,B,C,D,E)，函数依赖集F={AB,BCE,EDA}，找出r(R)的所有候选码。属性集CD没有在函数依赖的右部出现，故X=CD为候选码的一部分；因(CD)+=CD≠R，故CD不是候选码；因没有在函数依赖右部出现但左部不出现的属性，故Y=;在集合R-X-Y=ABE中寻找与X联合构成候选码的属性(集)：({A,CD})+=ACDBE=R，故ACD为候选码；({B,CD})+=BCDEA=R，故BCD为候选码；({E,CD})+=ACDBE=R，故ECD为候选码。因此，关系模式r(R)的候选码有ACD、BCD和ECD。判断属性集是否为候选码举例[例5.11]设关系模式R={A,B,C,D,E,G}，函数依赖集F={B→ADE,A→BE,AC→G,BC→D}，找出r(R)的所有候选码。因C没有在函数依赖的右部出现，故X=C为候选码的一部分;因C+=C≠R，故C不是候选码；在函数依赖右部出现但左部不出现的属性有DEG,故Y=DEG;在R-X-Y=AB中寻找与X联合起来构成候选码的属性(集)：({A,C})+=ACBEGD=R，故AC为候选码；({B,C})+=BCADEG=R，故BC为候选码。因此，关系模式r(R)的候选码有AC和BC。

无关属性定义

定义5.8

给定函数依赖集F及→F，如果去除或中的某属性A之后不会改变F+，则称属性A是无关的。定义5.9

给定函数依赖集F及→F，若A，且F

逻辑蕴涵(F-{→}){(-A)}（即(-A)F+），则属性A在中是无关的（左无关）。定义5.10

给定函数依赖集F及→F，若A，且(F-{}){(-A)}逻辑蕴涵F

（即→

((F-{}){(-A)})+），则属性A在中是无关的（右无关）。无关属性检测算法设r(R)为关系模式，F是函数依赖集，则检测上的属性A左无关或右无关的算法分别如图5-9(a)或(b)所示。if

A:＝

-{A};计算F下的闭包+;

if

+A在中是无关的;if

AF':=(F-{}){((-A)};计算F'下的闭包+;

ifA+A在中是无关的;(a)左无关属性检测算法

(b)右无关属性检测算法

图5-9无关属性检测算法无关属性检测举例[例5.12]

设F＝{AB→CD,A→E,E→C}，证明C在

AB→CD中为无关属性。证明：

由于C是AB→CD中的右边属性，依图5-9(b)的算法：

计算F'：F'={AB→D,A→E,E→C}；计算F'下(AB)+：(AB)+=ABCDE；判断C是否属于(AB)+：CABCDE。因此，C是AB→CD中的无关属性。证毕。正则覆盖定义和计算方法定义5.11

正则覆盖(canonicalcover)Fc是一个依赖集，使得F逻辑蕴涵Fc中的所有依赖，Fc逻辑蕴涵F中的所有依赖，而且必须具有下列特性：Fc中的任何函数依赖都不包含无关属性；Fc中函数依赖的左半部都是唯一的，即Fc中不存在两个依赖1→1和2→2，且1＝2。根据上述性质，计算F的正则覆盖Fc分为两个步骤：合并函数依赖：将F中所有形如1→1、1→2的函数依赖合并为1→12，得到新函数依赖集F'。去除无关属性：对F'中的每个函数依赖，依次判断是否包含无关属性。若发现无关属性，则用去除无关属性后的函数依赖代替F'中的原函数依赖。计算正则覆盖举例[例5.13]

考虑关系模式r(R)=r(A,B,C)和函数依赖集F={A→BC,B→C,A→B,AB→C},计算F的正则覆盖Fc。第1步，合并函数依赖：将A→BC和A→B合并为A→BC。F'={A→BC,B→C,AB→C}。第2步，去除无关属性：对于AB→C，根据图5-9(a)的算法可检测A是无关的。因此，去除无关属性A后，AB→C变为B→C，而B→C已在F'中存在，则F'={B→C,A→BC}。对于B→C，由于其左右两边都为单属性，故不存在无关属性。对于A→BC，根据图5-9(b)的算法可检测C是无关的。因此，去除无关属性C后，A→BC变为A→B，则F'={B→C,A→B}。F'中的函数依赖左半部都是唯一的，且都不存在无关属性，因此Fc={B→C,A→B}。正则覆盖说明对于正则覆盖，需做如下说明：可以证明Fc与F具有相同的闭包；Fc不包含无关属性，每个依赖是最小的，且是必要的；正则覆盖不一定唯一。

60无损连接分解-模式分解中存在的问题R(A,B,C)ABC112221AB1122BC1221ABC112221∏AB(R)∏BC(R)∏AB(R)∏BC(R)R(A,B,C)ABC111212AB1121BC1112ABC111112211212∏AB(R)∏BC(R)∏AB(R)∏BC(R)有损分解无损分解无损连接分解

定义5.12

给定关系模式r(R)及函数依赖集F，若r(R)的任意一个满足函数依赖集F的关系实例r都有

=r，其中r1(R1)、r2(R2)分别为分解后的子模式，则称该分解对于F是无损连接的。无损连接分解能够根据分解后的关系通过连接还原原来的关系实例。如何判定一分解是否是无损的？62无损连接分解定义 关系模式R<U,F>，U=Ui， ={R1<U1,F1>,R2<U2,F2>,…,Rn<Un,Fn>}是R<U,F>的一个分解，r是R<U,F>的一个关系定义m(r)=∏Ri(r),若对于R<U,F>的任一个关系r，都有r=m(r)，则称是R<U,F>的一个无损连接分解。那么判别一个分解是无损分解呢？6364无损连接分解算法：（判别一个分解的无损连接性）

U={A1,A2,…,An} ={R1<U1,F1>,R2<U2,F2>,…,Rk<Uk,Fk>} ⒈建立一个n列k行的矩阵TB={Cij|若Aj

Ui,Cij=aj,否则Cij=bij}A1A2…AnU1…CijUk只是检测，不证明！65无损连接分解 ⒉对F中每一个函数依赖XY，若TB中存在元组 t1，t2，使得t1[X]=t2[X]，t1[Y]≠t2[Y]，则对每一个Ai

Y： ①若t1[Ai]，t2[Ai]中有一个等于aj，则另一个也改 为aj； ②若①不成立，则取t1[Ai]=t2[Ai]（t2的行号小 于t1）。 66无损连接分解 ⒊反复执行⒉，直至： ①TB中出现一行为a1,a2,…,

an的一行。 ②TB不再发生变化，且没有一行为a1,…,

an。

在①情况下，为无损分解，否则为有损分解。67无损连接分解示例一：U={A,B,C,D,E},F={ABC,CD,DE} ={(A,B,C),(C,D),(D,E)}ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5ABCABCDEABCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5CDABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b32b33a4a5DE68无损连接分解示例二：U={A,B,C,D,E}, F={AC,BC,CD,DEC,CEA} ={(A,D),(A,B),(B,E),(C,D,E),(A,E)}ABCDEADa1b12b13a4b15ABa1a2b23b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b53b54a5ACABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b33b34a5CDEb41b42a3a4a5AEa1b52b13b54a569无损连接分解BCABCDEADa1b12b13a4b15ABa1a2b13b24b25BEb31a2b13b34a5CDEb41b42a3a4a5AEa1b52b13b54a5CDABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2b13a4a5CDEb41b42a3a4a5AEa1b52b13a4a5示例二：U={A,B,C,D,E}, F={AC,BC,CD,DEC,CEA} ={(A,D),(A,B),(B,E),(C,D,E),(A,E)}70无损连接分解DECABCDEADa1b12b13a4b15ABa1a2b13a4b25BEb31a2a3a4a5CDEb41b42a3a4a5AEa1b52a3a4a5CEAABCDEADa1b12b13a4b15ABa1a2b13a4b25BEa1a2a3a4a5CDEa1b42a3a4a5AEa1b52a3a4a5示例二：U={A,B,C,D,E}, F={AC,BC,CD,DEC,CEA} ={(A,D),(A,B),(B,E),(C,D,E),(A,E)}71无损连接分解无损连接分解定义（分解为两个关系模式） 关系模式R(U)，U1，U2U，U1U2=U，r是R上的一个关系，r1=∏U1(r)，r2=∏U2(r)，若r=r1r2，则称(r1，

r2)是r的一个无损连接分解。 注：r∏U1(r)∏U2(r)R(A,B,C)ABC112221AB1122BC1221ABC112221∏AB(R)∏BC(R)∏AB(R)∏BC(R)72无损连接分解定理 关系模式R(U)的分解={R1，R2}，则是一个无损连接分解的充要条件是R1∩R2R1R2（或R1∩R2R2R1）成立R1∩R2R1R2R2R1R1a…aa…ab…bR2a…ab…ba…aR1∩R2R1R2R2R1R1a…aa…ab…bR2a…aa…aa…aR1∩R2R1R273无损连接分解－例题R=ABC,F={AB},1={R1(AB),R2(AC)}是否是无损连接分解？R1∩R2=A,R1－R2=B由AB，得到1是无损连接分解2={R1(AB),R2(BC)}是否是无损连接分解？R1∩R2=B,R1－R2=A,R2－R1=CBA,BC均不成立，所以2不是无损连接分解无损连接分解判断方法定义5.13

给定关系模式r(R)及函数依赖集F，则将r(R)分解成r1(R1)、r2(R2)的分解是无损连接分解，当且仅当F+包含函数依赖R1R2→R1或R1R2→R2.即：在F下，R1(R1R2)+或R2(R1R2)+。因此，当一个关系模式分解为两个关系模式时，该分解为无损连接分解的充要条件是两分解关系的公共属性包含r1(R1)的码或r2(R2)的码。即：R1R2是关系r1(R1)

或r2(R2)的超码。无损连接分解判断举例[例5.14]

假设关系模式r(R)=r(A,B,C,D,E),F={ABC,CDE,BD,EA}，则可将r(R)进行两种不同的分解:分解1：r1(R1)=r1(A,

B,

C)，r2(R2)=r2(A,D,E)；分解2：r1(R1)=r1(A,B,C)，r2(R2)=r2(C,D,E)。对于分解1，R1R2＝A，且AR1，故此分解是无损连接分解。而对于分解2，R1R2＝C，且C→R1、C→R2，故此分解不是无损连接分解。保持依赖分解

关系数据库模式分解的另一个目标是保持依赖。定义5.14

给定关系模式r(R)及函数依赖集F，r1(R1),r2(R2),...,rn(Rn)为r(R)的分解。F在Ri的投影为闭包F+中所有只包含Ri属性的函数依赖的集合，记为Fi。即如果在Fi中，则和的所有属性均在Ri中。定义5.15

称具有函数依赖集F的关系模式r(R)的分解r1(R1),r2(R2),...,rn(Rn)为保持依赖分解，当且仅当(F1F2…Fn)+=F+。保持依赖分解判断举例[例5.15]

设关系模式r(R)=r(A,B,C)，F={AB,BC}，有两种分解：r1(R1)=r1(A,

B)、r2(R2)

=r2(B,

C)F1={AB}、F2={BC}该分解保持函数依赖，因为(F1F2)+=F+。r1(R1)=r1(A,B)、r2(R2)

=r2(A,

C)。F1={AB}、F2={A→C}（注：{A→C}F+）该分解不保持函数依赖。因为分解后函数依赖BC被丢失。目录范式5.4问题提出

5.1函数依赖定义5.2函数依赖理论5.3数据库模式求精

模式分解算法5.65.5范式概述基于函数依赖理论，关系模式可分成第一范式(1NF)第二范式(2NF)第三范式(3NF)Boyce-Codd范式(BCNF)这几种范式的要求一个比一个严格，它们之间的联系为：

BCNF

3NF2NF1NF满足BCNF范式的关系一定满足3NF范式，满足3NF范式的关系一定满足2NF范式，满足2NF范式的关系一定满足1NF范式。第一范式(1NF)——码

定义5.16

如果一关系模式r(R)的每个属性对应的域值都是不可分的(即原子的)，则称r(R)属于第一范式，记为r(R)1NF.第一范式的目标是：将基本数据划分成称为实体集或表的逻辑单元，当设计好每个实体后，需要为其指定主码。studentNostudentNamesexbirthdayageaddressclassNoprovincecitystreet图5-10非规范化的关系模式studentNostudentNamesexbirthdayageprovincecitystreetclassNo图5-111NF规范化后的关系模式第二范式(2NF)——全部是码

定义5.17

设有一关系模式r(R)，R。若包含在r(R)的某个候选码中，则称为主属性，否则为非主属性。在SCE关系中，属性集{studentNo,courseNo}是SCE的唯一候选码。因此，属性studentNo和courseNo为主属性，其余属性为非主属性。定义5.18

如果一个关系模式r(R)1NF，且所有非主属性都完全函数依赖于r(R)的候选码，则称r(R)属于第二范式，记为r(R)2NF。SCE中存在依赖关系studentNostudentName和courseNocourseName，即非主属性studentName和courseName部分依赖于SCE的候选码{studentNo,courseNo}，故SCE2NF。第二范式(2NF)——全部是码

第二范式的目标：将只部分依赖于候选码（即依赖于候选码的部分属性）的非主属性移到其他表中。也就是说，在满足第一范式的实体中，如果有复合候选码(即多个属性共同构成的候选码)，那么所有非主属性必须依赖于全部的候选码，不允许依赖于部分的候选码属性。即不允许候选码的一部分对非主属性起决定作用：全部是码违背2NF的模式，即存在非主属性对候选码的部分依赖，则可能导致例5.1所述的数据冗余及异常问题。第二范式(2NF)——全部是码对于非2NF范式的关系模式，可通过分解进行规范化，以消除部分依赖。如将关系模式SCE分解为关系模式S、C和E。这样在每个关系模式中，所有非主属性对候选码都是完全函数依赖，因此都属于2NF范式。2NF范式虽然消除了由于非主属性对候选码的部分依赖所引起的冗余及各种异常，但并没有排除传递依赖。因此，还需要对其进一步规范化。第三范式(3NF)第三范式的目标：去掉表中不直接依赖于候选码的非主属性.定义5.19

如果一个关系模式r(R)2NF，且所有非主属性都直接函数依赖于r(R)的候选码（即不存在非主属性传递依赖于候选码），则称r(R)属于第三范式，记为r(R)3NF.也就是说，在满足2NF的实体中，非主属性不能依赖于另一个非主属性（即非主属性只能直接依赖于候选码）总之，所有的非主属性应该直接依赖于(即不能存在传递依赖，这是3NF的要求)全部的候选码(即必须完全依赖,不能存在部分依赖，这是2NF的要求)。第三范式(3NF)[例5.16]

r(R)=r(A,B,C,D)，函数依赖集F={AB→C,B→D}。r(R)的候选码为AB，r(R)2NF?。因为函数依赖B→D中的决定属性B只是候选码的一部分，即D部分依赖于候选码AB。可将r(R)分解为r1(R1)=r1(A,B,C)、r2(R2)=r2(B,D)。r1(R1)的候选码为AB，r2(R2)的候选码为B。分解得到的r1(R1)和r2(R2)都属于3NF范式。[例5.17]

r(R)=r(A,B,C)，函数依赖集F={A→B,B→C}。r(R)的候选码为A，r(R)2NF，但r(R)3NF。因为函数依赖B→C中的决定属性B不是候选码。可将r(R)分解为r1(R1)=r1(A,B)、r2(R2)=r2(B,C)。

r1(R1)的候选码为A，r2(R2)的候选码为B。则分解得到的r1(R1)和r2(R2)都属于3NF范式。第三范式(3NF)[例5.18]

r(R)=r(A,B,C,D,E)，函数依赖集F={AB→C,B→D,C→E}。r(R)的候选码为AB，r(R)2NF?。因为函数依赖B→D中的决定属性B只是候选码的一部分，即D部分依赖于候选码AB。

r(R)分解为r1(R1)=r1(A,B,C)、r2(R2)=r2(B,D)、r3(R3)=r3(C,E)r1(R1)的候选码为AB，r2(R2)的候选码为B，r3(R3)的候选码为C。它们都属于3NF范式。[例5.19]

r(R)=r(A,B,C)，函数依赖集F={AB→C,C→A}.r(R)的候选码为AB或BC，r(R)3NF。因为关系模式r(R)没有非主属性，也就不可能有非主属性对候选码的部分依赖和传递依赖。

87BCNF示例STC(S#,T#,C#)，语义：每位老师只教授一门课,每门课有若干教师,某一学生选定某门课,就对应一个固定的教师.T#C#，每位老师只教授一门课（S#，T#）C#（S#，C#）T#，某学生选定一门课，就对应一位老师（S#，T#），（S#，C#）为候选码。思考

STC3NF？S#T#C#s1t1c1s2t2c2s3t3c2s3t1c1是由Boyce和Codd提出的,比3NF又进了一步,通常认为是修正的第三范式.88S#C#T#S#T#C#C#对码的传递依赖C#对码的部分依赖89BCNF不良特性插入异常：如果没有学生选修某位老师的任课，则该老师担任课程的信息就无法插入删除异常：删除学生选课信息，会删除掉老师的任课信息更新异常：如果老师所教授的课程有所改动，则所有选修该老师课程的学生元组都要做改动数据冗余：每位学生都存储了有关老师所教授的课程的信息症由： 主属性对码的不良依赖S#T#C#s1t1c1s2t2c2s3t3c2s3t1c190BCNF定义关系模式R<U,F>中，对于属性组X，Y，若XY且YX时X必含有码，则R<U,F>BCNF

如STC？BCNFSTCBCNF，因为T#

C#，而T#不含有码改造前：STC(S#,T#,C#)，改造后 将S分解为（S#，T#），（T#，C#）S#T#s1t1s2t2s3t3s3t1T#C#t1c1t2c2t3c291Boyce-Codd范式(BCNF)定义5.20

给定关系模式r(R)及函数依赖集F，若F+中的所有函数依赖

(R，R)至少满足下列条件之一：是平凡函数依赖(即)；是r(R)的一个超码(即+包含R的全部属性)。即起决定作用的属性必须是超码！

则称r(R)属于Boyce-Codd范式，记为r(R)BCNF。换句话说，在关系模式r(R)中，如果F+中的每一个非平凡函数依赖的决定属性集都包含候选码，则r(R)BCNF。特别说明：为确定r(R)是否满足BCNF范式，必须考虑F+而不是F中的每个依赖。从函数依赖角度可得出，一个满足BCNF的关系模式必然满足下列结论：（如果

非平凡，则是r(R)的一个超码）所有非主属性都完全函数依赖于每个候选码；所有主属性都完全函数依赖于每个不包含它的候选码；没有任何属性完全函数依赖于非候选码的任何一组属性。BCNF范式排除了：任何属性(包括主属性和非主属性)对候选码的部分依赖和传递依赖；主属性之间的传递依赖。Boyce-Codd范式(BCNF)从函数依赖角度可得出，一个满足BCNF的关系模式必然满足下列结论：（如果

非平凡，则是r(R)的一个超码）所有非主属性都完全函数依赖于每个候选码；所有主属性都完全函数依赖于每个不包含它的候选码；没有任何属性完全函数依赖于非候选码的任何一组属性。BCNF范式排除了：任何属性(包括主属性和非主属性)对候选码的部分依赖和传递依赖；主属性之间的传递依赖。Boyce-Codd范式(BCNF)候选码A非主属性1非主属性2非主属性k……候选码BХХХBoyce-Codd范式判断举例[例5.20]

r(R)=r(A,B,C)，F={A→B,B→C}。r(R)的候选码为A，r(R)BCNF，因为函数依赖B→C中的决定属性B不是超码。[例5.21]

r(R)=r(A,B,C)，F={AB→C,C→A}。r(R)的候选码为AB或BC，r(R)BCNF，因为C→A的决定属性C不是超码。[例5.22]

r(R)=r(A,B,C)，F={AB→C,BC→A}。r(R)的候选码为AB或BC，r(R)BCNF，因为两个函数依赖中的决定属性AB或BC都是r(R)的候选码。Boyce-Codd范式存在问题对于非BCNF范式的关系模式，可通过分解进行规范化，以消除部分依赖和传递依赖。[例5.20]

(r(R)=r(A,B,C),F={A→B,B→C},候选码为A)可分解为r1(R1)=r1(A,B)、r2(R2)

=r2(B,C)

(F1={A→B}、F2={B→C}

)或r1(R1)=r1(A,B)、r2(R2)

=r2(A,C)

(F1={A→B}、F2={A→C}

)显然，这两种分解得到的r1(R1)和r2(R2)都属于BCNF范式。但是，后一种分解不是保持依赖分解。因此，满足BCNF范式的模式分解，可能不是保持依赖分解。第三范式(3NF)——仅仅是码定义5.21

给定关系模式r(R)及函数依赖集F，若对F+中的所有函数依赖→

(R,R)至少满足下列条件之一：→是平凡函数依赖(即)；是r(R)的一个超码(即+包含R的全部属性)；-中的每个属性是r(R)的候选码的一部分(即主属性)。则称r(R)属于第三范式，记为

r(R)3NF。3NF与BCNF范式的区别在于第3个条件：-中的每个属性是r(R)的候选码的一部分。放松之处：允许存在主属性对候选码的传递依赖和部分依赖。第三范式(3NF)——仅仅是码定义5.21

给定关系模式r(R)及函数依赖集F，若对F+中的所有函数依赖→

(R,R)至少满足下列条件之一：→是平凡函数依赖(即)；是r(R)的一个超码(即+包含R的全部属性)；-中的每个属性是r(R)的候选码的一部分(即主属性)。则称r(R)属于第三范式，记为

r(R)3NF。3NF与BCNF范式的区别在于第3个条件：-中的每个属性是r(R)的候选码的一部分。放松之处：允许存在主属性对候选码的传递依赖和部分依赖。候选码C候选码B候选码Aabc主属性的传递依赖主属性的部分依赖第三范式(3NF)——仅仅是码注意：如果-中的每个属性是r(R)的候选码的一部分，那么中也一定包含候选码的一部分，即不可能全是非主属性(即中一定包含主属性)。不妨假设∩

=，→是非平凡函数依赖，且不存在无关属性。如果是候选码，由于→，那么是超码(包含候选码)，因此中一定包含主属性。否则，设是候选码，有()+=R；由于→，那么()+=R，即是超码(包含候选码)

。由于是候选码，即不能单独构成候选码，因此中一定包含主属性。第三范式(3NF)——仅仅是码注意：3NF的第3个条件不要求-中的每个属性必须包含在r(R)的一个候选码中。因此当r(R)有多个候选码时，即-中的每个属性可以包含在r(R)的不同候选码中。总之，非主属性对候选码的部分依赖问题在2NF中解决了,而非主属性对候选码的传递依赖问题由3NF来解决！即不允许非主属性起决定使用——仅仅是码。[例5.23]

r(R)=r(A,B,C)，F={AB→C,C→A}。r(R)的候选码为AB或BC，由[例5.19]和[例5.21]可知，r(R)3NF,但r(R)BCNF。

3NF与BCNF比较BCNF比3NF严格。BCNF要求所有的非平凡函数依赖中的是超码，而3NF则放松了该约束，允许不是超码。若关系模式属于BCNF范式就一定属于3N