第六章关系数据库设计理论(2014)

1、第六章 关系数据库设计理论12问题的提出基本概念34规范化函数依赖的公理系统5模式分解6.1 6.1 问题的提出问题的提出v 针对一个具体问题，设计一个好的关系数据库系针对一个具体问题，设计一个好的关系数据库系统，关键是要构造一个适合于它的数据模式（统，关键是要构造一个适合于它的数据模式（数据数据库逻辑设计问题库逻辑设计问题）v 数据库逻辑设计主要解决的问题：数据库逻辑设计主要解决的问题：n 应该构造几个关系模式应该构造几个关系模式n 每个关系模式包括哪些属性每个关系模式包括哪些属性v 数据库逻辑设计工具数据库逻辑设计工具关系数据库的关系数据库的规范化理论规范化理论6.1 6.1 问题的提出问

2、题的提出例：描述例：描述电力设备存放管理的数据库电力设备存放管理的数据库数据库：数据库：WAE(WAE(仓库号，所在区域，区域主管，设备号，数量仓库号，所在区域，区域主管，设备号，数量) )语义语义： 一个区域有多个仓库，一个仓库只能属于一个区域；一个区域有多个仓库，一个仓库只能属于一个区域； 一个区域只有一个区域主管；一个区域只有一个区域主管； 一个仓库可以存放多种设备，每种设备可以存放在一个仓库可以存放多种设备，每种设备可以存放在多个仓库中；多个仓库中；每个仓库的每种设备都有一个库存数量。每个仓库的每种设备都有一个库存数量。6.1 6.1 问题的提出问题的提出 数据冗余太大数据冗余太大浪费

3、大量的存储空间浪费大量的存储空间 更新异常更新异常更新代价大，可能导致数据不一致更新代价大，可能导致数据不一致 插入异常插入异常该插的数据插不进去该插的数据插不进去 删除异常删除异常不该删除的数据不得不删，造成某些数据丢失不该删除的数据不得不删，造成某些数据丢失存在的问题：存在的问题：6.1 6.1 问题的提出问题的提出结论：结论： WAE关系模式不是一个好的模式。关系模式不是一个好的模式。 “好好”的模式：不会发生插入异常、删除异常、的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。更新异常，数据冗余应尽可能少。原因：由存在于模式中的某些原因：由存在于模式中的某些数据依赖数据

4、依赖引起的引起的解决方法：通过解决方法：通过分解关系模式分解关系模式来消除其中不合适的来消除其中不合适的数据依赖。数据依赖。6.1 6.1 问题的提出问题的提出 分解成三个关系模式即可：分解成三个关系模式即可： W(W(仓库号，所在区域仓库号，所在区域) )； A( A(区域，区域主管区域，区域主管) )； WE( WE(仓库号，设备号，数量仓库号，设备号，数量) )6.2 6.2 基本概念基本概念 规范化理论规范化理论正是用来改造关系模式，正是用来改造关系模式，通过分解关系模式来消除其中不合适的数通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更据依赖，以解决插入异常、

5、删除异常、更新异常和数据冗余等问题。新异常和数据冗余等问题。6.2.1 6.2.1 函数依赖函数依赖定义定义6.16.1 设设R(U)R(U)是一个属性集是一个属性集U U上的关系模式，上的关系模式，X X和和Y Y是是U U的子集。若对于的子集。若对于R(U)R(U)的任意一个可能的关系的任意一个可能的关系r r，对对 t t1,1,t2t2 r r，若，若t1X=t2Xt1X=t2X，则，则t1Y=t2Yt1Y=t2Y则称则称X X函数决定函数决定Y Y或或Y Y函数依赖函数依赖X X，记作，记作XYXY。 如：如：仓库号仓库号 所在区域所在区域 所在区域所在区域 区域主管区域主管 （仓库

6、号，设备号）（仓库号，设备号） 数量数量若若Y不函数依赖于不函数依赖于X, 则记为则记为X Y若若XY，并且，并且YX, 则记为则记为XY若若XY，则称，则称X为这个函数依赖的决定因素为这个函数依赖的决定因素。6.2.1 6.2.1 函数依赖函数依赖1. 1. 函数依赖是函数依赖是语义范畴语义范畴的概念，只能根据数据的语的概念，只能根据数据的语义来确定函数依赖。义来确定函数依赖。 例：例：“区域主管区域主管所在区域所在区域” ” 只有在不允许有同只有在不允许有同名人的条件下成立名人的条件下成立2. 2. 函数依赖不是指关系模式函数依赖不是指关系模式R R的某个或某些关系实的某个或某些关系实例满

7、足的约束条件，而是指例满足的约束条件，而是指R R的所有关系实例均要的所有关系实例均要满足的约束条件。满足的约束条件。3.3.函数依赖存在的时间无关性函数依赖存在的时间无关性。说明说明:6.2.1 6.2.1 函数依赖函数依赖 函数依赖与属性间的联系类型有关函数依赖与属性间的联系类型有关(1) (1) 若属性若属性X X和和Y Y之间有之间有“一对一一对一”的联系的联系 则：则：X Y,Y X,X YX Y,Y X,X Y(2) (2) 若属性若属性X X和和Y Y之间有之间有“多对一多对一”的联系的联系 则：则：X Y,X Y,但但Y X Y X (3)(3)若属性若属性X X和和Y Y之间

