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

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

1、第06章关系数据理论第1页，共82页，编辑于2022年，星期日关系数据理论主要内容：问题的提出规范化数据依赖的公理系统模式分解第2页，共82页，编辑于2022年，星期日6.1问题提出及函数依赖如果将前面的student,course,和s_c表合成一个表，会是怎样的？其中(sno,cno)为主码。Snosname sagespnocnocnamemark52120066刘洋23100520006高等数学8552120076王敏24100320007数据库原理8752120066刘洋23100520007数据库原理8452120066刘洋23100510002数据结构90问题：第3页，共82页，

2、编辑于2022年，星期日1、在表中每添加一个选课记录(元组)，需要添加的信息包括哪些，这些数据有什么特点？2、假设“刘洋”同学的姓名改为“刘杨”，应该怎样操作？学生的姓名，年龄和课程名称也需要添加，同一个学生或同一门课程在多次添加选课记录时，重复太大存在的冗余大。需要修改每一个与“刘洋”有关的记录。更新异常。3、假设新增一门新课，还没有学生选修，如何在数据库中体现出？无法体现出插入异常4、假设有一部分同学毕业了，需要删除他们的记录，会发生怎样的情况？可能将课程的信息丢失了。删除异常若使用合并前的表，是否也会出现上述现象？因此第4页，共82页，编辑于2022年，星期日合并后的表，它的结构不合理，

3、原因分析：合并后的表，它的结构不合理，原因分析：1、学号，姓名，年龄，专业编号、学号，姓名，年龄，专业编号4个属性，从常识上讲只要知道个属性，从常识上讲只要知道学号，学号，其其他他3个属性便可得知，同理可知，知道了个属性便可得知，同理可知，知道了课程号课程号就可以知道课程的名称。就可以知道课程的名称。从另一个角度讲，一旦确定了学号的值或课程号的值就可以知道从另一个角度讲，一旦确定了学号的值或课程号的值就可以知道相应相应的的其他信息，如姓名，年龄，课程名称。其他信息，如姓名，年龄，课程名称。我们说姓名或年龄我们说姓名或年龄函数依赖于函数依赖于学号，课程名称学号，课程名称函数依赖于函数依赖于课程号

4、。课程号。函数依赖的定义：函数依赖的定义：在前面的关系中还有那些在前面的关系中还有那些依赖关系依赖关系？第5页，共82页，编辑于2022年，星期日所谓函数依赖是指在所谓函数依赖是指在关系关系R(型型)中中,X、Y为为R的两个属性或的两个属性或属性组属性组,如果对于如果对于R的所有的所有关系关系r(记录记录)都存在：都存在：对于对于X的每的每一个具体值一个具体值,Y都只有一个具体值与之对应都只有一个具体值与之对应,则称属性则称属性Y函数函数依赖于属性依赖于属性X。定义定义6.1 函数依赖函数依赖或者说或者说,属性属性X函数决定属性函数决定属性Y,记作记作XY。其中其中X称为这个函称为这个函数依赖

5、的决定属性组，也称为数依赖的决定属性组，也称为决定因素决定因素,Y称为称为被决定因素被决定因素。此定义可简单表述为：此定义可简单表述为：如果属性如果属性X的值决定属性的值决定属性Y的值的值,那么属性那么属性Y函数依赖于属性函数依赖于属性X。换一种说法是换一种说法是,如果知道如果知道X的值的值,就可以获得就可以获得Y的值的值。第6页，共82页，编辑于2022年，星期日术语和记号术语和记号Snosname sagespnocnocnamemark在该关系中下列函数依赖是否成立？1、Snosname2、(Sno,cno)sno两者有什么不同？第7页，共82页，编辑于2022年，星期日问题：什么时候存

6、在平凡的函数依赖？对于任何一个关系模式，平凡函数依赖都必然成立，因此，若不做特别说明，函数依赖总是指非平凡的函数依赖。第8页，共82页，编辑于2022年，星期日在前面关系中，存在哪些函数依赖？(Sno,cno)markSnosname,Snosage,SnospnoCnocnamesname和sage是否函数依赖于(Sno,cno)，还函数依赖于哪个属性，这个属性与(Sno,cno)的关系是什么？是，sno，包含与被包含的关系。有没有其他函数依赖关系？因此Snosname sagespnocnocnamemark第9页，共82页，编辑于2022年，星期日定义定义6.2 完全函数依赖与部分函数依

