《教学课件第六章关系数据理论》由会员分享，可在线阅读，更多相关《教学课件第六章关系数据理论（80页珍藏版）》请在金锄头文库上搜索。
1、数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论第六章 关系数据理论6.1问题的提出问题的提出6.2规范化规范化6.3数据依赖的公理系统数据依赖的公理系统*6.4模式的分解模式的分解数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.1问题的提出问题的提出关系数据库逻辑设计关系数据库逻辑设计针对具体问题，如何构造一个适合于它的数据模式针对具体问题，如何构造一个适合于它的数据模式数据库逻辑设计的工具数据库逻辑设计的工具关系数据库的规范化理论关系数据库的规范化理论v关系关系：描述实体、属性、实体间的联系。：描述实体、属性、实体间的联系。从形式上看，它是一张二维表
2、，是所涉及属性的笛卡尔积的一从形式上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。个子集。v关系模式关系模式：用来定义关系。：用来定义关系。v关系数据库关系数据库：基于关系模型的数据库，利用关系来描述现实世界。：基于关系模型的数据库，利用关系来描述现实世界。从形式上看，它由一组关系组成。从形式上看，它由一组关系组成。v关系数据库的模式关系数据库的模式：定义这组关系的关系模式的全体。：定义这组关系的关系模式的全体。一、概念回顾一、概念回顾数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论二、关系模式的形式化定义二、关系模式的形式化定义关系模式由五部分组成，即它是一个五元组
3、：关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)R：关系名关系名U：组成该关系的属性名集合组成该关系的属性名集合D：属性组属性组U中属性所来自的域中属性所来自的域DOM：属性向域的映象集合：属性向域的映象集合F：属性间数据的依赖关系集合属性间数据的依赖关系集合数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论三、什么是数据依赖三、什么是数据依赖1.完整性约束的表现形式完整性约束的表现形式限定属性取值范围：例如学生成绩必须在限定属性取值范围：例如学生成绩必须在0-100之间之间定义属性定义属性值值间的相互关连（主要体现于值的间的相互关连（主要体现于值的相等与否相
4、等与否），这就是数），这就是数据依赖，它是数据库模式设计的关键。据依赖，它是数据库模式设计的关键。2.数据依赖数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系；系；是现实世界属性间相互联系的抽象是数据内在的性质是是现实世界属性间相互联系的抽象是数据内在的性质是语义语义的体现。的体现。3.数据依赖的类型数据依赖的类型函数依赖（函数依赖（FunctionalDependency，简记为，简记为FD）多值依赖（多值依赖（MultivaluedDependency，简记为，简记为MVD）其他其他数据库系统概论数据库系统概论第
5、六章第六章 关系数据理论关系数据理论四、关系模式的简化表示四、关系模式的简化表示关系模式关系模式R（U,D,DOM,F）简化为一个三元组：简化为一个三元组：R（U,F）当且仅当当且仅当U上的一个关系上的一个关系r满足满足F时，时，r称为关称为关系系模式模式R（U,F）的一个）的一个关系关系数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论五、数据依赖对关系模式的影响五、数据依赖对关系模式的影响例：描述学校的数据库：例：描述学校的数据库：学生的学号（学生的学号（Sno）、所在系（）、所在系（Sdept）系主任姓名（系主任姓名（Mname）、课程名（）、课程名（Cname）成绩（成
6、绩（Grade）单一单一的关系模式的关系模式：StudentUSno,Sdept,Mname,Cname,Grade学校数据库的语义：学校数据库的语义：一个系有若干学生，一个系有若干学生，一个学生只属于一个系；一个学生只属于一个系；一个系只有一名主任；一个系只有一名主任；一个学生可以选修多门课程，一个学生可以选修多门课程，每门课程有若干学生选修；每门课程有若干学生选修；每个学生所学的每门课程都有一个成绩。每个学生所学的每门课程都有一个成绩。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论数据依赖对关系模式的影响数据依赖对关系模式的影响属性组属性组U上的一组函数依赖上的一组函数
7、依赖F：FSnoSdept,SdeptMname,(Sno,Cname)Grade SnoCnameSdeptMnameGrade数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论插入异常（插入异常（InsertionAnomalies）该插的数据插不进去该插的数据插不进去关系模式关系模式Student中存在的问题中存在的问题数据冗余太大数据冗余太大浪费大量的存储空间浪费大量的存储空间例：每一个系主任的姓名重复出现例：每一个系主任的姓名重复出现例：某系更换系主任后，系统必须例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组。修改与该系学生有关的每一个元组。例，如果一个
8、系刚成立，尚无学生，我们例，如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数就无法把这个系及其系主任的信息存入数据库。据库。删除异常（删除异常（DeletionAnomalies）不该删除的数据不得不删不该删除的数据不得不删例，如果某个系的学生全部毕业了，例，如果某个系的学生全部毕业了，我我们在删除该系学生信息的同时，把这个们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。系及其系主任的信息也丢掉了。Student(Sno,Sdept,Mname,Cname,Grade) 更新异常（更新异常（Update Anomalies）数据冗余数据冗余 ，更新数据时，维护
9、数据完整性代价大。更新数据时，维护数据完整性代价大。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论结论：结论：Student关系模式不是一个好的模式。关系模式不是一个好的模式。“好好”的模式：的模式：不会发生插入异常、删除异常、更新异常，数据冗余不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。应尽可能少。原因：原因：由存在于模式中的由存在于模式中的某些数据依赖某些数据依赖引起的引起的.解决方法：解决方法：通过通过分解分解关系模式来消除其中不合适的数据依赖。关系模式来消除其中不合适的数据依赖。分解成三个关系模式分解成三个关系模式:S(SNO,SDEPT,SNODEP
10、T);SG(SNO,CNAME,G,(SNO,CNAME)G);DEPT(SDEPT,MN,SDEPTMN);数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.2 6.2 规范化规范化规范化理论规范化理论正是用来改造关系模式，通过分解关系模式来消除其中正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据冗余问题。问题。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.2.1函数依赖函数依赖一、函数依赖一、函数依赖定义定义6.1设设R(U)是
11、一个属性集是一个属性集U上的关系模式，上的关系模式，X和和Y是是U的子集。若的子集。若对于对于R(U)的的任意任意一个可能的关系一个可能的关系r，r中不可能存在两个元组在中不可能存在两个元组在X上上的属性值相等，的属性值相等，而在而在Y上的属性值不等，上的属性值不等，则称则称“X函数确定函数确定Y”或或“Y函数依赖于函数依赖于X”，记作，记作:XY。X称为这个函数依赖的称为这个函数依赖的决定属性集决定属性集(决定因素决定因素)。Y=f(x)说明：说明：1.函数依赖不是指关系模式函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指的某个或某些关系实例满足的约束条件，而是指R的的所有
12、关系实例所有关系实例均要满足的约束条件。均要满足的约束条件。2.函数依赖是函数依赖是语义范畴语义范畴的概念。只能根据数据的语义来确定函数依赖。的概念。只能根据数据的语义来确定函数依赖。例如例如“姓名姓名年龄年龄”这个函数依赖只有在不允许有同名人的条件下成立这个函数依赖只有在不允许有同名人的条件下成立3.数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖函数依赖“姓名姓名年龄年龄”成立。所插入的元组必须满足规定的函数依赖，若成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，发现有同名人存在，则拒
13、绝装入该元组。则拒绝装入该元组。6.2 6.2 规范化规范化数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例例:Student(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有假设不允许重名，则有:SnoSsex，SnoSage,SnoSdept，SnoSname,SnameSsex，SnameSageSnameSdept若若XY，并且，并且YX,则记为则记为XY。若若Y不函数依赖于不函数依赖于X,则记为则记为XY。但但SsexSage数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论二、平凡函数依赖与非平凡函数依赖二、平凡函数依赖与
14、非平凡函数依赖在关系模式在关系模式R(U)中，对于中，对于U的的子集子集X和和Y，如果如果XY，但，但Y X，则称，则称XY是是平凡的函数依赖平凡的函数依赖例：在关系例：在关系SC(Sno,Cno,Grade)中，中，非平凡函数依赖：非平凡函数依赖：(Sno,Cno)Grade平凡函数依赖：平凡函数依赖：(Sno,Cno)Sno(Sno,Cno)Cno对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明，语义，因此若不特别声明， 我们总是讨论非平凡函数依赖。我们总是讨论非平凡函数依赖。若若XY，但，但Y X,
15、则称则称XY是是非平凡的函数依赖非平凡的函数依赖数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论三、完全函数依赖与部分函数依赖三、完全函数依赖与部分函数依赖定义定义6.2在关系模式在关系模式R(U)中，如果中，如果XY，并且对于，并且对于X的任何一个真子的任何一个真子集集X，都有，都有XY,则称则称Y完全函数依赖于完全函数依赖于X，记作，记作XFY。若若XY，但，但Y不完全函数依赖于不完全函数依赖于X，则称，则称Y部分函数依赖部分函数依赖于于X，记作，记作XPY。例例:在关系在关系SC(Sno,Cno,Grade)中，中，由于：由于：SnoGrade，CnoGrade，因此：
16、因此：(Sno,Cno)FGrade数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论四、传递函数依赖四、传递函数依赖注注:如果如果YX，即即XY，则，则Z直接依赖直接依赖于于X。定义定义6.3在关系模式在关系模式R(U)中，如果中，如果XY，YZ，且，且Y X，YX，则称，则称Z传递函数依赖传递函数依赖于于X。例例:在关系在关系Std(Sno,Sdept,Mname)中，有：中，有：SnoSdept，SdeptMnameMname传递函数依赖于传递函数依赖于Sno数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.2.2码码定义定义6.4设设K为关系模式为关
17、系模式R中的属性或属性组合。若中的属性或属性组合。若KFU，则，则K称为称为R的一个的一个侯选码侯选码（CandidateKey）。若关系模式）。若关系模式R有多个有多个候选码，则选定其中的一个做为候选码，则选定其中的一个做为主码主码（Primarykey）。）。n主属性与非主属性主属性与非主属性n全码全码(ALLKEY)定义定义6.5关系模式关系模式R 中属性或属性组中属性或属性组X 并非并非R的码，但的码，但X 是另一个是另一个关系模式的码，则称关系模式的码，则称X 是是R 的的外部码（外部码（Foreignkey）也称外码也称外码v主码又和外部码一起提供了表示关系间联系的手段。主码又和外
18、部码一起提供了表示关系间联系的手段。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.2.3范式范式v范式是符合某一种级别的关系模式的集合。范式是符合某一种级别的关系模式的集合。v关系数据库中的关系必须满足一定的要求。满足不同程度要求的关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。为不同范式。v范式的种类：范式的种类：第一范式第一范式(1NF)第二范式第二范式(2NF)第三范式第三范式(3NF)BC范式范式(BCNF)第四范式第四范式(4NF)第五范式第五范式(5NF)v各种范式之间存在联系：各种范式之间存在联系：v某一关系模式某一关系模式R为第为第n
19、范式，可简记为范式，可简记为:RnNF。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.2.42NFv1NF的定义的定义如果一个关系模式如果一个关系模式R的所有属性都是的所有属性都是不可分的基本数据项不可分的基本数据项，则，则R1NF。v第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。不能称为关系数据库。v但是满足第一范式的关系模式并不一定是一个好的关系模式。但是满足第一范式的关系模式并不一定是一个好的关系模式。例例:关系模式关系模式S-L-C(Sno,Sdept,Sloc,C
20、no,Grade)Sloc为学生住处，假设每个系的学生住在同一个地方。为学生住处，假设每个系的学生住在同一个地方。函数依赖包括：函数依赖包括：(Sno,Cno)FGradeSnoSdept(Sno,Cno)PSdeptSnoSloc(Sno,Cno)PSlocSdeptSlocSnoCnoGradeSdeptSlocS-L-CS-L-C的码为的码为(Sno,Cno)S-L-C满足第一范式。满足第一范式。非主属性非主属性Sdept和和Sloc部分函数依赖于码部分函数依赖于码(Sno,Cno)数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论S-L-C(Sno,Sdept,Sloc
21、,Cno,Grade)不是一个好的关系模式不是一个好的关系模式(1)插入异常插入异常假设假设Sno95102，SdeptIS，SlocN的学生还未选课，因课程的学生还未选课，因课程号是主属性，因此该学生的信息无法插入号是主属性，因此该学生的信息无法插入S-L-C。(2)删除异常删除异常假定某个学生本来只选修了假定某个学生本来只选修了3号课程这一门课。现在因身体不号课程这一门课。现在因身体不适，他连适，他连3号课程也不选修了。因课程号是主属性，此操作将号课程也不选修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。导致该学生信息的整个元组都要删除。(3)数据冗余度大数据冗余度大如果
22、一个学生选修了如果一个学生选修了10门课程，那么他的门课程，那么他的Sdept和和Sloc值就要重值就要重复存储了复存储了10次。次。(4)修改复杂修改复杂例如学生转系，在修改此学生元组的例如学生转系，在修改此学生元组的Sdept值的同时，还可能值的同时，还可能需要修改住处（需要修改住处（Sloc）。如果这个学生选修了）。如果这个学生选修了K门课，则必须门课，则必须无遗漏地修改无遗漏地修改K个元组中全部个元组中全部Sdept、Sloc信息。信息。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论v函数依赖图：函数依赖图：SdeptSlocSnoSLSnoCnoGradeSCv原
23、因原因Sdept、Sloc部分函数依赖于码。部分函数依赖于码。v解决方法解决方法S-L-C分解为两个关系模式，以消除这些部分函数依赖分解为两个关系模式，以消除这些部分函数依赖SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例：例：SLC(Sno,Sdept,Sloc,Cno,Grade)1NFSLC(Sno,Sdept,Sloc,Cno,Grade) 2NFSC（Sno，Cno，Grade）2NFSL（Sno，Sdept，Sloc）2NF2NF2NF定义定义定义定义6.6若关系模式若关系模式R1NF，并且每
24、一个，并且每一个非主非主属性都属性都完全完全函数依赖函数依赖于于R的码，则的码，则R2NF。v采用投影分解法将一个采用投影分解法将一个1NF的关系分解为多个的关系分解为多个2NF的关系，可以的关系，可以在一定程度上减轻原在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。据冗余度大、修改复杂等问题。v将一个将一个1NF关系分解为多个关系分解为多个2NF的关系，并不能完全消除关系模的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。式中的各种异常情况和数据冗余。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据
25、理论6.2.53NF例：例：2NF关系模式关系模式SL(Sno,Sdept,Sloc)中中函数依赖：函数依赖：SnoSdept，SnoSloc，SdeptSlocSloc传递函数依赖于传递函数依赖于Sno，即，即SL中存在非主属性对码的传递函数依赖。中存在非主属性对码的传递函数依赖。SdeptSlocSnoSL解决方法：解决方法：采用投影分解法，把采用投影分解法，把SL分解为两个关系模式，以消除传递函数分解为两个关系模式，以消除传递函数依赖：依赖：SD（Sno，Sdept）DL（Sdept，Sloc）SD的码为的码为Sno，DL的码为的码为Sdept。SnoSdeptSDSdeptSlocDL
26、数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例，例，SL(Sno,Sdept,Sloc)2NFSL(Sno,Sdept,Sloc) 3NFSD（Sno，Sdept）3NFDL（Sdept，Sloc）3NF3NF的定义的定义定义定义6.8关系模式关系模式R中若不存在这样的码中若不存在这样的码X、属性组、属性组Y及及非非主属性主属性Z（Z Y）, 使得使得XY，YX，YZ，成立，则称，成立，则称R3NF。v若若R3NF，则则R的每一个的每一个非主属性非主属性既不部分函数依赖于候选码也不既不部分函数依赖于候选码也不传递函数依赖于候选码。传递函数依赖于候选码。v如果如果R3NF，
27、则则R也是也是2NF。v采用投影分解法将一个采用投影分解法将一个2NF的关系分解为多个的关系分解为多个3NF的关系，可以在一的关系，可以在一定程度上解决原定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。大、修改复杂等问题。v将一个将一个2NF关系分解为多个关系分解为多个3NF的关系后，并不能完全消除关系模式的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。中的各种异常情况和数据冗余。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.2.6BC范式（范式（BCNF）定义定义6.9设关系模式设
28、关系模式R1NF，如果对于，如果对于R的的每个函数依赖每个函数依赖XY，若，若Y不属于不属于X，则，则X必含有候选码，那么必含有候选码，那么RBCNF。若若RBCNFv每一个决定属性集（因素）都包含（候选）码每一个决定属性集（因素）都包含（候选）码vR中的所有属性（主，非主属性）都完全函数依赖于码中的所有属性（主，非主属性）都完全函数依赖于码vR3NF（证明）证明）v若若R3NF则则R不一定不一定BCNF证明：采用反证法。设证明：采用反证法。设R R不是不是3NF3NF。则必然存在如下条件的函数依赖，则必然存在如下条件的函数依赖，XYXY（Y Y X X），），YZYZ，其中，其中X X是含有
29、码的是含有码的属性，属性，Y Y是任意属性组，是任意属性组，Z Z是非主属是非主属性，性，Z Z Y Y，这样，这样YZYZ函数依赖的决函数依赖的决定因素定因素Y Y不包含候选码，这与不包含候选码，这与BCNFBCNF范范式的定义相矛盾，所以如果式的定义相矛盾，所以如果R R BCNFBCNF，则，则R R也是也是3NF3NF数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例例1对关系模式对关系模式C、SC、S进行分析。进行分析。C(Cno,Cname,Pcno)SC(Sno,Cno,Grade)S(Sno,Sname,Sdept,Sage)它只有一个码它只有一个码CnoCn
30、o，这里没有任何属性对，这里没有任何属性对CnoCno部分依赖或传递依赖，所以部分依赖或传递依赖，所以C C3NF3NF。同。同时时C C中中CnoCno是唯一的决定因素，所以是唯一的决定因素，所以C CBCNFBCNF。假定假定SnameSname也具有唯一性，那么也具有唯一性，那么S S就有两个码，这两个码都由单个属性就有两个码，这两个码都由单个属性组成，彼此不相交。其他属性不存在对码的传递依赖与部分依赖，所组成，彼此不相交。其他属性不存在对码的传递依赖与部分依赖，所以以S S3NF3NF。同时。同时S S中除中除SnoSno，SnameSname外没有其他决定因素，所以外没有其他决定因素
31、，所以S SBCNFBCNF。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例例2：关系模式：关系模式SJP(S,J,P)中，中，S是学生，是学生，J表示课程，表示课程，P表示名次。表示名次。每一个学生选修每门课程的成绩有一定的名次，每门课程中每一名次每一个学生选修每门课程的成绩有一定的名次，每门课程中每一名次只有一个学生（即没有并列名次）。由语义可得到下面的函数依赖只有一个学生（即没有并列名次）。由语义可得到下面的函数依赖:(S，J)P；(J，P)S候选码为候选码为:(S，J)与与(J，P)这两个码各由两个属性组成，而且它们是相交的。这个关系模式中这两个码各由两个属性组成
32、，而且它们是相交的。这个关系模式中显然没有属性对码传递依赖或部分依赖。所以显然没有属性对码传递依赖或部分依赖。所以SJP3NF，而且除，而且除(S,J)与与(J,P)以外没有其它决定因素，所以以外没有其它决定因素，所以SJPBCNF数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例例3：在关系模式：在关系模式STJ（S，T，J）中，）中，S表示学生，表示学生，T表示教师，表示教师，J表示课程。表示课程。每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定
33、了所选课的名称确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称。由语义可得到下面的函数依赖由语义可得到下面的函数依赖:(S，J)T，(S，T)J，TJv候选码为：候选码为：(S，J)和和(S，T)vS、T、J都是主属性，所以都是主属性，所以STJ3NFvTJ，T是决定属性集，是决定属性集，T不是候选码不是候选码STJBCNFSJTSTJ解决方法：解决方法：将将STJ分解为二个关系模式：分解为二个关系模式：SJ(S，J)BCNF，TJ(T，J)BCNFTJTJSJST没有没有任何属性任何属性对码的部分函数依赖和传递函数依赖对码的部分函数依赖和传递函数依赖数据库系统概论数据库系统
34、概论第六章第六章 关系数据理论关系数据理论练习题练习题指明下列关系模式属于第几范式指明下列关系模式属于第几范式.1.1.R(X,Y,Z) F=XYZR(X,Y,Z) F=XYZ2.2.R(X,Y,Z) F=YZ,XZYR(X,Y,Z) F=YZ,XZY3.3.R(X,Y,Z) F=YZ,YX,XYZR(X,Y,Z) F=YZ,YX,XYZ4.4.R(X,Y,Z) F=XY,XZR(X,Y,Z) F=XY,XZ5.5.R(W,X,Y,Z) F=XZ,WXYR(W,X,Y,Z) F=XZ,WXY数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论3NF与与BCNF的关系与区别的关系与
35、区别v如果关系模式如果关系模式RBCNF，必定有，必定有R3NFv如果如果R3NF，且，且R只有一个候选码，则只有一个候选码，则R必属于必属于BCNF。v3NF和和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度是在函数依赖的条件下对模式分解所能达到的分离程度的测度。的测度。v一个模式中的关系模式如果都属于一个模式中的关系模式如果都属于BCNF，那么在函数依赖范畴内，那么在函数依赖范畴内，它已实现了彻底的分离，已消除了插入和删除的异常。它已实现了彻底的分离，已消除了插入和删除的异常。v3NF的的“不彻底不彻底”性表现在可能存在主属性对码的部分依赖和传递依性表现在可能存在主属性对码的部分
36、依赖和传递依赖。赖。BCNF的关系模式所具有的性质的关系模式所具有的性质所有所有非主属性非主属性都完全函数依赖于每个候选码都完全函数依赖于每个候选码;所有所有主属性主属性都完全函数依赖于每个不包含它的候选码都完全函数依赖于每个不包含它的候选码;没有任何属性完全函数依赖于没有任何属性完全函数依赖于非码非码的任何一组属性的任何一组属性.数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.2.7多值依赖多值依赖例例1:学校中某一门课程由多个教师学校中某一门课程由多个教师讲授，他们使用相同的一套参讲授，他们使用相同的一套参考书。考书。关系模式关系模式:Teaching(C,T,B)课
37、程课程C、教师、教师T和和参考书参考书B课课程程C教教员员T参参考考书书B物理物理数学数学计算数学计算数学李李勇勇王王军军李李勇勇张张平平张张平平周周峰峰普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析表表5.1数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论普通物理学普通物理学光学原理光学原理物理习题集物理习题集普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析微分方程微分方程高等代数高等代数李李勇勇李李勇勇李李勇勇王王军军王王军军王
38、王军军李李勇勇李李勇勇李李勇勇张张平平张张平平张张平平物物理理物物理理物物理理物物理理物物理理物物理理数数学学数数学学数数学学数数学学数数学学数数学学 参考书参考书B教员教员T课程课程C用二维表表示用二维表表示Teaching数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论用二分图表示用二分图表示Teaching物物理理普通物理学普通物理学光学原理光学原理物理习题集物理习题集李勇李勇王军王军数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论vTeachingBCNF:vTeaching具有唯一候选码具有唯一候选码(C，T，B)，即全码即全码vTeaching关
39、系模式中存在的问题关系模式中存在的问题(1)数据冗余度大：数据冗余度大：有多少名任课教师，参考书就要存储多少次。有多少名任课教师，参考书就要存储多少次。(2)插入操作复杂：插入操作复杂：当某一课程增加一名任课教师时，该课程有多少当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组。本参照书，就必须插入多少个元组。(3)删除操作复杂：删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组。师，就必须删除多少个元组。(4)修改操作复杂：修改操作复杂：某一门课要修改一本参考书，该课程有多少名教某一门课要修改一本参
40、考书，该课程有多少名教师，就必须修改多少个元组。师，就必须修改多少个元组。v产生原因：产生原因：存在多值依赖存在多值依赖数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论多值依赖的定义多值依赖的定义定义定义6.10设设R(U)是一个属性集是一个属性集U上的一个关系模式，上的一个关系模式，X、Y和和Z是是U的子集，的子集，并且并且ZUXY，多值依赖多值依赖XY成立当且仅当对成立当且仅当对R的的任一关系任一关系r，r在（在（X，Z）上的每个值对应一组）上的每个值对应一组Y的值，这组值仅仅决定于的值，这组值仅仅决定于X值而与值而与Z值无关。值无关。例例Teaching（C,T,B）对
41、于对于C的每一个值，的每一个值，T有一组值与之对应，而不论有一组值与之对应，而不论B取何值。取何值。另一等价定义另一等价定义在在R（U）的任一关系）的任一关系r中，如果存在元组中，如果存在元组t，s使得使得tX=sX，那么，那么就必然存在元组就必然存在元组w,v r，（，（w,v可以与可以与s，t相同），使得：相同），使得：(1)wX=vX=tX=sX，(2)wY=tY，wZ=sZ，(3)vY=sY，vZ=tZ（即交换（即交换s，t元组的元组的Y值所得的两个新元组必在值所得的两个新元组必在r中），中），则则Y多值依赖于多值依赖于X，记为，记为XY。这里，这里，X，Y是是U的子集，的子集，Z=U
42、-X-Y。txy1z2sxy2z1wxy1z1vxy2z2数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论平凡多值依赖和非平凡的多值依赖平凡多值依赖和非平凡的多值依赖若若XY，而，而Z，则称，则称XY为为平凡的多值依赖平凡的多值依赖否则称否则称XY为为非平凡的多值依赖非平凡的多值依赖数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例例2：关系模式：关系模式WSC(W,S,C)WSC(W,S,C)中，中，W W表示仓库，表示仓库，S S表示保管员，表示保管员，C C表示商品。假设每个仓库有若表示商品。假设每个仓库有若干个保管员，有若干种商品。每个保管员保管干个
43、保管员，有若干种商品。每个保管员保管所在仓库的所有商品，每种商品被所有保管员所在仓库的所有商品，每种商品被所有保管员保管。保管。仓库管理关系仓库管理关系按照语义对于按照语义对于W W的每一个值的每一个值W Wi i，S S有一个完整有一个完整的集合与之对应而不论的集合与之对应而不论C C取何值。所以取何值。所以W WS S。Si1 i1 ，Si2 i2 ，SininCi1 i1 ，Ci2 i2 ，CininWi iSCWi iWi i于是于是SSWiWi与与CCWiWi之间正好形式一个完全之间正好形式一个完全二分图，如图二分图，如图:数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数
44、据理论多值依赖的性质多值依赖的性质（1）多值依赖具有对称性）多值依赖具有对称性若若XY，则，则XZ，其中，其中ZUXY多值依赖的对称性可以用完全二分图直观地表示出来。多值依赖的对称性可以用完全二分图直观地表示出来。（2）多值依赖具有传递性）多值依赖具有传递性若若XY，YZ，则则XZ-YXiZi1Zi2ZimYi1Yi2Yin（3）函数依赖是多值依赖的特殊情况。）函数依赖是多值依赖的特殊情况。若若XY，则，则XY。（4）若）若XY，XZ，则，则XY Z。（5）若）若XY，XZ，则，则XYZ。（6）若）若XY，XZ，则，则XY-Z，XZ-Y。数据库系统概论数据库系统概论第六章第六章 关系数据理论关
45、系数据理论多值依赖与函数依赖的区别多值依赖与函数依赖的区别(1)有效性有效性多值依赖的有效性与属性集的范围有关多值依赖的有效性与属性集的范围有关若若XY在在U上成立，则在上成立，则在W（XY W U）上一定成立；反之则不然，）上一定成立；反之则不然，即即XY在在W（W U）上成立，在）上成立，在U上并不一定成立上并不一定成立多值依赖的定义中不仅涉及属性组多值依赖的定义中不仅涉及属性组X和和Y，而且涉及，而且涉及U中其余属性中其余属性Z。一般地，在一般地，在R（U）上若有）上若有XY在在W（W U）上成立，则称）上成立，则称XY为为R（U）的嵌入型多值依赖）的嵌入型多值依赖只要在只要在R（U）的
46、任何一个关系）的任何一个关系r中，元组在中，元组在X和和Y上的值满足定义上的值满足定义5.l（函数依（函数依赖），则函数依赖赖），则函数依赖XY在任何属性集在任何属性集W（XY W U）上成立。）上成立。(2)若函数依赖若函数依赖XY在在R（U）上成立，则对于任何上成立，则对于任何Y Y均有均有XY成立成立多值依赖多值依赖XY若在若在R(U)上成立，不能断言对于任何上成立，不能断言对于任何Y Y有有XY成立。成立。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.2.8第四范式（第四范式（4NF）v如果如果R4NF，则则RBCNF不允许不允许有非平凡且非函数依赖的有非平凡且
47、非函数依赖的多值依赖，允许多值依赖，允许的是的是函数依赖函数依赖（是平凡多值依赖）。（是平凡多值依赖）。定义定义5.10关系模式关系模式R1NF，如果对于，如果对于R的每个非平凡多值依的每个非平凡多值依赖赖XY（Y X），），X都含有候选码，则都含有候选码，则R4NF。（XY）v函数依赖和多值依赖是两种最重要的数据依赖。函数依赖和多值依赖是两种最重要的数据依赖。v如果只考虑如果只考虑函数依赖函数依赖，则属于，则属于BCNFBCNF的关系模式规范化程度已最高了。的关系模式规范化程度已最高了。v如果考虑如果考虑多值依赖多值依赖，则属于，则属于4 4NFNF的关系模式规范化程度是最高的了。的关系模式
48、规范化程度是最高的了。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论存在非平凡的多值依赖存在非平凡的多值依赖CT，且，且C不是候选码不是候选码v用投影分解法把用投影分解法把Teach分解为如下两个关系模式：分解为如下两个关系模式：CT(C,T)4NFCB(C,B)4NFCT，CB是平凡多值依赖是平凡多值依赖v同样的方法可以把同样的方法可以把WSC（W，S，C）分解为：分解为：WS（W，S）4NFWC（W，C）4NF例：例： Teach(C,T,B) 4NF数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.2.9规范化小结规范化小结v关系数据库的规范化理论
49、是数据库逻辑设计的工具。关系数据库的规范化理论是数据库逻辑设计的工具。v一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。这只是最基本的规范化。v规范化程度可以有多个不同的级别规范化程度可以有多个不同的级别v规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题插入异常、删除异常、修改复杂、数据冗余等问题v一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级一个低一级范式的关系模式，通过
50、模式分解可以转换为若干个高一级范式的关系模式集合（这个分解不是唯一的），这个过程就叫范式的关系模式集合（这个分解不是唯一的），这个过程就叫关系模关系模式的规范化式的规范化数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论v关系模式规范化的基本步骤关系模式规范化的基本步骤1NF消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除决定属性消除决定属性2NF集非码的非平集非码的非平消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖凡函数依赖凡函数依赖3NF消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖BCNF消除非平凡且非函数依赖的多值依赖
51、消除非平凡且非函数依赖的多值依赖4NF数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论规范化的基本思想规范化的基本思想v消除不合适的数据依赖消除不合适的数据依赖v模式中的各关系模式达到某种程度的模式中的各关系模式达到某种程度的“分离分离”v采用采用“一事一地一事一地”的模式设计原则的模式设计原则让一个关系描述一个概念、一个实体或者实体间的一种联系。若多让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它于一个概念就把它“分离分离”出去出去v所谓规范化实质上是概念的所谓规范化实质上是概念的单一单一化化v不能说规范化程度越高的关系模式就越好。不能说规范化程度
52、越高的关系模式就越好。v在设计数据库模式结构时，必须对现实世界的实际情况和用户应在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模用需求作进一步分析，确定一个合适的、能够反映现实世界的模式。式。v上面的规范化步骤可以在其中任何一步终止。上面的规范化步骤可以在其中任何一步终止。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.3数据依赖的公理系统数据依赖的公理系统逻辑蕴含逻辑蕴含定义定义6.11对于满足一组对于满足一组函数依赖函数依赖F的关系模式的关系模式R，其任何一个，其任何一个关系关系r，若函数依赖，若函数依赖
53、XY都成立都成立,则称：则称：F逻辑蕴含逻辑蕴含XYArmstrong公理系统公理系统一套推理规则，是模式分解算法的理论基础一套推理规则，是模式分解算法的理论基础用途用途:1)求给定关系模式的码求给定关系模式的码2)从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论1.Armstrong公理系统公理系统关系模式关系模式R来说有以下的推理规则：来说有以下的推理规则：Al.自反律自反律（Reflexivity）：）：若若Y X U，则，则XY为为F所蕴含。所蕴含。A2.增广律增广律（Augmentation）：若）：若
54、XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ为为F所蕴含。所蕴含。A3.传递律传递律（Transitivity）：若）：若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所所蕴含。蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于并不依赖于F数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论定理定理6.lArmstrong推理规则是正确的推理规则是正确的(l)自反律自反律:若若Y X U，则，则X Y为为F所蕴含所蕴含证证:设设Y X U对对R 的任一关系的任一关系r中的任意两个元
55、组中的任意两个元组t，s：若若tX=sX，由于，由于Y X，有，有ty=sy，所以所以XY成立成立.自反律得证自反律得证(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所蕴含所蕴含.增广律得证。增广律得证。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论(3)传递律：若
56、传递律：若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所蕴含。所蕴含。证：证：设设XY及及YZ为为F所蕴含。所蕴含。对对R的任一关系的任一关系r中的任意两个元组中的任意两个元组t，s。若若tX=sX，由于，由于XY，有，有tY=sY；再由再由YZ，有，有tZ=sZ，所以，所以XZ为为F所蕴含所蕴含.传递律得证。传递律得证。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论2.导出规则导出规则1.根据根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：这三条推理规则可以得到下面三条推理规则：合并规则合并规则：由：由XY，XZ，有，有XYZ。伪传递规则伪传递规则：由：由
57、XY，WYZ，有，有XWZ。分解规则分解规则：由：由XY及及Z Y，有，有XZ。2.根据合并规则和分解规则，可得引理根据合并规则和分解规则，可得引理6.1引理引理6.lXA1 A2Ak成立的充分必要条件是成立的充分必要条件是XAi成立（成立（i=l，2，k）。）。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论3.函数依赖闭包函数依赖闭包定义定义6.12在关系模式在关系模式R中为中为F所逻辑蕴含的函数依赖的全所逻辑蕴含的函数依赖的全体叫作体叫作F的闭包的闭包，记为，记为F+。定义定义6.13设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U，XF+=A|XA能
58、由能由F根据根据Armstrong公理导出公理导出，XF+称为属性集称为属性集X关于函数依关于函数依赖集赖集F的闭包的闭包例例:设设R，U=A，B，C)，FAB，BC，则：，则：当当XA时，时，XF+ABC；当当XB时，时，XF+BC；当当XC时，时，XF+C。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论F的闭包的闭包F=AB,BC,F+计算是计算是NP完全问题，完全问题，XA1A2.AnF+=A,B, C, AB,AC,BC,ABC,AA, BB, CC, ABA,ACA,BCB,ABCA,AB, BC,ABB,ACB,BCC,ABCB,AC, BBC,ABC,ACC,
59、BCBC,ABCC,AAB,ABAB,ACAB,ABCAB,AAC, ABBC,ACAC,ABCBC,ABC,ABAC,ACAB,ABCAC,AABC,ABABC,ACABC,ABCABC数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论关于闭包的引理关于闭包的引理引理引理6.2设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U，XY能由能由F根据根据Armstrong公理导出的充分必要条件是公理导出的充分必要条件是:Y XF+用途用途将判定将判定XY是否能由是否能由F根据根据Armstrong公理导出的问题，公理导出的问题，就转化为求出就转化为求出XF+，
60、判定，判定Y是否为是否为XF+的子集的问题。的子集的问题。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论求闭包的算法求闭包的算法算法算法6.l求属性集求属性集X（X U）关于）关于U上的函数依赖集上的函数依赖集F的闭包的闭包XF+输入：输入：X，F输出：输出：XF+步骤：步骤：（1）令）令X（0）=X，i=0（2）求）求B，这里，这里B=A|( V)( W)(VW FV X（i）A W)；（3）X（i+1）=BX（i）（4）判断）判断X（i+1）=X（i）吗吗?（5）若相等或）若相等或X（i）=U,则则X（i）就是就是XF+,算法终止。算法终止。（6）若否，则）若否，则i=
61、i+l，返回第（，返回第（2）步。）步。对于算法对于算法6.l，令令ai=|X（i）|，ai形成一个步长大于形成一个步长大于1的严格递增的的严格递增的序列，序列的上界是序列，序列的上界是|U|，因此该算法最多，因此该算法最多|U|-|X|次循环就会终止。次循环就会终止。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论求闭包的算法求闭包的算法例例1已知关系模式已知关系模式R，其中，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。求（求（AB）F+。解解设设X（0）=AB；(1)计算计算X（1）:逐一的扫描逐一的扫描F集合中各个函数依赖，集合中各个函数依赖，找
62、左部为找左部为A，B或或AB的函数依赖。得到两个：的函数依赖。得到两个：ABC，BD。于是于是X（1）=ABCD=ABCD。(2)因为因为X（0）X（1），所以再找出左部为，所以再找出左部为ABCD子集的那些函数子集的那些函数依赖，又得到依赖，又得到ABC，BD，CE，ACB，于是于是X（2）=X（1）BCDE=ABCDE。(3)因为因为X（2）=U，算法终止，算法终止所以（所以（AB）F+=ABCDE。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论求关系模式的码求关系模式的码例例2已知关系已知关系R，U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB。求求R的
63、码？的码？解法：解法：1.求出所有可能存在的闭包求出所有可能存在的闭包X(i)=XF+，2.若若X(i)=U，则选出其中的，则选出其中的X，3.在在X中选出最简的主属性组中选出最简的主属性组Xi,4.Xi就是所求的码。就是所求的码。具体解为：具体解为：(AB)F+=ABCDE(B)F+=BD(C)F+=CBDE(EC)F+=CBDE(AC)F+=ABCDE(ABC)F+=ABCDE(ABCE)F+=ABCDE(BC)F+=BCDE(BEC)F+=BCDE(AEC)F+=ABCDE包含包含全部属性全部属性的有的有(AB)F+，(AC)F+，(ABC)F+，(ABCE)F+，(AEC)F+挑选出挑
64、选出最简最简的是：的是：(AB)F+，(AC)F+所以所以R的的码码为：为：AB和和AC数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论证明：证明：1.有效性：有效性：可由定理可由定理5.l得证得证2.完备性：完备性：只需证明只需证明逆否命题逆否命题:若函数依赖若函数依赖XY不能由不能由F从从Armstrong公理导公理导出，那么它必然不为出，那么它必然不为F所蕴含所蕴含分三步证明：分三步证明：4.Armstrong公理系统的有效性与完备性公理系统的有效性与完备性有效性：有效性：由由F出发根据出发根据Armstrong公理推导出来的每一个函数依赖一公理推导出来的每一个函数依赖
65、一定在定在F+中。中。/*Armstrong正确正确完备性完备性：F+中的每一个函数依赖，必定可以由中的每一个函数依赖，必定可以由F出发根据出发根据Armstrong公理推导出来公理推导出来。/*Armstrong公理够用，完全公理够用，完全若若f不能用不能用Armstrong公理推导出来，公理推导出来，fF+有效性与完备性的证明有效性与完备性的证明数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论(1)引理引理:若若VW成立，且成立，且V XF+，则，则W XF+证证因为因为V XF+，所以有，所以有XV成立；成立；因为因为XV，VW，于是，于是XW成立成立所以所以W XF+
66、(2)/*若若f不能用不能用Armstrong公理推导出来，公理推导出来，fF+/*若存在若存在r，F+中的全部函数依赖在中的全部函数依赖在r上成立。上成立。/*而不能用而不能用Armstrong公理推导出来的公理推导出来的f,在在r上不成立。上不成立。构造一张二维表构造一张二维表r，它由下列两个元组构成，可以证明，它由下列两个元组构成，可以证明r必是必是R（U，F）的一个关系）的一个关系，即，即F+中的全部函数依赖在中的全部函数依赖在r上成立。上成立。若若r不不是是R的的关关系系，则则必必由由于于F中中有有函函数数依依赖赖VW在在r上上不不成成立立所所致致。由由r的的构构成成可可知知，V必必
67、定定是是XF+的的子子集集，而而W不不是是XF+的的子子集集，可可是由第（是由第（1）步，）步，W XF+，矛盾。所以，矛盾。所以r必是必是R的一个关系。的一个关系。XF+U-XF+11.100.011.111.1数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论(3)/*若若f不能用不能用Armstrong公理推导出来，公理推导出来，fF+/*而不能用而不能用Armstrong公理推导出来的公理推导出来的f,在在r上不成立。上不成立。若若XY不能由不能由F从从Armstrong公理导出，则公理导出，则Y不是不是XF+的子集。（引理的子集。（引理5.2）因此必有因此必有Y的子集
68、的子集Y满足满足Y U-XF+，则则XY在在r中不成立，中不成立，即即XY必不为必不为R蕴含蕴含/*因为因为F+中的全部函数依赖在中的全部函数依赖在r上成立。上成立。Armstrong公理的完备性及有效性说明公理的完备性及有效性说明:“蕴含蕴含”=“导出导出”等价的概念等价的概念 F+=由由F出发借助出发借助Armstrong公理导出的函数依赖的集合公理导出的函数依赖的集合数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论5.函数依赖集等价函数依赖集等价定义定义5.14如果如果G+=F+，就说函数依赖集，就说函数依赖集F覆盖覆盖G（F是是G的覆盖，或的覆盖，或G是是F的覆盖），
69、或的覆盖），或F与与G等价等价。引理引理5.3F+=G+的充分必要条件是：的充分必要条件是：F G+，和，和G F+证证:必要性显然，只证充分性。必要性显然，只证充分性。（1）若）若F G+，则，则XF+ XG+。（2）任取）任取XY F+则有则有Y XF+ XG+。所以所以XY (G+）+=G+。即。即F+ G+。（3）同理可证）同理可证G+ F+，所以，所以F+=G+。要要判判定定F G+，只只须须逐逐一一对对F中中的的函函数数依依赖赖XY，考考察察Y 是是否否属属于于XG+就行了。因此引理就行了。因此引理5.3给出了判断两个函数依赖集等价的可行算法。给出了判断两个函数依赖集等价的可行算法
70、。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.最小依赖集最小依赖集定定义义5.15如如果果函函数数依依赖赖集集F满满足足下下列列条条件件，则则称称F为为一一个个极极小小函函数依赖集数依赖集。亦称为。亦称为最小依赖集最小依赖集或或最小覆盖最小覆盖。(1)F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。(2)F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得F与与F-XA等价。等价。(3)F中不存在这样的函数依赖中不存在这样的函数依赖XA，X有真子集有真子集Z使得使得F-XAZA与与F等价。等价。数据库系统概论数据库系统概论第六章第六
71、章 关系数据理论关系数据理论例例2对于对于5.1节中的关系模式节中的关系模式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)SDEPTSNOSDEPT也与也与F 等价等价数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数
72、据理论7.极小化过程极小化过程定定理理5.3每每一一个个函函数数依依赖赖集集F均均等等价价于于一一个个极极小小函函数数依依赖赖集集Fm。此此Fm称为称为F的最小依赖集的最小依赖集证证:构构造造性性证证明明，依依据据定定义义分分三三步步对对F进进行行“极极小小化化处处理理”，找找出出F的的一个最小依赖集。一个最小依赖集。(1)逐一检查逐一检查F中各函数依赖中各函数依赖FDi：XY，若若Y=A1A2Ak，k2，则用则用XAj|j=1，2，k来取代来取代XY。引理引理5.1保证了保证了F变换前后的等价性。变换前后的等价性。(2)逐一检查逐一检查F中各函数依赖中各函数依赖FDi：XA，令令G=F-XA
73、，若，若A XG+，则从则从F中去掉此函数依赖。中去掉此函数依赖。由于由于F与与G=F-XA等价的充要条件是等价的充要条件是A XG+因此因此F变换前后是等价的。变换前后是等价的。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论因为对因为对F的每一次的每一次“改造改造”都保证了改造前后的两个函数依赖集等都保证了改造前后的两个函数依赖集等价，因此剩下的价，因此剩下的F与原来的与原来的F等价。等价。定理定理5.3的证明过程的证明过程也是求也是求F极小依赖集的过程极小依赖集的过程(3)逐一取出逐一取出F中各函数依赖中各函数依赖FDi：XA，设设X=B1B2Bm，逐一考查逐一考查Bi
74、（i=l，2，m），），若若A （X-Bi）F+，则以则以X-Bi取代取代X。由由于于F与与F-XAZA等等价价的的充充要要条条件件是是A ZF+，其其中中Z=X-Bi因此因此F变换前后是等价的。变换前后是等价的。由定义，最后剩下的由定义，最后剩下的F就一定是极小依赖集。就一定是极小依赖集。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例例3已已知知：F=AB，BA，BC，AC，CA，求求F的的极极小小函函数数依赖集依赖集Fm解：解：1.化右部为单一属性：化右部为单一属性：F=AB，BA，BC，AC，CA2.在在F中去掉中去掉AB，(A)F+=AC，B (A)F+，不去掉。
75、不去掉。在在F中去掉中去掉BA，(B)F+=ABC，A(B)F+，应去掉。应去掉。在在F中去掉中去掉BC，(B)F+=B，C (B)F+，不去掉。不去掉。在在F中去掉中去掉AC，(A)F+=ABC，C(A)F+，应去掉应去掉在在F中去掉中去掉CA，(C)F+=C，A (C)F+，不去掉。不去掉。3.因主属性是单属性，故不用再取其子集去考察。因主属性是单属性，故不用再取其子集去考察。故极小函数依赖集故极小函数依赖集Fm1=AB，BC，CAFm1=AB，BC，CAFm2=AB，BA，AC，CAFm1、Fm2都是都是F的最小依赖集：的最小依赖集：vF的最小依赖集的最小依赖集Fm不一定是唯一的它与对各
76、函数依赖不一定是唯一的它与对各函数依赖FDi及及XA中中X各属性的处置顺序有关各属性的处置顺序有关数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例例4：已知关系：已知关系R，U=A，B，C，D，E，F，G，H，I，J，F=AB，AC，ADE，DE，DEB，AFGHI，IJ。求求F的极小函数依赖集的极小函数依赖集Fm解：解：1.化右部为单一属性：化右部为单一属性：则则F=AB,AC，AD，AE，DE，DEB，AFG，AFH，AFI，IJ。2.AB：记：记G=F-AB，(A)G+=ACDEB，B(A)G+，去掉去掉AB，F=F-AB=AC，AD，AE，DE，DEB，AFG，AF
77、H，AFI，IJ。AC：记：记G=F-AC，(A)G+=ADEB，C (A)G+，不去掉不去掉AC，F=AC，AD，AE，DE，DEB，AFG，AFH，AFI，IJ。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论AE：记：记G=F-AE，(A)G+=ACDEB，E(A)G+，去掉去掉AE，F=F-AE=AC，AD，DE，DEB，AFG，AFH，AFI，IJ。同理考察：同理考察：AD，DE，DEB，AFG，AFH，AFI，IJ，它们都不能去掉。，它们都不能去掉。故记故记F为：为：F=AC，AD，DE，DEB，AFG，AFH，AFI，IJ。3.函数依赖左部的分解函数依赖左部的分
78、解.DEB：(D)F+=DEB，B(D)F+，用用DB代替代替DEB，记记F=AC，AD，DE，DB，AFG，AFH，AFI，IJ。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论.AFG：(A)F+=ACDEB，(F)F+=ACDEB，G (A)F+；G (F)F+，不能用不能用AG或或FG代替代替AFG，记记F=AC，AD，DE，DB，AFG，AFH，AFI，IJ。同理，可考察同理，可考察AFH，AFI，它们都应保留。，它们都应保留。所以，所以，Fm=AC，AD，DE，DB，AFG，AFH，AFI，IJ。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论v
79、极极小小化化过过程程(定定理理5.3的的证证明明)也也是是检检验验F是是否否为为极极小小依依赖赖集集的的一一个个算法算法若改造后的若改造后的F与原来的与原来的F相同，说明相同，说明F本身就是一个最小依赖集本身就是一个最小依赖集v在在R中可以用与中可以用与F等价的依赖集等价的依赖集G来取代来取代F原因：两个关系模式原因：两个关系模式R1，R2，如果，如果F与与G等价，等价，那么那么R1的关系一定是的关系一定是R2的关系。反过来，的关系。反过来，R2的关系也一定是的关系也一定是R1的关系。的关系。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论关系数据理论小结关系数据理论关系数据
80、理论为为关关系系数数据据库库设设计计提提供供了了理理论论的的指南和工具。指南和工具。n设计数据库的标准设计数据库的标准不存在插入异常、删除异常、修不存在插入异常、删除异常、修改异常和冗余度大等问题。改异常和冗余度大等问题。n设计数据库方法设计数据库方法概念模型概念模型关系数据模型关系数据模型关系数据规关系数据规范化范化（将数据库中的各关系尽量达到高一（将数据库中的各关系尽量达到高一级的范式）。级的范式）。n判判断断关关系系模模式式能能达达到到哪一级范式哪一级范式由关系模式中的由关系模式中的U、F和和Key根根据各范式定义来判断。据各范式定义来判断。n进行关系模式分解进行关系模式分解将低级范式的
81、关系模式分解使其将低级范式的关系模式分解使其达到高级范式。达到高级范式。Key的求法：的求法：1.求出所有可能存在的闭包求出所有可能存在的闭包X(i)=XF+2.若若X(i)=U，则选出其中的，则选出其中的X，3.在在X中选出最简的主属性组中选出最简的主属性组Xi,4.Xi就是所求的码。就是所求的码。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论6.4模式的分解模式的分解v把低一级的关系模式分解为若干个高一级的关系模式的方法并不把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的。是唯一的。v只有能够保证分解后的关系模式与原关系模式等价，分解方法才只有能够保证分
82、解后的关系模式与原关系模式等价，分解方法才有意义。有意义。三种模式分解的等价定义三种模式分解的等价定义 分解具有无损连接性。分解具有无损连接性。 分解要保持函数依赖。分解要保持函数依赖。 分解既要保持函数依赖，又要具有无损连接性。分解既要保持函数依赖，又要具有无损连接性。以上也是模式分解的原则。以上也是模式分解的原则。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例例:SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSlocSL2NF存在插入异常、删除异存在插入异常、删除异常、冗余度大和修改复常、冗余度大和修改复杂等问题杂等问题分解方法可
83、以有多种分解方法可以有多种:S-D(Sno，Sdept)D-L(Sdept，Sloc)4.S-D(Sno，Sdept)S-L(Sno，Sloc)3.S-L(Sno，Sloc)D-L(Sdept，Sloc)2.S(Sno)D(Sdept)L(Sloc)1.SnoSdept Sloc 95001 CS A95002 IS B95003 MA C95004 IS B95005 PH BSL数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论第一种分解第一种分解Sno95001950029500395004 95005SSdept CS IS MA PHDSloc A B CLSDL无法
84、连接无法连接 分解后的数据库分解后的数据库丢失了许多信息。丢失了许多信息。 例例如如无无法法查查询询95001学学生生所所在在系系或或所在宿舍。所在宿舍。 如如果果分分解解后后的的关关系系可可以以通通过过自自然然连连接接恢恢复复为为原原来来的的关关系系，那那么么这这种种分分解解就没有就没有丢失信息。丢失信息。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论第二种分解第二种分解Sno95001950029500395004 95005Sloc A B C B BS-LSloc A B C BSdept CS IS MA PHD-LS-LD-LSnoSdept Sloc 9500
85、1 CS A95002 IS B95002 PH B95003 MA C95004 IS B95004 PH B95005 IS B95005 PH B连接后比原来的连接后比原来的SL关系多了关系多了3个元个元组，无法知道组，无法知道95002、95004、95005究究竟是哪个系的学生。竟是哪个系的学生。元组增加了，信息丢失了。元组增加了，信息丢失了。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论第三种分解第三种分解SnoSdept Sloc 95001 CS A95002 IS B95003 MA C95004 IS B95005 PH BS-DS-LSno950019
86、50029500395004 95005Sdept CS IS MA IS PHS-DSloc A B C B BSno95001950029500395004 95005S-L没有丢失信息没有丢失信息，但原关系但原关系SL中的函数依赖中的函数依赖SdeptSloc在关系模式在关系模式S-D和和S-L上不见了。上不见了。有数据冗余。有数据冗余。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论第四种分解第四种分解Sno95001950029500395004 95005Sdept CS IS MA IS PHS-DSloc A B C B Sdept CS IS MA PH D
87、-LSnoSdept Sloc 95001 CS A95002 IS B95003 MA C95004 IS B95005 PH BS-DD-L这种分解方法这种分解方法没有丢失信息没有丢失信息和和数据冗余数据冗余，并保持并保持了函数依赖了函数依赖数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论例例:SL（Sno，Sdept，Sloc）F=SnoSdept,SdeptSloc,SnoSlocSL2NF存在插入异常、删除异存在插入异常、删除异常、冗余度大和修改复常、冗余度大和修改复杂等问题杂等问题分解方法可以有多种分解方法可以有多种:S-D(Sno，Sdept)D-L(Sdept
88、，Sloc)4.S-D(Sno，Sdept)S-L(Sno，Sloc)3.S-L(Sno，Sloc)D-L(Sdept，Sloc)2.S(Sno)D(Sdept)L(Sloc)1.SnoSdept Sloc 95001 CS A95002 IS B95003 MA C95004 IS B95005 PH BSL既没有保持函数依既没有保持函数依赖，又无法连接。赖，又无法连接。保持函数依赖，但丢保持函数依赖，但丢失信息，是有损连接。失信息，是有损连接。没有保持函数依赖，没没有保持函数依赖，没有丢失信息，是无损连有丢失信息，是无损连接，但有数据冗余。接，但有数据冗余。既保持函数依赖，既保持函数依赖，
89、又能无损连接。又能无损连接。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论模式分解的定义模式分解的定义定义定义5.16关系模式关系模式R的一个分解：的一个分解：=R1，R2，RnU=U1U2Un，且，且不存在不存在Ui Uj，Fi为为F在在Ui上的投影。上的投影。定义定义5.17函数依赖集合函数依赖集合XY|XY F+XY Ui的一个的一个覆盖覆盖Fi叫作叫作F在属在属性性Ui上的投影。上的投影。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论具有无损连接性和保持函数依赖的模式分解定义具有无损连接性和保持函数依赖的模式分解定义定义定义5.18平共平共设设=
90、R1,R2,.Rk是是R的一个分解，的一个分解，若对若对R的任何一个关系的任何一个关系r均有均有r=m(r)成立，则称分解成立，则称分解具有无具有无损联接性。损联接性。其中：其中：m(r)是是r在在中各关系模式上的投影的连接。中各关系模式上的投影的连接。定义定义519设设=R1,R2,.Rn是是R的一个分解，的一个分解，若若F+ =(F1F2Fn)+, ,则称关系模式则称关系模式R的这个分解的这个分解是保持函数依是保持函数依赖的赖的。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论v如果一个模式分解如果一个模式分解具有无损连接性具有无损连接性，则它能够保证不丢失信息。那，则它
91、能够保证不丢失信息。那么这个模式分解一定能够达到么这个模式分解一定能够达到4NF。v如果一个模式分解如果一个模式分解保持了函数依赖保持了函数依赖，则它可以减轻或解决各种异常，则它可以减轻或解决各种异常情况。那么这个模式分解一定能够达到情况。那么这个模式分解一定能够达到3NF，但不一定能够达到，但不一定能够达到BCNF。v分解具有无损连接性和分解保持函数依赖是两个分解具有无损连接性和分解保持函数依赖是两个互相独立互相独立的标准。的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。依赖的分解也
92、不一定具有无损连接性。v如果一个分解如果一个分解既具有无损连接性又保持了函数依赖既具有无损连接性又保持了函数依赖，则既能够保证，则既能够保证不丢失信息，还可以减轻或解决各种异常情况，是比较好的分解。不丢失信息，还可以减轻或解决各种异常情况，是比较好的分解。那么这个模式分解一定能够达到那么这个模式分解一定能够达到3NF，但不一定能够达到，但不一定能够达到BCNF。数据库系统概论数据库系统概论第六章第六章 关系数据理论关系数据理论分解算法分解算法算法算法5.2判别一个分解的无损连接性判别一个分解的无损连接性算法算法5.3（合成法）转换为（合成法）转换为3NF的保持函数依赖的分解。的保持函数依赖的分解。算法算法5.4转换为转换为3NF既有无损连接性又保持函数依赖的分解既有无损连接性又保持函数依赖的分解算法算法5.5转换为转换为BCNF的无损连接分解（分解法）的无损连接分解（分解法）算法算法5.6达到达到4NF的具有无损连接性的分解的具有无损连接性的分解