8、有之间有“多对多多对多”的联系的联系 则：则：X X与与Y Y之间不存在任何函数依赖之间不存在任何函数依赖注：当确定函数依赖关系时注：当确定函数依赖关系时, ,可从属性间的联系入手可从属性间的联系入手6.2.1 6.2.1 函数依赖函数依赖 平凡函数依赖与非平凡函数依赖平凡函数依赖与非平凡函数依赖定义定义6.2 在关系模式在关系模式R(U)R(U)中，对于中，对于U U的子集的子集X X和和Y Y：若若XYXY，但，但Y Y X X，则称，则称XYXY是是非平凡函数依赖非平凡函数依赖. .若若XYXY，但，但Y Y X X，则称，则称XYXY是是平凡函数依赖平凡函数依赖. .例：在关系例：在关

9、系WAEWAE中，中， 非平凡函数依赖：非平凡函数依赖：（仓库号，设备号）（仓库号，设备号） 数量数量 平凡函数依赖：平凡函数依赖： （仓库号，设备号）（仓库号，设备号）仓库号仓库号 （仓库号，设备号）（仓库号，设备号）设备号设备号注：对任一关系模式，平凡函数依赖必然存在，则一般讨论非平凡函注：对任一关系模式，平凡函数依赖必然存在，则一般讨论非平凡函数依赖。数依赖。6.2.1 函数依赖函数依赖 完全函数依赖与部分函数依赖完全函数依赖与部分函数依赖定义定义6.3 在在R(U)中，如果中，如果XY，并且对于，并且对于X的任何的任何一个真子集一个真子集X ，都有，都有X Y, 则称则称Y对对X完全函

10、数依完全函数依赖，记作赖，记作X Y。 若若XY，但，但Y不完全函数依赖于不完全函数依赖于X，则称，则称Y对对X部分函数依赖，记作部分函数依赖，记作X P Y。例：在关系例：在关系WAE中，中， 由于：由于： （仓库号，设备号）（仓库号，设备号） 数量数量, 但仓库号但仓库号数量数量, 设设备号备号 数量数量 因此：因此： （仓库号，设备号）（仓库号，设备号）数量数量6.2.1 函数依赖函数依赖 传递函数依赖与直接函数依赖传递函数依赖与直接函数依赖 如果如果YX， 即即XY，则，则Z对对X直接函数依赖。直接函数依赖。例：在关系例：在关系waewae中有：中有：定义定义6.4 在在R(U)中，如

11、果中，如果XY，YZ，且，且Y X，YX，则称，则称Z对对X传递函数依赖传递函数依赖,记作记作X t Z 。仓库号仓库号所在区域，所在区域所在区域，所在区域区域主管区域主管可可得到传递函数依赖：仓库号得到传递函数依赖：仓库号 t 区域主管区域主管6.2.2 码码定义定义6.5 设设K为为R中的属性或属性组合。若中的属性或属性组合。若K F U，则，则K称为称为R的一个的一个侯选码侯选码。 若关系模式若关系模式R有多个候选码，则选定其中的一有多个候选码，则选定其中的一个做为个做为主码主码。 主属性：主属性：包含在任何一个候选码中的属性包含在任何一个候选码中的属性 非主属性：非主属性：不包含在任何

12、一个码中的属性不包含在任何一个码中的属性 全码：全码：整个属性组全是码整个属性组全是码6.2.2 码码定义定义6.56.5 关系模式关系模式R R中属性或属性组中属性或属性组X X并非并非R R的码，的码，但但X X是另一个关系模式的码，则称是另一个关系模式的码，则称X X是是R R的外部码，的外部码，也称也称外码外码。注：主码和外码一起提供了表示关系间联系的手段。注：主码和外码一起提供了表示关系间联系的手段。例：在关系例：在关系SC(Sno, Cno, Grade)中，中， 由于：由于：Sno不是不是SC的码，但是另一个关系的码，但是另一个关系S的码的码 因此：因此：Sno是是SC的外码的外

13、码6.3 规范化规范化 范式是对关系数据库的规范化过程中为范式是对关系数据库的规范化过程中为不同不同程度的规范化要求程度的规范化要求设立的不同标准。设立的不同标准。 范式是符合某一种级别的关系模式的集合。范式是符合某一种级别的关系模式的集合。 范式的种类：范式的种类： 第一范式第一范式(1NF) 第二范式第二范式(2NF) 第三范式第三范式(3NF) BC范式范式(BCNF) 第四范式第四范式(4NF) 第五范式第五范式(5NF)6.3 规范化规范化 各种范式之间存在联系：各种范式之间存在联系：5NF 4NF BCNF 3NF 2NF 1NF 某一关系模式某一关系模式R为第为第n范式，可简记为

14、范式，可简记为RnNF。 通过模式分解将一个低级范式的关系模式转换为若通过模式分解将一个低级范式的关系模式转换为若干个高级范式的关系模式的过程称作干个高级范式的关系模式的过程称作规范化规范化。 6.3.1 第一范式（第一范式（1NF） 定义定义6.7 满足最低要求的范式。满足最低要求的范式。 如果一个关系模式如果一个关系模式R的所有属性都是不可分的所有属性都是不可分的基本数据项，则的基本数据项，则R1NF。 第一范式是对关系模式的最起码要求。第一范式是对关系模式的最起码要求。 不满足第一范式的数据库模式不能称为关系数据库。不满足第一范式的数据库模式不能称为关系数据库。 但满足第一范式的关系模式

