关系模式设计理论.ppt

《关系模式设计理论.ppt》由会员分享，可在线阅读，更多相关《关系模式设计理论.ppt（102页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关系模式设计理论关系模式设计理论现在学习的是第1页，共102页第三章第三章 关系模式设计理论关系模式设计理论教学重点：概念模式转换成关系模式的的方教学重点：概念模式转换成关系模式的的方法，数据依赖，关系规范化理论，关系模式法，数据依赖，关系规范化理论，关系模式的分解方法。的分解方法。教学难点：关系规范化理论，关系模式的分教学难点：关系规范化理论，关系模式的分解方法。解方法。教学时数：教学时数：8学时。学时。现在学习的是第2页，共102页教学内容教学内容 一、数据依赖一、数据依赖二、数据依赖的公理系统二、数据依赖的公理系统三、关系模式的规范形式三、关系模式的规范形式四、关系模式规范化方法四、关系

2、模式规范化方法现在学习的是第3页，共102页一、关系数据库设计理论一、关系数据库设计理论(一一)问题的提出问题的提出l针对具体问题，如何构造一个适合于它的数据模式针对具体问题，如何构造一个适合于它的数据模式l数据库逻辑设计的工具数据库逻辑设计的工具关系数据库的规范化理论关系数据库的规范化理论l一个初始的逻辑关系模式存在着很多问题一个初始的逻辑关系模式存在着很多问题l举例：举例：现在学习的是第4页，共102页S#(*) C#(*) Cname Tname01C1C语言语言张一张一02C1C语言语言张一张一03C3B语言语言张三张三04C4Java张四张四异常问题异常问题:1、数据冗余、数据冗余2

3、、修改异常、修改异常3、插入异常、插入异常4、删除异常、删除异常分解是解决冗余的主分解是解决冗余的主要方法要方法现在学习的是第5页，共102页( (二二) )函数依赖函数依赖一、函数依赖一、函数依赖二、平凡函数依赖与非平凡函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖四、传递函数依赖现在学习的是第6页，共102页一、函数依赖一、函数依赖定义定义: 设设R(U)是一个属性集是一个属性集U上的关系模式，上的关系模式，X和和Y是是U的子集的子集。 若对于若对于R(U)的任意一个可能的关系的任意一个可能的关系r，r中不可能存在两个元

4、中不可能存在两个元组在组在X上的属性值相等，上的属性值相等， 而在而在Y上的属性值不等，上的属性值不等， 则称则称 “X函函数确定数确定Y” 或或 “Y函数依赖于函数依赖于X”，记作，记作XY。 X称为这个称为这个函数依赖的决定属性集函数依赖的决定属性集(Determinant)。现在学习的是第7页，共102页说明：说明： 1. 函数依赖不是指关系模式函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件的某个或某些关系实例满足的约束条件，而是指，而是指R的所有关系实例均要满足的约束条件。的所有关系实例均要满足的约束条件。2. 函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖函数

5、依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。 例如例如“姓名姓名年龄年龄”这个函数依赖只有在不允许有同名人的条件下成这个函数依赖只有在不允许有同名人的条件下成立立3. 数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖现，函数依赖“姓名姓名年龄年龄”成立。所插入的元组必须满足规定成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，的函数依赖，若发现有同名人存在， 则拒绝装入该元组。则拒绝装入该元组。现在学习的是第8页，共102页函数依赖（续）函数依赖（续）例例: Student(Sno,

6、 Sname, Ssex, Sage, Sdept) 假设不允许重名，则有假设不允许重名，则有:Sno Ssex， Sno Sage , Sno Sdept， Sno Sname, Sname Ssex， Sname SageSname Sdept但但Ssex Sage若若XY，并且，并且YX, 则记为则记为XY。 若若Y不函数依赖于不函数依赖于X, 则记为则记为XY。现在学习的是第9页，共102页二、平凡函数依赖与非平凡函数依赖二、平凡函数依赖与非平凡函数依赖在关系模式在关系模式R(U)中，对于中，对于U的子集的子集X和和Y，如果如果XY，但，但Y X，则称，则称XY是非平凡的函数依赖是非平

