《关系数据理论》PPT课件.ppt

《《关系数据理论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《关系数据理论》PPT课件.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 关系数据理论关系数据理论主要内容主要内容6.1问题的提出问题的提出6.2 规范化规范化6.3 数据依赖的公理系统数据依赖的公理系统6.4 模式的分解模式的分解6.1 问题的提出问题的提出一、一、关系数据库逻辑设计关系数据库逻辑设计定义：定义：针对具体问题，如何构造一个适合于它的数据模式针对具体问题，如何构造一个适合于它的数据模式数据库逻辑设计的工具数据库逻辑设计的工具关系数据库的规范化理论关系数据库的规范化理论二、引例：数据模式二、引例：数据模式“好好”与与“不好不好”例：建立描述学校教务的数据库，涉及的对象如下：例：建立描述学校教务的数据库，涉及的对象如下：学生的学号（学生的学

2、号（SnoSno）、学生的姓名（）、学生的姓名（SnameSname）、所在系（）、所在系（SdeptSdept）、）、系主任姓名（系主任姓名（MnameMname）、课程号（）、课程号（CnoCno）、成绩（）、成绩（GradeGrade）对象间联系：对象间联系：1.1.一个系有若干学生，一个系有若干学生，一个学生只属于一个系；一个学生只属于一个系；2.2.一个系只有一名主任；一个系只有一名主任；3.3.一个学生可以选修多门课程，一个学生可以选修多门课程，每门课程有若干学生选修；每门课程有若干学生选修；4.4.每个学生所学的每门课程都有一个成绩。每个学生所学的每门课程都有一个成绩。引例：数据

3、模式引例：数据模式“好好”与与“不好不好”(续续)第一种设计方案：第一种设计方案：使用单一的关系模式使用单一的关系模式 ：StudentStudent（Sno,Sname,Sdept,Mname,Cno,GradeSno,Sname,Sdept,Mname,Cno,Grade）思考：确定表的主键。思考：确定表的主键。主键：主键：Sno，CnoSnoSnameSdeptMnameCnoGrades1王小华计算机系张明c195s1王小华计算机系张明c290s2刘丹计算机系张明c189s2刘丹计算机系张明c391s3李义计算机系张明c285s4谢敏物理系王志c490s4谢敏物理系王志C588.下面给

4、出该方案的一个实例：下面给出该方案的一个实例：存在以下问题：n数据冗余太大n更新异常n插入异常n删除异常结论：结论：该方案该方案“不好不好”引例：数据模式引例：数据模式“好好”与与“不好不好”(续续)第二种设计方案：第二种设计方案：使用三个关系模式使用三个关系模式 ：S S（Sno,Sname,Sdept,Sno,Sname,Sdept,）SC SC（Sno,Cno,GradeSno,Cno,Grade）DEPT DEPT（Sdept,MnameSdept,Mname）该方案解决了方案该方案解决了方案一中的问题，因此，该一中的问题，因此，该方案方案“好好”三、关系数据库规范化理论的内容三、关系

5、数据库规范化理论的内容数据依赖数据依赖范式范式模式设计（模式分解）模式设计（模式分解）函数依赖多值依赖由函数依赖决定的包括：1NF、2NF、3NF、BCNF由多值依赖决定的例如：4NF四、关系模式的简化表示四、关系模式的简化表示关系模式由五部分组成，即它是一个五元组：关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)R(U,D,DOM,F)R R：关系名关系名U U：组成该关系的属性名集合组成该关系的属性名集合D D：属性组属性组U U中属性所来自的域中属性所来自的域DOMDOM：属性向域的映象集合属性向域的映象集合F F：属性间数据的依赖关系集合属性间数据的依赖关系集合在规范化

