数据库原理与设计课件：第10章 关系数据库设计理论VIP

1、第10章 关系数据库设计理论22022/7/18第10章 关系数据库设计理论10.1 关系模型的存储异常10.2 函数依赖10.5 关系模式的规范化10.6 多值依赖和4NF10.3 函数依赖公理10.4* 模式分解10.8 小结32022/7/1810.1 关系模型的存储异常数据库模式的设计是数据库应用系统开发的核心问题由于认识或看问题的方法不同，一个数据库可以设计出不同的数据库模式。针对具体问题，如何构造一个适合于它的数据模式?即构造几个关系模式，每个关系有哪些属性这是数据库设计的问题,是关系数据库的逻辑设计关系数据库模式的设计，即数据库的逻辑设计就是要从各种可能的关系模式组合中选取一组关

2、系模式来构成一个数据库模式。 42022/7/1810.1 关系模型的存储异常某学校图书馆要建一个图书数据库，其中借阅管理包括借书证号(CARDNO)、借书人姓名(NAME)、借书人所在单位(DEPT)、单位负责人(MN)、图书编号(BNO)、借阅日期(DATE)等信息。借阅图书登记可以用如下关系模式来描述：BORROW（CARDNO，NAME，DEPT，MN，BNO，DATE）CARDNONAMEDEPTMNBNODATER001李晓鹏计算机张宏军TP31-12520070123R001李晓鹏计算机张宏军TP32-00720061112R001李晓鹏计算机张宏军TP12-2332007040

3、5R002王一鸣计算机张宏军TP51-21120080209R003刘明川无线电范和平TP23-12620071011R003刘明川无线电范和平TP23-02320080321R003刘明川无线电范和平TP25-04520080321 1. 数据冗余借书人每借一本书，很多信息重复存储大量的数据冗余不仅造成存储空间的浪费,而且存在着潜在的数据不一致。 52022/7/182. 插入异常BORROW（CARDNO，NAME，DEPT，MN，BNO，DATE）CARDNONAMEDEPTMNBNODATER001李晓鹏计算机张宏军TP31-12520070123R001李晓鹏计算机张宏军TP32-0

4、0720061112R001李晓鹏计算机张宏军TP12-23320070405R002王一鸣计算机张宏军TP51-21120080209R003刘明川无线电范和平TP23-12620071011R003刘明川无线电范和平TP23-02320080321R003刘明川无线电范和平TP25-04520080321 2. 插入异常关键字是由CARDNO和BNO组成的联合键,根据实体完整性规则，关键字不能为空如果要插入一个借书人的信息是不能进行的62022/7/18 3. 删除异常BORROW（CARDNO，NAME，DEPT，MN，BNO，DATE）CARDNONAMEDEPTMNBNODATER0

5、01李晓鹏计算机张宏军TP31-12520070123R001李晓鹏计算机张宏军TP32-00720061112R001李晓鹏计算机张宏军TP12-23320070405R002王一鸣计算机张宏军TP51-21120080209R003刘明川无线电范和平TP23-12620071011R003刘明川无线电范和平TP23-02320080321R003刘明川无线电范和平TP25-04520080321 3. 删除异常当借书人归还所借的书后，需要从借阅关系中删除相关信息如果借阅人把所借的书全部还清了，则连同借阅人及所在单位的所有信息都一起删除72022/7/184.更新异常BORROW（CARDN

6、O，NAME，DEPT，MN，BNO，DATE）CARDNONAMEDEPTMNBNODATER001李晓鹏计算机张宏军TP31-12520070123R001李晓鹏计算机张宏军TP32-00720061112R001李晓鹏计算机张宏军TP12-23320070405R002王一鸣计算机张宏军TP51-21120080209R003刘明川无线电范和平TP23-12620071011R003刘明川无线电范和平TP23-02320080321R003刘明川无线电范和平TP25-045200803214. 更新异常如果所在单位或单位负责人变了，需要修改该借书人在DEPT或MN属性上的值。但由于数据冗

7、余，有关借书人所有元组中的单位或单位负责人的信息都要修改。这不仅增加了更新代价，而且存在着潜在的不一致性82022/7/1810.1 关系模型的存储异常E.F.Codd把这些问题统称为存储异常这些问题不希望出现，这样设计的数据库不好为什么会出现存储异常呢？因为在数据间存在着一定的依赖关系如借书关系中，借阅人和借阅人所在单位单位负责人与借书证号之间以及借书证号、书号与借阅日期之间存在着依存关系。但BORROW模式没有很好地反映这些关系。在现实世界中，实体和实体间及实体内部的属性值之间存在着相互依赖又相互制约的关系，称为数据依赖92022/7/18第10章 关系数据库设计理论10.1 关系模型的存

8、储异常10.2 函数依赖10.5 关系模式的规范化10.6 多值依赖和4NF10.3 函数依赖公理10.4* 模式分解10.8 小结102022/7/1810.2.1 函数依赖的定义函数依赖(Functional Dependency, FD)是现实世界中最广泛存在的一种数据依赖，是现实世界属性间相互联系的抽象;是数据内在的性质;它表示了关系中属性间的一种制约关系。一、函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖112022/7/1810.2.1 函数依赖的定义定义10.1 设关系模式R(U)，X,YU，r是R(U)上的任一关系。对任意元组t1 、t2