7、赖完全函数依赖与部分函数依赖在R(U)中，如果XY，并且对于X的任何一个真子集X，都有则称Y对X完全函数依赖，记作若XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：问题：第10页，共82页，编辑于2022年，星期日下列关系中有哪些完全函数依赖关系，有哪些部分函数依赖关系？Snosnamesagespnocnocnamemark结论：表之所以存在前面的问题是因为它的非码属性之间存在函数依赖，即非码属性部分函数依赖于码，如何解决？SnosnamesagespnocnocnameSnocnomark分解后是否存在部分函数依赖？第11页，共82页，编辑于2022年，星期日考查下面关系：Sn

8、o(学号)Sdept(学生所在院系)Mname(系负责人)存在哪些完全函数依赖关系，特点是什么？SnoSdept，SdeptMnameSnoMname因此引出下面的定义：问题：SdeptSno是否成立？第12页，共82页，编辑于2022年，星期日定义定义6.3 传递函数依赖传递函数依赖若不添加，则XY，变成第13页，共82页，编辑于2022年，星期日问题：主码从函数依赖的角度，如何定义？定义定义6.4主码主码第14页，共82页，编辑于2022年，星期日函数依赖小结函数依赖非平凡的函数依赖完全函数依赖部分函数依赖传递函数依赖在关系(表)的“合理”化过程中如何使用函数依赖？第15页，共82页，编辑

9、于2022年，星期日6.2范式第1范式的内容是什么？主码与其他非码属性的关系应该是怎样的？考虑如下关系，(Sno,Cno)为码。Sno(学号)Sdept(院系)Sloc(宿舍)Cno(课程号)Grade(成绩)该关系中存在哪些完全函数依赖关系和部分函数依赖关系？第16页，共82页，编辑于2022年，星期日2、假设有一门课程C3只有某一个学生(如S6)选了，现在该学生退学了，需要删除他的信息，在删除时会发生怎样的现象？3、若有一个学生选修个多门课程，现在他要调宿舍，需要怎样修改表中的记录？1、若要添加一个学生，他还没有选课，会出现怎样的现象？4、假设有一个学生选修了多门课程，需要怎样添加记录？S

10、dept和Sloc多次填写冗余大主码不全，添加出错，插入异常将课程的信息也删除了删除异常需要修改多个记录修改复杂如何解决第17页，共82页，编辑于2022年，星期日定义定义6.6若关系R 1NF，且每个非主属性完全函数依赖于码，则R 2NF。前面的关系是否满足2NF，若不满足该如何修改使它满足2NF?Sno(学号)Sdept(院系)Sloc(宿舍)Cno(课程号)Grade(成绩)SlocSdeptSnoS_LSnoGradeCnoS_C分解后的各个关系是否满足2NF，分解的原则是什么？第18页，共82页，编辑于2022年，星期日若关系中存在非主属性部分函数依赖于主码(不满足2NF)，则修改关

11、系去掉这些部分函数依赖关系，一般做法就是分解关系成为多个关系，使它们满足2NF。考虑一下，分解后的关系S_L的特性？SlocSdeptSnoS_L在添加学生的记录时，需要添加哪些属性，哪些是冗余的，应该如何修改？第19页，共82页，编辑于2022年，星期日定义定义6.7关系模式R中若不存在这样的码X，属性组Y及非主属性Z()使得XY，YZ成立，YX，则称即若R是3NF，则在关系中每一个非码属性既不部分函数依赖于则在关系中每一个非码属性既不部分函数依赖于码也不传递依赖于码码也不传递依赖于码。因此：SlocSdeptSnoS_LSdeptSnoS_DSlocSdeptD_L分解后的两个关系是否满足

12、3NF，分解的原则是什么？第20页，共82页，编辑于2022年，星期日若关系不满足3NF，则分解关系去掉传递函数依赖关系，使分解后的各个关系满足3NF。银行系统现有关系如下：分行，客户，借贷编号，如何构造一个关系，体现3者的联系。Branch-name(分行)Customer-name(客户)Loan-number(借贷编号)该关系哪些属性是码，是否满足2NF，是否满足3NF？(Branch-name,Customer-name)是码，非主属性完全依赖于码，其没有传递依赖，故满足2NF和3NF，但是若借贷编号是为每个分行的不同金额的借贷业务编的号，则有没有数据冗余？有第21页，共82页，编辑于

13、2022年，星期日既然每个分行为不同金额的借贷业务编了号，Loan-number和Brach-name属性存在重复，且Loan-number不是码。因此对上述关系作如下修改：Branch-name(分行)Customer-name(客户)Loan-number(借贷编号)Loan-numberBranch-nameAmountCustomer-nameLoan-number实质是非主属性含有决定因素，如Loan-number。分解后去掉了非主属性的决定因素。第22页，共82页，编辑于2022年，星期日定义定义6.8关系模式R 若XY且 时X必含有码，则称由由BCNF的定义可以得到以下推论：的定

