第五章 关系数据理论PPT讲稿.ppt

第五章 关系数据理论第1页，共79页，编辑于2022年，星期三5.1问题的提出关系数据库逻辑设计关系数据库逻辑设计针针对对具具体体问问题题，如如何何构构造造一一个个适适合合于于它它的的数数据据模模式式数数据据库库逻逻辑辑设设计计的的工工具具关关系系数数据据库库的的规规范范化化理论理论第2页，共79页，编辑于2022年，星期三一、概念回顾v关系：描述实体、属性、实体间的联系。关系：描述实体、属性、实体间的联系。从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。个子集。v关系模式：用来定义关系。关系模式：用来定义关系。v关系数据库：基于关系模型的数据库，利用关系来描述现实关系数据库：基于关系模型的数据库，利用关系来描述现实世界。世界。从形式上看，它由一组关系组成。从形式上看，它由一组关系组成。v关系数据库的模式：定义这组关系的关系模式的全体。关系数据库的模式：定义这组关系的关系模式的全体。第3页，共79页，编辑于2022年，星期三二、关系模式的形式化定义关系模式由五部分组成，即它是一个五元组：关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)R：关系名关系名U：组成该关系的属性名集合组成该关系的属性名集合D：属性组属性组U中属性所来自的域中属性所来自的域DOM：属性向域的映象集合：属性向域的映象集合F：属性间数据的依赖关系集合属性间数据的依赖关系集合第4页，共79页，编辑于2022年，星期三三、什么是数据依赖1.完整性约束的表现形式完整性约束的表现形式v限定属性取值范围：例如学生成绩必须在0-100之间v定义属性值间的相互关连（主要体现于值的相等与否），这就是数据依赖，它是数据库模式设计的关键第5页，共79页，编辑于2022年，星期三数据依赖2.数据依赖数据依赖v是通过一个关系中属性间值的相等与否体现是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系出来的数据间的相互关系v是现实世界属性间相互联系的抽象是现实世界属性间相互联系的抽象v是数据内在的性质是数据内在的性质v是语义的体现是语义的体现第6页，共79页，编辑于2022年，星期三数据依赖的类型3.数据依赖的类型数据依赖的类型v函数依赖（函数依赖（Functional Dependency，简记为，简记为FD）v多值依赖（多值依赖（Multivalued Dependency，简记为，简记为MVD）v其他其他第7页，共79页，编辑于2022年，星期三四、关系模式的简化表示关系模式关系模式R（U,D,DOM,F）简化为一个三元组：简化为一个三元组：R（U,F）当且仅当当且仅当U上的一个关系上的一个关系r 满足满足F时，时，r称为关系模式称为关系模式 R（U,F）的一个关系）的一个关系第8页，共79页，编辑于2022年，星期三五、数据依赖对关系模式的影响例：描述学校的数据库：例：描述学校的数据库：学生的学号（学生的学号（Sno）、所在系（）、所在系（Sdept）系主任姓名（系主任姓名（Mname）、课程名（）、课程名（Cname）成绩（成绩（Grade）单一单一的关系模式的关系模式：Student U Sno,Sdept,Mname,Cname,Grade 第9页，共79页，编辑于2022年，星期三数据依赖对关系模式的影响学校数据库的语义：学校数据库的语义：一个系有若干学生，一个系有若干学生，一个学生只属于一个系；一个学生只属于一个系；一个系只有一名主任；一个系只有一名主任；一个学生可以选修多门课程，一个学生可以选修多门课程，每门课程有若干学生选修；每门课程有若干学生选修；每个学生所学的每门课程都有一个成绩。每个学生所学的每门课程都有一个成绩。第10页，共79页，编辑于2022年，星期三数据依赖对关系模式的影响属性组U上的一组函数依赖F：F Sno Sdept,Sdept Mname,(Sno,Cname)Grade SnoCnameSdeptMnameGrade第11页，共79页，编辑于2022年，星期三关系模式Student中存在的问题 数据冗余太大数据冗余太大浪费大量的存储空间浪费大量的存储空间 例：每一个系主任的姓名重复出现例：每一个系主任的姓名重复出现 更新异常（更新异常（Update Anomalies）数据冗余数据冗余，更新数据时，维护数据完整性代价大。更新数据时，维护数据完整性代价大。例：某系更换系主任后，系统必须修改与该系学生有关的例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组每一个元组第12页，共79页，编辑于2022年，星期三关系模式Student中存在的问题 插入异常（插入异常（Insertion Anomalies）该插的数据插不进去该插的数据插不进去 例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。任的信息存入数据库。删除异常（删除异常（Deletion Anomalies）不该删除的数据不得不删不该删除的数据不得不删例，如果某个系的学生全部毕业了，例，如果某个系的学生全部毕业了，我们在删除该系学生信我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。息的同时，把这个系及其系主任的信息也丢掉了。第13页，共79页，编辑于2022年，星期三数据依赖对关系模式的影响结论：结论：Student关系模式不是一个好的模式。关系模式不是一个好的模式。“好好”的模式：的模式：不会发生插入异常、删除异常、更新异常，不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。数据冗余应尽可能少。原因原因：由存在于模式中的由存在于模式中的某些数据依赖某些数据依赖引起的引起的解决方法：解决方法：通过通过分解分解关系模式来消除其中不合适关系模式来消除其中不合适 的数据依赖。的数据依赖。第14页，共79页，编辑于2022年，星期三规范化 规范化理论正是用来改造关系模式，通过分正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数以解决插入异常、删除异常、更新异常和数据冗余问题。据冗余问题。第15页，共79页，编辑于2022年，星期三5.2 5.2 规范化规范化 数据依赖数据依赖：关系中属性值之间的这种相互依赖又相互制约的联关系中属性值之间的这种相互依赖又相互制约的联系，称为数据依赖。包括：函数依赖、多值依赖。系，称为数据依赖。包括：函数依赖、多值依赖。一、函数依赖函数依赖定义1：设设R(U)R(U)是属性集是属性集U U上的关系模式。上的关系模式。X X，Y Y是是U U的子集。若对于的子集。若对于R(U)R(U)的任意一个可能的关系的任意一个可能的关系r r，r r中不可能存在两个元组在中不可能存在两个元组在X X上的属性上的属性值相等，而在值相等，而在Y Y上的属性值不等，则称上的属性值不等，则称X X函数决定函数决定Y Y或或Y Y函数依赖于函数依赖于X X，记作，记作XYXY。第16页，共79页，编辑于2022年，星期三说明：1.函数依赖不是指关系模式函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，的某个或某些关系实例满足的约束条件，而是指而是指R的的所有关系实例所有关系实例均要满足的约束条件。均要满足的约束条件。2.函数依赖是函数依赖是语义范畴语义范畴的概念。只能根据数据的语义来确定函数依的概念。只能根据数据的语义来确定函数依赖。赖。例如例如“姓名姓名年龄年龄”这个函数依赖只有在不允许有同名人的条件下成这个函数依赖只有在不允许有同名人的条件下成立立3.数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖出现，函数依赖“姓名姓名年龄年龄”成立。所插入的元组必须满足规定的成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，函数依赖，若发现有同名人存在，则拒绝装入该元组。则拒绝装入该元组。第17页，共79页，编辑于2022年，星期三根据函数依赖的定义，可找出下面规律：根据函数依赖的定义，可找出下面规律：1、在一个关系模式中，如属性、在一个关系模式中，如属性X，Y有有1：1联系，则存在联系，则存在函数依赖函数依赖XYXY、YXYX，可记作，可记作X XY Y2 2、X X、Y Y是是1 1：m m联系，则存在联系，则存在YXYX，但，但X YX Y3 3、X X、Y Y是是n:mn:m联系，则联系，则X X、Y Y之间不存在任何函数依赖之间不存在任何函数依赖第18页，共79页，编辑于2022年，星期三平凡函数依赖与非平凡函数依赖于任一关系模式，平凡函数依赖都是必然于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别成立的，它不反映新的语义，因此若不特别声明，声明，我们总是讨论非平凡函数依赖我们总是讨论非平凡函数依赖。XYXY，但，但Y Y X X则称则称XYXY是是平凡的函数依赖平凡的函数依赖。否则，称。否则，称非平非平凡的函数依赖凡的函数依赖。第19页，共79页，编辑于2022年，星期三定义定义2：在在R（U）中，如果）中，如果XYXY，并且对于，并且对于X X的任何一个的任何一个真子集真子集XX，都有，都有 XY XY，则，则称称Y Y对对X X部分函数依赖部分函数依赖，否则，否则，称称Y Y完全函数依赖于完全函数依赖于X X。定义定义3：在在R（U）中，如果）中，如果XYXY，（，（Y Y X X），），YXYX，YZYZ，则，则称称Z Z对对X X传递函数依赖。传递函数依赖。第20页，共79页，编辑于2022年，星期三定义定义4：设设K为为R中的属性或属性组合，若中的属性或属性组合，若KUU则则K K为为R R的的候选码候选码。若候选码多于一个，则选定其中的一个为若候选码多于一个，则选定其中的一个为主码主码（PrimaryKey）。）。包含在任何一个候选码中的属性，叫做包含在任何一个候选码中的属性，叫做主属性主属性。不包含在。不包含在任何码中的属性称为任何码中的属性称为非主属性非主属性或非码属性。整个属性组是码，称或非码属性。整个属性组是码，称为为全码全码。定义定义5：关系模式关系模式R中属性或属性组中属性或属性组X并非并非R的码，但的码，但X是另一个关系模是另一个关系模式的码，则称式的码，则称X是是R的外部码（的外部码（ForeignKey），也称），也称外码外码。二、码二、码f第21页，共79页，编辑于2022年，星期三5.2.3 范式v范式是符合某一种级别的关系模式的集合。范式是符合某一种级别的关系模式的集合。v关系数据库中的关系必须满足一定的要求。满足不同关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。程度要求的为不同范式。v范式的种类：范式的种类：第一范式第一范式(1NF)第二范式第二范式(2NF)第三范式第三范式(3NF)BC范式范式(BCNF)第四范式第四范式(4NF)第五范式第五范式(5NF)第22页，共79页，编辑于2022年，星期三三、范式v各种范式之间存在联系：各种范式之间存在联系：v某一关系模式某一关系模式R为第为第n范式，可简记为范式，可简记为RnNF。第23页，共79页，编辑于2022年，星期三v1NF的定义的定义如果一个关系模式如果一个关系模式R的所有属性都是的所有属性都是不可分的基本数据项不可分的基本数据项，则则R1NF。v第一范式是对关系模式的最起码的要求。不满足第一范第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。式的数据库模式不能称为关系数据库。v但是满足第一范式的关系模式并不一定是一个好的关但是满足第一范式的关系模式并不一定是一个好的关系模式。系模式。第24页，共79页，编辑于2022年，星期三四、四、四、四、2NF2NF定义定义6：若：若R 1NF，且每一个非主属性完全函数依赖于码，且每一个非主属性完全函数依赖于码，则则R 2NF。SNOCNOGSDEPT SLOC第25页，共79页，编辑于2022年，星期三不是2NF的SLC不是一个好的关系模式(1)插入异常插入异常假设假设Sno95102，SdeptIS，SlocN的学生还未选课，的学生还未选课，因课程号是主属性，因此该学生的信息无法插入因课程号是主属性，因此该学生的信息无法插入SLC。(2)删除异常删除异常 假定某个学生本来只选修了假定某个学生本来只选修了3号课程这一门课。现在因身体不号课程这一门课。现在因身体不适，他连适，他连3号课程也不选修了。因课程号是主属性，此操作将号课程也不选修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。导致该学生信息的整个元组都要删除。第26页，共79页，编辑于2022年，星期三SLC不是一个好的关系模式(3)数据冗余度大数据冗余度大 如果一个学生选修了如果一个学生选修了10门课程，那么他的门课程，那么他的Sdept和和Sloc值就值就要重复存储了要重复存储了10次。次。(4)修改复杂修改复杂 例如学生转系，在修改此学生元组的例如学生转系，在修改此学生元组的Sdept值的同时，还值的同时，还可能需要修改住处（可能需要修改住处（Sloc）。如果这个学生选修了）。如果这个学生选修了K门课，门课，则必须无遗漏地修改则必须无遗漏地修改K个元组中全部个元组中全部Sdept、Sloc信息信息。第27页，共79页，编辑于2022年，星期三v原因原因 Sdept、Sloc部分函数依赖于码。部分函数依赖于码。v解决方法解决方法 SLC分解为两个关系模式，以消除这些部分函数依赖分解为两个关系模式，以消除这些部分函数依赖 SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）第28页，共79页，编辑于2022年，星期三v采用投影分解法将一个采用投影分解法将一个1NF的关系分解为多个的关系分解为多个2NF的的关系，可以在一定程度上减轻原关系，可以在一定程度上减轻原1NF关系中存在的插关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。入异常、删除异常、数据冗余度大、修改复杂等问题。v将一个将一个1NF关系分解为多个关系分解为多个2NF的关系，并不能完全消除关的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。系模式中的各种异常情况和数据冗余。第29页，共79页，编辑于2022年，星期三五、五、3NF定义定义7：若：若R 2NF，且，且R中任一非主属性都不传递函数依赖于码，则中任一非主属性都不传递函数依赖于码，则R 3NF。SNOCNOGSDEPT SLOCSNOSLSC上例上例SL分解为：分解为：SD（SNO，SDEPT）DL（SDEPT，SLOC）由于第三范式有效地消除了非主属性对码的部分和传递依赖，因而由于第三范式有效地消除了非主属性对码的部分和传递依赖，因而消除了一大类操作异常问题。因此，消除了一大类操作异常问题。因此，3NF在数据库设计中得到了广泛在数据库设计中得到了广泛应用。应用。第30页，共79页，编辑于2022年，星期三v若若R3NF，则，则R的每一个的每一个非主属性非主属性既不部分函数依赖于候选码既不部分函数依赖于候选码也不传递函数依赖于候选码。也不传递函数依赖于候选码。v如果如果R3NF，则，则R也是也是2NF。v采用投影分解法将一个采用投影分解法将一个2NF的关系分解为多个的关系分解为多个3NF的关系，的关系，可以在一定程度上解决原可以在一定程度上解决原2NF关系中存在的插入异常、删除关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。异常、数据冗余度大、修改复杂等问题。v 将一个将一个2NF关系分解为多个关系分解为多个3NF的关系后，并不能完全消除关系的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。模式中的各种异常情况和数据冗余。第31页，共79页，编辑于2022年，星期三六、六、BCNF定义定义8：R BCNF，当且仅当每个决定因素都是码（候选键）。，当且仅当每个决定因素都是码（候选键）。v 所有所有非主属性非主属性都完全函数依赖于每个候选码都完全函数依赖于每个候选码v 所有所有主属性主属性都完全函数依赖于每个不包含它的候选都完全函数依赖于每个不包含它的候选码码v 没有任何属性完全函数依赖于非码的任何一组属没有任何属性完全函数依赖于非码的任何一组属性性第32页，共79页，编辑于2022年，星期三例：例：关系模式关系模式STJ（S，T，J）中，）中，S表示学生，表示学生，T表示教师，表示教师，J表示教师，表示教师，J表表示课程。每一教师只教一门课。每门课有若干示课程。每一教师只教一门课。每门课有若干教师，某一学生选定某门课，教师，某一学生选定某门课，就对应一个固定的教师。就对应一个固定的教师。由语义可得到如下的函数依赖：由语义可得到如下的函数依赖：（S，J）TT；（S S，T T）JJ；T J T J关系有两个候选键，是（关系有两个候选键，是（S，J）和（）和（S，T）第33页，共79页，编辑于2022年，星期三S、T、J都是主属性，不存在非主属性，更不会有非主属性对键都是主属性，不存在非主属性，更不会有非主属性对键的传递依赖、部分依赖了，因此，的传递依赖、部分依赖了，因此，STJ关系满足第三范式。关系满足第三范式。但仍然存在问题：但仍然存在问题：上例分解为：上例分解为：ST（S，T）、）、TJ（T，J）第34页，共79页，编辑于2022年，星期三七、多值依赖七、多值依赖例：学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教例：学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。如下表：员可以讲授多门课程，每种参考书可以供多门课程使用。如下表：课程课程C教员教员T参考书参考书B物理物理李勇李勇普通物理学普通物理学物理物理李勇李勇光学原理光学原理物理物理李勇李勇物理习题集物理习题集物理物理王军王军普通物理学普通物理学物理物理王军王军光学原理光学原理物理物理王军王军物理习题集物理习题集数学数学李勇李勇数学分析数学分析数学数学李勇李勇微分方程微分方程数学数学李勇李勇高等代数高等代数数学数学张平张平数学分析数学分析数学数学张平张平微分方程微分方程数学数学张平张平高等代数高等代数 第35页，共79页，编辑于2022年，星期三课课程程C教教员员T参参考考书书B物理物理数学数学计算数学计算数学李李勇勇王王军军李李勇勇张张平平张张平平周周峰峰普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析第36页，共79页，编辑于2022年，星期三vTeachingBCNF:vTeach具有唯一候选码具有唯一候选码(C，T，B)，即全码即全码vTeaching模式中存在的问题模式中存在的问题(1)数据冗余度大：有多少名任课教师，参考书就要存储多少数据冗余度大：有多少名任课教师，参考书就要存储多少次次 第37页，共79页，编辑于2022年，星期三 (2)插入操作复杂：插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组参照书，就必须插入多少个元组例如物理课增加一名教师刘关，需要插入两个元组：例如物理课增加一名教师刘关，需要插入两个元组：（物理，刘关，普通物理学）（物理，刘关，普通物理学）（物理，刘关，光学原理）（物理，刘关，光学原理）第38页，共79页，编辑于2022年，星期三(3)删除操作复杂：删除操作复杂：某一门课要去掉一本参考书，该某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组课程有多少名教师，就必须删除多少个元组(4)修改操作复杂：修改操作复杂：某一门课要修改一本参考书，该某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组课程有多少名教师，就必须修改多少个元组 v产生原因产生原因存在多值依赖存在多值依赖第39页，共79页，编辑于2022年，星期三定义定义9：关系模式关系模式R（U），），X，Y，Z是是U的子集，并且的子集，并且Z=U-X-Y。关系模式。关系模式R(U)中多值依赖中多值依赖XY成立，当且仅当对成立，当且仅当对R（U）的任一关系）的任一关系r，给定的一对（，给定的一对（x，z)值，有一组值，有一组Y的值，的值，这组值仅仅决定于这组值仅仅决定于x值而与值而与z值无关。值无关。若若XY，而，而Z=即即Z为空，则称为空，则称XY为为平凡的多值依赖平凡的多值依赖。第40页，共79页，编辑于2022年，星期三多值依赖性质：多值依赖性质：对称性。若对称性。若XY，则，则XZ，其中，其中Z=U。传递性。若传递性。若XY，则，则XY。函数依赖可看作是多值依赖的特殊情况。若函数依赖可看作是多值依赖的特殊情况。若XY，则，则XY。若若XY，X，则，则XY。若若XY，X，则，则XY。若若XY，X，则，则XY，XY。第41页，共79页，编辑于2022年，星期三多值依赖的对称性 XiZi1Zi2ZimYi1Yi2Yin第42页，共79页，编辑于2022年，星期三多值依赖的对称性 物物理理普通物理学普通物理学光学原理光学原理物理习题集物理习题集李勇李勇王军王军第43页，共79页，编辑于2022年，星期三多值依赖与函数依赖的区别(1)有效性v多值依赖的有效性与属性集的范围有关多值依赖的有效性与属性集的范围有关若若XY在在U上成立，则在上成立，则在W（X Y W U）上一定成立；反之）上一定成立；反之则不然，即则不然，即XY在在W（W U）上成立，在）上成立，在U上并不一定成上并不一定成立立多值依赖的定义中不仅涉及属性组多值依赖的定义中不仅涉及属性组 X和和 Y，而且涉及，而且涉及U中其余属中其余属性性Z。一般地，在一般地，在R（U）上若有）上若有XY在在W（W U）上成立，则）上成立，则称称XY为为R（U）的嵌入型多值依赖）的嵌入型多值依赖第44页，共79页，编辑于2022年，星期三多值依赖与函数依赖的区别v只要在只要在R（U）的任何一个关系）的任何一个关系r中，元组在中，元组在X和和Y上的值上的值满足定义满足定义5.l（函数依赖），（函数依赖），则函数依赖则函数依赖XY在任何属性集在任何属性集W（X Y W U）上成）上成立立。第45页，共79页，编辑于2022年，星期三(2)若函数依赖若函数依赖XY在在R（U）上成立，则对于任何）上成立，则对于任何Y Y均有均有XY 成立成立多值依赖多值依赖XY若在若在R(U)上成立，不能断言对上成立，不能断言对于任何于任何Y Y有有XY 成立成立多值依赖与函数依赖的区别第46页，共79页，编辑于2022年，星期三八、八、4NF定义定义10：关系模式：关系模式R 1NF，如果对于，如果对于R的每个非平凡多的每个非平凡多值依赖值依赖XY（Y X），），X都含有码，则称都含有码，则称R 4NF。第47页，共79页，编辑于2022年，星期三v关系数据库的规范化理论是数据库逻辑设计关系数据库的规范化理论是数据库逻辑设计的工具。的工具。v一个关系只要其分量都是不可分的数据项，一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规它就是规范化的关系，但这只是最基本的规范化。范化。v规范化程度可以有多个不同的级别规范化程度可以有多个不同的级别九、规范化小结九、规范化小结九、规范化小结九、规范化小结第48页，共79页，编辑于2022年，星期三v规范化程度过低的关系不一定能够很好地描述现实规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题数据冗余等问题v一个低一级范式的关系模式，通过模式分解可以转一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程换为若干个高一级范式的关系模式集合，这种过程就叫就叫关系模式的规范化关系模式的规范化第49页，共79页，编辑于2022年，星期三1NF消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖2NF消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖3NF消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖BCNF消除非平凡且非函数依赖的多值依赖消除非平凡且非函数依赖的多值依赖4NF第50页，共79页，编辑于2022年，星期三规范化的基本思想消除不合适的数据依赖，各关系模式达到某种程度的“分离”采用“一事一地”的模式设计原则 让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去所谓规范化实质上是概念的单一化第51页，共79页，编辑于2022年，星期三v不能说规范化程度越高的关系模式就越好不能说规范化程度越高的关系模式就越好v在设计数据库模式结构时，必须对现实世界的实际情况在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式反映现实世界的模式v上面的规范化步骤可以在其中任何一步终止上面的规范化步骤可以在其中任何一步终止第52页，共79页，编辑于2022年，星期三练习题v设有关系模式：授课表（课程号，课程名，学分，授课教师号，教师名，授课时数），其语义为：一门课程可以由多名教师讲授。指出此关系模式的候选码，判断此关系模式属于第几范式，若不是第三范式，将其分解为第三范式。第53页，共79页，编辑于2022年，星期三5.3 数据依赖的公理系统v逻辑蕴含逻辑蕴含定义定义9.11 对于满足一组对于满足一组函数依赖函数依赖 F 的关系模的关系模式式R，其任何一个关系，其任何一个关系r，若函数依，若函数依赖赖XY都成立都成立,则称则称 F逻辑蕴含逻辑蕴含X Y第54页，共79页，编辑于2022年，星期三Armstrong公理系统v一套推理规则，是模式分解算法的理论基础一套推理规则，是模式分解算法的理论基础v用途用途求给定关系模式的码求给定关系模式的码从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖第55页，共79页，编辑于2022年，星期三1.Armstrong公理系统 关系模式关系模式R 来说有以下的推理规则：来说有以下的推理规则：Al.自反律自反律（Reflexivity）：）：若若Y X U，则，则X Y为为F所蕴含。所蕴含。A2.增广律增广律（Augmentation）：若）：若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ为为F所蕴含。所蕴含。A3.传递律传递律（Transitivity）：若）：若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所蕴含。所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于的使用并不依赖于F第56页，共79页，编辑于2022年，星期三定理 5.l Armstrong推理规则是正确的（l）自反律）自反律:若若Y X U，则，则X Y为为F所蕴含所蕴含证证:设设Y X U 对对R 的任一关系的任一关系r中的任意两个元组中的任意两个元组t，s：若若tX=sX，由于，由于Y X，有，有ty=sy，所以所以XY成立成立.自反律得证自反律得证第57页，共79页，编辑于2022年，星期三(2)增广律增广律:若若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ 为为F所蕴含。所蕴含。证：证：设设XY为为F所蕴含，且所蕴含，且Z U。设设R 的任一关系的任一关系r中任意的两个元组中任意的两个元组t，s；若若tXZ=sXZ，则有，则有tX=sX和和tZ=sZ；由由XY，于是有，于是有tY=sY，所以，所以tYZ=sYZ，所以，所以XZYZ为为F所蕴含所蕴含.增广律得证。增广律得证。第58页，共79页，编辑于2022年，星期三(3)传递律：若传递律：若XY及及YZ为为F所蕴含，则所蕴含，则 XZ为为 F所蕴含。所蕴含。证：证：设设XY及及YZ为为F所蕴含。所蕴含。对对R 的任一关系的任一关系 r中的任意两个元组中的任意两个元组 t，s。若若tX=sX，由于，由于XY，有，有 tY=sY；再由再由YZ，有，有tZ=sZ，所以，所以XZ为为F所蕴含所蕴含.传递律得证。传递律得证。第59页，共79页，编辑于2022年，星期三2.导出规则1.根据根据A1，A2，A3这三条推理规则可以得到这三条推理规则可以得到下面三条推理规则：下面三条推理规则：合并规则合并规则：由：由XY，XZ，有，有XYZ。（A2，A3）伪传递规则伪传递规则：由：由XY，WYZ，有，有XWZ。（A2，A3）分解规则分解规则：由：由XY及及 Z Y，有，有XZ。（A1，A3）第60页，共79页，编辑于2022年，星期三导出规则2.根据合并规则和分解规则，可得引理根据合并规则和分解规则，可得引理5.1 引理引理5.l XA1 A2Ak成立的充分必要条件是成立的充分必要条件是XAi成立（成立（i=l，2，k）。）。第61页，共79页，编辑于2022年，星期三3.函数依赖闭包定义定义5.l2 在关系模式在关系模式R中为中为F所逻辑蕴含所逻辑蕴含的函数依赖的全体叫作的函数依赖的全体叫作 F的闭包的闭包，记为，记为F+。定义定义5.13 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U，XF+=A|XA能由能由F 根据根据Armstrong公理导出公理导出，XF+称为称为属性集属性集X关于函数依赖集关于函数依赖集F 的闭包的闭包第62页，共79页，编辑于2022年，星期三F的闭包 F=X Y,Y Z,F+计算是NP完全问题，X A1A2.An F+=X ,Y ,Z,XY ,XZ ,YZ ,XYZ ,X X,Y Y,Z Z,XY X,XZ X,YZ Y,XYZ X,X Y,Y Z,XY Y,XZ Y,YZ Z,XYZ Y,X Z,Y YZ,XY Z,XZ Z,YZ YZ,XYZ Z,X XY,XY XY,XZ XY,XYZ XY,X XZ,XY YZ,XZ XZ,XYZ YZX YZ,XY XZ,XZ XY,XYZ XZ,X ZYZ,XY XYZ,XZ XYZ,XYZ XYZ 第63页，共79页，编辑于2022年，星期三关于闭包的引理v引理引理5.2 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U，XY能由能由F 根据根据Armstrong公理导出的充分必要公理导出的充分必要条件是条件是Y XF+v用途用途 将判定将判定XY是否能由是否能由F根据根据Armstrong公理导出的问题，公理导出的问题，就转就转化为求出化为求出XF+，判定，判定Y是否为是否为XF+的子集的问题的子集的问题第64页，共79页，编辑于2022年，星期三求闭包的算法算法算法5.l 求属性集求属性集X（X U）关于）关于U上的函数依上的函数依 赖集赖集F 的闭包的闭包XF+输入：输入：X，F输出：输出：XF+步骤：步骤：（1）令）令X（0）=X，i=0（2）求）求B，这里，这里B=A|(V)(W)(VW F V X（i）A W)；（3）X（i+1）=BX（i）第65页，共79页，编辑于2022年，星期三（4）判断）判断X（i+1）=X（i）吗吗?（5）若相等或）若相等或X（i）=U,则则X（i）就是就是XF+,算法终止。算法终止。（6）若否，则）若否，则 i=i+l，返回第（，返回第（2）步。）步。对于算法对于算法5.l，令令ai=|X（i）|，ai 形成一个步长大形成一个步长大于于1的严格递增的序列，序列的上界是的严格递增的序列，序列的上界是|U|，因，因此该算法最多此该算法最多|U|-|X|次循环就会终止次循环就会终止。第66页，共79页，编辑于2022年，星期三 U=A,B,C,D;F=A B,BC D;vA+=AB.vC+=C.v(AC)+=ABCD.ExampleACB第67页，共79页，编辑于2022年，星期三 ExampleACDBU=A,B,C,D;A B,BC D.(AC)+=ABCD.第68页，共79页，编辑于2022年，星期三例例1 已知关系模式已知关系模式R，其中，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（求（AB）F+。解解 设设X（0）=AB；(1)计算计算X（1）:逐一的扫描逐一的扫描F集合中各个函数依赖，集合中各个函数依赖，找左部为找左部为A，B或或AB的函数依赖。得到两个：的函数依赖。得到两个：ABC，BD。于是于是X（1）=ABCD=ABCD。第69页，共79页，编辑于2022年，星期三(2)因为因为X（0）X（1），所以再找出左部为，所以再找出左部为ABCD子集的那子集的那些函数依赖，又得到些函数依赖，又得到ABC，BD，CE，ACB，于是于是X（2）=X（1）BCDE=ABCDE。(3)因为因为X（2）=U，算法终止，算法终止所以（所以（AB）F+=ABCDE。第70页，共79页，编辑于2022年，星期三4.Armstrong公理系统的有效性与完备性v有效性有效性：由：由F出发根据出发根据Armstrong公理推导出来的每一公理推导出来的每一个函数依赖一定在个函数依赖一定在F+中中 /*Armstrong正确正确v完备性完备性：F+中的每一个函数依赖，必定可以由中的每一个函数依赖，必定可以由F出发根据出发根据Armstrong公理推导出来公理推导出来 /*Armstrong公理够用，完全公理够用，完全第71页，共79页，编辑于2022年，星期三5.函数依赖集等价定义定义5.14 如果如果G+=F+，就说函数依赖集，就说函数依赖集F覆覆盖盖G（F是是G的覆盖，或的覆盖，或G是是F的覆盖），或的覆盖），或F与与G等价等价。第72页，共79页，编辑于2022年，星期三函数依赖集等价的充要条件引理引理9.3 F+=G+的充分必要条件是的充分必要条件是 F G+，和，和G F+证:必要性显然，只证充分性。（1）若FG+，则XF+XG+。（2）任取XYF+则有 Y XF+XG+。所以XY (G+）+=G+。即F+G+。（3）同理可证G+F+，所以F+=G+。第73页，共79页，编辑于2022年，星期三函数依赖集等价v要要判判定定F G+，只只须须逐逐一一对对F中中的的函函数数依依赖赖XY，考考察察 Y 是是否否属属于于XG+就就行行了了。因因此此引引理理9.3 给给出出了了判判断断两两个个函函数数依依赖赖集集等等价价的的可可行算法。行算法。第74页，共79页，编辑于2022年，星期三6.最小依赖集 定定义义5.15 如如果果函函数数依依赖赖集集F满满足足下下列列条条件件，则则称称F为为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。一个极小函数依赖集。亦称为最小依赖集或最小覆盖。(1)F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。(2)F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得F与与F-XA等价。等价。(3)F中不存在这样的函数依赖中不存在这样的函数依赖XA，X有真有真 子集子集Z使得使得F-XAZA与与F等价。等价。第75页，共79页，编辑于2022年，星期三最小依赖集例例2 对于对于5.l节中的关系模式节中的关系模式S，其中：，其中：U=SNO，SDEPT，MN，CNAME，G，F=SNOSDEPT，SDEPTMN，（SNO，CNAME）G 设设F=SNOSDEPT，SNOMN，SDEPTMN，(SNO，CNAME)G，(SNO，SDEPT)SDEPTF是最小覆盖，而是最小覆盖，而F 不是。不是。因为：因为：F-SNOMN与与F 等价等价 F-(SNO，SDEPT)SDEPT也与也与F 等价等价 F-(SNO，SDEPT)SDEP