9、r, 如果t1、t2在X上的属性值相等， t1、t2在Y上的属性值亦相等，则称X函数决定Y,或Y函数依赖于X，记为FD XY称X为决定因素，或称X为函数依赖的左部，称Y为函数依赖的右部。 BORROW（CARDNO，NAME，DEPT，MN，BNO，DATE）CARDNONAME；每个借书证号可以唯一确定一个读者 CARDNODEPT；每个借书证号可以唯一确定读者所在单位 CARDNOMN；借书证号可以唯一确定读者所在单位负责人 DEPTMN；单位可以唯一确定单位负责人 (CARDNO,BNO)DATE 借阅日期由证号和图书编号共同决定122022/7/1810.2.1 函数依赖的定义函数依赖

10、是指R的所有关系实例均要满足的约束条件, 而不是指关系模式R的某个或某些关系实例满足的约束条件。函数依赖是语义范畴的概念，只能根据现实世界中数据间的语义确定函数依赖 如函数依赖：姓名年龄，只有规定不允许有同名同姓的人的情况下才成立。 为满足这种语义约束，当装入元组到数据库时,就要检查这种约束条件，使相应元组上的属性值满足规定的函数依赖。 在模式设计中，设计者对需要处理的数据间的约束关系要非常清楚,才能根据实际情况确定属性间的函数依赖,从而设计出满足要求的数据库模式 132022/7/1810.2.1 函数依赖的定义定义10.2 设FD XY，如果YX，则称FD XY为非平凡的函数依赖；否则，若

11、YX，称FD XY为平凡的函数依赖。平凡的函数依赖是对模式R上的所有关系都成立的函数依赖。 例：在关系SC(Sno, Cno, Grade)中， 非平凡函数依赖： (Sno, Cno) Grade 平凡函数依赖： (Sno, Cno) Sno (Sno, Cno) Cno对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明， 总是讨论非平凡函数依赖。142022/7/1810.2.1 函数依赖的定义定义10.3 设FD XY，如果对任意的X X，XY都不成立,则称FD XY是完全函数依赖；若对X的真子集X有XX，而X Y成立，则称FD XY是部分函数依赖，即Y函数依

12、赖于X的一部分在借阅关系BORROW中，存在着完全函数依赖：(CARDNO, BNO)DATE，CARDNONAME，CARDNODEPT，CARDNOMN，DEPTMN。而以下函数依赖是部分函数依赖：(CARDNO, BNO)NAME，(CARDNO, BNO)DEPT，(CARDNO, BNO)MN。 152022/7/1810.2.1 函数依赖的定义定义10.4 设关系模式R，X、Y、Z是R的属性子集，若FD XY，Y X，YZ，则必有FD XZ，称FD XZ为传递函数依赖。例如，在借阅关系BORROW中，存在函数依赖CARDNODEPT，DEPTMN，而DEPT CARDNO ，则有传

13、递依赖CARDNOMN 注: 如果YX, 已知XY，则XY,又因为YZ，则有XZ, 称Z直接依赖于X。162022/7/1810.2.1 函数依赖的定义一、函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖了解现实世界中数据间的依存和制约关系，正确确定属性间的函数依赖关系，对设计一个好的数据库模式是很重要的 172022/7/18第10章 关系数据库设计理论10.1 关系模型的存储异常10.2 函数依赖10.5 关系模式的规范化10.6 多值依赖和4NF10.3 函数依赖公理10.4 模式分解10.8 小结182022/7/1810.5 关系模式的规范化研究

14、了规范化理论的目的设计好的数据模式 用规范化理论改造关系模式通过分解关系模式, 消除关系模式中不合适的数据依赖，解决插入异常、删除异常、更新异常和数据冗余问题1971年，E.F.Codd首先提出了规范化的问题，给出了范式(Normal Form, NF)的概念 根据关系模式所达到的不同约束提出了1NF、2NF、3NF的概念 1974年Codd和Boyce提出BCNF(Boyce-Codd Normal Form) 之后又研究了4NF、5NF 192022/7/1810.5 关系模式的规范化所谓范式就是规范化的关系模式。范式是符合某一种级别的关系模式的集合。关系数据库中的关系必须满足一定的要求。

15、满足不同程度要求的为不同范式。范式的种类：根据规范化程度的不同，数据库范式从低到高有1NF、 2NF、3NF、BC范式(BCNF)、 4NF一个数据库模式从低一级的范式，可以通过模式分解转化为若干个高一级的范式的关系模式的集合从低一级的范式通过分解达到高一级范式的过程称为关系模式的规范化 202022/7/1810.5.1 第一范式第一范式是最低级别的关系模式，关系数据库中的关系模式至少都应是第一范式的定义10. 15 如果关系模式R的每一个属性对应的域值都是不可再分的，称模式R属于第一范式，简记为R1NF若数据库模式R中的每个关系模式都是1NF，数据库模式R1NF。一个数据库系统中的关系至少