7、凡的函数依赖若若XY，但，但Y X, 则称则称XY是平凡的函数依赖是平凡的函数依赖例：在关系例：在关系SC(Sno, Cno, Grade)中，中， 非平凡函数依赖：非平凡函数依赖： (Sno, Cno) Grade 平凡函数依赖：平凡函数依赖： (Sno, Cno) Sno (Sno, Cno) Cno现在学习的是第10页，共102页平凡函数依赖与非平凡函数依赖（续）平凡函数依赖与非平凡函数依赖（续） 对于任一关系模式，平凡函数依赖都是必对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特然成立的，它不反映新的语义，因此若不特别声明，别声明， 我们总是讨论非平凡函数依赖

8、我们总是讨论非平凡函数依赖。现在学习的是第11页，共102页三、完全函数依赖与部分函数依赖三、完全函数依赖与部分函数依赖定义在关系模式定义在关系模式R(U)中，如果中，如果XY，并且对于，并且对于X的的任何一个真子集任何一个真子集X，都有，都有 X Y, 则称则称Y完全完全函数依赖于函数依赖于X，记作，记作X Y。 若若XY，但，但Y不完全函数依赖于不完全函数依赖于X，则称，则称Y部分函部分函数依赖于数依赖于X，记作，记作X P Y。 现在学习的是第12页，共102页完全函数依赖与部分函数依赖（续）完全函数依赖与部分函数依赖（续）例例: 在关系在关系SC(Sno, Cno, Grade)中，中

9、， 由于：由于：Sno Grade，Cno Grade， 因此：因此：(Sno, Cno) Grade 现在学习的是第13页，共102页四、传递函数依赖四、传递函数依赖定义定义5.3 在关系模式在关系模式R(U)中，如果中，如果XY，YZ，且，且Y X，YX，则称，则称Z传递函数依赖于传递函数依赖于X。注注: 如果如果YX， 即即XY，则，则Z直接依赖于直接依赖于X。例例: 在关系在关系Std(Sno, Sdept, Mname)中，有：中，有：Sno Sdept，Sdept Mname Mname传递函数依赖于传递函数依赖于Sno现在学习的是第14页，共102页码码定义定义5.4 设设K为关

10、系模式为关系模式R中的属性或属性组合。若中的属性或属性组合。若K U，则，则K称为称为R的一个侯选码（的一个侯选码（Candidate Key）。若关系模式）。若关系模式R有多个候选码，则选定其中的一个做为主码（有多个候选码，则选定其中的一个做为主码（Primary key）。）。主属性与非主属性主属性与非主属性ALL KEY现在学习的是第15页，共102页外部码外部码关系模式关系模式 R R 中属性或属性组中属性或属性组X X 并非并非 R R的码，但的码，但 X X 是另一个关系模式的码，则称是另一个关系模式的码，则称 X X 是是R R 的外部的外部码（码（Foreign keyFore

11、ign key）也称外码）也称外码主码又和外部码一起提供了表示关系间联系的手段主码又和外部码一起提供了表示关系间联系的手段。现在学习的是第16页，共102页四、关系模式的规范形式四、关系模式的规范形式范式是符合某一种级别的关系模式的集合。范式是符合某一种级别的关系模式的集合。关系数据库中的关系必须满足一定的要求。满足不同程度要关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。求的为不同范式。范式的种类：范式的种类：第一范式第一范式(1NF)第二范式第二范式(2NF)第三范式第三范式(3NF)BC范式范式(BCNF)第四范式第四范式(4NF)第五范式第五范式(5NF)现在学习的

12、是第17页，共102页四、关系模式的规范形式四、关系模式的规范形式各种范式之间存在联系：各种范式之间存在联系：某一关系模式某一关系模式R为第为第n范式，可简记为范式，可简记为RnNF。NF5NF4BCNFNF3NF2NF1现在学习的是第18页，共102页四、关系模式的规范形式四、关系模式的规范形式1、第一范式（、第一范式（1NF）2、第二范式（、第二范式（2NF）3、 第三范式（第三范式（3NF）4、 BC范式（范式（BCNF）5、 多值依赖与第四范式（多值依赖与第四范式（4NF）6、 规范化规范化现在学习的是第19页，共102页第一范式第一范式 1NF1NF1NF的定义的定义如果一个关系模式

