数据库原理课件--06_关系数据理论.ppt

1、1,数据库系统概论 An Introduction to Database System 第六章 关系数据理论,2,第六章 关系数据理论,6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 *6.4 模式的分解 6.5 小结,3,6.1 问题的提出,关系数据库逻辑设计 针对具体问题，如何构造一个适合于它的数据模式。 数据库逻辑设计的工具关系数据库的规范化理论。 数据依赖 范式 模式设计方法,4,一、概念回顾,关系模式的形式化定义 关系模式由五部分组成，即它是一个五元组： R(U, D, DOM, F) R： 关系名 U： 组成该关系的属性名集合 D： 属性组U中属性所来自的域 DO

2、M： 属性向域的映象集合 F： 属性间数据的依赖关系集合,返回,5,二、关系模式的简化表示,关系模式R（U, D, DOM, F） 简化为一个三元组： R（U, F） 当且仅当U上的一个关系r 满足F时，r称为关系模式 R（U, F）的一个关系,返回,6,三、什么是数据依赖,1. 数据依赖 是现实世界属性间相互联系的抽象 是通过一个关系中属性间值的相等与否体现出来 是数据内在的性质 是语义的体现 2. 数据依赖的类型 函数依赖（Functional Dependency，简记为FD） 多值依赖（Multivalued Dependency，简记为MVD） 其他,7,四、数据依赖对关系模式的影响

3、,例：描述学校的数据库： 学生的学号（Sno）、所在系（Sdept） 系主任姓名（Mname）、课程名（Cname） 成绩（Grade） 单一的关系模式 ： Student U Sno, Sdept, Mname, Cname, Grade ,8,数据依赖对关系模式的影响（续）,学校数据库的语义： 一个系有若干学生， 一个学生只属于一个系； 一个系只有一名主任； 一个学生可以选修多门课程， 每门课程有若干学生选修； 每个学生所学的每门课程都有一个成绩。,9,数据依赖对关系模式的影响（续）,属性组U上的一组函数依赖F： F Sno Sdept, Sdept Mname, (Sno, Cname)

4、 Grade ,10,在此关系模式中填入一部分具体的数据，则可得到student关系模式的实例，即一个教学管理数据库，如下表SCD所示。,11,关系模式Student中存在的问题, 数据冗余太大 更新异常（Update Anomalies） 插入异常（Insertion Anomalies） 删除异常（Deletion Anomalies）,12,数据依赖对关系模式的影响（续）,结论： Student关系模式不是一个好的模式。 “好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。 原因：产生上述问题的原因，直观地说，是因为关系中“包罗万象”，内容太杂了。实际上是由存在于模式

5、中的某些数据依赖引起的。 解决方法：通过分解关系模式来消除其中不合适的数据依赖。,13,我们把关系模式student分解为下面三个结构简单的关系模式，如图6.2所示。 学生关系S(Sno,Sname,Sdept ) 选课关系SC(Sno, Cname, Grade ) 系关系D(Sdept, Mname),14,图6.2 分解后的关系模式,15,6.2 规范化,6.2.1 函数依赖 6.2.2 码 6.2.3 范式 6.2.4 2NF 6.2.5 3NF 6.2.6 BCNF 6.2.7 多值依赖 6.2.8 4NF 6.2.9 规范化小结,返回,16,6.2.1 函数依赖,一、函数依赖 二、

6、平凡函数依赖与非平凡函数依赖 三、完全函数依赖与部分函数依赖 四、传递函数依赖,返回,17,一、函数依赖,定义6.1 设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等， 而在Y上的属性值不等， 则称 “X函数确定Y” 或 “Y函数依赖于X”，记作XY。我们称X为决定因素，Y为依赖因素。 Y=f(X),18,AB BA,T1,T2,T3,练习：请给出下列三个关系中A与B的函数依赖关系,AB BA,AB BA,19,说明,1. 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要

7、满足的约束条件，函数依赖是数据依赖的一种，也是特殊的完整性约束。 2. 函数依赖是语义范畴的概念。只能根据语义来确定一个函数依赖，而不能按照其形式化定义来证明一个函数依赖是否成立。,20,3. 数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在， 则拒绝装入该元组。,21,4函数依赖与属性之间的联系类型有关。 （1）在一个关系模式中，如果属性X与Y有1:1联系时，则存在函数依赖XY，YX，即XY。 例如，当学生无重名时，SNOSname。 （2）如果属性X与Y有1:m的联系时，则只存在函数依赖YX。