14、义可以得到以下推论：如果如果RBCNF,则则R中所有非主属性对每一个码都是中所有非主属性对每一个码都是完全函数依赖完全函数依赖;若不是，会得出什么结论？若不是，会得出什么结论？X必含有码的含义是什么，请举例？非主属性起决定作用，与定义矛盾。非主属性起决定作用，与定义矛盾。第23页，共82页，编辑于2022年，星期日R中所有主属性对每一个不包含它的码中所有主属性对每一个不包含它的码,都是都是完全函数依赖完全函数依赖关系有多个候选码的情况关系有多个候选码的情况;反之，会怎样？反之，会怎样？R中没有任何属性中没有任何属性完全函数依赖完全函数依赖于非码的任何一组属性。于非码的任何一组属性。反之，会怎样

15、？反之，会怎样？非主属性起决定作用，与定义矛盾。非主属性起决定作用，与定义矛盾。非主属性起决定作用，与定义矛盾。非主属性起决定作用，与定义矛盾。BCNF与3NF的关系是什么？第24页，共82页，编辑于2022年，星期日定理：定理：如果如果RBCNF,则则R3NF一定成立一定成立。证明：证明：用反证法。用反证法。如果如果RBCNF,但不是但不是3NF,则则R中一定存在传递函数依中一定存在传递函数依赖赖。即即R中必定存在候选码中必定存在候选码X,非主属性非主属性A,属性组属性组Y,其中其中AX,AY,XY,使得使得XYA成立。成立。Y不是不是R的码的码,但但Y是是R的决定因素的决定因素(YA),根

16、据根据BCNF的定义的定义,R不是不是BCNF,与与假设相矛盾。假设相矛盾。所以假设不成立。所以假设不成立。但是如果但是如果R3NF,R未必属于未必属于BCNF。3NF比比BCNF放宽了一放宽了一个限制个限制,即允许决定因素不包含码即允许决定因素不包含码。请看下面两个例子：请看下面两个例子：第25页，共82页，编辑于2022年，星期日例例 1：通讯（通讯（城市名城市名,街道名街道名,邮政编码）邮政编码）该该关关系系的的码码是是（城城市市名名,街街道道名名）,根根据据语语义义其其函函数数依赖集为：依赖集为：F=（城城市市名名,街街道道名名）邮邮政政编编码码,邮邮政政编编码码城城市市名名 所所以以

17、非非主主属属性性邮邮政政编编码码完完全全函函数数依依赖赖于于码码,且且无无传传递递依依赖赖,属属于于3NF。但但邮邮政政编编码码也也是是一一个个决决定定因因素素,它它没没有有包包含含码码,所所以以该该关关系系不不属属于于BCNF。存存在在冗冗余余(城城市市名名,邮邮政政编编码码),可可以以作如下分解：作如下分解：（城市名城市名,邮政编码）邮政编码）（街道名街道名,邮政编码）邮政编码）第26页，共82页，编辑于2022年，星期日例例 2 授课（学生授课（学生,教师教师,课程）课程）假假设设该该校校规规定定：一一个个教教师师只只能能教教一一门门课课,每每门门课课可可由由多多个个教教师师讲讲授授。学

18、学生生一一旦旦选选定定某某门门课课,教教师师就就相相应应地地固固定定。根据语义关系的函数依赖集为：根据语义关系的函数依赖集为：F=教教师师课课程程,（学学生生,课课程程）教教师师,（学学生生,教教师师）课程课程 该该关关系系的的候候选选码码为为（学学生生,课课程程）或或（学学生生,教教师师）,该该关关系系一一定定是是3NF的的。但但由由于于决决定定因因素素教教师师没没包包含含码码,该该关关系系不不属属于于BCNF。假假设设有有100名名学学生生选选课课，存存在在冗冗余余(教教师师,课课程程)，可分解为：可分解为：教师（教师教师（教师,课程）课程）学生（学生学生（学生,教师）教师）第27页，共8

19、2页，编辑于2022年，星期日小结：2NF的定义：强调完全函数依赖。3NF的定义：强调不存在传递函数依赖。BCNF的定义：强调只有码才可以是决定因素。它们之间的关系如何？第28页，共82页，编辑于2022年，星期日关系是2NF，不能保证是3NF和BCNF；3NF，能保证是2NF，但不能保证是BCNF；BCNF，能保证是2NF和3NF。关系如下：2NF3NFBCNF一个关系模式一个关系模式如果达到了如果达到了BCNF,那么那么在函数依赖范围内在函数依赖范围内,它已实现了彻底的分离它已实现了彻底的分离,消消除了数据冗余、除了数据冗余、插入和删插入和删除异常除异常。第29页，共82页，编辑于2022