13、如果一个关系模式R的所有属性都是不可分的基本数据项，的所有属性都是不可分的基本数据项，则则R1NF。第一范式是对关系模式的最起码的要求。不满足第一范式的第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。数据库模式不能称为关系数据库。但是满足第一范式的关系模式并不一定是一个好的关系但是满足第一范式的关系模式并不一定是一个好的关系模式。模式。现在学习的是第20页，共102页1NF1NF例例: 关系模式关系模式 SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc为学生住处，假设每个系的学生住在同一个地方。为学生住处，假设每个系的学生住在同一个

14、地方。函数依赖包括：函数依赖包括： (Sno, Cno) f Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno) P Sloc Sdept Sloc现在学习的是第21页，共102页 1NF1NFSLC的码为的码为(Sno, Cno)SLC满足第一范式。满足第一范式。 非主属性非主属性Sdept和和Sloc部分函数依赖于码部分函数依赖于码(Sno, Cno)SnoCnoGradeSdeptSlocSLC现在学习的是第22页，共102页SLCSLC不是一个好的关系模式不是一个好的关系模式存在的问题存在的问题:插入异常插入异常删除异常删除异常

15、数据冗余度大数据冗余度大(4) 修改复杂修改复杂 现在学习的是第23页，共102页 1NF1NF原因原因 Sdept、 Sloc部分函数依赖于码。部分函数依赖于码。解决方法解决方法 SLC分解为两个关系模式，以消除这些部分函数依赖分解为两个关系模式，以消除这些部分函数依赖 SC（Sno， Cno， Grade） SL（Sno， Sdept， Sloc）现在学习的是第24页，共102页2NF2NF函数依赖图函数依赖图：SnoCnoGradeSCSLSnoSdeptSloc现在学习的是第25页，共102页第二范式第二范式 2NF2NF2NF的定义的定义定义定义 若关系模式若关系模式R1NF，并且每

16、一个非主属性都完全，并且每一个非主属性都完全函数依赖于函数依赖于R的码，则的码，则R2NF。例：例：SLC(Sno, Sdept, Sloc, Cno, Grade) 1NF SLC(Sno, Sdept, Sloc, Cno, Grade) 2NF SC（Sno， Cno， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF现在学习的是第26页，共102页 第二范式（续）第二范式（续）采用投影分解法将一个采用投影分解法将一个1NF的关系分解为多个的关系分解为多个2NF的关的关系，可以在一定程度上减轻原系，可以在一定程度上减轻原1NF关系中存在的插入异常关系中存在的插入异常

17、、删除异常、数据冗余度大、修改复杂等问题。、删除异常、数据冗余度大、修改复杂等问题。将一个将一个1NF关系分解为多个关系分解为多个2NF的关系，并不能完全消除关的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。系模式中的各种异常情况和数据冗余。现在学习的是第27页，共102页2NF2NF例：例：2NF关系模式关系模式SL(Sno, Sdept, Sloc)中中函数依赖：函数依赖： SnoSdept SdeptSloc SnoSlocSloc传递函数依赖于传递函数依赖于Sno，即，即SL中存在非主中存在非主属性对码的传递函数依赖。属性对码的传递函数依赖。现在学习的是第28页，共102页

18、2NF2NF函数依赖图函数依赖图：SLSnoSdeptSloc现在学习的是第29页，共102页 2NF2NF解决方法解决方法 采用投影分解法，把采用投影分解法，把SL分解为两个关系模式，以消除传递函分解为两个关系模式，以消除传递函数依赖：数依赖： SD（Sno， Sdept） DL（Sdept， Sloc）SD的码为的码为Sno， DL的码为的码为Sdept。现在学习的是第30页，共102页 3NF3NFSD的码为的码为Sno， DL的码为的码为Sdept。SnoSdeptSDSdeptSlocDL现在学习的是第31页，共102页第三范式第三范式3NF3NF3NF的定义的定义定义定义 关系模式