6、理论中，简化为一个三元组：在规范化理论中，简化为一个三元组：R R（U,FU,F）6.2 规范化规范化6.2.1 函数依赖函数依赖函数依赖函数依赖例如：“学号”确定之后，学生姓名就被唯一地确定；Sno，Cno确定之后，成绩就被唯一地确定；这种依赖关系类似于数学中的函数y=f(x)，因此，称为函数依赖。SnoSnameSdeptMnameCnoGrades1王小华计算机系张明c195s1王小华计算机系张明c290s2刘丹计算机系张明c189s2刘丹计算机系张明c391s3李义计算机系张明c285s4谢敏物理系王志c490s4谢敏物理系王志c588.Student一、函数依赖定义一、函数依赖定义

7、定义定义6.1 6.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。X X称为这个函数依赖的称为这个函数依赖的决定属性集决定属性集(Determinant)(Determinant)。思考：写出思考：写出Stu

8、dent中的函数依赖。中的函数依赖。Student（Sno,Sname,Sdept,Mname,Cno,Grade）F=Sno Sname,Sno Sdept,Sdept Mname,（Sno,Cno）Grade，说明：说明：函数依赖不是指关系模式函数依赖不是指关系模式R R的某个或某些关系实例满足的的某个或某些关系实例满足的约束条件，而是指约束条件，而是指R R的所有关系实例均要满足的约束条件。的所有关系实例均要满足的约束条件。函数依赖是函数依赖是语义范畴语义范畴的概念。只能根据数据的语义来确定的概念。只能根据数据的语义来确定函数依赖。函数依赖。例如：例如：姓名姓名年龄年龄这个函数依赖只有在

