关系数据库理论-第五章关系数据库理论.ppt

《关系数据库理论-第五章关系数据库理论.ppt》由会员分享，可在线阅读，更多相关《关系数据库理论-第五章关系数据库理论.ppt（137页珍藏版）》请在三一办公上搜索。

1、第五章 关系数据库理论（6学时）,主讲：曹志英 副教授大连海事大学计算机科学与技术学院研究方向：软件工程与理论数据库与信息系统电话：84729625Email：,数据库原理和语言,学习要点,（1）函数依赖及Armstrong公理系统；（2）为什么要对模式进行分解，如何分解？（3）如何判断关系模式达到几范式？（4）如何求属性的闭包及如何求最小函数依赖集？,通过本章的学习，应该重点掌握：,章节目录,5.1 问题的提出5.2 规范化（Normalization）5.3 数据依赖的公理系统,5.1 问题的提出,5.1.1 规范化问题的提出在现实世界中，进行数据处理，关键是：针对一个具体问题应该如何构造

2、一个适合于它的数据模式，即构造合理的数据逻辑结构这就需要理论指导。采用关系模型讨论这个问题的理由：由于关系模型有严格数学理论基础并且可以向别的数据模型转换从而，形成了数据库逻辑设计的一个有力工具关系数据库的规范化理论。,规范化理论虽然是以关系模型为背景，但是它对于一般的数据库设计同样具有理论上的意义。关系模式：R（U，D，dom，F）一个五元组 其中：影响关系模式设计合理性的主要因素为U和F，即：属性属性间依赖关系，所以，可以简化为R(U，F)；,数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系。是数据内在的性质,是一种语义体现；是现实世界中属性间相互联系的抽象；表示数据间

3、存在的一种限制或制约关系。根据人们对事物的理解判定依赖关系。数据依赖有多种类型，最重要的是函数依赖（Functional Dependency，简称FD）多值依赖（Multivalued Dependency，简称MVD）关系数据库的规范化理论主要包括三个方面的内容：函数依赖范式（Normal Form）模式设计其中，函数依赖起着核心的作用，是模式分解和模式设计的基础，范式是模式分解的标准。,5.1.2 关系模式的存储异常问题,数据库的逻辑设计为什么要遵循一定的规范化理论？什么是好的关系模式？某些不好的关系模式可能导致哪些问题？,实例：(P171)现在要建立一个数据库，来描述学生(Studen

4、t)的一些情况。,面临的对象有：学生（用学号SNo描述）系（用系名SDept描述）系负责人（用其姓名MN描述）课程（用课程名CName描述）成绩（G）,如果用一个关系模式来描述，则得到：U=SNo，SName，SDept，MN，CName，G,由现实世界可得知：一个系有若干学生，但一个学生只属于一个系。一个系只有一名（正职）负责人。一个学生可以选修多门课程，每门课程有若干学生选修。每个学生学习每一门课程都有一个成绩。于是，得到属性组U上的一组函数依赖：F=SNOSdept,SDept MN,(SNO,CName)G,图5.1 Student数据库的函数依赖图示,若只考虑函数依赖这一种数据依赖，

5、就得到：一个描述学校的数据库模式S，它由一个单一的关系模式构成。,这样的关系模式，有如下三个毛病：（1）插入异常：如果一个系刚成立，尚无学生，或者虽然有学生，但尚未安排课程，那么就无法把这个系及其负责人的信息存入数据库。（2）删除异常：如果某个系的学生全部毕业了，在删除该系学生选修课的同时，把这个系及其负责人的信息也丢了。（3）冗余太大：每一个系负责人的姓名要与该系每一个学生的每门功课的成绩出现的次数一样多，这样，一方面浪费存储，另一方面系统要付出很大的代价来维护数据库的完整性，比如某系负责人更换后，就必须逐一修改每一个元组。,为什么产生异常？模式中的函数依赖存在不好的性质；或者说，数据模式组

6、织不合理。,效果：这三个模式都不会发生异常冗余也得到控制。是一个好的关系数据库模式,改进：把这个单一的模式改造,分成3个关系模式。S(SNo，SDept，SNoSDept)SG(SNo，CName，G，(SNo，CName)G)D(SDept，MN，SDeptMN),结论：一个好的关系模式应该具备以下四个条件：尽可能少的数据冗余。没有插入异常。没有删除异常。没有更新异常。注意：一个好的关系模式并不是在任何情况下都是最优的，要从实际设计的目标出发进行设计。,5.2 规范化（Normalization）,作用：规范化理论使数据库设计方法走向完备。起源：1971年提出。,定义：如何按照一定的规范设计