19、关系模式R 中若不存在这样的码中若不存在这样的码X、属性组、属性组Y及非主属性及非主属性Z（Z Y）, 使得使得XY，Y X，YZ，成，成立，则称立，则称R 3NF。例，例， SL(Sno, Sdept, Sloc) 2NF SL(Sno, Sdept, Sloc) 3NF SD（Sno， Sdept） 3NF DL（Sdept， Sloc） 3NF现在学习的是第32页，共102页 3NF3NF若若R3NF，则，则R的每一个非主属性既不部分函数依赖于候选码也的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。不传递函数依赖于候选码。如果如果R3NF，则，则R也是也是2NF。采用投

20、影分解法将一个采用投影分解法将一个2NF的关系分解为多个的关系分解为多个3NF的关系，可以在一的关系，可以在一定程度上解决原定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。、修改复杂等问题。 将一个将一个2NF关系分解为多个关系分解为多个3NF的关系后，并不能完全消除关系的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。模式中的各种异常情况和数据冗余。现在学习的是第33页，共102页以下数据表为几范式以下数据表为几范式S(sno,sname,cno,cname,grade)图书表图书表(书号书号,名字名字,

21、书类别书类别,类别名字类别名字)学生表学生表(学号学号,姓名姓名,班级班级,辅导员辅导员)现在学习的是第34页，共102页BCBC范式（范式（BCNFBCNF）定义定义5.9 设关系模式设关系模式R1NF，如果对于，如果对于R的每个函数依的每个函数依赖赖XY，若，若Y不属于不属于X，则，则X必含有候选码，那么必含有候选码，那么RBCNF。若若RBCNF 每一个决定属性集（因素）都包含（候选）码每一个决定属性集（因素）都包含（候选）码R中的所有属性（主，非主属性）都完全函数依赖于码中的所有属性（主，非主属性）都完全函数依赖于码R3NF（证明）（证明）若若R3NF 则则 R不一定不一定BCNF现在

22、学习的是第35页，共102页 BCNFBCNF例：在关系模式例：在关系模式STJ（S，T，J）中，）中，S表示学生，表示学生，T表示表示教师，教师，J表示课程。表示课程。每一教师只教一门课。每门课由若干教师教，某一学生选定某门课每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称所选课的名称 ： (S，J)T，(S，T)J，TJ现在学习的是第36页，共102页 BCNFBCNF SJTSTJSTJ现在学习的是第37页，共102页BCNFBCNFSTJ3NF (S

23、，J)和和(S，T)都可以作为候选码都可以作为候选码 S、T、J都是主属性都是主属性STJBCNFTJ，T是决定属性集，是决定属性集，T不是候选码不是候选码现在学习的是第38页，共102页BCNFBCNF解决方法：将解决方法：将STJ分解为二个关系模式分解为二个关系模式： SJ(S，J) BCNF， TJ(T，J) BCNF 没有没有任何属性任何属性对码的部分函数依赖和传递函数依赖对码的部分函数依赖和传递函数依赖SJSTTJTJ现在学习的是第39页，共102页3NF3NF与与BCNFBCNF的关系的关系如果关系模式如果关系模式RBCNF， 必定有必定有R3NF如果如果R3NF，且，且R只有一个

24、候选码，只有一个候选码， 则则R必属于必属于BCNF。现在学习的是第40页，共102页复习复习1NF:每个表的每个属性是不可再分的每个表的每个属性是不可再分的”最小最小列名列名”2NF:属于属于1NF,且表中不存在且表中不存在”非主属性非主属性”对对码的码的”部分函数依赖部分函数依赖”3NF:属于属于2NF且不存在且不存在”非主属性非主属性”对码的对码的”传递函数依赖传递函数依赖”现在学习的是第41页，共102页判定范式的技巧判定范式的技巧1.主码为单列属性的表一定是主码为单列属性的表一定是2NF2.属于属于2NF且非主属性只有且非主属性只有0-1个，一定是个，一定是3NF3.二元关系一定是二