9、不重名的条件下才成立这个函数依赖只有在不重名的条件下才成立函数依赖例题函数依赖例题 例例:S(Sno,Sname,Ssex,Sage,Sdept):S(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有假设不允许重名，则有:F=Sno SsexF=Sno Ssex，Sno SageSno Sage，Sno SdeptSno Sdept，Sname SsexSname Ssex，Sname SageSname Sage，Sname SdeptSname Sdept，Sno SnameSno Sname 若若XYXY，并且，并且YX,YX,则记为则记为X XY Y。若若Y Y

10、不函数依赖于不函数依赖于X,X,则记为则记为X YX Y，例如：，例如：Ssex SageSsex Sage二、函数依赖的分类二、函数依赖的分类可以从不同角度分类：可以从不同角度分类：平凡函数依赖与非平凡函数依赖平凡函数依赖与非平凡函数依赖完全函数依赖与部分函数依赖完全函数依赖与部分函数依赖直接函数依赖与传递函数依赖直接函数依赖与传递函数依赖1、平凡函数依赖与非平凡函数依赖、平凡函数依赖与非平凡函数依赖如果如果XYXY，但，但Y Y X X，则称，则称XYXY是平凡的函数依赖是平凡的函数依赖若果若果XYXY，但，但Y Y X,X,则称则称XYXY是非平凡的函数依赖是非平凡的函数依赖例如：例如：

11、StudentStudent（Sno,Sname,Sdept,Mname,Cno,GradeSno,Sname,Sdept,Mname,Cno,Grade）非平凡的函数依赖：非平凡的函数依赖：Sno Sno SnameSname Sdept Sdept MnameMname （Sno,CnoSno,Cno）GradeGrade平凡的函数依赖：平凡的函数依赖：Sno Sno Sno,Sno,（Sno,SnameSno,Sname）SnameSname平凡函数依赖与非平凡函数依赖（续）平凡函数依赖与非平凡函数依赖（续）对于任一关系模式，平凡函数依赖都是必然成立的，对于任一关系模式，平凡函数依赖都是

12、必然成立的，它不反映新的语义，因此若不特别声明，它不反映新的语义，因此若不特别声明，我们总是讨我们总是讨论论非平凡函数依赖非平凡函数依赖。2、完全函数依赖与部分函数依赖、完全函数依赖与部分函数依赖 如果如果XYXY，并且对于，并且对于X X的任何一个真子集的任何一个真子集X X，都有，都有X Y,X Y,则称则称Y Y完全函数依赖于完全函数依赖于X X，记作，记作X X Y Y。若若XYXY，但，但Y Y不完全函数依赖于不完全函数依赖于X X，则称，则称Y Y部分函数依赖于部分函数依赖于X X，记作记作X X P P Y Y。例如：例如：Student（Sno,Sname,Sdept,Mnam

13、e,Cno,Grade）指出下面的函数依赖哪些是完全的，哪些是部分的：指出下面的函数依赖哪些是完全的，哪些是部分的：Sno Sname （Sno,Cno）Grade （Sno,Sname）Sdept完全完全完全完全部分部分直接函数依赖与传递函数依赖直接函数依赖与传递函数依赖如果如果XYXY，YZYZ，且，且Y Y X X，YXYX，则称，则称Z Z传递函数依赖传递函数依赖于于X X。例如：例如：StudentStudent（Sno,Sname,Sdept,Mname,Cno,GradeSno,Sname,Sdept,Mname,Cno,Grade）因为因为Sno Sno SdeptSdept，

14、Sdept Sdept Mname Mname 所以存在传递依赖所以存在传递依赖Sno Sno MnameMname注注:如果如果XYXY，则，则Z Z直接依赖于直接依赖于X X。6.2.2 码码 若若K K U U，则，则K K称为称为R R的一个的一个侯选码侯选码（Candidate KeyCandidate Key）。若关）。若关系模式系模式R R有多个候选码，则选定其中的一个做为有多个候选码，则选定其中的一个做为主码主码（Primary keyPrimary key）。）。一些概念：一些概念：n候选码候选码n主码主码n主属性主属性n非主非主(码码)属性属性n超键超键包含候选码的属性组称

15、为超键，即:候选码超键例如，Student（Sno,Sname,Sdept,Mname,Cno,Grade）候选键：Sno，Cno超键：Sno，Cno，Sname、Sno，Cno，Sdept等等6.2.3 范式范式范式范式是符合某一种级别的关系模式的集合。是符合某一种级别的关系模式的集合。关系必须满足一定的要求。满足不同程度要求的为不同范式。关系必须满足一定的要求。满足不同程度要求的为不同范式。范式的种类：范式的种类：第一范式第一范式(1NF)(1NF)第二范式第二范式(2NF)(2NF)第三范式第三范式(3NF)(3NF)BCBC范式范式 (BCNF)(BCNF)第四范式第四范式(4NF)(

16、4NF)第五范式第五范式(5NF)(5NF)问题越少6.2.3 范式范式各种范式之间存在各种范式之间存在联系，如右图所示。联系，如右图所示。某一关系模式某一关系模式R R为为第第n n范式，可简记为范式，可简记为R R nNFnNF。一个低一级范式的一个低一级范式的关系模式，通过模关系模式，通过模式分解可以转换为式分解可以转换为若干个高一级范式若干个高一级范式的关系模式的集合，的关系模式的集合，这种过程叫做这种过程叫做规范规范化化。1NF2NF3NF4NF5NF1NF1NF1NF的定义的定义如果一个关系模式如果一个关系模式R R的所有属性都是的所有属性都是不可分的基本数据不可分的基本数据项项，

17、则，则R R 1NF1NF。第一范式是对关系模式的最起码的要求。不满足第一范式的第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。数据库模式不能称为关系数据库。但是满足第一范式的关系模式并不一定是一个好的关系模式。但是满足第一范式的关系模式并不一定是一个好的关系模式。6.2.4 2NF2NF2NF的定义的定义如果如果R R 1NF1NF，且每一个非主属性完全函数依赖于码，且每一个非主属性完全函数依赖于码，则，则，R R 2NF 2NF。2NF（续）（续）例例:关系模式关系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)S-L-C(Sno,Sde

18、pt,Sloc,Cno,Grade)其中，其中，SlocSloc为学生住处，假设每个系的学生住在同一个地方。为学生住处，假设每个系的学生住在同一个地方。主键：主键：Sno,CnoSno,Cno 函数依赖包括：函数依赖包括：F=(Sno,Cno)F=(Sno,Cno)f f Grade Grade，Sno SdeptSno Sdept，Sno SlocSno Sloc，Sdept SlocSdept Sloc 1.指出主属性和非主属性2.是2NF吗？为什么？2NF（续）（续）S-L-CS-L-C满足第一范式。满足第一范式。非主属性非主属性SdeptSdept和和SlocSloc部分函数依赖于码部