20、年，星期日现有例子如下：课程C教员T参考书B物理李勇王军 普通物理学光学原理 物理习题集数学李勇张平数学分析微分方程高等代数计算数学张平周峰数学分析学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用，非规范化数据如下：什么是函数依赖，该数据中，各个属性间存在函数依赖吗？它们之间的关系应该是怎样的？第30页，共82页，编辑于2022年，星期日课程C 教员T 参考书B物理 李勇 普通物理学物理 李勇 光学原理物理 李勇 物理习题集物理 王军 光学原理物理 王军 普通物理学物理 王军 物理习题集数学 李勇 数学分析数学 李勇 微分方程数学

21、 李勇 高等代数数学 王平 数学分析数学 王平 微分方程数学 王平 高等代数 在这个关系中码是什么？全码教员的值由哪个属性决定？课程C，即给出一组(课程，参考书)的值，无论参考书的变化，教员的值仅仅取决于课程的值。因此，写成规范化形式如下：第31页，共82页，编辑于2022年，星期日定义定义6.9设R(U)是属性集U上的一个关系模式，X,Y,Z是U的子集，并且Z=U-X-Y。当且仅当对R(U)的任一关系r，给定一对(x,z)值，有一组Y的值，这组值仅仅决定于x的值而与z值无关，称关系模式R(U)中多值依赖多值依赖X XY Y成立。如上例，参考书=U(课程，教员，参考书)-课程-教员，(物理，光

22、学原理)决定了(李勇，王军)，但是(李勇，王军)仅仅决定于物理与光学原理无关。因此教员因此教员因此教员因此教员T T多值依赖于课程多值依赖于课程多值依赖于课程多值依赖于课程C C。因此，可以做出如下结论：第32页，共82页，编辑于2022年，星期日我们可以从已知的元组推出表中一定存在的其他元组。我们可以从已知的元组推出表中一定存在的其他元组。例如例如,如果已知表中存在元组：如果已知表中存在元组：（物理，王军，光学原理）（物理，王军，光学原理）（物理，李勇，普通物理学）（物理，李勇，普通物理学）那么表中应该有元组：那么表中应该有元组：（物理，王军，普通物理学）（物理，王军，普通物理学）（物理，李

23、勇，光学原理）（物理，李勇，光学原理）Why?多值依赖具有对称性多值依赖具有对称性。若若XY,则则XZ,其中其中Z=U-X-Y。第33页，共82页，编辑于2022年，星期日问题，如果给物理课程添加一名教员需要添加几条记录，同样某一门课程(如物理)要去掉一本参考书需要删除几条记录？存在冗余，如何处理。另外一个例子课程教员参考书课程教员课程参考书第34页，共82页，编辑于2022年，星期日数据如下：t1t2t3Go 33第35页，共82页，编辑于2022年，星期日t1t2t3Go 33第36页，共82页，编辑于2022年，星期日针对上面数据，给定同一课程(X相同)的两个记录(元组)t1和t2，总能

24、找到同一课程的一个记录t3(可以与t1或t2相同)，它满足如下条件：在t3的另外两个属性中，其中一个属性和t1的对应属性相同，另一个属性与t2的对应属性相同。上述描述是否总是正确？例子是，因此给出多值依赖的另一种等价的形式化定义如下：第37页，共82页，编辑于2022年，星期日多值依赖的另一个等价的形式化定义为：设关系模式R（U）,X、Y、Z是U的子集,Z=U-X-Y,r是R的任意一个关系,t1、t2是r的任意两个元组。如果t1X=t2X,在r中存在元组t3,使得 t3X=t1X,t3Y=t1Y,t3Z=t2Z 成立,则XY。成立的含义？是指t3也在r中。上述定义中,由于t1、t2的对称性,实

25、际隐含着关系r中还存在着另一个元组t4,t4满足：t4X=t1X,t4Y=t2Y,t4Z=t1Zt1,t2,t3,t4 可以分别由 t,s,w,v代替教材P179的形式化定义。第38页，共82页，编辑于2022年，星期日换换句句话话说说,如如果果r有有两两个个元元组组在在X属属性性上上的的值值相相等等,则则交交换换这这两两个个元元组组在在Y上上的的属属性性值值,得得到到的的两两个个新新元元组组也也必必是是r中中的的元组元组。定定义义中中如如果果Z=（即即Z为为空空集集）,则则称称XY为为平平凡凡的多值依赖的多值依赖,否则为否则为非平凡多值依赖非平凡多值依赖。第39页，共82页，编辑于2022年