8、 例如，Sage，Sdept与SNO之间均为1:m联系，所以有SNOSage ，SNOSdept 。,22,（3）如果属性X与Y有m: n的联系时，则X与Y之间不存在任何函数依赖关系。 例如，一个学生可以选修多门课程，一门课程又可以为多个学生选修，所以SNO与CNO之间不存在函数依赖关系。 由于函数依赖与属性之间的联系类型有关，所以在确定属性间的函数依赖关系时，可以从分析属性间的联系类型入手，便可确定属性间的函数依赖。,23,练习：设关系模式R（ABCD），在R的关系中，属性值间有如下的联系：A值与B值有一对多联系，即每个A值有多个B值与之联系，而每个B值只有一个A值与之联系；C值与D值之间有

9、一对一联系。试根据这些规则写出相应的函数依赖。,解：因为A值与B值有一对多联系，故可写出函数依赖B A； 因为C值与D值有一对一联系，故可写出两个函数依赖CD和D C。,24,5函数依赖关系的存在与时间无关 当关系中的元组增加、删除或更新后都不能破坏这种函数依赖。 所以函数依赖关系的存在与时间无关，而只与数据之间的语义规定有关。,25,函数依赖（续）,例: Student(Sno, Sname, Ssex, Sage, Sdept) 假设不允许重名，则有: Sno Ssex，Sno Sage , Sno Sdept， SnoSname, Sname Ssex， Sname Sage Sname

10、 Sdept 但Ssex Sage 若XY，并且YX, 则记为XY。 若Y不函数依赖于X, 则记为XY。,返回,26,二、平凡函数依赖与非平凡函数依赖,在关系模式R(U)中，对于U的子集X和Y， 如果XY，但Y X，则称XY是非平凡的函数依赖 若XY，但Y X, 则称XY是平凡的函数依赖 例：在关系SC(Sno, Cno, Grade)中， 非平凡函数依赖： (Sno, Cno) Grade 平凡函数依赖： (Sno, Cno) Sno (Sno, Cno) Cno,27,平凡函数依赖与非平凡函数依赖（续）,对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明， 我

11、们总是讨论非平凡函数依赖。,返回,28,三、完全函数依赖与部分函数依赖,定义6.2 在关系模式R(U)中，如果XY，并且对于X的任何一个真子集X，都有X Y, 则称Y完全函数依赖于X，记作X F Y。 若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作X P Y。,29,完全函数依赖与部分函数依赖（续）,例: 在关系SC(Sno, Cno, Grade)中， 由于：Sno Grade，Cno Grade， 因此：(Sno, Cno) F Grade,30,完全函数依赖与部分函数依赖（续）,只有当决定因素是组合属性时，讨论部分函数依赖才有意义，当决定因素是单属性时，只能是完全函数依赖。

12、 例：关系模式S（SNO，SName，Sage，Sdept） 决定因素为单属性SNO， SNO（SName，Sage，Sdept ），则不存在部分函数依赖。,返回,31,四、传递函数依赖,定义6.3 在关系模式R(U)中，如果XY，YZ，且Y X，YX，则称Z传递函数依赖于X。 注: 如果YX， 即XY，则Z直接函数依赖于X。 第一节例 3NF,32,函数依赖（续）,综上所述，函数依赖分为完全函数依赖、部分函数依赖和传递函数依赖三类，它们是规范化理论的依据和规范化程度的准则，数据库的规范设计将以这些概念为基础来进行。,返回,33,6.2.2 码,定义6.4 设K为关系模式R中的属性或属性组合。

13、若K F U，则K称为R的一个侯选码（Candidate Key）。若关系模式R有多个候选码，则选定其中的一个做为主码（Primary key）。 主属性与非主属性 ALL KEY,34,全码举例,一个教师可以讲授多门课程，一门课程可以为多个教师讲授 同样一个学生可以选听多门课程，一门课程可以为多个学生选听 (T,C,S)三个属性的组合是主码，T、C、S都是主属性，而无非主属性。,35,外部码,定义6.5 关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R 的外部码（Foreign key）也称外码。 主码和外部码一起提供了表示关系间联系的手段。,返回,36,6.2.3