15、并不一定是一个好的关系模式。但满足第一范式的关系模式并不一定是一个好的关系模式。6.3.2 第二范式（第二范式（2NF）定义定义6.8 若关系模式若关系模式R1NF，并且每一个非主属，并且每一个非主属性都完全函数依赖于性都完全函数依赖于R的码，则的码，则R2NF。即：即：消除非主属性对码的部分依赖消除非主属性对码的部分依赖 如果一个数据库模式中的每个关系模式都是第二范式的，如果一个数据库模式中的每个关系模式都是第二范式的，则称此数据库模式属于第二范式的数据库模式。则称此数据库模式属于第二范式的数据库模式。 从从1NF1NF中消除非主属性对候选码的部分函数依赖中消除非主属性对候选码的部分函数依赖

16、, ,则获得则获得2NF2NF。6.3.2 第二范式（第二范式（2NF）例例: 关系模式关系模式WAE中中: WAE(WAE(仓库号，所在区域，区域仓库号，所在区域，区域主管，设备号，数量主管，设备号，数量) ) 码码： (仓库号仓库号, 设备号设备号) 主属性主属性:仓库号仓库号, 设备号设备号 非主属性非主属性: 所在区域、区域主管和数量所在区域、区域主管和数量 函数依赖：函数依赖：6.3.2 第二范式（第二范式（2NF）仓库号仓库号 设备号设备号数量数量 所在区域所在区域 区域主管区域主管关系关系WAE码为码为(仓库号仓库号, 设备号设备号)非主属性所在区域和区域主管部分函数依赖于码非主

17、属性所在区域和区域主管部分函数依赖于码WAE满足第一范式，但不满足第二范式。满足第一范式，但不满足第二范式。6.3.2 第二范式（第二范式（2NF） 解决方法：将解决方法：将WAE分解为两个关系模式，消除这些部分函分解为两个关系模式，消除这些部分函数依赖：数依赖： 即：即： WE（仓库号，设备号，数量仓库号，设备号，数量） WA（仓库号，所在区域，区域主管仓库号，所在区域，区域主管）仓库号仓库号设备号设备号数量数量关系关系WE关系关系WA仓库号仓库号所在区域所在区域区域主管区域主管WE2NF, WA2NF6.3.2 第二范式（第二范式（2NF）注：注： 采用投影分解法将一个采用投影分解法将一个

18、1NF的关系分解为多个的关系分解为多个2NF的关系，的关系，可以在可以在一定程度上减轻一定程度上减轻原原1NF关系中存在的插入异常、删关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。除异常、数据冗余度大、修改复杂等问题。 将一个将一个1NF关系分解为多个关系分解为多个2NF的关系，的关系，并不能完全消除并不能完全消除关系模式中的各种异常情况和数据冗余。关系模式中的各种异常情况和数据冗余。 如：如：(1) (1) 若某个区域刚刚设立还没有仓库，则所在区域和若某个区域刚刚设立还没有仓库，则所在区域和区域主管的值无法插入，造成区域主管的值无法插入，造成插入异常插入异常。 (2) (2)

19、 有一定的有一定的数据冗余数据冗余，当多个仓库处于同一个区域，当多个仓库处于同一个区域时，区域主管的值被多次存储。时，区域主管的值被多次存储。 (3) (3) 若某区域要更换区域主管，则要逐一地修改该区若某区域要更换区域主管，则要逐一地修改该区域的所有区域主管记录，稍有不慎，就有可能漏改某些记域的所有区域主管记录，稍有不慎，就有可能漏改某些记录，造成录，造成更新异常更新异常。6.3.3 第三范式（第三范式（3NF）如果一个数据库模式中的每个关系模式都是第三范如果一个数据库模式中的每个关系模式都是第三范式的，则称此数据库模式属于第三范式的数据库模式的，则称此数据库模式属于第三范式的数据库模式。式

20、。从从2NF2NF中消除非主属性对候选码的传递依赖中消除非主属性对候选码的传递依赖, ,则获得则获得3NF3NF。定义定义6.9 如果关系模式如果关系模式R2NF，且每个非主属性都不，且每个非主属性都不传递函数依赖于传递函数依赖于R的候选码，则称的候选码，则称R属于第三范式，简称属于第三范式，简称3NF，记作，记作R3NF。 即：消除非主属性对码的即：消除非主属性对码的部分依赖部分依赖和和传递依赖传递依赖6.3.3 第三范式（第三范式（3NF）例例: WE（仓库号，设备号，数量仓库号，设备号，数量） WA（仓库号，所在区域，区域主管仓库号，所在区域，区域主管） 函数依赖：函数依赖： WE中中：

21、 (仓库号，设备号仓库号，设备号) f 数量数量 WA中：中：仓库号仓库号所在区域，所在区域所在区域，所在区域区域主管区域主管 可可得到传递函数依赖：仓库号得到传递函数依赖：仓库号 区域主管区域主管 因此：因此： WE 3NF，而，而WA 3NF6.3.3 第三范式（第三范式（3NF） 原因原因:区域主管传递依赖于码。区域主管传递依赖于码。 解决方法：将解决方法：将WA分解为两个关系模式，消除这些分解为两个关系模式，消除这些传递依赖：传递依赖： 即：即： W（仓库号，所在区域仓库号，所在区域） A（所在区域，区域主管所在区域，区域主管）仓库号仓库号所在区域所在区域关系关系W关系关系A所在区域所

22、在区域区域主管区域主管W3NF, A3NF6.3.3 第三范式（第三范式（3NF）注：注： 采用采用投影分解法投影分解法将一个将一个2NF的关系分解为多个的关系分解为多个3NF的的关系，可以在关系，可以在一定程度上减轻一定程度上减轻原原2NF关系中存在的关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等插入异常、删除异常、数据冗余度大、修改复杂等问题。问题。 将一个将一个2NF关系分解为多个关系分解为多个3NF的关系，的关系，并不能完全并不能完全消除消除关系模式中的各种异常情况和数据冗余。表现关系模式中的各种异常情况和数据冗余。表现在可能存在主属性对码的部分和传递依赖。在可能存在主属性对