26、，星期日(1)多多值值依依赖赖具具有有对对称称性性。若若XY,则则XZ,其其中中Z=U-X-Y。(2)多值依赖具有传递性多值依赖具有传递性。若若XY,YZ,则则XZ-Y。(3)若若XY,XZ,则则XYZ(或者写成或者写成YZ)。(4)若若XY,XZ,则则XYZ。(5)若若XY,XZ,则则XY-Z,XZ-Y。多值依赖应该具有的性质多值依赖应该具有的性质注意：注意：函数依赖可看成是多值依赖的特例，函数依赖可看成是多值依赖的特例，即函即函数依赖一定是多值依赖，多值依赖不一定数依赖一定是多值依赖，多值依赖不一定是函数依赖。是函数依赖。第40页，共82页，编辑于2022年，星期日看下例：码是什么，项目是

27、否是决定因素，是否是候选码？根据BCNF的定义，该关系是否满足BCNF?该关系是否存在数据冗余，若存在该如何处理？供应关系第41页，共82页，编辑于2022年，星期日定义定义6.10如果关系模式如果关系模式R1NF,对于对于R的每个的每个非平凡的多值非平凡的多值依赖依赖XY（YX）,X含有码含有码,则称则称R是第四范是第四范式式,即即R4NF。一一个个关关系系模模式式如如果果属属于于4NF,则则一一定定属属于于BCNF,但但一一个个BCNF的的关关系系模模式式不不一一定定是是4NF的的,R中中所有的平凡多值依赖实际上是所有的平凡多值依赖实际上是函数依赖函数依赖。注意：注意：4NF是限制关系模式

28、的属性之间不允许有非平凡且非函数依赖是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。的多值依赖。第42页，共82页，编辑于2022年，星期日在前面的供应关系中在前面的供应关系中,项目项目供应商供应商,项目项目零件零件,且且都都是非平凡的多值依赖是非平凡的多值依赖。但但该该关关系系的的码码是是全全码码（项项目目,供供应应商商,零零件件）,而而项项目目没没有有包包含含码码（只只是是码码的的一一部部分分）,所所以以该该关关系系模模式式属属于于BCNF(根根据据定义定义)而不属于而不属于4NF。如将其分解为两个关系如将其分解为两个关系,可达到可达到4NF：需求（项目需求（项目,零件）零件

29、）供应（项目供应（项目,供应商）供应商）这这两两个个关关系系中中,项项目目零零件件,项项目目供供应应商商,它它们们均均是是平平凡凡多多值值依依赖赖。即即关关系系中中已已不不存存在在非非平平凡凡、非非函函数数依赖的多值依赖依赖的多值依赖,所以它们均是所以它们均是4NF。第43页，共82页，编辑于2022年，星期日6.3关系的规范化程度关关系系规规范范化化的的目目的的是是解解决决关关系系模模式式中中存存在在的的数数据据冗冗余余、插插入入和和删删除除异异常常、更更新新繁繁琐琐等等问问题题。其其基基本本思思想想是是消消除除数数据据依依赖赖中中的的不不合合适适部部分分,使使各各关关系系模模式式达达到到某

30、某种种程程度度的的分分离离,使使一一个个关关系系描描述述一一个个概概念念、一一个个实实体体或或实实体体间间的的一一种种联联系系。因因此此,规规范范化化的的实实质质是是概概念念的的单一化单一化。各种规范化之间的关系为：各种规范化之间的关系为：关系规范化的递进过程如下图关系规范化的递进过程如下图 所示所示第44页，共82页，编辑于2022年，星期日范式递进过程示意图 1NF消除非主属性对码的部分函数依赖BCNF2NF消除非主属性对码的传递函数依赖3NF消除主属性对码的部分和传递依赖4NF消除非平凡且非函数依赖的多值依赖第45页，共82页，编辑于2022年，星期日所所以以,规规范范化化的的基基本本原

31、原则则是是：由由低低到到高高,逐逐步步规规范范,权权衡衡利利弊弊,适适可而止可而止。通常通常,以满足第三范式为基本要求以满足第三范式为基本要求。把把一一个个非非规规范范化化的的数数据据结结构构转转换换成成第第三三范范式式,一一般般经经过以下几步：过以下几步：(1)把该结构分解成若干个属于第一范式的关系把该结构分解成若干个属于第一范式的关系。(2)对对那那些些存存在在组组合合码码,且且有有非非主主属属性性部部分分函函数数依依赖赖的的关关系系必须继续分解必须继续分解,使所得关系都是属于第二范式使所得关系都是属于第二范式。(3)若若关关系系中中有有非非主主属属性性传传递递依依赖赖于于码码,则则继继续