19、分函数依赖于码(SnoSno,CnoCno)S-L-CS-L-C不是不是2NF2NF，存在诸多问题，存在诸多问题。SnoCnoGradeSdeptSlocS-L-C2NF（续）（续）解决方法：解决方法：投影分解投影分解SnoCnoGradeSCSLSnoSdeptSloc 2NF（续）（续）SLCSLC分解为两个关系模式，以消除这些部分函数依赖分解为两个关系模式，以消除这些部分函数依赖 SCSC（SnoSno，CnoCno，GradeGrade）SLSL（SnoSno，SdeptSdept，SlocSloc）思考思考：分别指出两个表的主键。：分别指出两个表的主键。第二范式（续）第二范式（续）采

20、用采用投影分解法投影分解法将一个将一个1NF1NF的关系分解为多个的关系分解为多个2NF2NF的关系，的关系，可以在一定程度上减轻原可以在一定程度上减轻原1NF1NF关系中存在的插入异常、删除关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。异常、数据冗余度大、修改复杂等问题。将一个将一个1NF1NF关系分解为多个关系分解为多个2NF2NF的关系，的关系，并不能完全并不能完全消除关消除关系模式中的各种异常情况和数据冗余。系模式中的各种异常情况和数据冗余。课堂练习课堂练习1：例如：例如：StudentStudent（Sno,Sname,Sdept,Mname,Cno,GradeSno

21、,Sname,Sdept,Mname,Cno,Grade）主键：主键：Sno,CnoSno,Cno其上的函数依赖集合如下：其上的函数依赖集合如下：F=Sno F=Sno Sname,Sno Sname,Sno Sdept,Sdept Sdept,Sdept Mname,Mname,（Sno,CnoSno,Cno）GradeGrade1 1、指出主属性和非主属性、指出主属性和非主属性2 2、该关系是否属于、该关系是否属于2NF2NF？为什么？如果不是，请将其分解为一组？为什么？如果不是，请将其分解为一组2NF2NF关系模式。关系模式。课堂练习课堂练习1答案：答案：将将StudentStudent

22、（Sno,Sname,Sdept,Mname,Cno,GradeSno,Sname,Sdept,Mname,Cno,Grade）分解）分解为为一组一组2NF2NF模式：模式：SC(Sno,Cno,Grade)SC(Sno,Cno,Grade)主键：主键：SnoSno，CnoCnoSD(Sno,Sname,Sdept,Mname)SD(Sno,Sname,Sdept,Mname)主键：主键：SnoSno6.2.5 3NF3NF3NF的定义的定义如果如果R R 是是2NF2NF，且每个非主属性都，且每个非主属性都不传递依赖不传递依赖于于R R的候选码，则的候选码，则R R属于属于3NF3NF。3N

23、F（续）（续）分析下面的两个分析下面的两个2NF2NF，它们是不是属于，它们是不是属于3NF3NF。SCSC（SnoSno，CnoCno，GradeGrade）SLSL（SnoSno，SdeptSdept，SlocSloc）SnoCnoGradeSCSLSnoSdeptSloc是是不是不是 3NF（续）（续）解决方法解决方法 采用采用投影分解法投影分解法，把，把SLSL分解为两个关系模式，分解为两个关系模式，以消除传递函数依赖：以消除传递函数依赖：SDSD（SnoSno，SdeptSdept）DLDL（SdeptSdept，SlocSloc）SDSD的码为的码为SnoSno，DLDL的码为的码