7、关系模式，将结构复杂的关系分解成结构简单的关系，从而把不好的关系数据库模式转变为好的关系数据库模式，这就是关系的规范化。数据库模式的好坏和关系中各属性间的依赖关系有关，因此，我们先讨论属性间的依赖关系，然后再讨论关系规范化理论。,5.2.1 函数依赖5.2.2 码：用函数依赖的概念来定义码。5.2.3 范式（Normal Form）NF5.2.4 多值依赖5.2.5 4NF,5.2.1 函数依赖,定义1：设R(U)是属性集U上的关系模式。X，Y是U的子集，若对于R(U)的任意一个可能的关系r，r 中不可能存在两个元组t,s在X上的属性值相等，即tX=sX；而在Y上的属性值不等，即tYsY；则称

8、X函数确定Y或Y函数依赖于X，记作：XY。,或者换个通俗的话对于X的一个值，只有唯一的Y值与之对应，则称 XY。,x,f(x)=y,函数依赖是一个语义范畴的概念，如：姓名 年龄，姓名 出生日期，姓名 籍贯只能在姓名唯一的假设前提下成立。当我们确定关系模式R中的某个函数依赖时，是指R的所有可能关系r都必须满足这个函数依赖；反之，如果R中只要有一个关系r不满足这个函数依赖，我们就认为R不存在这个函数依赖。函数依赖只能从属性含义上加以说明，而不能在数学上加以证明。只有数据库设计者才能决定是否存在某种函数依赖。这就使得数据库系统可以根据设计者的意图来维护数据库的完整性。,例如：关系模式R12=学号(S

9、)，课程号(CB)，课程名(CN)，学期数(T)，学分(CG)，成绩(G)中的函数依赖可表示为：CBT;(S,CB)G;CBCN;CBCG;(S,CB,CN)G等等。几个记号和术语：,X Y，但X Y，则称X Y是平凡的函数依赖。若X Y，则X叫做决定因素（Determinant）。若X Y，Y X，则记作XY。,定义2：完全依赖和部分依赖,例如：关系模式R12=S,CB,CN,T,CG,G中，CBT说明T完全函数依赖于CB；又因为(S,CB)G，(S,CB,CN)G，则G部分依赖于（S,CB,CN）。在实际的一个关系表中：如果主码只有一个属性，则基本上是完全函数依赖。如果主码由若干个属性组成

10、，则可能存在部分依赖，也可能是完全依赖。,若XY，但Y不完全函数依赖于X（只依赖于X的一部分），则称Y对X部分函数依赖，记作：,实例1,存在以下函数依赖：l SNo SName（若无重名）lSNo SDept l SNo SAge,实例2,在这里，单个属性不能作为决定因素，但属性的组合可以作为决定因素，即：,零件编号,零件名,（零件编号，工程编号，规格型号）,数量,（工程编号，零件编号）,零件名称，规格型号,（零件编号，工程编号）,实例3,PJTP(*工程编号，工程名称，*零件编号，零件名称，规格型号，数量),工程名称,工程编号,工程名称,（工程编号，零件编号）,数量,定义3：传递依赖,例如：

11、关系模式R=A,B,C,D，其上的函数依赖集F=AB,BC,AC,ABD，则AC为传递函数依赖。,5.2.2 码：用函数依赖的概念来定义码。,定义4：设K为R(U，F)中属性或属性组合。,主属性（Prime attribute）非主属性（Non Prime attribute）或非码属性（Non-Key-attribute）全码（all key）：关系模式中，整个属性组是码。定义5：外码关系模式R 中属性或属性组X并非R 的码，但X是另一个关系模式的码，则X是R的外部码（Foreign Key），也称外码。,若候选码为多个，则选定其中的一个为主码（Primary Key）。,5.2.3 范式（

12、Normal Form）NF,必要性：关系数据库中关系要满足一定要求；满足不同层要求的关系，为不同范式。范式的提出：19711972年，系统地提出1NF,2NF,3NF。1974年，Codd和Boyce又共同提出了一个新范式BCNF。1976年，Fagin提出4NF。后来又提出了5NF。范式表示关系的某一级别，现在把范式理解为符合某一种级别的关系模式的集合，则R为第几范式，可写成R xNF。,各种范式之间有如下关系,一个高一级的范式，必须属于低一级范式。一个低一级范式的关系模式，通过模式分解，可以转化为若干个高一级范式的关系模式集合。这种过程就叫规范化。规范化的基本思想是消除关系模式中的数据冗