32、续分分解解之之,使使得关系都属于第三范式得关系都属于第三范式。第46页，共82页，编辑于2022年，星期日关关系系模模式式的的规规范范化化过过程程是是通通过过投投影影分分解解实实现现的的,即即用用投投影影运算把一个模式分解成若干个高一级的关系模式运算把一个模式分解成若干个高一级的关系模式。这种投影分解这种投影分解不是唯一不是唯一的。的。在分解时应注意满足以下在分解时应注意满足以下三个条件三个条件：(1)分分解解是是无无损损连连接接分分解解,分分解解后后既既不不丢丢失失又又不不增增加加信息信息。(2)分解所得的所有关系分解所得的所有关系都是高一级范式都是高一级范式的。的。(3)分解所得关系的分解

33、所得关系的个数最少个数最少。什么是无损连接分解?第47页，共82页，编辑于2022年，星期日6.4模式的分解1、数据依赖的公理系统2、模式分解第48页，共82页，编辑于2022年，星期日背景知识在关系模式R中，U的含义是什么，F的含义是什么，它应该包含什么？在关系模式(sno,sname,sage,cno,cname,grade)中，U指什么，F是什么，应该包含哪些内容？例如(Sno,Cno,Grade)中关系模式关系模式是什么，关系关系又是什么，两者的联系是什么？P43,46函数依赖如何定义？在线性代数中，n维空间和n维空间的基的关系是什么？在离算数学中，蕴含的含义是什么？第49页，共82页

34、，编辑于2022年，星期日6.4.1数据依赖的公理系统只作介绍不作证明只作介绍不作证明提出的目的：是模式分解的理论基础；从一组函数依赖求得蕴含的函数依赖，例如已知函数依赖集F，判断XY是否为F所蕴含。第50页，共82页，编辑于2022年，星期日定义定义6.11对于满足一组函数依赖F的关系模式R，其任何一个关系r，若函数依赖XY都成立(即r中任意两元组t,s，若tX=sX，则tY=sY)，则称F逻辑蕴含XY。在该定义中：在该定义中：F应该包含哪些内容，关系r的含义是什么，函数依赖XY的特点是什么？该定义可以如何描述？在一个关系模式的所有关系中都成立的函数依赖，一定可以被该关系模式的函数依赖集F所

35、蕴含。第51页，共82页，编辑于2022年，星期日Armstrong公理系统设U为属性集总体，F是U上的一组函数依赖，于是有关系模式R。根据逻辑蕴含的定义，能否说F逻辑蕴含XY？所以若Y X U，则XY为F所蕴含。自反律自反律若Y X U，则XY的特点是什么？1、得到的是平凡的函数依赖，自反律的使用不依赖于F.第52页，共82页，编辑于2022年，星期日2、若XY为F所蕴含，是指什么？如果Z U，则X ZY Z是否在R的所有关系上成立？例如在(sno,sname,sage,cno,cname,grade)中，(sno,cno)grade总是成立；(sno,cno,sage)(grade,sag

36、e)是否总是成立？增广律：若若XY为为F所蕴含，且所蕴含，且Z U，则，则X ZY Z为为F所蕴含所蕴含。第53页，共82页，编辑于2022年，星期日3、若XY及YZ为F所蕴含，是指什么？能否得到XZ是否在R的所有关系上总是成立？请举例。传递律：若若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所蕴含所蕴含。因此得到：设U为属性集总体，F是U上的一组函数依赖，于是有关系模式R。对R有如下推理规则：自反律：若Y X U，则XY为F所蕴含。增广律：若XY为F所蕴含，且Z U，则X ZY Z为F所蕴含。传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。(sno,sdept,sdname)第54页，

37、共82页，编辑于2022年，星期日1、若XY,XZ在R中的所有关系上都成立，能否推出XY Z在R中的所有关系上都成立？例如：(sno,sname,sage,class)中，Snosname,Snosage成立，Sno(sname,sage)成立吗？推论：合并规则：若若XY,XZ,则则XY Z；第55页，共82页，编辑于2022年，星期日2、若XY Z在R中的所有关系上都成立，能否推出XY,XZ在R中的所有关系上都成立？例如：(sno,sname,sage,class)中，Sno(sname,sage)成立，Snosname,Snosage成立吗？分解规则：若若XY Z,则则XY,XZ；第56页