23、码的部分和传递依赖。6.3.4 BC范式（范式（BCNF） BCNF范式是第三范式的改进形式，建立在第一范范式是第三范式的改进形式，建立在第一范式的基础上，消除了主属性对码的部分和传递依赖。式的基础上，消除了主属性对码的部分和传递依赖。定义定义6.10 设关系模式设关系模式R1NF，若对于，若对于R的每个函的每个函数依赖数依赖XY，若，若Y不属于不属于X，则，则X必含有候选码，那必含有候选码，那么么RBCNF。即：每一个决定因素（决定属性集）都包含码即：每一个决定因素（决定属性集）都包含码6.3.4 BC范式（范式（BCNF）证明：证明：BCNF 3NF反证：若反证：若R BCNF， 但但R

24、3NF，则按，则按3NF定义，定义，一定有非主属性对码的传递依赖。一定有非主属性对码的传递依赖。 于是存在：于是存在：R的码的码X ，属性组，属性组Y，以及非主属，以及非主属性性Z（Z Y），使得），使得XY， Y Z，YX成立。成立。 由由YZ，按，按BCNF定义，定义，Y含有码，则是含有码，则是YX成成立，这与立，这与YX矛盾。矛盾。 所以：所以：R 3NF。6.3.4 BC范式（范式（BCNF）注意：注意： 若若RBCNF ，则，则R3NF 若若R3NF ，则，则R不一定属于不一定属于BCNF若若RBCNF 所有非主属性对每一个候选码都是完全函数依赖；所有非主属性对每一个候选码都是完全函

25、数依赖； 所有主属性对所有主属性对每一个不包含它的候选码每一个不包含它的候选码都是完全函数都是完全函数依赖；依赖； 没有任何属性完全函数依赖于非码的任何一组属性。没有任何属性完全函数依赖于非码的任何一组属性。6.3.4 BC范式（范式（BCNF）例例1: Course（Cno, Creidt, Pcno） 函数依赖函数依赖： Cno Credit, Cno Pcno 即：无部分依赖和传递依赖，且即：无部分依赖和传递依赖，且Cno是唯一决定因素是唯一决定因素 因此：因此： Course 3NF，且，且Course BCNF 码码： Cno 即为主属性，决定因素即为主属性，决定因素6.3.4 BC

26、范式（范式（BCNF）例例2：在关系模式：在关系模式SCP（S, C, P）中，）中，S表示学生，表示学生，C表示课程，表示课程， P表示名次。表示名次。说明：说明： 每一个学生选修每一门课程都有一个固定的名每一个学生选修每一门课程都有一个固定的名次：次： 每一门课程中每一名次只对应一个学生（假设每一门课程中每一名次只对应一个学生（假设没有相同名次的学生）没有相同名次的学生） ：(S，C)P(C，P)S6.3.4 BC范式（范式（BCNF）SCPCPS关系关系SCP 候选码候选码： (S，C) 和和(C，P)即：即：S，C和和P都是主属性都是主属性 决定因素决定因素： (S，C)和和(C，P)

27、 结论结论：SCPBCNF 只有只有(S，C)和和(C，P)决定因素且包含候选码，决定因素且包含候选码，无其他决定因素无其他决定因素SCP3NF S、C、P都是主属性都是主属性无部分依赖和传递依赖无部分依赖和传递依赖6.3.4 BC范式（范式（BCNF）例例3：在关系模式：在关系模式WES(仓库号仓库号,设备号设备号,职工号职工号)中。中。说明：说明：一个仓库可以有多个职工一个仓库可以有多个职工;一个职工仅在一个仓库工作一个职工仅在一个仓库工作;1.每个仓库一种设备仅由一名职工保管每个仓库一种设备仅由一名职工保管,但每名职工可以保但每名职工可以保管多种设备管多种设备. 问问:该关系的码该关系的

28、码?属于第几范式属于第几范式?答答:码码: (仓库号仓库号,设备号设备号) 属于属于3NF,但不属于但不属于BCNF 非非BCNF的不良特性的不良特性:某位职工刚分配到某位职工刚分配到一个仓库工作，但一个仓库工作，但尚未负责具体设备，尚未负责具体设备，这样的信息就无法这样的信息就无法插入插入。职工号职工号仓库号仓库号 (仓库号仓库号,设备号设备号) 职工号职工号练习练习1 1：问：关系模式问：关系模式R中的属性中的属性全部是主属性全部是主属性,则则R的的必定是必定是_。 3NF练习练习2：如下表所示的关系如下表所示的关系R R，下列选项中关于该关系模，下列选项中关于该关系模式属于第几范式判断正

29、确的是式属于第几范式判断正确的是（ ）。）。A、不是、不是3NF B、是、是3NF但不是但不是2NFC、是、是3NF但不是但不是BCNFD、是、是BCNFD任何一个二元关系必定任何一个二元关系必定属于基于函数依赖最高属于基于函数依赖最高范式范式BCNFBCNF。6.3.5 多值依赖与第四范式多值依赖与第四范式课课 程程 C教教 员员 T参参 考考 书书 B物理物理 数学数学 计算数计算数学学李李 勇勇王王 军军 李李 勇勇张张 平平 张张 平平周周 峰峰 普通物理学普通物理学光学原理光学原理 物理习题集物理习题集 数学分析数学分析微分方程微分方程高等代数高等代数 数学分析数学分析 例例: 学校