13、余，消除数据依赖中的不合适的部分，解决数据插入、删除异常。,5NF 4NF BCNF 3NF 2NF 1NF,一、1NF 第一范式,关系模式中每一个分量，必须是不可分的数据项，满足了这个条件的关系模式，就属于第一范式（1NF），即：关系模式中不存在复合数据项；是平坦的数据结构。例，职工档案（非规范的）,人们在处理这个问题的时候，不规范的作法是-采用：（1）横向冗余法（例如，表A）（2）纵向冗余法（例如，表B）,化为1NF，将上述关系拆开成两个表，即把组合项拿出来单独形成一个表：,二、2NF 第二范式,从2NF开始，判断非主属性与主属性间关系定义6：若R 1NF，且每一个非码属性完全函数依赖于码

14、，则R 2NF。书中例子：P175，非2NF。2NF定义：如果一个规范化的数据结构，它所有的非关键字数据元素都完全函数依赖于整个关键字，我们称它是第二规范化形式(Second Normal Form)的数据结构，简称第二范式(2NF)。推论1：一个规范化的数据结构，如果其关键字仅由一个数据元素组成或其全体属性均为主属性，那么它必然属于2NF。推论2：如果关键字是由若干个属性组成，要判别所有的非关键字与关键字的函数依赖关系，如果存在部分依赖关系，则不属于2NF。,例如：描述一个在校大学生的学习情况涉及以下一些属性：学号（Sno）、姓名（Sname）、性别（Sex）、系别（Sdept）、学籍类型（

15、SL）、专业（Spec）、班级(SC)、课程号（Cno）、课程名（Cname）、学期数（T）、学分（Credit）和成绩（G），该关系模式R（U，F）属性集合表示为U=Sno,Sname,Sex,ID,Sdept,SL,Spec,SC,Cno,Cname,T,Credit,G。函数依赖集合F=SnoSname,SnoSex,SnoSdept,SnoSL,SnoSpec,SnoSC,CnoCname,CnoT,CnoCredit,(Sno,Cno)G 显然，该关系模式的码为（Sno,Cno）-可丛常识判断，也可从F中求解侯选码。R1NF-所有的属性都是最小的不可分的数据项 R2NF-存在非码属性

16、对码的部分函数依赖关系,R中存在以下几个问题：(1)冗余。(2)插入异常。假如新增一门课程，其Cno=1011，Cname=多媒体技术，学分=3，但因此课程还没有学生选修，则这样的元组不能插入R的关系中。(3)删除异常。假如有一门课（如课程号为C5）目前只有一位学生选修了，但这位学生又不选了，那么 C5这个数据项就要删除。由于C5是主属性，删除了C5，整个元组就不存在了，也必须删除，但这样也把不应该删除的信息删除了，造成删除异常。,实例一,将R化为2NF-消除部分函数依赖关系。R可分解为以下三个表：R1（U1，F1）-码为Sno 属于2NFU1=Sno,Sname,Sex,ID,Sdept,S

17、L,Spec,SCF1=SnoSname,SnoSex,SnoSdept,SnoSL,SnoSpec,SnoSCR2（U2，F2）-码为Cno 属于2NFU2=Cno,Cname,T,CreditF2=CnoCname,CnoT,CnoCreditR3（U3，F3）-码为(Sno,Cno)属于2NFU3=Sno，Cno，GF3=(Sno,Cno)G对属性集进行分解，对函数依赖集进行分解,实例一,实例二：配件-供应商-库存关系，语义描述：“配件编号”代表每种配件（名称和规格）；每种配件的“库存量”、“价格”、“库存占用资金”还和“供应商”有关（即：同一配件，可由不同的供应商供应，其价格、库存量及

18、库存占用资金因供应商不同而不同）。同一供应商可供应多种配件。这个关系达到1NF，因其所有的属性都是不可分的。根据语义描述，非关键字与关键字有如下的函数依赖关系。“配件编号+供应商名称”是关键字。,函数依赖关系：配件编号配件名称 配件编号规格 供应商名称供应商地址 配件编号+供应商名称价格 配件编号+供应商名称库存量，配件编号+供应商名称库存占用资金 因为“配件名称”、“规格”和“供应商地址”并不完全函数依赖于整个关键字。存在非主属性部分函数依赖于关键字，所以它不属于2NF。,*配件编号 配件名称 规格*供应商名称 供应商地址 价格（厂价）库存量 库存占用资金,对这样一个数据结构，可能会有如下毛

19、病。,插入异常 如果汽车配件公司准备引进一种新的汽车配件，知道它的名称和规格，给它规定一个配件编号，想把这种新配件插入到“配件供应商库存”数据存贮中去，但是配件公司还没有决定由哪一家供应商提供这种新配件，也就是还没有该配件的供应商数据和库存数据；就无法插入这项新配件的数据（关键字不能为空）。,修改异常 如果某家供应商的地址发生了变化，需要修改这家供应商的地址；但是有上百种或上千种配件是由这家供应商提供的，那么要逐个地修改“供应商地址”，与这家供应商有关的元组一条也不能遗漏，这就为修改带来了麻烦。,删除异常 如果汽车配件公司和某家供应商断绝了业务关系，就没有必要再保存这家供应商的数据，而这家供应