38、，共82页，编辑于2022年，星期日3、若XY,W YZ,在R中的所有关系上都成立，能否推出X WZ在R中的所有关系上都成立？例如：(sno,sdept,job,room)其中room 为办公室，job为职务snosdept,(job,sdept)room,(sno,job)room成立吗？伪传递规则：若XY,W YZ,则X WZ。根据这3条推理规则(自反律、增广律、传递律)可以得到如下的推理规则：合并规则：若XY,XZ,则XY Z；分解规则：若XY Z,则XY,XZ；伪传递规则：若XY,W YZ,则X WZ。第57页，共82页，编辑于2022年，星期日因此，设U为属性集总体，F是U上的一组函

39、数依赖，于是有关系模式R。对R有如下推理规则：自反律：若Y X U，则XY为F所蕴含。得到的是平凡的函数依赖，自反律的使用不依赖于F.增广律：若XY为F所蕴含，且Z U，则X ZY Z为F所蕴含。传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。加上：合并规则：若XY,XZ,则XY Z；分解规则：若XY Z,则XY,XZ；伪传递规则：若XY,W YZ,则X WZ。注意：实质是在关系R上的基本运算基本运算(变换变换)规则规则。第58页，共82页，编辑于2022年，星期日在关系模式R中，根据分解规则，XA1A2Ak成立是否XAi成立(i=1,2,k)？根据合成规则，XAi成立(i=1,2,k)是否

40、XA1A2Ak成立？引理引理6.1：XA1A2Ak成立的充分必要条件是XAi成立(i=1,2,k)。思考：在n维空间中，任给一个n维向量t，它与n维空间和n维空间的基P的关系是什么？任意一个n维向量：1、它属于它属于n维空间；维空间；2、它可以用它可以用n维空间的基维空间的基P表示出来表示出来。第59页，共82页，编辑于2022年，星期日若在关系模式R中，函数依赖的全体表示为F+，F+中任何一个函数依赖(XY)都蕴含于F，这种关系与n维空间，n维向量和n维空间的基的相似点是什么？F对应于n维空间的基，注意此时F可能比n维空间的基大，即含有相关的函数依赖；函数依赖(XY)对应于n维向量；F+对应

41、于n维空间。因此：定义定义6.12在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记作F+。因此：第60页，共82页，编辑于2022年，星期日由F出发根据Armstrong公理(自反律、增广律、传递律、合并规则、伪传递规则，分解规则)推导出来的每一个函数依赖是否一定在F+中?反之，在F+中的每一个函数依赖，是否可以由F出发根据Armstrong公理推导出来？定理定理6.2：Armstrong公理系统是有效的、完备的。公理系统是有效的、完备的。有效性有效性：指由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中；完备性完备性：指F+中的每一个函数依赖，必定可以由F出发

42、根据Armstrong公理推导出来。第61页，共82页，编辑于2022年，星期日定义定义6.13设F为属性集U上的一组函数依赖，X U，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集称为属性集X关于函数依赖集关于函数依赖集F的闭包的闭包。思考：在关系模式(sno,sname,sage,cno,cname,grade)中，F应该包含哪些函数依赖，Sno起决定作用的函数依赖有哪些(即哪些属性可以由Sno决定)？在R中，X,Y U，XY能由F根据Armstrong公理导出，能否说Y XF+，反之，Y XF+能否说能否说XY能由F根据Armstrong公理导出？第62页，共82

43、页，编辑于2022年，星期日引理引理6.2：设F为属性集U上的一组函数依赖，X,Y U，XY能由F根据Armstrong公理导出的充分必要条件是 Y XF+。在数学分析中，什么是覆盖？定义定义6.14如果G+=F+，就说函数依赖F覆盖G(F是G的覆盖，或G是F的覆盖)，或F与G等价。引理引理6.3：G+=F+的充分必要条件是F G+,和G F+。在关系模式R中有没有可能存在这样的F，F中的函数依赖的数目最少，但是R中所有的函数依赖都可以由F中的函数依赖导出(蕴含)，若有，F有什么特点？第63页，共82页，编辑于2022年，星期日在关系模式R中，如果函数依赖集F满足下列条件，F中任一函数依赖的右

44、部仅含有一个属性；最简形式；F中不存在这样的函数依赖XA,使得F与F-XA等价；不能包含多余的函数依赖；F中不存在这样的函数依赖XA,X有真子集Z使得F-XA ZA与F等价。F中的函数依赖全部是完全函数依赖。则称F为一个极小函数依赖集，亦称为最小依赖集或最小覆盖。第64页，共82页，编辑于2022年，星期日定理定理6.3每一个函数依赖集每一个函数依赖集F均等价于一个极小函数依赖集均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集最小依赖集。第65页，共82页，编辑于2022年，星期日6.4.2模式分解如果一个关系不满足2NF，应该做怎样的处理，通过哪种操作可以实现？对关系进行分解处理使它