16、应该是1NF的，是关系作为二维表的起码的要求。不满足1NF的数据库模式不能称为关系数据库但是满足1NF的关系模式不一定是好的关系模式212022/7/1810.5.2 第二范式(2NF)定义10.16 设关系模式R，A是R中的属性，F是R上的函数依赖集。如果A包含在R的某个候选键中，称A为主属性，否则称A为非主属性。定义10.17 如果一个关系模式R1NF，且所有非主属性都完全依赖于R的每个候选键，则R2NF。 判定一个关系模式是否属于2NF，需要了解关系模式的属性间存在哪些依赖 根据数据依赖关系，找出关系模式的候选键， 确定哪些属性是主属性，哪些属性是非主属性， 确定非主属性与候选键之间是否

17、存在完全函数依赖关系，以判定该模式是否属于2NF 222022/7/1810.5.2 第二范式(2NF)借书关系BORROW(CARDNO, NAME, DEPT, MN, BNO, DATE)是1NF的，但不是2NF 函数依赖： CARDNONAME，CARDNODEPT, CARDNOMN， DEPTMN， (CARDNO、BNO)DATE 属性NAME、DEPT和MN部分依赖于BORROW的候选键。因此，BORROW2NF BORROW不是一个好的关系模式(插入异常、删除异常、数据冗余、修改复杂)原因: NAME、DEPT和MN部分函数依赖于候选键232022/7/1810.5.2 第二

18、范式(2NF)解决方法: BORROW分解为两个关系模式，以消除这些部分函数依赖LOANS(CARDNO，NAME，DEPT，MN) 2NF BORROW (CARDNO，BNO，DATE) 2NF CARDNONAMEDEPTMNR001李晓鹏计算机系张宏军R002王一鸣计算机系张宏军R003刘明川无线电系范和平CARDNOBNODATER001TP31-12520070123R001TP32-00720061112R001TP12-23320070405R002TP51-21120080209将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异

19、常、数据冗余度大、修改复杂等问题。并不能完全消除关系模式中的各种存储异常情况242022/7/1810.5.3 第三范式LOANS(CARDNO，NAME，DEPT，MN) 2NF函数依赖：CARDNODEPT，DEPTMN，且DEPT CARDNO ，则FD CARDNOMN是传递依赖存在非主属性对候选键的传递函数依赖解决方法，把LOANS分解为两个关系模式，以消除传递函数依赖CARDNONAMEDEPTMNR001李晓鹏计算机系张宏军R002王一鸣计算机系张宏军R003刘明川无线电系范和平CARDNONAMEDEPTR001李晓鹏计算机系R002王一鸣计算机系R003刘明川无线电系DEPT

20、MN计算机系张宏军无线电系范和平252022/7/1810.5.3 第三范式定义10.18 设R1NF，若在R中没有非主属性传递依赖于R的候选键，则关系模式R3NF 。如果数据库模式R中每一关系模式都是3NF，则数据库模式R3NF 结论一个2NF的关系模式不一定属于3NF. 但是，一个关系模式若是3NF的，则一定属于2NF。 262022/7/1810.5.3 第三范式定理10.6 若任一关系模式R3NF，则R2NF。 证明：用反证法。设R上的函数依赖集为F，R的键为K.假设R3NF但R2NF,则有R中非主属性A部分依赖于关键字K。那么，存在K的真子集K ，使得F|=KA。由于KK, 有FD

21、KK, 但K K. 于是, KK, K K，KA，并且AK，因而A传递依赖于K，即R3NF，与假设矛盾。证毕若R3NF，则R的每一个非主属性既不部分函数依赖于候选键也不传递函数依赖于候选键。272022/7/1810.5.4 Boyce-Codd范式(BCNF)第三范式消除了非主属性和主属性间的部分函数依赖和传递函数依赖，在一定程度上解决了存储异常问题但只是涉及非主属性和主属性间的函数依赖，而没有考虑主属性间的函数依赖问题。 282022/7/1810.5.4 Boyce-Codd范式(BCNF)实际上，在主属性间也存在着部分函数依赖和传递函数依赖，同样会出现存储异常问题 。例如，关系模式R(

22、City, Street, Zip)，R上的函数依赖为 (City,Street)Zip, Zip City候选键为(City, Street)或(Street, Zip)R中没有非主属性，因而也不存在非主属性与主属性间的部分函数依赖和传递函数依赖，R3NF但由于有Zip City，对候选键(Street, Zip)，(Street, Zip) City为部分函数依赖,造成C值多次重复，同样会引起更新异常如若要修改北京对应的邮政编码为110000，必须修改北京地区的所有邮政编码 292022/7/1810.5.4 Boyce-Codd范式(BCNF)定义10.19 若R1NF，而且R中没有任何

23、属性传递依赖于R中的任一关键字，则关系模式R属于Boyce-Codd范式（BCNF）。如果数据库模式R中的每个关系模式R都属于BCNF，则数据库模式RBCNF BCNF不但排除了非主属性对主属性的传递依赖，也排除了主属性间的传递依赖 一个更直观的等价的BCNF的定义 定义10.20 设关系模式R1NF，F是R上的函数依赖集,对于F中的每一个函数依赖XY，必有X是R的一个候选键，则RBCNF 如果RBCNF，则R上的每一个函数依赖中的,每个决定因素都包含侯选键 302022/7/1810.5.4 Boyce-Codd范式(BCNF)3NF与BCNF的关系若RBCNF 每一个决定属性集（因素）都包