24、为SdeptSdept。3NF（续）（续）这样这样S-L-C(Sno,Sdept,Sloc,Cno,Grade)S-L-C(Sno,Sdept,Sloc,Cno,Grade)就分解成为一组就分解成为一组3NF3NF模式模式SCSC（SnoSno，CnoCno，GradeGrade）SDSD（SnoSno，SdeptSdept）DLDL（SdeptSdept，SlocSloc）3NF（续）（续）若若R R 3NF3NF，则，则R R的每一个的每一个非主属性非主属性既不部分函数依赖于候选既不部分函数依赖于候选码也不传递函数依赖于候选码。码也不传递函数依赖于候选码。如果如果R R 3NF3NF，则，

25、则R R也是也是2NF2NF。采用投影分解法将一个采用投影分解法将一个2NF2NF的关系分解为多个的关系分解为多个3NF3NF的关系，的关系，可以在一定程度上解决原可以在一定程度上解决原2NF2NF关系中存在的插入异常、删除关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。异常、数据冗余度大、修改复杂等问题。将一个将一个2NF2NF关系分解为多个关系分解为多个3NF3NF的关系后，并不能完全消除的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。关系模式中的各种异常情况和数据冗余。课堂练习课堂练习2：将将StudentStudent（Sno,Sname,Sdept,Mnam

26、e,Cno,GradeSno,Sname,Sdept,Mname,Cno,Grade）分解）分解为一组为一组2NF2NF模式：模式：SC(Sno,Cno,Grade)SC(Sno,Cno,Grade)SD(Sno,Sname,Sdept,Mname)SD(Sno,Sname,Sdept,Mname)判断上述两个判断上述两个2NF2NF是否是是否是3NF3NF，如果不是请分解。，如果不是请分解。课堂练习课堂练习2答案：答案：SCSC是是3NF3NF SD SD不是不是3NF3NF 将将SDSD分解为分解为S S（Sno,Sname,SdeptSno,Sname,Sdept）和）和D D（Sdep

27、tSdept，MnameMname）这样，这样，StudentStudent（Sno,Sname,Sdept,Mname,Cno,GradeSno,Sname,Sdept,Mname,Cno,Grade）分解为一组分解为一组3NF3NF模式：模式：SC(Sno,Cno,Grade)SC(Sno,Cno,Grade)S S（Sno,Sname,SdeptSno,Sname,Sdept）D D（SdeptSdept，MnameMname）小结：小结：2NF2NF和和3NF3NF都是对都是对非主属性非主属性的要求，的要求，2NF2NF要求每一个非主属要求每一个非主属性完全函数依赖于码；性完全函数依赖

28、于码；3NF3NF要求每一个非主属性既不部分要求每一个非主属性既不部分依赖于码也不传递依赖于码。依赖于码也不传递依赖于码。6.2.6 BCNFBCNFBCNF的定义的定义R R 1NF1NF，若，若XYXY且且Y Y X X 时时X X必含有码，则，必含有码，则，R R BCNFBCNF。说明：说明：BCNFBCNF不仅对非主属性有要求，而且也对主属性有要求；不仅对非主属性有要求，而且也对主属性有要求；每一个函数依赖的每一个函数依赖的“决定属性集决定属性集”必须是超键。必须是超键。BCNF（续）（续）S-L-C(Sno,Sdept,Sloc,Cno,Grade)S-L-C(Sno,Sdept,

29、Sloc,Cno,Grade)已经分解成为一组已经分解成为一组3NF3NF模式模式SCSC（SnoSno，CnoCno，GradeGrade）key:Sno,Cno F=(Sno,Cno)Gradekey:Sno,Cno F=(Sno,Cno)GradeSDSD（SnoSno，SdeptSdept）key:Sno F=Sno Sdeptkey:Sno F=Sno SdeptDLDL（SdeptSdept，SlocSloc）key:Sdept F=Sdept Slockey:Sdept F=Sdept Sloc判断该模式集中的每个模式是不是同时满足判断该模式集中的每个模式是不是同时满足BCNFB