14、 范式,把关系数据库规范化过程中为不同程度的规范化要求设立的不同标准称为范式（Normal Form），它是符合某一种级别的关系模式的集合。每种范式都规定了一些限制约束条件。 由于规范化的程度不同，就产生了不同的范式。 满足最基本规范化要求的关系模式叫第一范式， 在第一范式中进一步满足一些要求为第二范式， 依此类推就产生了第三范式、BC范式、第四范式以及第五范式概念。,37,范式(续),各种范式之间存在联系： 如下图所示：,38,1NF （First Normal Form）,在关系模式R中的每一个具体关系r中，如果每个属性值都是不可再分的最小数据单位，则称R是第一范式的模式。 职工号、姓名、

15、电话号码组成一个表（一个人可能有一个办公室电话 和一个家里电话号码） 规范成为1NF有三种方法：,39,原表,法1,法2,法3,40,6.2.4 2NF,第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。 但是满足第一范式的关系模式并不一定是一个好的关系模式。,41,2NF(续),例: 关系模式SLC(Sno, Sdept, Sloc, Cno, Grade) Sloc为学生住处，假设每个系的学生住在同一个地方。 函数依赖包括： (Sno, Cno) F Grade Sno Sdept (Sno, Cno) P Sdept Sno Sloc (Sno, Cno)

16、 P Sloc Sdept Sloc,42,2NF (续),SLC的码为(Sno, Cno) SLC满足第一范式。 非主属性Sdept和Sloc部分函数依赖于码(Sno, Cno),43,SLC不是一个好的关系模式,关系模式SLC(Sno, Sdept, Sloc, Cno, Grade) (1) 插入异常 假设Sno95102，SdeptIS，SlocN的学生还未选课，因课程号是主属性，因此该学生的信息无法插入SLC。 (2) 删除异常 假定某个学生本来只选修了3号课程这一门课。现在因身体不适，他连3号课程也不选修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。,44,SLC

17、不是一个好的关系模式(续),关系模式SLC(Sno, Sdept, Sloc, Cno, Grade) (3) 数据冗余度大 如果一个学生选修了10门课程，那么他的Sdept和Sloc值就要重复存储了10次。 (4) 修改复杂 例如学生转系，在修改此学生元组的Sdept值的同时，还可能需要修改住处（Sloc）。如果这个学生选修了K门课，则必须无遗漏地修改K个元组中全部Sdept、Sloc信息。,45,2NF (续),原因 非主属性Sdept、 Sloc部分函数依赖于码。 解决方法 SLC分解为两个关系模式，以消除这些部分函数依赖 SC（Sno， Cno， Grade） SL（Sno， Sdep

18、t， Sloc）,46,2NF (续),函数依赖图：,47,2NF的定义(续),定义6.6 若关系模式R1NF，并且每一个非主属性都完全函数依赖于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,48,第二范式（续）,采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。,49,算

19、法：将关系模式R分解成2NF模式集,设有关系模式R（U），主码是W，R上还存在FD XZ，其中Z是非主属性，XW，则X Z就是一个部分依赖。此时应把R分解成两个模式： R1（XZ），主键是X； R2（Y），其中Y=U-Z，主键仍是W，外键是X（参考R1）。 利用外码和主码的连接可以从R1和R2重新得到R。 如果R1和R2还不是2NF，则重复上述过程，一直到数据库模式中每一个关系模式都是2NF为止。,50,第二范式（续）,经以上分析，可以得到两个结论： 1从1NF关系中消除非主属性对码的部分函数依赖，则可得到2NF关系。 2如果R的码为单属性，或R的全体属性均为主属性，则R2NF。,返回,51,

20、6.2.5 3NF,将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。 例：2NF关系模式SL(Sno, Sdept, Sloc)中有如下函数依赖： SnoSdept SdeptSloc SnoSloc Sloc传递函数依赖于Sno，即SL中存在非主属性对码的传递函数依赖。,52,3NF的定义,定义6.7 关系模式R 中若不存在这样的码X、属性组Y及非主属性Z（Z Y）, 使得XY，Y X，YZ，成立，则称R 3NF。 也即：如果关系模式R是1NF，且每个非主属性都不传递依赖于码，那么称R是第三范式的模式。如果数据库模式中每个关系模式都是3NF，则称其为

21、3NF的数据库模式。,53,3NF (续),解决方法 采用投影分解法，把SL分解为两个关系模式，以消除传递函数依赖： SD（Sno， Sdept） DL（Sdept， Sloc） SD的码为Sno， DL的码为Sdept。,54,例如： SL(Sno, Sdept, Sloc) 2NF SL(Sno, Sdept, Sloc) 3NF SD（Sno， Sdept） 3NF DL（Sdept， Sloc） 3NF,55,算法：将关系模式R分解成3NF模式集,设关系模式R (U)，主码是W，R上还存在FD XZ，其中Z是非主属性，ZX且X不是候选码，这样WZ就是一个传递依赖。此时应把R分解成两个模