20、商恰恰是某种(或某几种)配件的唯一供应商，当把这家供应商的数据删除时，整个元组也就不存在了，那么这种（或这几种）配件的数据也都丢失了，把不应该删除的数据也删除了。,解决办法,属于第一范式的数据结构还是一个不好的数据结构，需要进一步把它转换成第二规范化形式，办法是：把1NF关系模式通过投影分解转换成2NF关系模式的集合，即对函数依赖关系按决定因素分组，决定因素相同的分为一组，构成一个关系模式。分解时遵循的基本原则就是“一事一地”，让一个关系只描述一个实体或者实体间的联系。因此，“配件-供应商-库存”可以分解成三个数据结构，它们都是属于2NF的数据结构。,三、3NF 第三范式,3NF定义：如果一个

21、属于第二范式的数据结构，它所有的非关键字数据元素都是彼此函数独立的，换句话说，在所有的非关键字数据元素之间，不存在函数依赖关系，那么我们称它是第三规范化形式(Third Normal Form)的数据结构，简称第三范式（3NF)。,即关系模式中不存在部分依赖和传递依赖关系。,例1,3NF,“配件库存”已经是第二范式的数据结构，但是存在着传递依赖关系。因为“库存占用资金”函数依赖于“库存量”和“价格”，这三个数据元素都是属于非关键字域，而“库存量”和“价格”都完全函数依赖于整个关键字；因此“库存占用资金”传递依赖于关键字。这说明在非关键字域中，存在着冗余的数据元素，因为已知“库存量”和“价格”，

22、就必然能够计算出“库存占用资金”，它作为一个数据元素存在，为修改“配件库存”带来不方便，每当修改，“库存量”的时候，就必须修改“库存占用资金”，显然是不合理的。,例2,有若干项工程，每项工程都有规定的完工日期，每项工程要由若干人完成，每一个职工只能承担一项工程，每一个职工有固定的工资。那么，可以设计一个称为“分派职工任务”的数据存贮的数据结构。,分解成3NF,*,如果又增加一个新的工程项目，规定了它的代号和完成日期，但是还没有指派由哪些职工承担，这时就无法插入这项新工程的数据。即使是第二范式，“分派职工任务”的数据结构也仍然存在上述插入、删除、修改等异常问题，产生的原因就是存在着传递依赖关系。

23、解决的办法是：Q去掉传递依赖关系；Q 必要时，分解成若干个第三规范化形式的数据结构。对于“分派职工任务”数据结构，可以把它分解成两个第三范式的数据结构，“职工工程”和“工程”。,证明若R3NF,则R必属于2NF,R2NF(用反证法),这与题设R 3NF矛盾,证明：假设R3NF，R2NF则 存在属性A，候选码X，A,X R，使得,这样在R中就有非主属性A，不满足第三范式的定义，所以 R3NF,并且：,四、BCNF(Boyce Codd Normal Form),由Boyce 和Codd 1974年共同提出，对3NF进行扩充、修正。,即：关系R中所有的决定因素都是候选码。由BCNF的定义可以得出结

24、论，一个满足BCNF的关系模式有：所有的非主属性，对每一个码，都是完全函数依赖。所有的主属性对每一个不包含它的码，也是完全函数依赖。没有任何属性完全函数依赖于非码的任何一组属性。,实例,非BCNF范式：关系模式STJ（S，T，J）中，S是学生、T是老师、J是课程；每个老师只教一门课；每门课都有若干老师；某一学生选定一门课就对应一个固定的老师。由语义可以得到如下的函数依赖：（S，J）T（S，T）J T J函数依赖图示（见右图5.6）,T,J,图5.6 STJ中的函数依赖,实例分析,这个关系的候选码：（S，J）和（S，T）STJ是3NF，因为没有任何非主属性对码传递依赖或部分依赖。但是，存在主属性

25、J 对候选键(S,T)的部分依赖，或者说 T是决定因素，而T不是码，STJ不是BCNF。经BCNF分解后，得到：ST（S，T）TJ（T，J）,对BCNF的分析,3NF和BCNF，是在函数依赖的条件下，对模式分解所能达到的分离程度的“测度”。BCNF实现了彻底的分离，已消除了插入、删除异常。3NF的分离的“不彻底性”，表现在可能存在主属性对码的部分依赖和传递依赖。,5.2.4 多值依赖,实例：教员，课程，参考书(P178-P179)学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。我们可以用一个非规范化的关系来表示教员T,课程C和参