30、CNF？答：三个模式都满足答：三个模式都满足BCNF.BCNF（续）（续）如果一个关系模式只有两个属性构成，则该关系模式一定属于BCNF。证明：R(A,B)BCNFBCNFR上的函数依赖集可能有四种情况：上的函数依赖集可能有四种情况：1、F=A B，此时，此时，A是候选码，函数依赖的是候选码，函数依赖的“决定属性集决定属性集”是超键，是超键，因此因此R BCNF2、F=B A，此时，此时，B是候选码，函数依赖的是候选码，函数依赖的“决定属性集决定属性集”是超键，是超键，因此因此R BCNF3、F=A B，B A，此时，此时，A、B都是候选码，每个函数依赖的都是候选码，每个函数依赖的“决决定属性

31、集定属性集”是超键，因此是超键，因此R BCNF4、A，B是候选码，则不存在非平凡的函数依赖，因此是候选码，则不存在非平凡的函数依赖，因此R BCNF结论：结论：R(A,B)BCNF课堂练习课堂练习3：StudentStudent（Sno,Sname,Sdept,Mname,Cno,GradeSno,Sname,Sdept,Mname,Cno,Grade）已经分）已经分解为一组解为一组3NF3NF模式：模式：SC(Sno,Cno,Grade)SC(Sno,Cno,Grade)S S（Sno,Sname,SdeptSno,Sname,Sdept）D D（SdeptSdept，MnameMname

32、）对于该组模式：对于该组模式：1 1、指出每个模式的主键，写出其函数依赖集。、指出每个模式的主键，写出其函数依赖集。2 2、确定每个模式是否同时满足、确定每个模式是否同时满足BCNFBCNF。BCNF（续）（续）例例7 7、关系模式、关系模式SJP(S,J,P)SJP(S,J,P)中，中，S S是学生学号，是学生学号，J J是课程号，是课程号，P P表示表示名次（没有并列名次），每一个学生选修每门课程的成绩有一名次（没有并列名次），每一个学生选修每门课程的成绩有一定的名次，由语义可得到函数依赖集定的名次，由语义可得到函数依赖集F F如下：如下：F=F=（S,JS,J）PP，（J,PJ,P）S

33、S 思考：思考：指出该关系模式的候选码指出该关系模式的候选码指出主属性、非主属性指出主属性、非主属性该关系模式是否是该关系模式是否是3NF3NF？该关系模式是否是该关系模式是否是BCNFBCNF？有两个：（有两个：（S,J），（），（J,P）主属性：主属性：S、J、P；没有非主属性；没有非主属性SJP 3NFSJP BCNFSJP BCNFBCNF（续）（续）例例8 8、关系模式、关系模式STJ(S,T,J)STJ(S,T,J)中，中，S S是学生学号，是学生学号，T T表示教师编表示教师编号，号，J J是课程号，每个教师只教一门课，每门课有若干教师是课程号，每个教师只教一门课，每门课有若干教

34、师讲授，某一学生选定某门课，就对应一个固定的教师。由讲授，某一学生选定某门课，就对应一个固定的教师。由语义可得到函数依赖集语义可得到函数依赖集F F如下：如下：F=F=（S,JS,J）TT，（，（S,TS,T）J,T J J,T J 思考：思考：指出该关系模式的候选码指出该关系模式的候选码指出主属性、非主属性指出主属性、非主属性该关系模式是否是该关系模式是否是3NF3NF？该关系模式是否是该关系模式是否是BCNFBCNF？有两个：（有两个：（S,J），（），（S,T）主属性：主属性：S、J、P；没有非主属性；没有非主属性SJP 3NF规范化小节规范化小节关系模式规范化的基本步骤关系模式规范化的

35、基本步骤 1NF1NF 消除非主属性对码的消除非主属性对码的部分函数依赖部分函数依赖 2NF2NF 消除非主属性对码的消除非主属性对码的传递函数依赖传递函数依赖 3NF3NF 消除消除主属性主属性对码的部分和传递函数依赖对码的部分和传递函数依赖 BCNF BCNF 规范化小节（续）规范化小节（续）说明：说明：不能说规范化程度越高的关系模式就越好不能说规范化程度越高的关系模式就越好在设计数据库模式结构时，必须对现实世界的实际情况和用在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式