22、式： R1(XZ)，主键是X； R2(Y)，其中Y=U-Z，主键仍是W，外键是X（参考R1）。 利用外码和主码相匹配机制，R1和R2通过连接可以重新得到R。 如果R1和R2还不是3NF，则重复上述过程，一直到数据库模式中每一个关系模式都是3NF为止。,返回,56,3NF(续),若R3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。 如果R3NF，则R也是2NF。,57,6.2.6 BC范式（BCNF）,定义6.8 设关系模式R1NF，如果对于R的每个函数依赖XY，且Y不属于X，则X必含有候选码，那么RBCNF。 也即，关系模式R中，若每一个决定因素都包含码，则R B

23、CNF。,58,BCNF的关系模式所具有的性质, 所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非码的任何一组属性,59,BCNF (续),例：在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。 每一教师只教一门课，每门课由若干教师教；某一学生选定某门课就确定了一个固定的教师，某个学生选修某个教师的课就确定了所选课的名称。则有如下函数依赖：,(S，J)T，(S，T)J，TJ,60,BCNF (续),STJ3NF (S，J)和(S，T)都可以作为候选码 S、T、J都是主属性 STJBCNF TJ，T是决定属性

24、集，T不是候选码,61,对于STJ，（S，J）和（S，T）都是候选键，两个候选键相交，有公共的属性S。 STJ中不存在非主属性，也就不可能存在非主属性对键的部分依赖或传递依赖，所以STJ 3NF。 但从STJ的一个关系实例分析，仍存在一些问题。,关系STJ,62,1数据冗余。虽然每个教师只开一门课，但每个选修该教师所开课程的学生元组都要记录这一信息。 2插入异常。当某门课程本学期不开，自然就没有学生选修。没有学生选修，因为主属性不能为空，教师上该门课程的信息就无法插入。同样原因，学生刚入校,尚未选课，有关信息也不能输入。 3删除异常。如果选修某门课程的学生全部毕业，删除学生记录的同时,随之也删

25、除了教师开设该门课程的信息。 4更新异常。当某个教师开设的某门课程改名后，所有选修该教师该门课程的学生元组都要进行修改，如果漏改某个数据，则破坏了数据的完整性。,63,BCNF(续),解决方法：将STJ分解为二个关系模式： ST(S，T) BCNF， TJ(T，J) BCNF 没有任何属性对码的部分函数依赖和传递函数依赖,64,关系模式STJ由规范到BCNF后，使原来存在的四个异常问题得到解决。 1数据冗余降低。每个教师开设课程的信息只在TJ关系中存储一次。 2不存在插入异常。对于所开课程尚未有学生选修的教师信息可以直接存储在关系TJ中，而对于尚未选修课程的学生可以存储在关系ST中。 3不存在

26、删除异常。如果选修某门课程的学生全部毕业，可以只删除关系ST中的相关学生记录，而不影响系关系TJ中相应教师开设该门课程的信息。 4不存在更新异常。当某教师开设的某门课程改名后，只需修改关系TJ中的一个相应元组即可，不会破坏数据完整性。,65,BC范式（续）,若RBCNF 每一个决定属性集（因素）都包含（候选）码 R中的所有属性（主，非主属性）都完全函数依赖于码 R3NF（证明） 若R3NF，则 R不一定BCNF,66,命题：若RBCNF，则R3NF 证明：设R是BCNF，但不是3NF，那么R上必存在传递依赖XY，YA，这里X是R的键，AY，YX。显然Y不包含R的键；否则，YX也成立。因此YA违

27、反了BCNF的定义，与假设R是BCNF矛盾，从而定理得证。,BC范式（续）,67,BC范式（续）,如果R3NF，则R不一定是BCNF。 设关系模式SNC（SNO，SName，CNO，SCORE），假设没有重名。SNC有两个候选键（SNO，CNO）和（SName ，CNO）其函数依赖如下： SNO SName （SNO，CNO）SCORE （SName ，CNO）SCORE。 唯一的非主属性SCORE对键不存在部分函数依赖，也不存在传递函数依赖。所以SNC3NF。,68,但是，因为SNOSName，即决定因素SNO不包含候选键，从另一个角度说，存在着主属性对键的部分函数依赖：（SNO，CNO）F