24、含（候选）键R中的所有属性(主，非主属性)都完全函数依赖于键所以R3NF若R3NF, R不一定BCNF如果R3NF，且R只有一个候选键，则R必属于BCNFBCNF比3NF严格，3NF仅消除了非主属性的存储异常，3NF的“不彻底”性表现在可能存在主属性对键的部分依赖和传递依赖。而BCNF消除了整个关系模式的存储异常。312022/7/1810.5.4 Boyce-Codd范式(BCNF)BCNF的关系模式所具有的性质 所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非码的任何一组属性在函数依赖的范围内，BCNF已达到了关系模式的最

25、大分离，已经消除了插入、删除异常，是函数依赖范围内能够达到的最高范式322022/7/18第10章 关系数据库设计理论10.1 关系模型的存储异常10.2 函数依赖10.5 关系模式的规范化10.6 多值依赖和4NF10.3 函数依赖公理10.4 模式分解10.8 小结332022/7/1810.6 多值依赖和4NF属于BCNF的关系模式是否完美？例: 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。关系模式Teaching(C, T, B)课 程 C教 员 T参 考 书 B物理数学计算数学李 勇王 军李 勇张 平张 平周 峰 普通物理学光学原理 物理习题集数学分析微分方程高等代数数

26、学分析342022/7/18普通物理学光学原理物理习题集普通物理学光学原理物理习题集数学分析微分方程高等代数数学分析微分方程高等代数李 勇李 勇李 勇王 军王 军王 军李 勇李 勇李 勇张 平张 平张 平 物 理物 理物 理物 理物 理物 理数 学数 学数 学数 学数 学数 学 参考书B教员T课程C10.6 多值依赖和4NF用二维表表示Teaching352022/7/1810.6 多值依赖和4NFTeachingBCNF:Teaching具有唯一候选键(课程C,教师T,参考书B), 即全键362022/7/1810.6 多值依赖和4NFTeaching模式中存在的问题 (1)数据冗余度大：有

27、多少名任课教师，参考书就要存储多少次(2)插入操作复杂：当某课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组 例如物理课增加一名教师刘关，需要插入两个元组：（物理，刘关，普通物理学） （物理，刘关，光学原理）(3) 删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组(4) 修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组 产生原因存在多值依赖 课程教员 课程参考书372022/7/18uts10.6.1 多值依赖定义10.21 设R(U)是一个关系模式，X和Y是U的子集,且Z=U(XY)。如果对于关系r(R)中的任

28、意两个元组s和t,若sX=tX，在r中存在元组u，有： uX=sX，uY=sY，且uZ=tZ， 则关系r(R)满足多值依赖(MVD) XY，称X多值决定Y或Y多值依赖于X。 Teaching(X,Y,Z) 对于X的每一个值，Y有一组值与之对应，而不论Z取何值存在多值依赖 课程教员 课程参考书普通物理学光学原理物理习题集普通物理学光学原理物理习题集李 勇李 勇李 勇王 军王 军王 军物 理物 理物 理物 理物 理物 理参考书Z教员Y课程X382022/7/1810.6.1 多值依赖等价的多值依赖的另一个定义 定义10.22设R(U)是一个关系模式，X,Y和Z是U的子集,且Z=UX Y。r是R上的

29、一个关系。当且仅当对于给定的一个x值，有一组y的值，且这组y值仅仅决定于x值，而与r中的其它属性 z 无关，则称X多值决定Y或Y多值依赖于X，记为XY 普通物理学光学原理物理习题集普通物理学光学原理物理习题集李 勇李 勇李 勇王 军王 军王 军物 理物 理物 理物 理物 理物 理参考书Z教员Y课程X存在多值依赖 课程教员 课程参考书392022/7/1810.6.1 多值依赖平凡多值依赖和非平凡的多值依赖若XY,而Z,则称 XY为平凡的多值依赖否则称XY为非平凡的多值依赖402022/7/18多值依赖的性质(1) 多值依赖具有对称性若XY，则XZ，其中ZUXY多值依赖的对称性可以用完全二分图直

30、观表示XiZi1 Zi2 ZimYi1 Yi2 Yin 物 理普通物理学 光学原理 物理习题集李勇 王军412022/7/18多值依赖的性质(2) 多值依赖具有传递性若XY、YZ，则XZY(3) 函数依赖是多值依赖的特殊情况若XY，则XY这是因为当XY时，对X的每一个值x，Y有确定的值y与之对应，所以XY422022/7/1810.6.1 多值依赖设r是模式R上的关系，且W、X、Y、Z是R的子集。多值依赖的推理公理为：M1：自反律 若Y X 则XY。M2：增广律 若XY，W Z，则XZYW。M3：相加律 若XY、XZ，则XYZ。M4：投影律 若XY、XZ， 则XYZ、 XYZ。M5：传递律 若

31、XY、YZ，则XZY。M6：伪传递律 若XY、YWZ， 则XWZ(YW)M7：互补律 若XY、ZR(XY)，则XZM8：重复律 若XY，则XY。 M9：结合律 若XY，ZW，其中W Y和YZ，则XW。 432022/7/1810.6.2 4NF若关系模式存在多值依赖时，还需要进一步规范化 定义10.23 设关系模式R1NF，F是R上的FD和MVD集。如果对于R上的任何一个非平凡的多值依赖XY，X都含有键(码)，则R4NF。如果数据库模式R中的每一个关系模式R都属于4NF，那么，数据库模式R4NF。 定义3.3 设关系模式R ( U )，K U，r是R上的任一关系，若对r中的任意二个不同的元组满