36、世界的模式上面的规范化步骤可以在其中任何一步终止上面的规范化步骤可以在其中任何一步终止第六章第六章 关系数据理论关系数据理论6.1 6.1 数据依赖数据依赖6.2 6.2 规范化规范化6.3 6.3 数据依赖的公理系统数据依赖的公理系统6.4 6.4 模式的分解模式的分解6.3 数据依赖的公理系统数据依赖的公理系统逻辑蕴含逻辑蕴含定义定义6.11 6.11 对于满足一组对于满足一组函数依赖函数依赖 F F 的关系模式的关系模式R R ，其任何一个关系其任何一个关系r r，若函数依赖若函数依赖XYXY都成立都成立,则称则称F F逻辑蕴含逻辑蕴含X X YY 例如：已知例如：已知R(X,Y,Z)R

37、(X,Y,Z)，F=XYF=XY，YZ,YZ,则则 XZXZ成立，成立，XZXZ被被F F逻辑蕴含。逻辑蕴含。Armstrong公理系统公理系统一套推理规则，是模式分解算法的理论基础一套推理规则，是模式分解算法的理论基础用途用途从一组函数依赖求得蕴含的函数依赖从一组函数依赖求得蕴含的函数依赖求给定关系模式的码求给定关系模式的码1.Armstrong公理系统公理系统 关系模式关系模式R UR F 有以下的推理规则：有以下的推理规则：Al.Al.自反律自反律（ReflexivityReflexivity）：）：若若Y Y X X U U，则，则X X Y Y为为F F所蕴含。所蕴含。A2.A2.增

38、广律增广律（AugmentationAugmentation）：若）：若X XY Y为为F F所蕴含，且所蕴含，且Z Z U U，则，则XZXZYZYZ为为F F所蕴含。所蕴含。A3.A3.传递律传递律（TransitivityTransitivity）：若）：若X XY Y及及Y YZ Z为为F F所蕴含，则所蕴含，则X XZ Z为为F F所蕴含。所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于依赖于F F证明证明(2)(2)增广律增广律:若若X XY Y为为F F所蕴含，且所蕴含，且Z Z U

39、 U，则，则XZXZYZ YZ 为为F F所蕴含。所蕴含。证：证：设设X XY Y为为F F所蕴含，且所蕴含，且Z Z U U。设设RURF 的任一关系的任一关系r r中任意的两个元组中任意的两个元组t t，s s；若若t t XZXZ=s s XZXZ，则有，则有t t X X=s s X X 和和t t Z Z=s s Z Z；由由X XY Y，于是有，于是有t t Y Y=s s Y Y，所以，所以t t YZYZ=s s YZYZ，所以，所以XZXZYZYZ为为F F所蕴含所蕴含.增广律得证。增广律得证。2.导出规则导出规则1.1.根据根据A1A1，A2A2，A3A3这三条推理规则可以

40、得到下面三条推理规这三条推理规则可以得到下面三条推理规则：则：合并规则合并规则：由：由X XY Y，X XZ Z，有，有X XYZYZ。伪传递规则伪传递规则：由：由X XY Y，WYWYZ Z，有，有XWXWZ Z。分解规则分解规则：由：由X XYZYZ，有有X XY Y、X XZ Z。3.函数依赖集闭包函数依赖集闭包定义定义6.l2 6.l2 在关系模式在关系模式RURF中为中为F F所逻辑蕴含所逻辑蕴含的函数依赖的全体叫作的函数依赖的全体叫作 F F的闭包的闭包，记为，记为F F+。说明：F+是R上的全部函数依赖。F的闭包的闭包F+计算是NP完全问题，F+是R上的全部函数依赖。F+=X ,