45、满足2NF，通过投影投影操作便可以实现分解处理。第66页，共82页，编辑于2022年，星期日定义定义6.16关系模式R的一个分解是指p=R1,R2,Rn其中定义定义6.17函数依赖集合 的一个覆盖Fi叫作F在属性在属性Ui上的投影上的投影。注意：Ui和和Uj可以有重叠的部分。可以有重叠的部分。第67页，共82页，编辑于2022年，星期日6.4.2.1模式分解的模式分解的3个定义个定义关系模式经分解后关系模式经分解后,应与原来的关系模式应与原来的关系模式等价等价。所谓所谓“等价等价”是指两者对是指两者对数据的使用者来说数据的使用者来说应是等价的。应是等价的。即对分解前即对分解前后的关系后的关系,

46、做相同内容的查询做相同内容的查询,应产生同样的结果应产生同样的结果。这是对模这是对模式分解的基本要求。式分解的基本要求。等价概念的三种不同的定义：等价概念的三种不同的定义：分解具有分解具有“无损连接性无损连接性”；分解具有分解具有“函数依赖保持性函数依赖保持性”；分解既要具有分解既要具有“无损连接性无损连接性”,又要具有又要具有“函数依赖保持性函数依赖保持性”。看下例：第68页，共82页，编辑于2022年，星期日在关系模式R，其中U=Sno,Sdept,Mname,F=SnoSdept,SdeptMname。该关系中存在传递函数依赖SnoMname，会发生异常。故作如下几种分解：1、p1=R1

47、,R2,R3，即将前面关系中的每一个属性单独作为一个关系，有什么特点？2、p2=R1,R2，有什么特点？该分解丢失了信息。该分解虽然没有丢失信息(无损连接性无损连接性)，但是去掉了函数依赖SdeptMname。故仍会发生异常。第69页，共82页，编辑于2022年，星期日3、p2=R1,R2，有什么特点？该分解既没有丢失信息，也保持了函数依赖(具有具有“无损连接无损连接性性”,又要具有又要具有“函数依赖保持性函数依赖保持性”)，解决了操作异常。问题：给定一个关系该如何分解才能具有具有“无损连接性无损连接性”,又要具有又要具有“函数依赖保持性函数依赖保持性”？第70页，共82页，编辑于2022年，

48、星期日6.4.2.2分解无损连接性和保持函数依赖性分解无损连接性和保持函数依赖性符号：R的一个分解p，表示为r是R的一个关系。mp(r)是r在p中各关系模式上投影的连接。第71页，共82页，编辑于2022年，星期日引理引理6.4:设R是一个关系模式，是R的一个分解，r是R的一个关系，则第72页，共82页，编辑于2022年，星期日定义定义6.18是R的一个分解，若对R的任何一个关系r均有成立，则称分解p具有无损连接性。简称p为无损分解。如何判断一个分解的无损连接性？即分解后通过连接可以复原。即分解后通过连接可以复原。第73页，共82页，编辑于2022年，星期日算法：判断一个分解的无损连接性。例：

49、已知R,U=A,B,C,D,E,F=ABC,CD,DE,R的一个分解为R1(A,B,C),R2(C,D),R3(D,E)，判断该分解是否是无损连接性。即ABCDEABCCDDE根据上述描述，作表如下：第74页，共82页，编辑于2022年，星期日ABCDEa1a2a3b14b15b21b22b23b24b25b31b32b33b34b35R1(A,B,C)ABCDEb11b12b13b14b15b21b22b23b24b25b31b32b33b34b35第75页，共82页，编辑于2022年，星期日ABCDEa1a2a3b14b15b21b22a3a4b25b31b32b33a4a5ABCDEa1

50、a2a3b14b15b21b22a3a4b25b31b32b33b34b35R2(C,D)R3(D,E)第76页，共82页，编辑于2022年，星期日ABCDEa1a2a3b14b15b21b22a3a4b25b31b32b33a4a5ABCCDABCDEa1a2a3a4b15b21b22a3a4b25b31b32b33a4a5第77页，共82页，编辑于2022年，星期日DEABCDEa1a2a3a4a5b21b22a3a4a5b31b32b33a4a5其中有一行(第1行)变成a1，a2，a3，a4，a5。此时说，该分解具有无损连接性。对于一般性分解问题，该如何处理？第78页，共82页，编辑于2