30、中某一门课学校中某一门课程由多个教师讲授，程由多个教师讲授，他们使用相同的一他们使用相同的一套参考书。套参考书。即：关系模式即：关系模式Teaching(C, T, B) 课程课程C、教师、教师T 和和 参参考书考书B6.3.5 多值依赖与第四范式多值依赖与第四范式普通物理学普通物理学光学原理光学原理物理习题集物理习题集普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析微分方程微分方程高等代数高等代数李李 勇勇李李 勇勇李李 勇勇王王 军军王王 军军王王 军军李李 勇勇李李 勇勇李李 勇勇张张 平平张张 平平张张 平平 物物

31、 理理物物 理理物物 理理物物 理理物物 理理物物 理理数数 学学数数 学学数数 学学数数 学学数数 学学数数 学学 参考书参考书B教员教员T课程课程C用二维表表示用二维表表示Teaching6.3.5 多值依赖与第四范式多值依赖与第四范式 Teach具有唯一候选码具有唯一候选码(C, T, B)， 即全码即全码 TeachingBCNF 存在的问题存在的问题 (1)数据冗余数据冗余：有多少名任课教师，参考书就要存储多少次：有多少名任课教师，参考书就要存储多少次 ； (2)插入异常插入异常：当某一课程增加一名任课教师时，该课程有：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多

32、少个元组；多少本参照书，就必须插入多少个元组； (3) 删除异常：删除异常：某一门课要去掉一本参考书，该课程有多少某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组；名教师，就必须删除多少个元组； (4) 修改异常：修改异常：某一门课要修改一本参考书，该课程有多少某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组。名教师，就必须修改多少个元组。 产生原因：存在产生原因：存在多值依赖多值依赖6.3.5 多值依赖与第四范式多值依赖与第四范式定义定义6.11 设设R(U)是属性集是属性集U上的一个关系模式。上的一个关系模式。X、 Y、Z是是U的子集，并且的子集，并且Z

33、UXY，多值依，多值依赖赖 XY成立当且仅当对成立当且仅当对R的任一关系的任一关系r，给定一给定一对（对（x，z）值，则对应一组）值，则对应一组Y值，且这组值仅仅决值，且这组值仅仅决定于定于X值而与值而与Z值无关值无关。例：例： Teaching（C, T, B） 对于对于C的每一个值，的每一个值，T总有一组值与之对应，而总有一组值与之对应，而与与B的取值无关，则的取值无关，则T多值依赖于多值依赖于C即：即：CT，且，且B也多值依赖于也多值依赖于C即：即：CB。6.3.5 多值依赖与第四范式多值依赖与第四范式 平凡多值依赖和非平凡的多值依赖平凡多值依赖和非平凡的多值依赖 若若XY，而，而Z，则

34、称，则称XY为平凡为平凡的多值依赖；的多值依赖； 否则称否则称XY为非平凡的多值依赖。为非平凡的多值依赖。如非平凡的多值依赖：如非平凡的多值依赖：CT，CB6.3.5 多值依赖与第四范式多值依赖与第四范式 多值依赖的性质：多值依赖的性质：（1）对称性对称性： 即：若即：若XY，则，则XZ，其中，其中ZUXY 多值依赖的对称性可以用多值依赖的对称性可以用完全二分图完全二分图直观地直观地表示出来。表示出来。（2）传递性传递性：即：若即：若XY，YZ， 则则XZ Y6.3.5 多值依赖与第四范式多值依赖与第四范式 物物 理理普通物理学普通物理学 光学原理光学原理 物理习题集物理习题集李勇李勇 王军王

35、军完全二分图描述多值依赖对称性完全二分图描述多值依赖对称性6.3.5 多值依赖与第四范式多值依赖与第四范式（5）函数依赖是多值依赖的特殊情况：）函数依赖是多值依赖的特殊情况： 即：若即：若XY，则，则XY。（3）合并性合并性: 若若XY，XZ，则，则 XY Z。（4）分解性分解性: 若若XY，XZ，则，则 XYZ, XYZ， XZY。6.3.5 多值依赖与第四范式多值依赖与第四范式定义定义6.12 关系模式关系模式R1NF，如果对于，如果对于R的每个非平的每个非平凡多值依赖凡多值依赖XY（Y X），），X都含有候选码，都含有候选码，则则R4NF。即：即：消除各属性间非平凡且非函数依赖的多值依赖

36、。消除各属性间非平凡且非函数依赖的多值依赖。 允许出现函数依赖（非平凡多值依赖）允许出现函数依赖（非平凡多值依赖） 允许出现平凡多值依赖允许出现平凡多值依赖 如果如果R 4NF， 则则R BCNF6.3.5 多值依赖与第四范式多值依赖与第四范式证明：证明：4NF BCNF反证：若反证：若R 4NF， 但但R BCNF，则按，则按BCNF定定义，一定有一个决定因素不包含码。义，一定有一个决定因素不包含码。 于是存在：于是存在：XY， Y X，且，且X中不含有码。中不含有码。 由于函数依赖是多值依赖的特殊情况，即：由于函数依赖是多值依赖的特殊情况，即：XY ，可得，可得XY （Y X） ，按按4N