28、 SName，（SName，CNO） F SNO，所以SNC不是BCNF。 正是存在着这种主属性对键的部分函数依赖关系，造成了关系SNC中存在着较大的数据冗余，学生姓名的存储次数等于该生所选的课程数。从而会引起修改异常。 比如，当要更改某个学生的姓名时，则必须搜索出现该姓名的每个学生记录，并对其姓名逐一修改，这样容易造成数据的不一致问题。 解决这一问题的办法仍然是通过投影分解进一步提高SNC的范式等级，将SNC规范到BCNF。,BC范式（续）,69,例：将SNC(SNO,SName,CNO，SCORE)规范到BCNF。 分析SNC数据冗余的原因，是因为在这一个关系中存在两个实体，一个为学生实体

29、，属性有SNO、SName；另一个是选课实体，属性有SNO、CNO和SCORE。 我们可以将SNC分解成如下两个关系： S1(SNO,SName)，描述学生实体； S2(SNO,CNO,SCORE)，描述学生与课程的联系。 对于S1，有两个候选键SNO和SName， 对于S2，主键为（SNO，CNO）。 在这两个关系中，无论主属性还是非主属性都不存在对键的部分依赖和传递依赖，S1BCNF，S2BCNF。,70,分解后，S1和S2的函数依赖分别如图a和b所示。,关系SNC转换成BCNF后，数据冗余度明显降低。 学生姓名只在关系S1中存储一次，学生要改名时，只需改动一条学生记录中的相应的SName

30、值，从而不会发生修改异常。,71,BCNF (续),如果一个关系数据库中所有关系模式都属于3NF，则已在很大程度上消除了插入异常和删除异常，但由于可能存在主属性对候选键的部分依赖和传递依赖，因此关系模式的分离仍不够彻底。 如果一个关系数据库中所有关系模式都属于BCNF，那么在函数依赖的范畴内，已经实现了模式的彻底分解，消除了产生插入异常和删除异常的根源，而且数据冗余也减少到极小程度。,返回,72,6.2.7 多值依赖,例：学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。则关系模式Teaching(C, T, B)。,用二维表表示Teaching,74,多值依赖,TeachingBCN

31、F: Teaching具有唯一候选码(C，T，B)， 即全码 Teaching模式中存在的问题 (1)数据冗余度大：有多少名任课教师，参考书就要存储多少次,75,多值依赖（续）,(2)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组 例如物理课增加一名教师刘关，需要插入三个元组： （物理，刘关，普通物理学） （物理，刘关，光学原理） （物理，刘关，物理习题集）,76,多值依赖（续）,(3) 删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组 (4) 修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元

32、组 产生原因 存在多值依赖,77,多值依赖的定义,定义6.9 设R(U)是一个属性集U上的一个关系模式， X、Y和Z是U的子集，并且ZUXY，多值依赖 XY成立当且仅当对R的任一关系r，r在（X，Z）上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关。 例：Teaching（C, T, B） 对于C的每一个值，T有一组值与之对应，而不论B取何值,X,Y,Z,78,多值依赖的另一个等价的形式化定义,设R(U)是一个属性集U上的一个关系模式， X、Y和Z是U的子集，并且ZUXY，在R（U）的任一关系r中，如果存在元组（x， y1，z1）和（x ，y2，z2），就也存在元组（x， y1，z2

33、）和（x ，y2，z1），那么就称多值依赖 XY成立 XYZ t x y1 z2 s x y2 z1 w x y1 z1 v x y2 z2,79,多值依赖（续）,平凡多值依赖和非平凡的多值依赖 若XY，而Z，则称 XY为平凡的多值依赖 否则称XY为非平凡的多值依赖,80,6.2.8 第四范式（4NF）,定义6.10 关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y X），X都含有候选码，则R4NF。 不允许有非平凡多值依赖（非函数依赖） 允许函数依赖（是非平凡多值依赖的特例） 允许平凡的多值依赖 如果R 4NF， 则R BCNF,81,采用反证法，设R4NF，如果R BCNF，则 存

34、在XA,A不是X的真子集，且X不包含码 因为XA，则X A 由知道R中除了X，A外还有其他属性 由此X A是非平凡的，因此R4NF，与题设矛盾。 由此4NFBCNF,82,第四范式（续）,例： Teach(C,T,B) 4NF 存在非平凡的多值依赖CT，且C不是候选码 用投影分解法把Teach分解为如下两个关系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依赖,83,第四范式（续）,如果只考虑函数依赖，则属于BCNF的关系模式规范化程度已经是最高的了。 如果考虑多值依赖，则属于4NF的关系模式规范化程度是最高的。 数据依赖中除了最重要的函数依赖和多值依赖外，