26、考书B之间的关系：,关系的码是(C,T,B),即A1l_Key。因而TEACHINGBCNF。但是当某一课程(如物理)增加一名讲课教员(如周英)时,必须插人多个元组：(物理,周英,普通物理学),(物理,周英,光学原理),(物理,周英,物理习题集)当某一课程（如数学）去掉一本参考书（如微分方程），则必须删除多个元组。对数据的增删改很不方便,数据的冗余也十分明显。,Teaching,定义：设R(U)是属性集U上的一个关系模式，X、Y、Z是U的子集，并且Z=U-X-Y。若对R(U)的任一关系r，对于X的一个给定值x，存在Y的一组值与其对应，而Y的这组值又不以任何方式与属性Z 的值相关，那么就是说，Y

27、多值依赖于X，记为：XY。当Y的这组值个数为1时，XY就成了XY。,多值依赖的示意图,多值依赖的另一个等价的形式化的定义,在R(U)的任一关系r 中，如果存在元组t,s，使得tXsX，那么就必然存在元组w,vr，（w,v可以与s,t相同），使得wX=vX=t X，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交换s,t元组的Y值所得两个新元组必在r 中），这里X、Y是U的子集，Z=UXY。称 Y 多值依赖于X，即为XY。若XY，而Z=UXY=（为空），则称XY为平凡的多值依赖。,多值依赖的性质,1.多值依赖具有对称性，即：若XY，则XZ，其中Z=UXY。2.多值依赖的传递性，若XY，YZ

28、，则 XZ-Y。3.函数依赖可以看作是多值依赖的特殊情况，即若XY，则XY。4.若XY，XZ，则XYZ。5.若XY，XZ，则XYZ。6.若XY，XZ，则XY Z，X ZY。,多值依赖与函数依赖的区别,多值依赖的有效性，与属性集的范围有关。若XY在U上成立，则在W(XYWU)上一定成立。反之则不然。即：XY在W(WU)上成立，在U上不一定成立。即在小范围上成立，在大范围上不一定成立。因为多值依赖的定义中不仅涉及属性组X和Y，而且涉及U中其余属性Z。但是函数依赖XY的有效性仅决定于X,Y这两个属性集的值。若函数依赖XY在R(U)上成立，则对于任何Y Y 均有XY 成立。而多值依赖XY若在R(U)上

29、成立，却不能断言对于任何Y Y有XY成立。,5.2.5 4NF,定义：关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y!X），X都含有码，则称R 4NF。4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。因为根据定义，对于 每一个非平凡的对值依赖XY，X都含有候选码，于是就有XY。所以4NF所允许的非平凡的多值依赖实际上是函数依赖。函数依赖和多值依赖，是两种重要的数据依赖：如果只考虑函数依赖，则BCNF方式是规范化程度最高；如果考虑多值依赖，则属于4NF的关系模式是规范化程度最高的了。,非4NF关系模式的例子,关系模式WSC(仓库W，保管员S，产品C)；语义：一个仓

30、库可以有多个保管员，一个仓库可以存放多种产品。每个保管员保管所在仓库的所有商品，每种商品被所有保管员保管。WS；WC；都是 非平凡的多值依赖。因为UWS=C，UWC=S不为空。而关系的码为（W,S,C），W不是码，WSR 4NF分解为：WS(W，S)WC(W，C),各种范式及规范化过程（1）,所有的属性必须是不可分的数据项,消除非主属性对码的部分函数依赖,消除非主属性对码的部分函数依赖和传递函数依赖,消除主属性对码的部分和传递函数依赖,消除非平凡且非函数依赖的多值依赖,各种范式及规范化过程（2）,第一步：（去掉重复的组项）把所有的非平坦的数据结构分解为若干二维表形式的数据结构，指定一个或若干个

31、数据元素作为关键字，唯一标识出每个元组，关键字应该由尽可能少的数据元素组成。,第二步：（去掉部分依赖）如果关键字由不止一个的数据元素组成，必须确保每一个非关键字数据元素完全函数依赖于整个关键字。否则，在必要的时候，通过分解的办法转换成若干个满足这种要求的数据结构。,第三步：（去掉传递依赖）检查所有的非关键字数据元素是否彼此独立，如果不是，消除传递依赖关系，去掉冗余的数据元素，或通过分解的办法，转换成若干个满足这种要求的数据结构。,一般情况下，我们说没有异常弊病的数据库设计是好的数据库设计，一个不好的关系模式也总是可以通过分解转换成好的关系模式的集合。但是在分解时要全面衡量，综合考虑，视实际情况