37、F定义，定义，X一定含有码，则与一定含有码，则与X中不含有码矛盾。中不含有码矛盾。 所以：所以：R BCNF。6.3.5 多值依赖与第四范式多值依赖与第四范式 存在非平凡的多值依赖存在非平凡的多值依赖CT，且，且C不是候选不是候选码，该关系模式的码是码，该关系模式的码是(C,T,B) ，即全码。，即全码。 存在问题存在问题：数据冗余大，插入、删除、更新异常：数据冗余大，插入、删除、更新异常 解决方法解决方法：用投影分解法把：用投影分解法把Teach分解为如下两个分解为如下两个关系模式关系模式： CT(C, T) 4NF CB(C, B) 4NF 其中：其中：CT， CB是平凡多值依赖是平凡多值

38、依赖 例：例： Teach(C,T,B) 4NF6.3.5 多值依赖与第四范式多值依赖与第四范式 函数依赖和多值依赖是两种非常重要的数据依赖函数依赖和多值依赖是两种非常重要的数据依赖 若只考虑若只考虑函数依赖函数依赖，则，则BCNF为最高范式（但为最高范式（但不是数据库模式设计的最高范式）；不是数据库模式设计的最高范式）； 若考虑若考虑多值依赖多值依赖，则，则4NF为最高范式；为最高范式； 若消除了若消除了4NF中的中的连接依赖连接依赖，可以得到更为规，可以得到更为规范化的范化的5NF。6.3.6 关系模式规范化关系模式规范化 一个关系只要其分量都是不可分的数据项，它就是一个关系只要其分量都是

39、不可分的数据项，它就是规范化的关系，但这只是最基本的规范化规范化的关系，但这只是最基本的规范化1NF。 规范化程度过低的关系不一定能够很好地描述现实规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题。数据冗余等问题。 一个低一级范式的关系模式，通过一个低一级范式的关系模式，通过模式分解模式分解可以转可以转换为若干个高一级范式的关系模式集合，这种过程换为若干个高一级范式的关系模式集合，这种过程就叫就叫关系模式的规范化关系模式的规范化。6.3.6 关系模式规范化关系模式规范化 消除不合适的数据依赖消

40、除不合适的数据依赖; 采用采用“一事一地一事一地”的模式设计原则，使各关系模的模式设计原则，使各关系模式达到某种程度的式达到某种程度的“分离分离”； 让一个关系描述一个概念、一个实体或者实体间让一个关系描述一个概念、一个实体或者实体间的一种联系的一种联系; 若多于一个概念就把它若多于一个概念就把它“分离分离”出去；出去； 所谓规范化实质上是所谓规范化实质上是概念的单一化概念的单一化。 规范化的基本思想规范化的基本思想6.3.6 关系模式规范化关系模式规范化 关系模式规范化的基本步骤关系模式规范化的基本步骤 1NF 消除决定因素消除决定因素 2NF非码的非平凡非码的非平凡 函数依赖函数依赖 3N

41、F BCNF 4NF消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖消除非平凡且非函数依赖的多值依赖消除非平凡且非函数依赖的多值依赖不能说规范化程度越高的关系模式就越好；不能说规范化程度越高的关系模式就越好；在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式；进一步分析，确定一个合适的、能够反映现实世界的模式；上面的规范化步骤可以

42、在其中任何一步终止。上面的规范化步骤可以在其中任何一步终止。注意：注意：练习练习 给定关系模式和函数依赖集合，要求判断达给定关系模式和函数依赖集合，要求判断达到的最高范式。到的最高范式。步骤如下步骤如下：1.1.求出给定关系的候选码（可能不止一个）求出给定关系的候选码（可能不止一个）2.2.根据码，写出主属性和非主属性。根据码，写出主属性和非主属性。3.3.判断是否满足第一范式判断是否满足第一范式( (属性的值域是否可以分解）属性的值域是否可以分解）4.4.判断是否满足第二范式判断是否满足第二范式( (非主属性对码的部分函数非主属性对码的部分函数依赖依赖) ) 5.5.判断是否满足第三范式判断

43、是否满足第三范式( (非主属性对码的传递函数非主属性对码的传递函数依赖依赖) ) 6.6.判断是否满足判断是否满足BCNFBCNF范式范式( (主属性对码的传递和部分主属性对码的传递和部分函数依赖函数依赖) )解：解：1. 关系关系r的候选码为：的候选码为：AB和和AC 练习练习1. 已知关系模式已知关系模式R U=A,B,C,D F=ABD, AC BD, BC在函数依赖范围内在函数依赖范围内该关系属于的最高范式是什么？该关系属于的最高范式是什么？2. 主属性为：主属性为：A、B、C 非主属性为：非主属性为：D3. 判断是否满足各个范式的要求判断是否满足各个范式的要求： 1) R的的所有的属

44、性值域都不可再分，则所有的属性值域都不可再分，则r 1NF。 2) 非主属性非主属性D不存在对任何码的部分函数依赖，则不存在对任何码的部分函数依赖，则r 2NF。 3) 非主属性非主属性D不存在对任何码的传递函数依赖不存在对任何码的传递函数依赖，则，则r 3NF。 4) 因为有函数依赖因为有函数依赖BC，而，而B不是关系不是关系R的码，则的码，则r不属于不属于BCNF。则：则： r 3NF 解：解：1. 关系关系r的候选码为：的候选码为：AC练习练习2. 已知关系模式已知关系模式R U=A,B,C,D,E,F F=AB, C DF, ACE, DF在函数依赖范围内在函数依赖范围内该关系属于的最