35、还有其他数据依赖，如连接依赖。 函数依赖是多值依赖的一种特殊情况，而多值依赖实际上又是连接依赖的一种特殊情况。但连接依赖不像函数依赖和多值依赖可由语义直接导出，而是在关系的连接运算时才反映出来。,返回,84,6.2.9 规范化小结,关系数据库的规范化理论是数据库逻辑设计的工具。 一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。 规范化程度可以有多个不同的级别。,85,规范化（续）,规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题。 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式

36、集合，这种过程就叫关系模式的规范化。,86,规范化（续）,关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖 消除决定因素 2NF 非码的非平凡 消除非主属性对码的传递函数依赖 函数依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NF,87,规范化的基本思想,消除不合适的数据依赖。 各关系模式达到某种程度的“分离”。 采用“一事一地”的模式设计原则。 让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去。 所谓规范化实质上是概念的单一化。,88,规范化（续）,不能说规范化程度越高的关系模式就越好。

37、在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式。,89,规范化（续）,对于那些只要求查询而不要求插入、删除等操作的系统，几种异常现象的存在并不影响数据库的操作。这时便不宜过度分解，否则当要对整体查询时，需要更多的多表连接操作，这有可能得不偿失。 上面的规范化步骤可以在其中任何一步终止 在实际应用中，最有价值的是3NF和BCNF，在进行关系模式的设计时，通常分解到3NF就足够了,90,练习题,1.关系数据库规范化是为解决关系数据库中（ ）问题而引入的。 A、插入异常、删除异常和数据冗余 B、提高查询速度 C、减少数据操作的复杂性

38、 D、保证数据的安全性和完整性 2.假设关系模式R（U，F）属于3NF，下列说法中（ ）是正确的。 A、它一定消除了插入和删除异常 B、仍存在一定的插入和删除异常 C、一定属于BCNFD、A和C都是,A,B,91,练习题(续),3.关系模式的候选码可以有1个或多个，而主码有（ ）。 A.多个 B.0个 C.1个 D.1个或多个 4.已知关系模式R（A，B，C，D，E）及其上的函数依赖集合FAD，BC ，EA ，该关系模式 的候选码是（ ）。 A.AB B.BE C.CD D.DE,C,B,92,练习题(续),5.关系模型中的关系模式至少是（ ）。 A、1NFB、2NFC、3NFD、BCNF 6

39、.关系模式中，满足2NF的模式（ ）。 A、可能是1NFB、必定是1NF C、必定是3NFD、必定是BCNF 7.消除了部分函数依赖的1NF的关系模式必定是（ ）。 A、1NFB、2NFC、3NFD、4NF,A,B,B,93,练习题（续）,8.有关系模式学生（学号，课程号，名次），若每一名学生每门课程有一定的名次，每门课程每一名次只有一名学生，则以下叙述中错误的是（ ）。 A、（学号，课程号）和（课程号，名次）都可以作为候选码 B、只有（学号，课程号）能作为候选码 C、关系模式属于3NF D、关系模式属于BCNF 9.在关系数据库中，任何二元关系模式的最高范式必定是( )。 A、1NFB、2N

40、FC、3NFD、BCNF,D,B,解：该关系有两个候选码，所有的属性都是主属性，所以属于3NF；同时该关系上的两个函数依赖的左部都包含了该关系的候选码，所以也属于BCNF。,94,补充作业题,设有关系模式：订购(客户名，住址，联系电话，书号，书名，作者，出版社，社址)，其中F=客户名住址，客户名联系电话，书号书名，书号作者，书号出版社，出版社社址。求本关系模式的关键码，判断其为第几范式，如何将它规范化为符合BCNF的关系？,返回,95,6.3 数据依赖的公理系统,关系的规范化 将结构复杂的关系分解成结构简单的关系 把低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合 数

41、据依赖的公理系统是模式分解算法的理论基础。,96,数据依赖的公理系统（续）,逻辑蕴含 定义6.11 对于满足一组函数依赖 F 的关系模式R ，其任何一个关系r，若函数依赖XY都成立（即r中任意两元组t、s，若tX=sX，则tY=sY）， 则称：F逻辑蕴含XY,97,Armstrong公理系统,对关系模式R 来说有以下的推理规则： Al.自反律（Reflexivity）： 若Y X U，则X Y为F所蕴含。 A2.增广律（Augmentation）：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。 A3.传递律（Transitivity）：若XY及YZ为F所蕴含，则XZ为F所蕴含。 注意：由自