32、足：t1 K t2K, 则称K是R的超键( superkey ) 。 若不存在K K, 使得t1 K t2 K成立, 称K是R的键(码)442022/7/1810.6.2 4NF根据4NF的定义，关系模式R1NF，如果对于R的每个非平凡多值依赖XY(Y X)，X都含有候选键，则必然有XY，所以4NF所允许的非平凡多值依赖实际上是函数依赖。如果R 4NF， 则R BCNF函数依赖是多值依赖的特殊情况若XY，则XY这是因为当XY时，对X的每一个值x，Y有确定的值y与之对应，所以XY定义10.20 设关系模式R1NF，F是R上的函数依赖集,对于F中的每一个函数依赖XY，必有X是R的一个候选键，则RB

33、CNF 452022/7/1810.6.2 4NF可采用分解的方法消去非平凡非函数依赖的多值依赖例： Teaching(C,T,B) 4NF 存在非平凡的多值依赖CT，且C不是候选码用投影分解法把Teaching分解为如下两个关系模式 CT(课程C,教师T) 4NF CB(课程C,参考书B) 4NF CT， CB是平凡多值依赖只考虑函数依赖，BCNF是关系模式规范化的最高程度考虑多值依赖，4NF是关系模式规范化的最高程度462022/7/18规范化小结关系数据库的规范化理论是数据库逻辑设计的工具。一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。规范化程度可以有

34、多个不同的级别,规范化程度过低的关系不一定能够很好地描述现实世界，可能存在插入异常、删除异常、修改复杂、数据冗余等问题一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化472022/7/18规范化小结关系模式规范化的基本步骤 1NF 消除非主属性对候选键的部分函数依赖消除决定属性 2NF集非码的非平 消除非主属性对候选键的传递函数依赖凡函数依赖 3NF 消除主属性对候选键的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NF482022/7/18规范化的基本思想所谓规范化实质上是概念的单一化消除不合适的数据依赖,使模式

35、中的各关系模式达到某种程度的“分离”采用“一事一地”的模式设计原则,让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去上面的规范化步骤可以在其中任何一步终止不能说规范化程度越高的关系模式就越好在设计数据库模式结构时，必须对实际情况和用户需求作进一步分析，确定合适的的模式规范化是范式的升高，而连接的本质是范式的降低。492022/7/18第10章 关系数据库设计理论10.1 关系模型的存储异常10.2 函数依赖10.5 关系模式的规范化10.6 多值依赖和4NF10.3 函数依赖公理10.4 模式分解10.8 小结502022/7/1810.2.1 函数依赖的

36、定义(回顾)一、函数依赖二、平凡函数依赖与非平凡函数依赖三、完全函数依赖与部分函数依赖四、传递函数依赖512022/7/1810.2.2 函数依赖的蕴涵性一个关系模式R上的任一关系r(R)，在任意给定的时刻都有它所满足的一组函数依赖集F。若关系模式R上的任一关系都能满足一个确定的函数依赖集F，则称F为R满足的函数依赖集 对于给定的一组函数依赖，需要判断另外一些函数依赖是否成立。例如,已知关系模式R上的函数依赖集为F, F中有函数依赖XY，XZ，问XYZ是否成立。这是函数依赖的逻辑蕴涵所要研究的问题定义10.5 设函数依赖集F和关系模式R(U)，属性集X,YU，关系模式R满足F 。如果关系模式R

37、满足FD XY，则称F逻辑蕴涵FD XY，或称XY逻辑蕴涵于F。记为 F |= XY。 522022/7/1810.2.2 函数依赖的蕴涵性定义10.6 设函数依赖集F，所有被F逻辑蕴涵的函数依赖称为F的闭包，记为F+。F+ 可表示为：F+ = XY| 所有F 蕴涵的FD XY 例: F=ABC, CB是R(A, B, C)上的一组函数依赖F+ =AA，ABA，ACA，ABCA， BB，ABB，BCB，ABCB， CC，ACC，BCC，ABCC， ABAB，ABCAB， ACAC，ABCAC， BCBC，ABCBC， ABCABC， ABC，ABAC，ABBC，ABABC， CB，CBC，AC

38、B，ACAB，ACABC 532022/7/1810.2.2 函数依赖的蕴涵性定义10.7 设关系模式R（U，F），U是R的属性全集，F是R的函数依赖集，X是U的子集。如果满足条件：(1) XU F+；(2) 不存在XX且XU F+成立。则称X为模式R的一个候选键。要确定关系模式的关键字,需要确定模式中属性间的依赖关系 为了从一组函数依赖求得蕴涵的函数依赖，例如已知函数依赖集F，求FD XY是否为F所蕴涵，就需要一套推理规则，这组推理规则是1974年首先由Armstrong提出来的。542022/7/1810.3.1 Armstrong公理函数依赖的公理系统是模式分解算法的理论基础， Arms