45、高范式是什么？该关系属于的最高范式是什么？2. 主属性为：主属性为：A、C 非主属性为：非主属性为：B、D、E、F3. 判断是否满足各个范式的要求：判断是否满足各个范式的要求： 1) R的的所有的属性值域都不可再分，则所有的属性值域都不可再分，则r 1NF。 2) 由于存在函数依赖由于存在函数依赖AB, C DF，而，而A A和和C C均不是关系的均不是关系的码，存在码，存在非主属性非主属性B、D、F对码的部分函数依赖，则对码的部分函数依赖，则r不属于不属于2NF。则：则： r 1NF 练习练习练习练习3.假设假设：某商业集团数据库中有一关系模式：某商业集团数据库中有一关系模式R R如下：如下

46、：R (R (商店编号，商品编号，数量，部门编号，负责人商店编号，商品编号，数量，部门编号，负责人) )如果规定如果规定： (1) (1) 每个商店的每种商品只在一个部门销售；每个商店的每种商品只在一个部门销售；(2) (2) 每个商店的每个部门只有一个负责人；每个商店的每个部门只有一个负责人；(3) (3) 每个商店的每种商品只有一个库存数量。每个商店的每种商品只有一个库存数量。试回答下列问题试回答下列问题：(1) (1) 根据上述规定，写出关系模式根据上述规定，写出关系模式R R的基本函数依赖；的基本函数依赖；(2) (2) 找出关系模式找出关系模式R R的候选码；的候选码；(3) (3)

47、 试问关系模式试问关系模式R R最高已经达到第几范式？为什么？最高已经达到第几范式？为什么？(4) (4) 如果如果R R不属于不属于3NF3NF，请将，请将R R分解成分解成3NF3NF模式集模式集 练习练习(1)(1)有三个函数依赖有三个函数依赖： ( (商店编号，商品编号商店编号，商品编号) ) 部门编号部门编号 ( (商店编号，部门编号商店编号，部门编号) ) 负责人负责人 ( (商店编号，商品编号商店编号，商品编号) ) 数量数量(2) R(2) R的的候选键候选键: (: (商店编号，商品编号商店编号，商品编号) )(3)(3)因为因为R R中存在着非主属性中存在着非主属性“负责人

48、负责人”对候选码对候选码 ( (商店编号、商品编号商店编号、商品编号) )的传递函数依赖，但无部的传递函数依赖，但无部分函数依赖，所以分函数依赖，所以R R属于属于2NF2NF，R R不属于不属于3NF3NF。(4) (4) 将将R R分解成：分解成： R1 (R1 (商店编号，商品编号，数量，部门编号商店编号，商品编号，数量，部门编号) ) R2 ( R2 (商店编号，部门编号，负责人商店编号，部门编号，负责人) ) 6.4Armstrong公理系统公理系统 函数依赖公理函数依赖公理 一套推理规则，是模式分解算法的理论基础。一套推理规则，是模式分解算法的理论基础。 用途：用途：（1 1）求函

49、数依赖集闭包、属性集闭包。）求函数依赖集闭包、属性集闭包。（2 2）求最小函数依赖集。）求最小函数依赖集。（3 3）求给定关系模式的候选码。）求给定关系模式的候选码。（4 4）模式分解。）模式分解。一、逻辑蕴含的定义一、逻辑蕴含的定义定义定义1: 设设F是关系模式是关系模式R 的一个函数依赖的一个函数依赖集，集，X,Y U,对对 r，XY都成立都成立, 则称则称F逻辑蕴逻辑蕴含含X Y。另一等价定义：设另一等价定义：设F是关系模式是关系模式R 的一个的一个函数依赖集，函数依赖集，X,Y U,若从若从F中的函数依赖可推中的函数依赖可推出出X Y, 则称则称F逻辑蕴含逻辑蕴含X Y。二、推理规则二

50、、推理规则设关系模式为设关系模式为R （1）A1自反律（自反律（Reflexivity）：）： 若若Y X U，则，则X Y为为F所蕴含。所蕴含。证明证明: 设设Y X U （仅需了解！（仅需了解！ ）R 的的 r中，对中，对 元组元组t，s：若若tX=sX，(1)Y X，则，则tY=sY，(2)由由(1),(2)可得可得XY成立，自反律得证。成立，自反律得证。注意注意：由自反律所得到的：由自反律所得到的函数依赖均是函数依赖均是平凡的函数平凡的函数依赖依赖，自反律的使用并不，自反律的使用并不依赖于依赖于F。如：如：(sno,sname)-sname（2）A2.增广律（增广律（Augmentat

51、ion）：）： 若若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ为为F所蕴含。所蕴含。证明：证明： （仅需了解！（仅需了解！ ）设设R 的的 r中，中， 元组元组t，s；若若tXZ=sXZ （1），），则有则有tX=sX和和tZ=sZ；（；（2）XY，则有，则有tY=sY，（，（3）由由(2),(3)可得：可得：tYZ=sYZ （4） 由由(1)，(4)可得，则可得，则XZYZ为为F所蕴含，所蕴含，增广律得证。增广律得证。如：如：sno-sname，sdeptU, U, 则则(sno,sdept)-(sname,sdept)(sno,sdept)-(sname,sdept)（3）A3.

52、传递律（传递律（Transitivity）：）： 若若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所所蕴含。蕴含。证明：设证明：设XY及及YZ为为F所蕴含。所蕴含。对对R 的的 r， 元组元组 t，s。若若tX=sX （1），），XY，则，则 tY=sY；又又YZ，则有，则有tZ=sZ （2），），由由(1),(2)可得：可得：XZ为为F所蕴含，传递律得所蕴含，传递律得证。证。如：如：sno-sdept，sdept-dname-dname可得：可得：sno-dnamesno-dname（4）由由Armstrong公理得到以下推论公理得到以下推论:1）、合并律：如果）、合并律：如果XY和和X