42、反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F,98,定理 6.l Armstrong推理规则是正确的,（l）自反律：若Y X U，则X Y为F所蕴含 证： 设Y X U 对R 的任一关系r中的任意两个元组t，s： 若tX=sX，由于Y X，有tY=sY， 所以XY成立。自反律得证 注： 由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F,99,定理 6.l Armstrong推理规则是正确的,(2)增广律: 若XY为F所蕴含，且Z U，则XZYZ 为F所蕴含。 证：设XY为F所蕴含，且Z U。 设R 的任一关系r中任意的两个元组t，s； 若tXZ=sXZ，

43、则有tX=sX和tZ=sZ； 由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ为F所蕴含。增广律得证。,100,定理 6.l Armstrong推理规则是正确的,(3) 传递律：若XY及YZ为F所蕴含，则XZ为 F所蕴含。 证：设XY及YZ为F所蕴含。 对R 的任一关系 r中的任意两个元组 t，s。 若tX=sX，由于XY，有 tY=sY； 再由YZ，有tZ=sZ，所以XZ为F所蕴含。 传递律得证。,101,2. 导出规则,根据A1，A2，A3这三条推理规则可以得到下面三条推理规则： 合并规则：由XY，XZ，有XYZ。 （A2， A3） 伪传递规则：由XY，WYZ，有XWZ。 （A2

44、， A3） 分解规则：由XY及 ZY，有XZ。 （A1， A3）,102,导出规则（续）,根据合并规则和分解规则，可得引理6.1 引理6.l XA1 A2Ak成立的充分必要条件是XAi成立（i=l，2，k）。,103,3. 函数依赖闭包,定义6.l2 在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。 定义6.13 设F为属性集U上的一组函数依赖，X U， XF+ = A|XA能由F 根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 的闭包,104,F的闭包,例：已知关系模式R（XYZ），F=XY，YZ，求F+。 解： F+= , X,Y,Z,XY, XZ

45、, YZ,XYX, XX, YY, ZZ, XYX, XZX, YZY, XYZX, XY, YZ, XYY, XZY, YZZ, XYZY, XZ, YYZ, XYZ, XZZ, YZYZ,XYZZ, XXY, XYXY,XZXY, XYZXY, XXZ, XYYZ,XZXZ, XYZYZ, XYZ, XYXZ,XZYZ, XYZXZ, XXYZ, XYXYZ,XZXYZ, XYZXYZ F+计算是NP完全问题。 根据规则A1可推出X(表示空属性集),105,关于闭包的引理,引理6.2 设F为属性集U上的一组函数依赖，X，Y U，XY能由F 根据Armstrong公理导出的充分必要条件是Y

46、XF+ 用途 将判定XY是否能由F根据Armstrong公理导出的问题，转化为求出XF+ ，判定Y是否为XF+的子集的问题。,106,求闭包的算法,算法6.l 求属性集X（X U）关于U上的函数依赖集F 的闭包XF+ 输入：X，F 输出：XF+ 步骤： （1）令X（0）=X，i=0 （2）求B，这里B = A |( V)( W)(VWF V X（i）AW)； （3）X（i+1）=BX（i）,107,算法6.l(续),（4）判断X（i+1）= X （i）吗? （5）若相等或X（i）=U , 则X（i）就是XF+ , 算法终止。 （6）若否，则 i=i+l，返回第（2）步。 对于算法6.l，令ai

47、 =|X（i）|，ai 形成一个步长大于1的严格递增的序列，序列的上界是 | U |，因此该算法最多 |U| - |X| 次循环就会终止。,108,函数依赖闭包(续),例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。,109,函数依赖闭包(续),(2)因为X（0） X（1） ，所以再找出左部为ABCD子集的那些函数依赖，又得到ABC，BD， CE，ACB，