41、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 YZ,XYZ XZ,X XYZ,XY XYZ,XZ XYZ,XYZ XYZ R（X,Y,Z）,F=X Y,Y Z属性组的闭包属性组的闭包 定义定义6.13 6.13 设设F F为属性集为属性集U U上的一组函数依赖，上的一组函数依赖，X X U U

42、，X XF F+=A|XA|XA A能由能由F F 根据根据ArmstrongArmstrong公理导出公理导出，X XF F+称为属性集称为属性集X X关于函数依赖集关于函数依赖集F F 的闭包。的闭包。求闭包的算法求闭包的算法算法算法6.l 6.l 求属性集求属性集X X（X X U U）关于）关于U U上的函数依上的函数依 赖集赖集F F 的闭包的闭包X XF F+输入：输入：X X，F F输出：输出：X XF F+步骤：步骤：（1 1）令）令X X（0 0）=X X，i i=0=0（2 2）求）求B B，YBYB，其中，其中Y Y X X且且 B B X X；（3 3）X X（i+1i

43、+1）=B B X X（i i）算法算法6.l（4 4）判断）判断X X（i+1i+1）=X X （i i）吗吗?（5 5）若相等或）若相等或X X（i i）=U,U,则则X X（i i）就是就是X XF F+,算法终止。算法终止。（6 6）若否，则）若否，则 i i=i i+l+l，返回第（，返回第（2 2）步。）步。对于算法对于算法6.l6.l，令令a ai i=|=|X X（i i）|，a ai i 形成一个步长大形成一个步长大于于1 1的严格递增的序列，序列的上界是的严格递增的序列，序列的上界是|U U|，因，因此该算法最多此该算法最多|U U|-|-|X|X|次循环就会终止。次循环就

44、会终止。U=A,B,C,D;F=A B,BC D;U=A,B,C,D;F=A B,BC D;计算计算A AF F+=AB=AB 例子例子ABAF+=A，B U=A,B,C,D;F=A B,BC D;U=A,B,C,D;F=A B,BC D;计算计算C CF F+例子例子CCF+=C U=A,B,C,D;F=A B,BC D;U=A,B,C,D;F=A B,BC D;计算计算(AC)(AC)F F+课堂练习课堂练习1(AC)F+=A,B,C,DBACDR(A,B,C,D)R(A,B,C,D)，F=A B,BC D;F=A B,BC D;问：问：AC DAC D是否在是否在R R上成立？上成立？判

45、断一个函数依赖在判断一个函数依赖在R上是否成立上是否成立 由于由于(AC)F+=A,B,C,D，所以，所以AC D在R上成立。第一种解决方法：计算F+，看看AC D是否在其中。该方法计算量大，不可行。第二种解决方法：如果AC D成立，则D一定属于(AC)F+,因此，首先计算(AC)F+，如果D(AC)F+，则成立，否则，不成立。关于闭包的引理关于闭包的引理引理引理6.2 6.2 设设F F为属性集为属性集U U上的一组函数依赖，上的一组函数依赖，X X，Y Y U U，X XY Y能由能由F F 根根据据ArmstrongArmstrong公理导出的充分必要条件是公理导出的充分必要条件是Y Y

46、 X XF F+用途用途 将判定将判定X XY Y是否能由是否能由F F根据根据ArmstrongArmstrong公理导出的问题，公理导出的问题，就转化为求出就转化为求出X XF F+，判定，判定Y Y是否为是否为X XF F+的子集的问题的子集的问题课堂练习课堂练习2 已知关系模式已知关系模式R R ，其中，其中U U=A A，B B，C C，D D，E E；F F=ABABC C，B BD D，C CE E，ECECB B，ACACB B。ABABE E是否成立？是否成立？由于(A,B)F+=A,B,C,D,E，所以ABE成立。内容回顾内容回顾以上详细讲解了：以上详细讲解了：n 函数依赖函数依赖n 规范化规范化作业：作业：n本章习题：本章习题：1 1、2 2