32、而定。对于那些只要求查询而不要求插入、删除等操作的系统，几种异常现象的存在并不影响数据库的操作。这时便不宜过度分解，否则当要对整体查询时，需要更多的多表连接操作，这有可能得不偿失。在实际应用中，最有价值的是3NF和BCNF，在进行关系模式的设计时，通常分解到3NF就足够了。,小结,关系模式属性间存在数据依赖，数据依赖是语义体现R数据依赖可分为多种，如：函数依赖，多值依赖，连接依赖。进行数据设计一般只考虑：函数依赖；多值依赖。关系模式中属性间数据依赖要满足一定的程度要求范式。满足不同程度要求的为不同范式。,一个低一级范式的关系模式，通过模式分解可以转换成若干个高一级范式的关系模式集合，这种过程叫

33、规范化。FD 函数依赖的概念：完全函数依赖部分函数依赖传递函数依赖非平凡的函数依赖,5.3 数据依赖的公理系统 5.3.1 Armstrong公理系统,数据依赖的公理系统是模式分解算法的理论基础。函数依赖的一个有效而完备的公理系统-Armstrong公理系统。定义5-11：逻辑蕴含：设关系模式R(U，F)，X，Y U，F是关于R的函数依赖集合。又设XY为R中的一个函数依赖，若对R的每一个关系r，满足F中每一个依赖，则r也必须满足XY，我们就说F逻辑蕴涵XY，或称XY从F推导出来的，或称XY逻辑蕴涵于F。对于满足一组函数依赖F的关系模式R，若对其任何一个关系r，函数依赖XY都成立(即r中任意的两

34、元组t,s，若tX=sX，则tY=s Y)，则称F逻辑蕴含XY。(即XYF),Armstrong公理系统（1974年，由Armstrong提出）由几个推理规则组成。设U为属性集总体，F是U上的一组函数依赖，于是有关系模式R，对R来说有以下的推理规则：u A1自反律（Reflexivity）：若YX U，则XY为F所蕴含。uA2增广律：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。u A3传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。,例:R,U=A,B,C,F=AB,B C 求证:A ABC?证明:A BA AB BCB BCAB ABCA ABC.,例:关系模式R(CITY,ST,Z

35、IP)，其中CITY表示城市，ST表示城市的街道，ZIP表示街道所在地区的邮政编码，函数依赖集合F=(CITY,ST)ZIP,ZIPCITY，证明ST,ZIP和CITY,ST是候选键。,证：因为ZIPCITY（由给定条件得出）(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)也是候选键。证毕。,定理5

36、.1：Armstrong推理规则是正确的。证明:（书P184），对每个推理规则由定义出发证明。设YXU对R的任一关系r中的任意两个元组t,s:若tX=sX,由于YX,有tY=sY,所以XY 成立(自反律得证).设XY为F所蕴含，且ZU，对R的任一关系r中的任意两个元组t,s:若tXZ=sXZ,则有tX=sX和tZ=sZ,由于XY,于是有tY=sY,所以tYZ=sYZ,所以 XZYZ为F所蕴含(增广律得证)。,由A1、A2、A3三条规则，得到下面三个规则：u 合并规则：由XY，XZ有XYZ。u 伪传递规则：由XY，WYZ，有WXZ。u 分解规则：由XY及Z Y有XZ。,证明：设XY及YZ为F所蕴

37、含对于R的任一关系r中的任意两个元组t,s:若tX=sX,由于XY,有tY=sY,由于YZ,有tZ=sZ,所以XZ为F所蕴含(传递律得证)。,引理5.1：由XA1,A2,Ak成立的充分必要条件是 XAi（i=1,2,k）成立。定义5.12：在关系模式R中为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记为F+。例：设关系模式R(U)，U=A,B,C,F=ABC,CB是R(U)上的一组函数依赖，则F+=AA,ABA,ACA,ABCA,BB,ABB,BCB,ABCB,CC,ACC,BCC,ABCC,ABAB,ABCAB,ACAC,ABCAC,BCBC,ABCBC,ABCABC,ABC,ABAC,ABB