39、trong公理 设关系模式R(U，F)，并且X、Y、Z和W是U的子集A1 自反律(Reflexivity)若YXU, 则 F |= XY；A2 增广律(Augmentation) 若XY且ZU，则 F |= XZYZ；A3 传递律(Transitivity)若XY, YZ，则 F |= XZ.552022/7/1810.3.1 Armstrong公理证明：自反律(Reflexivity)若YXU, 则 F|=XY；(1) 若t1X=t2X，则X的任意子集在t1、t2上的属性值相同， 因YX，即有t1Y = t2Y。 根据函数依赖的定义，XY成立 。则 F|=XY在一个关系中，两个元组不可能在属

40、性集X上的值相同、而在X的子集Y上的值不同。所以，公理A1是平凡的。 562022/7/1810.3.1 Armstrong公理证明：增广律(Augmentation) 若XY且ZU，则 F |= XZYZ(2) 设t1XZ=t2XZ，则有t1Xt1Z=t2Xt2Z，则t1X=t2X，t1Z=t2Z由已知条件XY可知，t1Y=t2Y。因此，有t1YZ=t1Yt1Z=t2Yt2Z=t2YZ根据函数依赖的定义，若t1XZ=t2XZ，有t1YZ=t2YZ时，XZYZ成立增广律表明，在一个函数依赖的左部增加R的属性，所得函数依赖亦成立。公理A2还可以写为：若XY且WZU，则 F|=XZYW。 5720

41、22/7/1810.3.1 Armstrong公理证明：传递律(Transitivity) 若XY, YZ，则 F|=XZ ；(3) 已知XY，则t1X=t2X时，有t1Y=t2Y。又已知YZ，则t1Y=t2Y时, 有t1Z=t2Z。显然，XZ 成立 582022/7/18导出推论 根据A1，A2，A3这三条推理规则可以得到下面三条很有用的推论： 合成规则由XY, XZ, 则XYZ （A2， A3）分解规则由XY及 ZY,则XZ （A1， A3） 伪传递规则由XY, YZW,则XZW （A2， A3） Al. 自反律若Y X U,则X Y为F所蕴含 A2. 增广律若XY为F所蕴含，且Z U，则

42、XZYZ为F所蕴含。 A3. 传递律若XY及YZ为F所蕴含，则XZ为F所蕴含。592022/7/18导出推论 合成规则由XY,XZ,则XYZ （A2， A3）证明： 若XY,由公理A2， 有XXXY。 若XZ,同理有XYYZ 由公理A3，有XXYZ， 即XYZ。 Al. 自反律若Y X U,则X Y为F所蕴含 A2. 增广律若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。 A3. 传递律若XY及YZ为F所蕴含，则XZ为F所蕴含。602022/7/18导出推论分解规则由XY及 ZY,则XZ （A1， A3）证明：若ZY， 由公理A1, 有YZ， 又已知XY， 由公理A3，XZ成立 Al. 自反

43、律若Y X U,则X Y为F所蕴含 A2. 增广律若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。 A3. 传递律若XY及YZ为F所蕴含，则XZ为F所蕴含。612022/7/18导出推论 伪传递规则由XY, YZW,则XZW （A2， A3）证明： 若XY， 由公理A2有XZYZ， 又有YZW， 根据公理A3， XZW成立。 Al. 自反律若Y X U,则X Y为F所蕴含 A2. 增广律若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。 A3. 传递律若XY及YZ为F所蕴含，则XZ为F所蕴含。622022/7/18导出推论 根据A1，A2，A3可以得到下面三条推论： 合成规则 由XY,XZ,

44、则XYZ 分解规则 由XY及 ZY,则XZ 伪传递规则 由XY, YZW,则XZW根据合成规则和分解规则，可得 XA1 A2Ak 成立的充分必要条件是 XAi 成立 （i=l，2，k）。 632022/7/18Armstrong公理用途Armstrong公理系统是一套推理规则从一组函数依赖求得蕴含的函数依赖是模式分解算法的理论基础求给定关系模式的关键字642022/7/18Armstrong公理完备性Armstrong公理是正确的、完备的?正确性 利用该公理系统，如果能从函数依赖集F推出FD XY成立，则F蕴涵 XY完备性用公理可以从已知的一组函数依赖F推出它所蕴涵的所有函数依赖 。要说明公理

45、的完备性，可以对已知函数依赖集F求F+。如果可以用公理推导出F+中所有的函数依赖,则可以证明公理是完备的。由F=XA1, XAn出发可以推导出2n个不同的函数依赖。该问题属于NP完全问题。由F求F+ 是行不通的可以用穷举法得到答案，计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了652022/7/18属性闭包定义10.8 设关系模式R(U, F)，U=A1,A2,An，XU。所有用公理推出的函数依赖XAi中Ai的属性集合称为属性集X关于函数依赖集F的闭包，记为XF+。 XF+=Ai | 所有用公理由F推出的XAi。 显然，由自反律知道XXF+ 。例如，设R(A, B, D, E,

46、H)， R上的函数依赖集F=AD，ABDE，EH若X=A，(A)F+ =AD。 若X=AB，(AB)F+ =ABDEH。有了属性闭包的概念，就可以从XF+中看出某个函数依赖XY是否能够用公理从F中推出。662022/7/18属性闭包定理10.1 设关系模式R(U, F), X,YU。能够由Armstrong公理从F导出XY成立的充要条件是Y XF+ 证明：设Y= A1,A2,Ak ，AiU (i=1,2, ,k)。先证充分性。设Y XF+ ，由XF+的定义知，XAi (i=1,2, , k)是由Armstrong公理从F中导出的，根据合成规则，XY成立。证必要性。设XY是用Armstrong公