25、元关系一定是3NF4.只要是抽象的关系一定是只要是抽象的关系一定是1NF现在学习的是第42页，共102页 例例:2004年数据库系统工程师考试题：年数据库系统工程师考试题：答：答：D现在学习的是第43页，共102页BCNFBCNF的关系模式所具有的性质的关系模式所具有的性质 所有非主属性都完全函数依赖于每个候选码所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非码的任何一组属性没有任何属性完全函数依赖于非码的任何一组属性现在学习的是第44页，共102页三、数据依赖的公理系统三、数据依

26、赖的公理系统逻辑蕴含逻辑蕴含定义定义5.11 对于满足一组函数依赖对于满足一组函数依赖 F 的关系模的关系模式式R ，其任何一个关系，其任何一个关系r，若函数依，若函数依赖赖XY都成立都成立, 则称则称 F逻辑蕴含逻辑蕴含X Y现在学习的是第45页，共102页ArmstrongArmstrong公理系统公理系统一套推理规则，是模式分解算法的理论基础一套推理规则，是模式分解算法的理论基础用途用途l求给定关系模式的码求给定关系模式的码l从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖现在学习的是第46页，共102页1. Armstrong1. Armstrong公理系统公理系统 关

27、系模式关系模式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现在学习的是第47页，共102页（

28、l）自反律）自反律:若若Y X U，则，则X Y为为F所蕴含所蕴含证证: 设设Y X U 对对R 的任一关系的任一关系r中的任意两个元组中的任意两个元组t，s：若若tX=sX，由于，由于Y X，有，有ty=sy，所以所以XY成立成立.自反律得证自反律得证Armstrong推理规则是正确的现在学习的是第48页，共102页(2)增广律增广律: 若若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ 为为F所所蕴含。蕴含。 证：证：设设XY为为F所蕴含，且所蕴含，且Z U。 设设R 的任一关系的任一关系r中任意的两个元组中任意的两个元组t，s；若若tXZ=sXZ，则有，则有tX=sX和和tZ=sZ

29、；由由XY，于是有，于是有tY=sY，所以，所以tYZ=sYZ，所以，所以XZYZ为为F所蕴含所蕴含.增广律得证。增广律得证。现在学习的是第49页，共102页(3) 传递律：若传递律：若XY及及YZ为为F所蕴含，则所蕴含，则 XZ为为 F所蕴含。所蕴含。证：证：设设XY及及YZ为为F所蕴含。所蕴含。对对R 的任一关系的任一关系 r中的任意两个元组中的任意两个元组 t，s。若若tX=sX，由于，由于XY，有，有 tY=sY；再由再由YZ，有，有tZ=sZ，所以，所以XZ为为F所蕴含所蕴含.传递律得证。传递律得证。现在学习的是第50页，共102页2. 2. 导出规则导出规则1.根据根据A1，A2，

30、A3这三条推理规则可以得到下面三条推理规这三条推理规则可以得到下面三条推理规则：则： 合并规则：由合并规则：由XY，XZ，有，有XYZ。伪传递规则：由伪传递规则：由XY，WYZ，有，有XWZ。分解规则：由分解规则：由XY及及 Z Y，有，有XZ。现在学习的是第51页，共102页设关系模式设关系模式R（ABCDE），），F是是R上成立的上成立的FD集，集，F=（AB C,CD E,DE B),试判断试判断AB是是R的候选码？的候选码？ABD呢？呢？现在学习的是第52页，共102页有关系模式有关系模式R（ABC），），F是是R上成立的上成立的FD集，集，F=(C B,B A),该关系是几范式该关系