38、C,ABABC,CB,CBC,ACB,定义5.13：设F为属性集U上的一组函数依赖，X U，XF+=A|X A能根据Armstrong公理导出，XF+为属性X关于函数依赖集F的闭包。引理5.2 设F为属性集U上的一组函数依赖，X，YU，XY的能由F根据Armstrong导出的充分必要条件是Y XF+。所以判定XY是否能由F根据Armstrong导出的问题，就转化为求XF+，判定Y是否为XF+的子集的问题,算法5.1 求属性集X（X U）关于U上的关于函数依赖F的闭包XF+。输入：X，F输出：XF+步骤：1.初始化 令X（0）=X，i=0。2.加上新属性 X（i+1）=X（i）B.其中B=A|(

39、V)(W)(VWFV X(i)AW3.判断终止 当X（i+1）=X（i）或X(i+1)=U 时，X（i+1）即为XF+，算法结束；否则，令i=i+1，转第二步。,例1 设关系模式R(U)上的函数依赖集为F,U=A,B,C,D,E,I;F=AD,ABE,BIE,CDI,EC，试计算(AE)+。解：令X(0)=AE，i=0;在F中找出左边是AE子集的函数依赖，因AD，则X(1)=AED;因EC，则X(2)=AEDC；因CDI,则X(3)=AEDCI;因已没有VWF，能使X(3+1)X(3)，则X+=X(3),即(AE)+=ACDEI。,例2 已知关系R，U=A，B，C，D，E，F=ABC，BD，C

40、E，ECB，ACB。求：（AB）F+。解：X（0）=ABX（1）=AB CD=ABCDX（2）=ABCD EB=ABCDE，是全部属性集合。故（AB）F+=ABCDE。练习：已知关系R，U=A，B，C，D，E，G，F=ABC，DEG，CA，BEC，CGBD，ACD B，CEG。求：（CD）F+。,定理5.2：Armstrong公理系统是有效的、完备的。有效性：由F出发根据Armstrong 推导出来的每一个函数依赖一定在F+中。完备性：F+中的每一个函数依赖，必定可由F出发据Armstrong公理系统推导出来。Armstrong公理系统的正确性和完备性说明了“通过F推导出的函数依赖”与“F所蕴

41、涵的函数依赖”两种说法是完全等价的。所以，F+也可以说成是由F出发经Armstrong公理系统导出的函数依赖集合。,函数依赖集合F的极小函数依赖集,在实际应用中，经常需要将一个已知的函数依赖集变换为其它的或更简洁的表示形式。例如，需要把一个大的关系模式分解为几个小的关系模式，这时就需要将相应的函数依赖也投影到分解后的模式上。这就涉及一个函数依赖集的等价问题。下面，从蕴涵（或导出）的概念出发，再引出两个概念。这些概念在关系模式规范化处理中十分重要。,1.两个函数依赖集F和G等价,定义5.14 两个函数依赖集F和G等价定义:设模式R上的两个函数依赖集F和G，如果有F+=G+，则称F和G等价，记作F

42、G。若FG，则F是G的一个覆盖，同样，G是F的一个覆盖。引理5.3:G+=F+的充分必要条件是F G+和G F+。证明：必要性显然，只证充分性。1.若F G+,则XF+XG+2.任取XYF+,有Y XF+XG+所以 XY(G+)+=G+，即 F+G+3.同理可证G+F+,所以F+=G+。,2.函数依赖集F的极小（或最小）函数依赖集,定义5.15（P186）：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集，亦称为最小依赖集，或最小覆盖。（1）F中任一函数依赖的右部仅含有一个属性。（2）F中不存在这样的函数依赖X A，使得F与FX A 等价。,F中没有多余的函数依赖,（3）F中不存在这样

43、的函数依赖X A，X有真子集Z使得 FX A ZA与F等价。,F中每个函数依赖的左部没有多余的属性,注意：F 的极小依赖集不一定是惟一的。,例：考察关系模式S，其中：U=SNo，SDept，MN，CName，G F=SNoSDept，SDept MN，(SNo,CName)G 由最小函数依赖集定义，可判知F为最小覆盖设 F=SNoSDept,SNoMN,SDept MN,(SNo，CName)G,(SNo，SDept)SDept 由定义5.15（极小函数依赖集）可知F不是极小函数依赖集。因为：1）满足第一个条件，右部仅含有一个属性。2）F SNoMN与F等价 3）F(SNo,SDept)SDe

44、pt 与F等价不满足第（2）条为非极小函数依赖。,定理5.3：每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集。证明：这是一个构造性证明1.逐一检查F中各函数依赖FDi：XY，若Y=A1A2Ak,k2，则用XAj|j=1,2,k来代替。2.逐一检查F中各函数依赖XA，令G=F-X A,若A XG+,则从F中去掉此函数依赖(因为F与G等价的充要条件是AXG+)。3.逐一取出F中各函数依赖XA，设X=B1B2Bm,逐一考查Bi(i=1,2,m),若A(X-Bi)F+,则以X-Bi取代X(因为F与F-X A Z A等价的充要条件是 AZF+,其中Z=X-Bi)。,应当指出：

45、F的最小依赖集Fm不一定是唯一的；它与对各函数依赖FDi及XA中各属性的处置顺序有关。【例】设关系模式R(U)上的函数依赖集为F,U=A,B,C,D,E,G,;F=ABC,BCD,ACDB,DEG,CA,BEC,CGBD,CEAG。试计算其等价的极小函数依赖集F。解：（1）应用分解规则，使F的每一个函数依赖的右部属性单一化。结果为：F1=ABC,BCD,ACDB,DE,DG,CA,BEC,CGB,CGD,CEA,CEG。,（2）去掉各函数依赖左部多余的属性。因为CEA,CA,则E是多余的；对于ACDB,由于(CD)+F1=ABCDEG，则CD B,所以A是多余的。其它函数依赖中无左部多余的属性

46、。删除函数依赖左部多余的函数依赖后的结果为：F2=ABC,BCD,CDB,DE,DG,CA,BEC,CGB,CGD,CEG。(3)在F2中去掉多余的函数依赖。对于CGB,令G=（F2-（CG B）=ABC,BCD,CDB,DE,DG,CA,BEC,CGD,CEG，由于(CG)G+=ABCDEG,则CGB是多余的。其等价的极小函数依赖集F的结果为：F=ABC,BCD,CDB,DE,DG,CA,BEC,CGD,CEG。,5.3.3 关系模式的分解,根据需求分析中得到的用户要求，我们可以把关系分为两类。静态关系：其特点是一旦数据已加载，用户只能在这个关系上运行查询操作。这种关系的要求是必须属于1NF

47、。动态关系：其特点是当数据加载后，经常对数据进行增、删、改操作。这种关系的要求是至少属于3NF。一旦关系模式不满足要求，就要对此关系模式进行分解，这是关系模式规范化的主要方法。但问题是，分解后的多个模式是否与原来的模式完全一样呢？即所表示的信息是否与原来的信息一致呢？所表达的函数依赖集是否与原来的函数依赖集等价呢？这就涉及分解的概念和原则。,一、关系模式分解的概念,1.关系模式分解 设关系模式R(U)，U=A1,A2,An,F是R(U)上的函数依赖的集合。=R1,R2,Rn 是R的一个分解，使得R1R2Rn=R,U=U1U2Un，且不存在Ui Uj,1i,j n,，其中，Fi是F在Ui上的投影

48、。定义：F在Ri的属性集合Ui上的投影是Fi=XY|XYF+XY Ui。,2.关系模式分解的主要目的 其目的是为了解决关系模式中可能存在的插入、删除和修改时的异常情况。注：一般此工作由数据库设计者来进行的。3.关系模式分解的原则 关系模式分解的原则：分解后产生的模式应与原模式等价。仅当下述三种情况之一，才能保证分解后产生的模式与原模式等价：(1)分解具有“无损连接性”；(2)分解具有“保持函数依赖性”；(3)分解既要“保持函数依赖性”，又要具有“无损连接性”。,1.分解具有无损连接性 设关系模式R(U)，F是R上的函数依赖集合，=R1,R2,Rn是R的一个分解，如果对R的任一满足F的关系r下式

49、成立：,二、具有无损连接性的关系模式分解,无损连接分解的特性说明：关系模式分解后所表示的信息应与原模式等价，即分解后的多个关系再连接得到的新关系不能“丢失”信息。实际上，连接后的关系不会少了任何元组，而是可能多出一些元组，因与原来的关系不等价，所以是有损的。,则称分解为具有无损连接性或分解为无损连接分解。,2.判定一个分解的无损连接性算法 输入：关系模式R(A1,A2,An)，R上的分解=R1,R2,Rn，R上的函数依赖集为F。输出：分解是否具有无损连接性。方法：(1)构造一个k行n 列的初始表，第i 行对应于关系模式Ri，第j列对应于属性Aj。如果AjRi，则在第i行第j列上填符号ai；否则

50、填符号bij。,二、具有无损连接性的关系模式分解,(2)逐个检查F中的每一个函数依赖，并修改表中的元素。具体办法如下：从函数依赖集F中取一个函数依赖XY，在X的分量中寻找相同的行，然后将这些行中Y的分量改为相同的符号。如果其中有aj,则将bij 改为aj;否则，改为bij(指用其中的一个bij替换另一个，通常是把下标改为较小的那个数)。(3)这样反复进行，如果发现某一行变成了a1,a2,an，即存在某一行全为a 类符号，则分解具有无损连接性；如果 F中所有函数依赖都不能再修改表中的内容，且没有发现这样的行，则分解不具有无损连接性。,【例】已知关系模式R(U)，U=A,B,C,D,E，R上的函数