53、Z成立，则成立，则XYZ成立。成立。2）、伪传递律：如果）、伪传递律：如果XY和和WYZ成立，则成立，则WXZ成立。成立。3）、分解律：如果）、分解律：如果XY和和ZY成立，则成立，则XZ成立。成立。（5）根据合并规则和分解规则，可得的引理：）根据合并规则和分解规则，可得的引理： 引理引理1： XA1 A2Ak成立的充分必要条件是成立的充分必要条件是XAi （i=l，2，k）成立。）成立。若已知：若已知：sno-sname,sdept可得：可得：sno-sname, sno-sdeptsno-sname, sno-sdept若已知若已知sno-sname, sno-sdeptsno-sname

54、, sno-sdept可得：可得： sno-sname,sdept三、函数依赖闭包定义三、函数依赖闭包定义定义定义2：由被：由被F逻辑蕴涵的函数依赖的全体构成逻辑蕴涵的函数依赖的全体构成的集合，称为的集合，称为F的闭包的闭包，记作，记作F+。四、四、 Armstrong公理系统的有效性、完备性公理系统的有效性、完备性1、有效性：由、有效性：由F出发可由出发可由Armstrong公理推导公理推导出来的每一个函数依赖一定在出来的每一个函数依赖一定在F+中；中；2、完备性是指：、完备性是指：F+中的每一个函数依赖，必中的每一个函数依赖，必定可由定可由F根据根据Armstrong公理推导出来。公理推导

55、出来。6.4 函数依赖的公理系统函数依赖的公理系统 逻辑蕴含逻辑蕴含 定义定义6.13 对于满足一组函数依赖对于满足一组函数依赖 F 的关系模式的关系模式R ，其任何一个关系，其任何一个关系r，若函数依赖，若函数依赖XY都都成立，成立， 则称则称F逻辑蕴含逻辑蕴含X Y ，或称，或称X Y 为为F所所蕴含蕴含。即：对于即：对于r中任意两个元组中任意两个元组t和和s，有：若有：若 tX=sX 则则 tY=sY 必成立。必成立。 6.4.1 Armstong公理系统公理系统 Armstrong公理系统公理系统函数依赖的推理规则函数依赖的推理规则 关系模式关系模式R 有以下推理规则：有以下推理规则：

56、Al 自反律自反律：若：若Y X U，则，则X Y为为F所蕴含。所蕴含。A2 增广律增广律：若：若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ为为F所蕴含。所蕴含。A3 传递律传递律：若：若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所蕴含。所蕴含。注：由自反律所得到的函数依赖均是平凡的函数依赖，自反律注：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于的使用并不依赖于F。6.4.1 Armstong公理系统公理系统伪传递规则：伪传递规则：若若X Y，WY Z，则，则XW Z 。分解规则：分解规则：若若X Y及及 Z Y，则则X Z 。X Y增广律增广律X XYX

57、 Z增广律增广律XY YZ传递律传递律X YZ证明合并规则：证明合并规则： 由由Armstrong公理导出的推理规则公理导出的推理规则:合并规则：合并规则：若若X Y，X Z，则，则X YZ。6.4.2 闭包闭包 引理引理6.l 若若A1A2An是关系模式是关系模式R的属性集的属性集, 则：则：XA1 A2Ak XAi成立成立(i=l,2,k)。证明：充分性：由合并律证明：充分性：由合并律 必要性：由分解律必要性：由分解律 根据合并规则和分解规则，可得：根据合并规则和分解规则，可得：6.4.2 闭包闭包定义定义6.14 在关系模式在关系模式R中为中为F所逻辑蕴含的函数依赖所逻辑蕴含的函数依赖的

58、全体叫作的全体叫作 F的闭包的闭包，记为，记为F+。定义定义6.15 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U， XF+ = A|XA能由能由F 根据根据Armstrong公理导出公理导出，XF+称为称为属性集属性集X关于函数依赖集关于函数依赖集F 的闭包。的闭包。引理引理6.2 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U，XY能由能由F 根据根据Armstrong公理导出的充分必要条件是公理导出的充分必要条件是Y XF+用途：将判定用途：将判定XY是否能由是否能由F根据根据Armstrong公理导出的问公理导出的问题，转化为求出题，转化为

59、求出XF+ ，判定，判定Y是否为是否为XF+的子集的问题。的子集的问题。6.4.2 闭包闭包算法算法6.l 求属性集求属性集X（X U）关于）关于U上的函数依赖集上的函数依赖集F 的闭包的闭包XF+ 输入：输入：X，F输出：输出：XF+步骤：步骤：（1）令）令X（0）=X，i=0（2）求）求B：B = A |( V)( W)(VW F V 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=i+l，返回第（，返回第（2

60、）步。）步。例：例： 已知关系模式已知关系模式R，其中，其中U=A，B，C，D，EF=ABC，BD，CE，ECB，ACB求（求（AB）F+ 。解：解： (1) 设设X（0）=AB； (2) 计算计算X（1）: 逐一扫描逐一扫描F集合中各个函数依赖，找左部为集合中各个函数依赖，找左部为A，B或或AB的函数依赖。的函数依赖。 得到两个：得到两个：ABC，BD。 (3) X（1）=ABCD=ABCD。 (4) X（0） X（1） 则需再找出左部为则需再找出左部为ABCD子集的那些函数依赖，又得到子集的那些函数依赖，又得到ABC，BD， CE，ACB 于是：于是：X（2）=X（1）BCDE=ABCDE