47、理从F推导出的。根据分解规则，有XAi (i=1,2, ,k)成立，由XF+的定义知， Ai XF+ (i=1,2, ,k)，即Y XF+ 。 证毕。用途： 将判定XY是否能由F根据Armstrong公理导出的问题，转化为求出XF+ ，判定Y是否为XF+的子集的问题672022/7/18Armstrong公理完备性的思路证明完备性：用公理可以从已知的一组函数依赖F推出它所蕴涵的所有函数依赖(1) 对已知函数依赖集F求F+。如果可以用公理推导出F+中所有的函数依赖,则可以证明公理是完备的定义10.6 设函数依赖集F，所有被F逻辑蕴涵的函数依赖称为F的闭包，记为F+。F+ 可表示为：F+ = XY

48、| 所有F 蕴涵的FD XY(2) 有了属性闭包的概念，就可以从X+中看出某个函数依赖XY是否能够用公理从F中推出。将判定XY是否能由F根据Armstrong公理导出的问题，转化为求出XF+, 判定Y是否为XF+的子集的问题682022/7/18Armstrong公理完备性定理10.2 Armstrong公理是正确的，完备的 正确性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中（ Armstrong公理的正确性已在前面证明）完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来只需证明逆否命题: 若函数依赖XY不能由F从Armstrong公

49、理导出，那么它必然不为F所蕴含思路：给出关系r(R)，如果能够证明以下两点则完备性得证 存在r(R)满足F中的所有函数依赖 不能用Armstrong公理推导出来的XY , 在r(R)上不成立692022/7/18Armstrong公理完备性证明证明：先证明 r(R)满足F中的所有函数依赖 构造一张二维表r，它由下列两个元组构成，可以证明r必是R(U, F)的一个关系，即满足F中的所有函数依赖 。 设FD WZF，W在r中有两种情况：(1) W XF+ 。根据属性闭包的定义，有XW，又因WZ，由函数依赖的传递性得FD XZ成立。根据属性闭包的定义，有Z XF+ 。由r的构造知WZ在r上成立。(2

50、) W XF+ 。则在r中有tWtW，因此，WZ在r上总是成立的。由(1)和(2)知，对F中的任意函数依赖在r上都是成立的,即r满足F。 XF+U- XF+A1A2.An111000111111702022/7/18Armstrong公理完备性证明：(续) 再证明不能用Armstrong公理推导出来的XY , 在r(R)上不成立 因为XY不能由F从公理推出,由定理10.1知,Y XF+tX=tX，而Y XF+ ，则tYtY，即r不满足XY。证毕 定理10.1 设关系模式R(U, F), X,YU。能够由Armstrong公理从F导出XY成立的充要条件是YXF+ XF+U- XF+A1A2.An

51、111000111111712022/7/18Armstrong公理完备性说明“蕴含” 和 “导出”的等价“通过F推导出的函数依赖”“F所蕴涵的函数依赖”这两种说法是等价的 属性闭包XF+和函数依赖集的闭包F+的等价 XF+= Ai | 所有F|= XAi。 F+ = XY| 用公理从F导出的所有FD XY对于一个给定的关系模式R以及R的函数依赖集F，经常需要判断某一个函数依赖XY是否被F所逻辑蕴涵判断XY是否是F+ 中的成员 F+很大 求XF+然后判断Y X+是否成立 计算XF+不困难 722022/7/18求属性闭包的算法算法10.1 计算属性集X关于F的闭包XF+ 输入:模式R的属性全集

52、U,U上的函数依赖集F,属性集X输出：属性集X的闭包XF+方法：计算X(i)（i=0, 1, ）(1) 初值 X(0) = X，i=0；(2) X(i+1) = X(i) Z；其中，属性集Z=A | 存在VWF，VX(i)且AW而A X(i)(3) 判断X(i+1) = X(i)或X(i+1) =U是否成立，若成立转(5)(4) i=i+1，转(2)；输出XF+的结果X(i+1)只要F中的函数依赖的左部属性包含在中间结果X(i)中，就可以将没有出现在X(i)中的右部属性A并入X(i)中。XA显然成立732022/7/18求属性闭包的算法【例10-1】设关系模式R(U,F), U=A,B,C,D

53、,E,G, F= ABC,BCD,ACDB,DEG,BEC,CEAG,求 (BD)+解：令X=BD (1) 初值 (X)(0)=BD (2) 在F中寻找左部是BD子集的函数依赖，DEG满足条件。结果为：(X)(1)=BDEG。X(0) X(1)。 在F中继续寻找左部是BDEG子集的函数依赖，得 BEC，C不包含在BDEG中，结果为(X)(2)=BCDEG在F中继续寻找左部是BCDEG子集的函数依赖，得BCD，CEAG。这里仅有右部属性A是未出现在(X)(2) 中的属性，结果为 (X)(3)=ABCDEG。X(3) X(2)，虽然F中还有未考察过的函数依赖，但X(3) 已包含了R中的所有属性，结