48、于是X（2）=X（1）BCDE=ABCDE。 (3)因为X（2）=U，算法终止 所以（AB）F+ =ABCDE。,110,4. Armstrong公理系统的有效性与完备性,建立公理系统体系目的：从已知的 f 推导出未知的f 明确：1.公理系统推导出来的 f 正确？ 2. F+中的每一个 f 都能推导出来？,111,4. Armstrong公理系统的有效性与完备性,有效性：由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F+中/* Armstrong正确 完备性：F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来 /* Armstrong公理够用，完全 完

49、备性：所有不能用Armstrong公理推导出来f, 都不为真；若 f 不能用Armstrong公理推导出来， f F+,112,有效性与完备性的证明,证明： 1. 有效性 可由定理5.l得证 2. 完备性 只需证明逆否命题: 若函数依赖XY不能由F从Armstrong公理导出，那么它必然不为F所蕴含 分三步证明：,113,有效性与完备性的证明(续),(1)引理: 若VW成立，且V XF+，则W XF+ 证 因为 V XF+ ，所以有XV成立； 因为X V，VW，于是XW成立 所以W XF+ (2)/* 存在关系r， F+中的全部函数依赖在 r上成立，即使r是R（U，F）的一个关系。 构造一张二

50、维表r，它由下列两个元组构成，可以证明r必是R（U，F）的一个关系，即F+中的全部函数依赖在 r上成立。,114,Armstrong公理系统的有效性与完备性(续),XF+ U-XF+ 11.1 00.0 11.1 11.1 若r不是R 的关系，则必由于F中有函数依赖VW在r上不成立所致。 由r的构成可知，V必定是XF+ 的子集，而W不是XF+ 的子集; 可是由第（1）步，W XF+，矛盾。所以r必是R的一个关系。,115,Armstrong公理系统的有效性与完备性(续),(3) )/* f： XY 不能用Armstrong公理推导出来， f 在r上不成立。 若XY 不能由F从Armstrong

51、公理导出，则Y 不是 XF+ 的子集。（引理5.2） 因此必有Y 的子集Y 满足 Y U-XF+， 则XY在 r 中不成立，即XY必不为 R 蕴含 /* 因为 F+中的全部函数依赖在 r上成立。,116,5. 函数依赖集等价,定义6.14 如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。,117,函数依赖集等价的充要条件,引理6.3 F+ = G+ 的充分必要条件是F G+ ，和G F+ 证: 必要性显然，只证充分性。 （1）若FG+ ，则XF+ XG+ 。 （2）任取XYF+ 则有 Y XF+ XG+ 。 所以XY (G+）+= G+。即F+ G+。 （

52、3）同理可证G+ F+ ，所以F+ = G+。,118,6. 最小依赖集,定义6.15 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖XA，使得F与 F-XA等价。 (3) F中不存在这样的函数依赖XA，X有真子集Z使得F-XAZA与F等价。,119,最小依赖集(续),例2 对于6.l节中的关系模式S，其中： U= SNO，SDEPT，MN，CNAME，G ， F= SNOSDEPT，SDEPTMN， （SNO，CNAME）G 设F =SNOSDEPT，SNOMN， SDE

53、PTMN，(SNO，CNAME)G， (SNO，SDEPT)SDEPT F是最小覆盖，而F 不是。 因为：F -SNOMN与F 等价 F -(SNO，SDEPT)SDEPT也与F 等价,120,7. 极小化过程,定理6.3 每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集 证：构造性证明，依据定义分三步对F进行“极小化处理”，找出F的一个最小依赖集。 (1)逐一检查F中各函数依赖FDi：XY，若Y=A1A2 Ak，k 2，则用 XAj |j=1，2， k 来取代XY。 引理6.1保证了F变换前后的等价性。,121,极小化过程(续),(2)逐一检查F中各函数依赖FDi：

54、XA， 令G=F-XA，若AXG+， 则从F中去掉此函数依赖。 由于F与G =F-XA等价的充要条件是AXG+，因此F变换前后是等价的。,122,极小化过程(续),(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变换前后是等价的。,123,极小化过程(续),例3 F = AB，BA，BC， AC，CA Fm1、Fm2都是F的最小依赖集： Fm1= AB，BC，CA Fm2= AB，BA，AC，CA F的最小依赖集Fm不一

55、定是唯一的，它与对各函数依赖FDi 及XA中X各属性的处置顺序有关,124,极小化过程（例）,设有关系模式R（U，F），其中：U=E，F，G，H，F=EG，GE，FEG，HEG，FHE，求F的最小依赖集。 解： 将F中右部属性单一化： F1= EG，GE，FE，FG，HE，HG，FHE 去掉左部冗余的属性。对于FHE，由于有FE，则为多余的。故， F2= EG，GE，FE，FG，HE，HG 去掉冗余的函数依赖。F2中的FE和FG分别与EG 和GE结合可得到对方，故应舍弃一个，同理HE和HG中也应舍弃一个，则： F3= EG，GE，FG，HG,返回,125,6.4 模式的分解,把低一级的关系模式分解为若干个高一级的