31、是几范式现在学习的是第53页，共102页3. 3. 函数依赖闭包函数依赖闭包定义定义3.7 在关系模式在关系模式R中为中为F所逻辑蕴含所逻辑蕴含的函数依赖的全体叫作的函数依赖的全体叫作 F的闭包，记为的闭包，记为F+。定义定义4.13 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U， XF+ = A|XA能由能由F 根据根据Armstrong公理导出公理导出，XF+称为属性称为属性集集X关于函数依赖集关于函数依赖集F 的闭包的闭包现在学习的是第54页，共102页关于闭包的引理关于闭包的引理引理引理3.4 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U

32、，XY能由能由F 根据根据Armstrong公理导出的充分必要条件是公理导出的充分必要条件是Y XF+用途用途 将判定将判定XY是否能由是否能由F根据根据Armstrong公理导出的问题，公理导出的问题， 就转化为求出就转化为求出XF+ ，判定，判定Y是否为是否为XF+的子集的问题的子集的问题现在学习的是第55页，共102页求闭包的算法求闭包的算法算法算法 3.1 求属性集求属性集X（X U）关于）关于U上的函数依上的函数依 赖集赖集F 的闭包的闭包XF+ 输入：输入：X，F输出：输出：XF+步骤：步骤：（1）令）令X（0）=X，i=0（2）求）求B，这里，这里B = A |( V)( W)(

33、VW F V X（i）A W)；（3）X（i+1）=BX（i） 现在学习的是第56页，共102页算法算法3.13.1（4）判断）判断X（i+1）= X （i）吗吗?（5）若相等或）若相等或X（i）=U , 则则X（i）就是就是XF+ , 算法终止。算法终止。（6）若否，则）若否，则 i=i+l，返回第（，返回第（2）步。）步。对于算法对于算法3.l， 令令ai =|X（i）|，ai 形成一个步长大形成一个步长大于于1的严格递增的序列，序列的上界是的严格递增的序列，序列的上界是 | U |，因，因此该算法最多此该算法最多 |U| - |X| 次循环就会终止。次循环就会终止。现在学习的是第57页，

34、共102页函数依赖闭包函数依赖闭包例例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。现在学习的是第58页，共102页函数依赖闭包函数依赖闭包(2)因为因为X（0） X（1） ，所以再找出左部为，所以再找出左部为ABCD子集的那些函子集的那些函数依赖，又得到数依赖，又得到A

35、BC，BD， CE，ACB， 于是于是X（2）=X（1）BCDE=ABCDE。(3)因为因为X（2）=U，算法终止，算法终止所以（所以（AB）F+ =ABCDE。现在学习的是第59页，共102页函数依赖闭包函数依赖闭包练习：给定关系模式练习：给定关系模式R（U，F），），U=A，B，C，D，E，F=B-A,D-A,A-E,AC-B,其属性其属性AD的闭包为的闭包为_,其候选关键字为其候选关键字为_.答案：答案：AD的闭包为：的闭包为：ADE其候选关键字为：其候选关键字为：CD 现在学习的是第60页，共102页4. Armstrong4. Armstrong公理系统的有效性与完备性公理系统的有效