54、束。输出结果：(BD)+ = ABCDEG 只要F中的函数依赖的左部属性包含在中间结果X(i)中，就可以将没有出现在X(i)中的右部属性A并入X(i)中。XA显然成立742022/7/1810.3.2 函数依赖集的等价和覆盖定义10.9 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。函数依赖集等价的充要条件引理10.1 F+ = G+ 的充分必要条件是F G+ ，同时G F+ 证: 必要性显然，只证充分性。（1）若FG+ ，则XF+ XG+ 。（2）任取XYF+ 则有 Y XF+ XG+ 。 所以XY (G+)+= G+。即F+ G+。（3）同理可证G+

55、 F+ ，所以F+ = G+。要判定F G+，只须逐一对F中的函数依赖XY，考察 Y 是否属于XG+ 就行了。 引理10.1 给出了判断两个函数依赖集等价的可行算法。752022/7/18最小依赖集定义10.10 如果函数依赖集F满足下列条件，则称F为一个最小函数依赖集 或 最小覆盖(1) F中的所有函数依赖其右部都是单属性 (2)对F中的任一函数依赖XA, FXA与F不等价(3)对F中的任一函数依赖XA，FXAZA 与F不等价。其中，Z是X的真子集762022/7/18最小依赖集例 对于关系模式S，其中： U= Sno，Sdept，Mname，Cno，Grade ， F= SnoSdept，

56、SdeptMname， （Sno，Cno）Grade 设F=Sno Sdept ，SnoMname， Sdept Mname ，(Sno ， Cno) Grade ， (SNO，Sdept)SdeptF是最小覆盖，而F 不是。因为：F - SnoMname与F 等价 F - (Sno，Sdept)Sdept也与F 等价 F - (Sno，Sdept)Sdept SnoSdept也与F 等价772022/7/18最小依赖集定理10.3 每一个函数依赖集F均等价于一个最小 函数依赖集Fm证: 构造性证明，找出F的一个最小依赖集。(1)逐一检查F中各函数依赖FDi：XA，令G=F-XA，若AXG+，

57、 则从F中去掉此函数依赖由于F与G =F-XA等价的充要条件是AXG+ 因此F变换前后是等价的。(2) 逐一检查F中各函数依赖FDi：XY， 若Y=A1A2 Ak，k 2， 则用 XAj | j=1，2， k 来取代XY。782022/7/18最小依赖集(3)逐一取出F中各函数依赖FDi：XA， 设X=B1B2Bm， 逐一考查Bi (i=l，2，m)， 若A (X-Bi )F+ ， 则以X-Bi 取代X。由于F与F-XAZA等价的充要条件是AZF+ ，其中Z=X-Bi 因此F变换前后是等价的。由定义，最后剩下的F就一定是极小依赖集。 过程的每一步都保证了改造前后的两个函数依赖集等价,因此剩下的

58、F与原来的F等价。 证毕792022/7/18极小化过程F的最小函数依赖集Fm不一定是唯一的。它与对各函数依赖集FDi中X各属性的处置顺序有关若改造后的F与原来的F相同，说明F本身就是一个最小依赖集定理10.3的证明过程 是求F最小依赖集的过程，也可以验证F是否为最小依赖集802022/7/18极小化过程例 由关系模式R(U, F), 其中UA,B,C,D,E， F=ABC，BD，CE，ECB，ACB, 求Fm 解：(1)将F中的所有函数依赖转换为右部为单属性的。本题目F中函数依赖右部都仅含有一个属性，得Fm = F(2)分别去掉一个函数依赖XA后求关于X的闭包，去掉多余的函数依赖令F=F-A

59、BC,求AB的闭包，得ABF+ =ABD,不包含C，故ABC不能去掉令F=F-BD,求B的闭包，得BF+ =B,不包含D，故BD不能去掉令F=F-CE,求C的闭包，得CF+ =C,不包含E，故CE不能去掉812022/7/18极小化过程例 由关系模式R(U, F), 其中UA,B,C,D,E， F=ABC，BD，CE，ECB，ACB, 求Fm 解：(2)分别去掉一个函数依赖XA后求关于X的闭包,去掉多余的函数依赖（续）令F=F-ECB,求EC的闭包，得ECF+ =EC, 不包含B，故ECB不能去掉令F=F-ACB,求AC的闭包,得ACF+ =ABCDE, 包含B，故ACB可以去掉则在F中去掉函

60、数依赖ACB，得Fm ABC，BD，CE，ECB,822022/7/18极小化过程例 由关系模式R(U, F), 其中UA,B,C,D,E， F=ABC，BD，CE，ECB，ACB, 求Fm 解: (续)(3)去掉函数依赖左部多余的属性 检查形如B1B2BmA的函数依赖,若A (X-Bi )F+ , 则以X-Bi 取代X检查函数依赖ABC令BiA，BF+=B,D: ABC中A不能去掉令BiB，AF+=A: ABC中B不能去掉检查函数依赖ECB令BiE,CF+=CEB: ECB中E可以去掉(包含B)令BiC，EF+=E: ECB中C不能去掉得Fm ABC，BD，CE，CB, 解毕832022/7