36、性与完备性定理定理3.4 Armstrong的公理系统是有效且完备的。的公理系统是有效且完备的。有效性：由有效性：由F出发根据出发根据Armstrong公理推导出来的每一个公理推导出来的每一个函数依赖一定在函数依赖一定在F+中。中。 /*Armstrong正确正确完备性：完备性：F+中的每一个函数依赖，必定可以由中的每一个函数依赖，必定可以由F出发根据出发根据Armstrong公理推导出来公理推导出来 。/* Armstrong公理够用，完全完备公理够用，完全完备性：所有不能用性：所有不能用Armstrong公理推导出来公理推导出来f, 都不为真。若都不为真。若 f 不能不能用用Armstro

37、ng公理推导出来，公理推导出来， f F+ 现在学习的是第61页，共102页有效性与完备性的证明有效性与完备性的证明证明：证明：1. 有效性有效性2. 完备性完备性只需证明逆否命题只需证明逆否命题: 若函数依赖若函数依赖XY不能由不能由F从从Armstrong公理导出，那么它必然不为公理导出，那么它必然不为F所蕴含所蕴含分三步证明：分三步证明：现在学习的是第62页，共102页5. 5. 函数依赖集等价函数依赖集等价定义定义6.2.9 如果如果G+=F+，就说函数依赖集，就说函数依赖集F覆覆盖盖G（F是是G的覆盖，或的覆盖，或G是是F的覆盖），或的覆盖），或F与与G等价。等价。现在学习的是第63

38、页，共102页函数依赖集等价的充要条件函数依赖集等价的充要条件引理引理6.2.3 F+ = 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+。现在学习的是第64页，共102页函数依赖集等价函数依赖集等价要判定要判定F G+，只须逐一对，只须逐一对F中的函数依赖中的函数依赖XY，考察，考察 Y 是否属

39、于是否属于XG+ 就行了。因此就行了。因此引理引理5.3 给出了判断两个函数依赖集等价的可给出了判断两个函数依赖集等价的可行算法。行算法。 现在学习的是第65页，共102页6. 6. 最小依赖集最小依赖集 定义定义3.10 如果函数依赖集如果函数依赖集F满足下列条件，则满足下列条件，则称称F为一个极小函数依赖集。亦称为最小依赖为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。集或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得F与与 F-XA等价。等价。 (3) F中不存在这样的

40、函数依赖中不存在这样的函数依赖XA， X有真有真 子集子集Z使得使得F-XAZA与与F等价。等价。 现在学习的是第66页，共102页最小依赖集最小依赖集例例2 对于关系模式对于关系模式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 -(

41、SNO，SDEPT)SDEPT SNOSDEPT也与也与F 等价等价现在学习的是第67页，共102页7. 7. 极小化过程极小化过程定理定理6.2.5 每一个函数依赖集每一个函数依赖集F均等价于一个极小均等价于一个极小 函数依赖集函数依赖集Fm。此。此Fm称为称为F的最小依赖集的最小依赖集证证:构造性证明，依据定义分三步对构造性证明，依据定义分三步对F进行进行“极小化处理极小化处理”，找，找出出F的一个最小依赖集。的一个最小依赖集。(1)逐一检查逐一检查F中各函数依赖中各函数依赖FDi：XY， 若若Y=A1A2 Ak，k 2， 则用则用 XAj |j=1，2， k 来取代来取代XY。 引理引理

42、5.1保证了保证了F变换前后的等价性。变换前后的等价性。现在学习的是第68页，共102页极小化过程极小化过程(2)逐一检查逐一检查F中各函数依赖中各函数依赖FDi：XA， 令令G=F-XA， 若若A XG+， 则从则从F中去掉此函数依赖。中去掉此函数依赖。 由于由于F与与G =F-XA等价的充要条件是等价的充要条件是A XG+ 因此因此F变换前后是等价的。变换前后是等价的。现在学习的是第69页，共102页极小化过程极小化过程(3)逐一取出逐一取出F中各函数依赖中各函数依赖FDi：XA， 设设X=B1B2Bm， 逐一考查逐一考查Bi （i=l，2，m），）， 若若A （X-Bi ）F+ ， 则以

43、则以X-Bi 取代取代X。 由于由于F与与F-XAZA等价的充要条件是等价的充要条件是A ZF+ ，其中，其中Z=X-Bi 因此因此F变换前后是等价的。变换前后是等价的。现在学习的是第70页，共102页极小化过程极小化过程由定义，最后剩下的由定义，最后剩下的F就一定是极小依赖集。就一定是极小依赖集。 因为对因为对F的每一次的每一次“改造改造”都保证了改造前后的两个函都保证了改造前后的两个函数依赖集等价，因此剩下的数依赖集等价，因此剩下的F与原来的与原来的F等价。等价。 证毕证毕定理定理5.3的证明过程的证明过程 也是求也是求F极小依赖集的极小依赖集的过程过程现在学习的是第71页，共102页极小

44、化过程极小化过程例例3 F = AB，BA，BC， AC，CA Fm1、Fm2都是都是F的最小依赖集：的最小依赖集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依赖集的最小依赖集Fm不一定是唯一的它与对各函数依赖不一定是唯一的它与对各函数依赖FDi 及及XA中中X各属性的处置顺序有关各属性的处置顺序有关现在学习的是第72页，共102页极小化过程极小化过程极小化过程极小化过程( 定理定理6.2.5 的证明的证明 )也是检验也是检验F是是否为极小依赖集的一个算法否为极小依赖集的一个算法l若改造后的若改造后的F与原来的与原来的F相同，说明相同，说明F本身就是本身就是一个最

45、小依赖集一个最小依赖集现在学习的是第73页，共102页极小化过程极小化过程在在R中可以用与中可以用与F等价的依赖集等价的依赖集G来取代来取代Fl原因：两个关系模式原因：两个关系模式R1 ，R2，如，如果果F与与G等价，那么等价，那么R1的关系一定是的关系一定是R2的关系。反的关系。反过来，过来，R2的关系也一定是的关系也一定是R1的关系。的关系。 现在学习的是第74页，共102页五、关系模式规范化方法五、关系模式规范化方法关系数据库的规范化理论是数据库逻辑设计关系数据库的规范化理论是数据库逻辑设计的工具。的工具。一个关系只要其分量都是不可分的数据项，一个关系只要其分量都是不可分的数据项，它就是

46、规范化的关系，但这只是最基本的规它就是规范化的关系，但这只是最基本的规范化。范化。规范化程度可以有多个不同的级别规范化程度可以有多个不同的级别现在学习的是第75页，共102页规范化（续）规范化（续）规范化程度过低的关系不一定能够很好地描规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题常、修改复杂、数据冗余等问题一个低一级范式的关系模式，通过模式分解一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化合，这种过

47、程就叫关系模式的规范化现在学习的是第76页，共102页规范化（续）规范化（续）关系模式规范化的基本步骤关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除决定属性消除决定属性 2NF集非码的非平集非码的非平 消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖凡函数依赖凡函数依赖 3NF 消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖消除非平凡且非函数依赖的多值依赖 4NF现在学习的是第77页，共102页规范化的基本思想规范化的基本思想l消除不合适的数据依赖消除不合适的数据依

48、赖l的各关系模式达到某种程度的的各关系模式达到某种程度的“分离分离”l采用采用“一事一地一事一地”的模式设计原则的模式设计原则 让一个关系描述一个概念、一个实体或者实让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它体间的一种联系。若多于一个概念就把它“分离分离”出去出去l所谓规范化实质上是概念的单一化所谓规范化实质上是概念的单一化现在学习的是第78页，共102页规范化（续）规范化（续）不能说规范化程度越高的关系模式就越好不能说规范化程度越高的关系模式就越好在设计数据库模式结构时，必须对现实世界的实际情况和用在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求

49、作进一步分析，确定一个合适的、能够反映现实户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式世界的模式上面的规范化步骤可以在其中任何一步终止上面的规范化步骤可以在其中任何一步终止现在学习的是第79页，共102页3.3 3.3 模式的分解模式的分解把低一级的关系模式分解为若干个高一级的把低一级的关系模式分解为若干个高一级的关系模式的方法并不是唯一的关系模式的方法并不是唯一的只有能够保证分解后的关系模式与原关系模只有能够保证分解后的关系模式与原关系模式等价，分解方法才有意义式等价，分解方法才有意义现在学习的是第80页，共102页关系模式分解的标准关系模式分解的标准三种模式分解的等价定义

50、三种模式分解的等价定义 分解具有无损连接性分解具有无损连接性 分解要保持函数依赖分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连接性分解既要保持函数依赖，又要具有无损连接性现在学习的是第81页，共102页模式的分解（续）模式的分解（续）定义定义4.16 关系模式关系模式R的一个分解：的一个分解：= R1，R2，Rn U=U1U2Un，且不存在且不存在 Ui Uj，Fi 为为 F在在 Ui 上的投影上的投影定义定义4.17 函数依赖集合函数依赖集合XY | XY F+XY Ui 的一个覆盖的一个覆盖 Fi 叫作叫作 F 在属性在属性 Ui 上的投影上的投影现在学习的是第82页，共102页