理论课数据库chapter04

1、上一章回顾,主要内容 SQL的数据定义 SQL的数据查询 SQL的数据更新 SQL的视图,1,上一章回顾,SQL的功能有哪些？ 数据定义 数据查询 数据操纵 数据控制 表达SQL功能的九个动词？ 数据定义：CREATE, DROP, ALTER 数据查询：SELECT 数据操纵：INSERT, DELETE, UPDATE 数据控制：GRANT, REVOKE,2,上一章回顾数据定义,用SQL语句创建一个学生表，包含学号、姓名两个属性，学号为主码，姓名要非空。,3,CREATE TABLE student( sno NUMERIC(6) , sname VARCHAR(8) NOT NULL,

2、 PRIMARY KEY(sno) );,增加两个属性列年龄和性别,ALTER TABLE student ADD (age INT, sex CHAR(2) );,上一章回顾数据定义,修改学生中性别列长度改为8。,4,删除学生表中性别列,ALTER TABLE student DROP sex；,删除学生表,DROP TABLE student CASCADE;,ALTER TABLE student MODIFY sex CHAR(8);,上一章回顾数据查询,请写出数据查询的一般形式,一般形式： SELECT , FROM , WHERE GROUP BY HAVING ORDER BY

3、ASC | DESC,上一章回顾数据查询,查选了004号课程且成绩在80到90之间学生的学号,6,SELECT sno FROM s_c WHERE cno=004 AND grade BETWEEN 80 AND 90;,SELECT COUNT(sno), AVG(grade) FROM s_c WHERE cno=004;,求选修了004号课程学生的人数和平均成绩,上一章回顾数据查询,查所有名字中第二个字为宇字的学生学号、姓名,7,SELECT sno，sname FROM student WHERE sname LIKE _ _宇%;,SELECT sno, sname, AVG(gr

4、ade) AS ag FROM student, s_c WHERE cno=004 AND student.sno=s_c.sno GROUP BY sno HAVING ag85 ORDER BY ag DESC;,求选修了004号课程的学生的学号、姓名和他们所选全部课程的平均成绩，将平均成绩大于85的输出，按平均成绩降序排列,上一章回顾数据查询,查选修了004号课程的学生学号、姓名,8,SELECT sno，sname FROM student WHERE sno IN (SELECT sno FROM s_c WHERE cno=004);,上一章回顾数据更新,将student表中性别

5、为男的学生学号、姓名和年龄插入到表s2中,9,INSERT INTO s2(sno, sname, age) SELECT sno，sname, age FROM student WHERE sex=男;,例：DELETE FROM student WHERE sno IN （SELECT sno FROM s_c WHERE cno=001);,将选修了为001号课程的学生信息从student表中删除,上一章回顾视图,10,例：CREATE VIEW s_st(no, name, age) AS SELECT sno, sname, age FROM student WHERE sex =

6、女；,建立一个只包含女学生学号、姓名和年龄的视图s_st,例：CREATE VIEW s_grade AS SELECT student.sno, sname, cname, grade FROM student, course, s_c WHERE student.sno = s_c.sno AND o = s_o;,从学生表、课表和选课表中产生一个视图s_grade，包含学号、姓名、课程名和成绩,4.1 函数依赖,4.2 关系模式的规范化,4.3 数据依赖的公理系统,4.4 关系模式的分解,第四章 关系数据理论,4.5 规范化的问题,11,4.1函数依赖,应用系统中数据库的设计就是要把现实

7、世界表达成适当的模式，逻辑设计 层次、网状模型主要凭经验，无规则和理论 关系模型有严格数据学理论基础，通过关系规范化理论来辅助逻辑设计 规范化理论：即将不规范的设计变成规范的设计,12,不同的设计人员可能对同一个应用设计出不同的关系模式，这些模式之间有优劣之分。 一、如何分析一个关系模式存在的问题 例：假设有学生关系模式 S(S#,SNAME,CLASS,C#,TNAME,TAGE,ADDRESS,GRADE) 其中 S#学号、 SNAME学生姓名、 CLASS班级、 C#课程号、 TNAME教师姓名、 TAGE教师年龄、ADDRESS教师地址、 GRADE成绩。,4.1函数依赖,13,4.1

8、函数依赖,问题1：数据冗余度高。SNAME、CLASS、TNAME、TAGE、ADDRESS重复存储多次。,问题2：修改复杂。,主码：(SNO，CNO),问题3：插入异常。应该插入到数据库中的数据不能执行插入操作。,14,4删除异常。 删除异常是指不应该删去的数据被删去的情形。 例如：选修某门课的所有学生都退选时，删除相关元组，会丢失该课程老师的信息。 解决：关系模式分解（关系规范化） 分解为 ST(S#，SNAME，CLASS) CT(C#,TNAME) TA(TNAME,TAGE,ADDRESS) SC(S#,C#,GRADE),4.1函数依赖,15,4.1函数依赖,16,4.1函数依赖,

9、关系分解解决了冗余、插入、删除异常 关系分解带来了“连接”操作 例：要查询某课程老师的信息，需连接CT和TA 原来的关系在性能上较优，而分解后的关系在模式上较优,17,到底什么样的模式才是较优的？,数据间的函数依赖,规范化理论讨论的是实体内各属性之间的联系，分为函数依赖和多值依赖，统称为数据依赖 二、函数依赖（Functional Dependency, FD） 定义4.1：设关系模式R( U )，X，Y 为U的子集，r是R的任一关系，对于r中任意两个元组s、t，如果由sX=tX能够导致sY=tY，称X函数决定Y，或者Y函数依赖X，记为XY。 另一种定义：若R的任意关系有：对X中的每个属性值，

10、在Y中都有惟一的值与之对应，则称Y函数依赖于X。 函数依赖是语义范畴的概念，只能通过语义确定 函数依赖要求对关系模式的所有关系都成立,4.1函数依赖,18,例：指出关系R中的函数依赖是否存在。,AB-C AC CA ABD,4.1函数依赖,19,例：试指出学生关系S(SNO，SNAME，CLASS，CNO，TNO，TNAME，TAGE，ADDRESS，GRADE)中存在的函数依赖关系。 SNOSNAME（每个学号只能有一个学生姓名） SNOCLASS（每个学号只能有一个班级） CNOTNO（设每门课程只有一个教师任教，而一个教师可教多门课程，见CT表） TNO TNAME（每个教师只能有一个姓

11、名） TNOTAGE（每个教师只能有一个年龄） TNOADDRESS（每个教师只能有一个地址） (SNO，CNO)GRADE（每个学生学习一门课只能有一个成绩） (S#，C#)SNAME、 (S#，C#)CLASS、 (S#，C#)C#、 (S#，C#)TNAME、 (S#，C#)TAGE、 (S#，C#)ADDRESS,4.1函数依赖,20,函数依赖与属性间的关系有： 若X，Y是1 1关系， 则存在 XY或Y X 。如学号与借书证号 若X，Y是m 1关系， 则存在 XY但 Y X。如学号与姓名 若X，Y是m n关系， 则X，Y间不存在函数依赖关系。如姓名与课程,4.1函数依赖,21,平凡、非

12、平凡函数依赖 XY，但Y X则称XY是非平凡的函数依赖。 XY，但Y X 则称XY是平凡的函数依赖。 若XY ，则X叫做决定因素。 若XY，Y X，则记作: X Y。 如果Y不函数依赖于X，则记做X Y。,4.1函数依赖,22,/,三、函数依赖的分类 定义4.2：在R( U)中，X, Y, Z为U的不同子集。 完全函数依赖: 是指 XY，且对任何X的真子集X， 都有X Y，记作：X Y。 部分函数依赖: 是指XY，且存在X的真子集X ， 有X Y， 记作： X Y 。 左部为单属性的函数依赖一定是完全函数依赖。,4.1函数依赖,23,f,P,/,左部为多属性的函数依赖，如何判断其是否为完全函数

13、依赖？ 方法：取真子集，看其能否决定右部属性。 例：试指出学生关系S中存在的完全函数依赖和部分函数依赖。 SNO SNAME，SNO CLASS，TNAME TAGE， TNAME ADDRESS，CNO TNAME都是完全函数依赖。 (SNO，CNO) GRADE 是一个完全函数依赖，因为 SNO GRADE，CNO GRADE。,4.1函数依赖,24,/,/,(SNO, CNO) SNAME，(SNO，CNO) CLASS， (SNO，CNO) TNAME，(SNO，CNO) TAGE， (SNO，CNO) ADDRESS都是部分函数依赖，因为： SNO SNAME，SNO CLASS，C

14、NO TNAME CNO TAGE，CNO ADDRESS。,4.1函数依赖,25,定义4.3：在R( U )中 传递函数依赖：是指若XY (Y 不包含于 X)， Y X ， 而Y Z。记作： X Z 。 例：试指出学生关系S中存在的传递函数依赖。 解：因为CNO TNAME，TNAME CNO，TNAME TAGE， 所以CNO TAGE 是一个传递函数依赖。 类似地，CNO ADDRESS也是一个传递函数依赖。,4.1函数依赖,26,t,/,/,四、候选码 用函数依赖的概念来定义码。 定义4.4 : 设X为R中的属性或属性组合，若 X U 则X为R的候选码。 说明： X U X U X能决

15、定整个元组 X U X中无多余的属性 存在性与不唯一性,4.1函数依赖,27,f,f,/,术语： 主码：选定候选码中的一个作为主码，一个关系的主码是唯一的 主属性: 包含在任何一个侯选码中的属性 非主属性：不包含在任何一个候选码中的属性 全码：整个属性组为码 例：R(顾客，商品，日期),4.1函数依赖,例：指出学生关系中的候选码、主属性和非主属性 学号、姓名均可作为候选码 学号、姓名为主属性 性别、年龄、系名为非主属性,28,例：试指出下列关系R中的侯选码、主属性和非主属性。,解：关系R的侯选码为：A，(D,E) 关系R的主属性为：A，D，E 关系R的非主属性：无,函数依赖判断：A D? D

16、A? AD E? 候选码判断: A ADE? AD ADE?,4.1函数依赖,29,一、关系与范式 关系的规范化是将一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。 关系模式分解的目的：去冗余、满足约束。 关系模式的冗余性问题。 约束条件通过函数的多值依赖和连接依赖及范式完成。,4.2 关系模式的规范化,30,二、第一范式：1NF 定义4.5: 若R的每个属性值都是不可再分的最小数据单位，则R1NF。 从型上看：不存在组合属性 例：工资（基本，补助） 从值上看：不存在重复组 例：跨行属性值 1NF是关系模式的最低要求。 非1NF转换为1NF的方法： 组合属性：拆分成多个单

17、属性、合并为单属性 重复组：拆分成多个元组,4.2 关系模式的规范化,31,例：学生关系S(SNO，SNAME，CLASS，CNO，TNAME，TAGE，ADDRESS，GRADE)是1NF关系，但它存在数据冗余，插入异常和删除异常等问题。,4.2 关系模式的规范化,32,三、第二范式： 2NF 定义4.6 若R1NF，且R中的每一个非主属性都完全函数依赖于R的任一候选码，则R2NF。 例：学生关系S(SNO，SNAME，CLASS，CNO，TNAME，TAGE，ADDRESS，GRADE),判断R是否为2NF? 侯选码为(SNO，CNO)，非主属性有：SNAME，CLASS，TNAME，TA

18、GE，ADDRESS，GRADE (SNO,CNO) SNAME，SNO SNAME (SNO,CNO) SNAME S2NF(每一个非主属性!)。,4.2 关系模式的规范化,33,P,分解为2NF的方法：破坏部分依赖的条件。 将满足部分函数依赖和满足完全函数依赖的属性分解到不同的关系中。 对上例，考察非主属性和侯选码之间的函数依赖关系： (S#，C#) SNAME， (S#，C#) CLASS， (S#，C#) TNAME， (S#，C#) TAGE， (S#，C#) ADDRESS， (S#，C#) GRADE (S#，C#) TNO 区分出完全依赖和部分依赖，若是部分依赖，标记出其中的主

19、属性。,4.2 关系模式的规范化,34,P,P,P,P,P,F,P,#表示NO，如S#表示SNO,用投影运算把关系S分解为三个关系： ST(S#，SNAME，CLASS)（只依赖S#的属性分解到一个子模式中） CTA(C#，T#,TNAME，TAGE，ADDRESS) （只依赖C#的属性分解到另一个子模式中） SC(S#，C#，GRADE) （完全函数依赖于候选码的属性分解到第三个子模式中） 分解后，关系ST、CTA和SC都为2NF。 结论1：若关系R的侯选码是单属性的，则R必定是2NF。,4.2 关系模式的规范化,35,达到2NF的关系仍然可能存在问题。 例如，在关系CTA中还存在以下问题：

20、 （1） 数据冗余。一个教师承担多门课程时，教师的姓名、年龄、地址要重复存储。 （2） 修改复杂。一个教师更换地址时，必须修改相关的多个元组。 （3） 插入异常。一个新教师报到，需将其有关数据插入到CTA关系中，但该教师暂时还未承担任何教学任务，则因缺码C#值而不能进行插入操作。 （4） 删除异常。删除某门课程时，会丢失该课程任课教师的姓名、年龄和地址信息。,4.2 关系模式的规范化,36,原因是存在传递依赖！,四、第三范式： 3NF 定义4.7 如果关系R的任意一个非主属性都不传递函数依赖于它的任意一个候选码，则R3NF。 关系CTA(C#，T#,TNAME，TAGE，ADDRESS)是2N

21、F，但不是3NF。 候选码：C#，非主属性：T#、TNAME、TAGE、ADDRESS。 由于C# T#，T# C#，T# TNAME，所以 C# TNAME，同样有C# ADDRESS，即存在非主属性对候选码的传递函数依赖。,4.2 关系模式的规范化,37,/,T,分解为3NF的方法：破坏传递依赖的条件。 将涉及传递函数依赖中的两个依赖中的属性分解到不同的关系中。 例：CTA中，三个传递依赖 C# T#，T# C#，T# TNAME：C# TNAME C# T#，T# C#，T# TAGE：C# TAGE C# T#，T# C#，T# ADDRESS：C# ADDRESS 将CTA分解为：

22、CT(C#，T#) TA(T#, TNAME，TAGE，ADDRESS) 则关系CT和TA都是3NF，关系CTA中存在的问题得到了解决。,4.2 关系模式的规范化,38,/,/,/,T,T,T,定理4.1 一个3NF的关系必定是 2NF。 （3NF不传递函数依赖，2NF完全函数依赖。） 证明：用反证法。设R3NF，但R2NF，则R中必有非主属性A、侯选码X和X的真子集X存在，使得XA。 X是侯选码X的真子集，有X-X；A是非主属性，A-X，A-X，这样A、X、X是U的不同子集。 X是侯选码X的真子集，则有XX 且 X X，联合反证假设XA可知存在传递依赖（XX,X X，XA） R不是3NF，与

23、题设矛盾。,4.2 关系模式的规范化,39,/,/,4.2 关系模式的规范化,判别3NF的方法 找候选码，确定非主属性 检查非主属性是否对候选码是否存在部分函数依赖，存在则不是2NF 判断非主属性之间是否存在函数依赖，存在则不是3NF,40,通过转为2NF消除了部分依赖，通过转为3NF消除了传递依赖，问题：达到3NF的关系是否仍然存在问题？ 例：每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称 ：,4.2 关系模式的规范化,41,解：关系SCT的侯选码：(S#，CNAME)和(S#，TNAME) 非主属性：无 （S

24、CT至少是一个3NF关系) 结论2：若关系R的所有属性都是主属性，则R必定是3NF。,候选码判断: S#S#，CNAME，TNAME 取左部的相同值，判断右部。,4.2 关系模式的规范化,42,在3NF关系SCT中存在： 插入异常。例如，一个新课程和任课教师的数据，在没有学生选课时不能插入数据库。 删除异常。例如，删除某门课的所有选课记录，会丢失课程与教师的数据。 达到3NF的关系仍然可能存在问题。,4.2 关系模式的规范化,43,可能存在主属性对候选码的部分依赖或者传递依赖，需要进一步对其进行规范。,五、BCNF 定义4.8 关系模式R1NF。若函数依赖集合F中的 所有函数依赖XY（Y不包含

25、于X）的左部都包含R的任一侯选码，则RBCNF。 换言之，BCNF中的所有依赖的左部都必须包含候选码。 例：关系SCT是否BCNF? 因为TNAMECNAME，其左部未包含该关系的任一侯选码 ，所以它不是BCNF。 解决：BCNF分解。,4.2 关系模式的规范化,44,分解为BCNF的方法： 消除不包含关系。 1. 假设R(U)不是BCNF, X是R的属性子集，A是R的单个属性，X-A是导致违反BCNF的函数依赖，则将R分解为R-A 以及 XA。 2. 若R-A以及 XA 仍然不是BCNF，则在R-A 以及 XA递归地执行上述分解。 例 SCT：(S#，CNAME，TNAME)，FD: TNA

26、MECNAME。 可分解为SC(S#，TNAME)和CT(CNAME，TNAME)，它们都是BCNF。,4.2 关系模式的规范化,45,定理4.2：一个BCNF的关系必定是3NF。 （3NF：任意的非主属性都不传递依赖于任意一个候选码。） 证明：用反证法。设R是一个BCNF，但不是3NF，则必存在一个非主属性A和候选码X以及属性集Y，使得A传递依赖于X，即XY(Y不包含于X)，YX，YA。 这就是说Y不包含R的候选码，但YA却成立。 根据BCNF定义可知，R不是BCNF，与题设矛盾。 结论3：任何的二元关系必定是BCNF。,4.2 关系模式的规范化,46,/,3NF下仍然存在插入异常和删除异常

27、， 原因在于可能存在主属性对候选码的部分函数依赖和传递函数依赖。 一个模式中的关系模式如果都属于BCNF，则在函数依赖的范畴内实现了彻底的分离，已消除了插入和删除的异常。 其它问题？,4.2 关系模式的规范化,47,函数依赖只能表达属性值之间的多对一的联系，但函数依赖不能表示属性值之间的一对多联系。 需要引入多值依赖。,4.2 关系模式的规范化,关系CTX中：课程可以由多位老师讲授，使用同一套参考书，每个老师可讲授多门课程，每本参考书可以供多门课程使用。,48,4.2 关系模式的规范化,49,规范化后：,TeachingBCNF: Teach具有唯一候选码(C，T，B)， 即全码 Teachi

28、ng模式中存在的问题 (1)数据冗余度大：有多少名任课教师，参考书就要存储多少次 (2)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组 例如物理课增加一名教师刘关，需要插入三个元组： （物理，刘关，普通物理学）、 （物理，刘关，光学原理）、 （物理，刘关，物理习题集）,4.2 关系模式的规范化,50,(3) 删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组 (4) 修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组 产生原因 教师和参考书之间是间接关系，存在多值依赖,4.2 关系模式的规范化,

29、51,4.2 关系模式的规范化,多值依赖 定义4.9 设关系模式R(U)，X、Y、Z是U的子集，且Z=U-X-Y，当且仅当对于R(U)的任一关系r，给定的一对(x,z)的值，有一组Y的值与之对应，且这组Y值仅仅决定于X值而与Z值无关，则称Y多值依赖于X，或称X多值决定Y，记为X Y。,52,4.2 关系模式的规范化,对于(数学，微分方程)，有一组T值(李勇，张平） 但这组T值仅仅取决于C值即“数学”，对于其他的(数学，？)值，得到的也是同一组T值 因此T多值依赖于C，同样X多值依赖于C,53,4.2 关系模式的规范化,多值依赖的另一个定义： 设R(U)，X、Y、Z是U的子集且Z=U-X-Y，当

30、且仅当对于R(U)的任一关系r，如果存在元组(x,y1,z1)和(x,y2,z2)时，一定存在(x,y1,z2)和(x,y2,z1)，即交换两元组在Y上的值产生的新元组依然在关系中。则称Y多值依赖于X。,54,4.2 关系模式的规范化,平凡多值依赖 对于属性集U上的一个多值依赖XY，如果Y X或者XY=U，称XY是一个平凡的多值依赖。 例：设R(A,B,C)上有一个多值依赖AB，如果已知R的一个关系中已有三个元组(a,b1,c1) (a,b2,c2) (a,b3,c3)，该关系中至少还存在哪些元组？ (a,b2,c1) (a,b1,c2) (a,b3,c1) (a,b1,c3) (a,b3,c

31、2) (a,b2,c3),55,4.2 关系模式的规范化,多值依赖的特点 (1)允许X的一个值决定Y的一组值，并且决定关系与Z值无关 (2)多值依赖是全模式的依赖关系，需要看属性Z才能确定X和Y是否有多值依赖关系,56,4.2 关系模式的规范化,多值依赖公理 设关系模式R，属性全集U，X、Y、Z、V、W是U的子集 1)多值依赖公理 补规则：如果X Y，则X (U-X-Y) 增广律：如果X Y，V W，则WX VY 传递律：如果X Y，Y Z，则X (Z-Y) , X (Y-Z),57,4.2 关系模式的规范化,函数依赖导出多值依赖：如果XY则X Y 多值依赖导出函数依赖：如果X Y，Z Y，Y

32、W=，W Z，则XZ 2)多值依赖推论 合并律：若XY，XZ，则XYZ 伪传递律：若XY，WYZ，则WX(Z-WY),58,4.2 关系模式的规范化,混合伪传递律：若X Y，XYZ，则X(Z-Y) 分解律：若XY，XZ，则 X(Y Z) X(Y-Z) X(Z-Y),59,第四范式：4NF 定义4.10 若R 1NF，D是R上的多值依赖集合，如果对于任何一个非平凡多值依赖X Y ，X都包含了R的一个候选码，则R4NF。 4NF必定是BCNF，但BCNF不一定是4NF。 CTX关系中：C T，C X，CTX的候选码是（C, T,X），显然两个多值依赖的左部不包含候选码，所以CTX不是4NF。,4.

33、2 关系模式的规范化,60,定理4.3 如果关系模式R4NF，则R必为BCNF。 证明：用反证法。设R4NF，但RBCNF，则R中必 有某个函数依赖XY(Y不包含于X)，且X不包含R的侯选码。由多值依赖公理可知，若XY，则XY，而此时X不包含R的侯选码，R不是4NF，与假设矛盾，从而定理得证。,61,4.2 关系模式的规范化,分解为4NF的方法： （ 类似于BCNF，消除不包含关系。） 1) 假设R(U)不是4NF, XA是导致违反4NF的多值依赖，则将R分解为R-A 以及 XA。 2) 若R-A以及 XA 仍然不是4NF，则在R-A 以及 XA递归地执行上述分解。,62,4.2 关系模式的规

34、范化,4.2 关系模式的规范化,函数依赖、多值依赖通过语义导出，而连接依赖只有在关系连接运算时才会显现 连接依赖 当关系模式分解为n个投影(n2)时会产生一些特殊的情况。,63,4.2 关系模式的规范化,64,SPPJSJ=SPJ,定义4.11 给定关系模式R，(R1, R2, , Rn)是R的分解，当且仅当R是由它在R1, R2, , Rn上的投影的自然连接所组成时，称R满足对于R1, R2, , Rn的连接依赖，记为JD* R1, R2, , Rn。 即： 若R=R1R2 Rn， 且r = R1(r) R2(r) Rn(r)，则称R满足对于R1, R2, , Rn的连接依赖。 如果其中某个

35、Ri就是R本身，则连接依赖是平凡的。,4.2 关系模式的规范化,65,第五范式：5NF 定义4.12 给定关系模式R，当且仅当R中的每一个非平凡的连接依赖都被R的候选码所蕴含时，则R是5NF。 R的连接依赖JD* R1, R2, , Rn被候选码所蕴含当且仅当R1、R2,Rn中任何一个都包含候选码。 关系模式SPJ不是5NF，其候选码(Sno,Pno,Jno)并不蕴含连接依赖，SP、PJ、SJ连接时不是用该候选码连接。 但SP、PJ、SJ不包含任何非平凡的连接依赖，都是5NF。,4.2 关系模式的规范化,66,5种范式的关系：,1NF,非规范化的关系,2NF,3NF,4NF,BCNF,1NF,

36、2NF,3NF,BCNF,4NF,67,关系的规范化是将一个低级范式的关系模式，通过关系模式的分解转换为若干个高级范式的过程。 范式的转换过程是通过分析和消除属性间的数据依赖关系来实现的。 属性可分为码和非主属性。 2NF, 3NF考察非主属性和码的关系，BCNF考察主属性和码的关系。 属性间的依赖关系包括函数依赖和多值依赖。 1NF, 2NF, 3NF, BCNF考察了函数依赖关系；4NF考察了多值依赖。,4.2 关系模式的规范化,68,1.阿氏公理 在进行函数依赖的检查时，需要判断另外一些函数依赖是否成立，通过函数依赖的逻辑蕴涵即可做到。 定义4.13 设F是关系模式R的函数依赖集，X、Y

37、是R的属性子集，如果从F的函数依赖中能够推出XY，则称F逻辑蕴涵XY。,4.3 数据依赖的公理系统,69,Armstrong公理(阿氏公理)： 对R 有： A1自反律：若YX ，则XY。 A2增广律：若XY，则XZYZ。 A3传递律：若XY、YZ，则XZ。 由自反律：所有的平凡函数依赖都是成立的 由增广律：函数依赖两边增加相同属性也成立 由传递律：由已知函数依赖可以推导出新依赖,4.3 数据依赖的公理系统,70,证：设s，t是r的任意两个元组，r是R的任意一个关系。 A1自反律：若YX ，则XY。 若sx=tx，则在s和t中的x的任何子集也必相等。 YX， sy=ty XY。 A2增广律：若X

38、Y，则XZYZ。 若sxz=txz，即sxsz=txtz 则 sx=tx 且 sz=tz XY， sy=ty syz=sysz=tytz=tyz XZYZ,4.3 数据依赖的公理系统,71,A3传递律：若XY、YZ，则XZ。 若sx=tx XY sy=ty 又 YZ sz=tz XZ。,4.3 数据依赖的公理系统,72,公理的推论： 合并规则：若XY 、 XZ，则XYZ。 分解规则：若XYZ，则XY,XZ。 伪传递规则：若XY 、WYZ，则WXZ。 证明： 合并规则： XY XXY (A2) 又 XZ XYYZ (A2) XYZ (A3),4.3 数据依赖的公理系统,73,分解规则： YY Z

39、 YZY (A1) 又 XYZ(已知） XY (A3) 同理可证XZ。 伪传递规则： XY WXWY (A2) 又 WYZ (已知) WXZ (A3) 定理4.5: XA1A2An成立的充分必要条件是XAi成立。,4.3 数据依赖的公理系统,74,2. 公理的完备性 定义4.14 设有关系模式R,X、Y为U的子集，函数依赖集F的闭包定义为： F+=X Y| X Y基于阿氏公理推出 即F+为F所逻辑蕴含的函数依赖全体。 F+= F中的函数依赖，由属性语义决定； 由F推出的非平凡的函数依赖； 由F推出的平凡的函数依赖：A、AA、ABA. 例：有关系模式R(A，B，C)，它的函依赖集F=AB，BC，

40、计算F的闭包。,4.3 数据依赖的公理系统,75,例：有关系模式R(A，B，C)，它的函依赖集F=AB，BC，计算F的闭包。 解： (1)F中的函数依赖： AB，BC (2)由F推出的非平凡函数依赖： AC，ACB (3)由F推出的平凡函数依赖： A，AA F+的计算很麻烦，可能会非常大,4.3 数据依赖的公理系统,76,定义4.15 设F是属性集合U上的一个函数依赖集，XU： XF+=A|XA能由F用阿氏公理导出 XF+称为属性集X关于F的闭包，也可简写为X+。 由X从F中推出的所有函数依赖右部的集合。 例如：R(A,B,C)中，F=AB，BC，则 AF+=ABC，BF+=BC，CF+=C

41、属性闭包的计算比F的闭包要容易地多。 定理4.6： XY能从F中用阿氏公理导出的充要条件是：YXF+,4.3 数据依赖的公理系统,77,定理4.6的证明 证明： 充分性（ YXF+ 可得 XY） 假设YXF+ (其中Y=A1A2An ) 由属性闭包定义可知， XA1， XA2， XAn能由阿氏公理导出，再由合并规则得X A1A2An，即XY。,4.3 数据依赖的公理系统,78,必要性：（ XY 可得YXF+ ） 假设XY能由阿氏公理导出(Y=A1A2An) 则有XA1A2An 由分解规则得： XA1， XA2， XAn 由XF+的定义可知，Ai XF+ (i=1,2,n) 即YXF+ 。,4.

42、3 数据依赖的公理系统,79,4.3 数据依赖的公理系统,阿氏公理的完备性 建立公理体系的目的在于有效而准确的从已知的函数依赖推出未知的函数依赖，公理系统要满足两个特性： (1)正确性：按阿氏公理推出的依赖都是正确的 （定理4.4已证明） (2)完备性：能推出所有的依赖 完备性等价于：所有不能用公理系统推出的依赖都不成立，即不能由F逻辑蕴涵 或者存在一个具体关系r，F中所有函数依赖都满足r，但不能用公理推出的X Y却不满足r。,80,4.3 数据依赖的公理系统,Armstrong公理完备性的证明 证明：(即不能从F中用公理推出的依赖不在F+中) 设F是U上的依赖集，且X Y不能从F中用公理推出

43、。现在要证明： X Y不在F+中，即至少有一个关系r满足F，但不满足X Y。 构造r：由两个元组t1和t2构成，t1在U上全部属性值为1。t2在X+中属性上值为1，在U-X+的属性上值为0。,81,4.3 数据依赖的公理系统,证明过程： (1)首先证明r满足F 设V W是F中任意一个函数依赖，则: (a)V X+。根据定理4.6可知X V成立，再由传递律可知X W，从而W X+。关系r中所有X+中的属性值都相等，所以t1V=t2V, t1W=t2W。于是V W在r中成立。 (b)V不属于X+。则t1V不等于t2V，根据函数依赖的定义， V W在r中成立。 因此r满足F,82,4.3 数据依赖的

44、公理系统,(2)证明关系r中， X Y不能成立 由于X Y不能从阿氏公理导出，因此根据定理4.6，Y不属于X+。而XX+，所以r中两个元组中X的属性值相同，而在Y上的属性值不同，因此X Y在r中不能成立。 综合(1)(2)：只要X Y不能从F通过阿氏公理导出，则F就不能逻辑蕴涵X Y。,83,3. 属性闭包的计算 F的闭包F+计算起来相当麻烦，且其中有很多冗余信息，因此计算F+是不现实的。 判断X Y在不在F+中，只要判断Y是否属于X+。 因此计算F+的问题可以变换成计算X+的问题，而X+的计算相对简单。,84,4.3 数据依赖的公理系统,算法4.1 : 求属性集X关于F的闭包XF+(X+)。

45、 算法： 设 R，A为U中属性(集)。 (1) X(0)=X (2) X(i+1)=X(i)A 其中A： 对F中任一个没有使用过的Yj Zj，且YjX(i)； 所有的这些Zj构成A 求得X(i+1) 后，对Yj Zj做已使用的标记。如果找不到这样的A，则转(4) (3)若X(i+1)=X(i) 或 X(i+1) =U则转(4)，否则转(2)。 (4)结束，输出X(i)，即为X+,最多|U-X|步,85,4.3 数据依赖的公理系统,闭包的计算,86,例：设有关系模式R，其中U=A,B,C,D,E,I， F=AD,AB E,BI E,CD I,E C 计算(AE)+ (1)X0=AE (2)X1=

46、X0DC=ACDE，用了AD和EC (3)X2=X1I=ACDEI，用了CD I (4)F中没有左部属于X2的函数依赖，X2为(AE)+,闭包的计算,例：U=A,B,C,D,E,G F=ABC,CA,BCD,ACDB,DEG,BE C,CG BD,CE AG，求(BD)+ (1)X0=BD (2)X1=BDEG DEG (3)X2=BCDEG BE C (4)X3=ABCDEG CA (5)X3=U，所以(BD)+=X3,87,闭包的计算,判断闭包计算结束的方法： （1）X(i+1)=Xi （2）当发现Xi中包含了所有的属性 （3）当F中的函数依赖的右边再也找不到Xi中未出现过的属性 （4）在

47、F中未用过的函数依赖的左边已没有Xi的子集,88,闭包计算算法的正确性,定理4.8算法4.1是正确的。 证明： (1) 终结性证明。Xi的变化有两种可能： a) Xi单调向上，因Xi有上界U，且Xi单调向上，算法可终止 b) Xi非单调变化，在某步出现A=，则Xi=Xi+1，也会终止,89,闭包计算算法的正确性,(2) 正确性证明。 由X+的定义及算法可知Xi X+，只需证明X+Xi成立，即可得到Xi=X+ 只要说明任何一个XY中的Y都属于Xi。 因为XY可通过三条公理导出： a)如果利用自反律，由于Xi包含X，则Xi包含Y b)如果利用传递律，X W,W Y，且W属于Xi，则下一步Y将被加入

48、到Xi c)如果利用增广律，XWZW,ZWY，设W属于X+，有X ZW，根据传递律，Y也应属于Xi,90,4.函数依赖集的等价和覆盖 定义4.16 : 如果F+=G+ ，就说函数依赖集F覆盖G或F与G等价。 性质 (1)若GF，则G+F+ 证：设XYG+，则该依赖可用G推出。而G是F的一部分，因此从F也可推出该依赖 (2)(F+)+=F+ 证：设XY(F+)+，则该依赖可用F+推出，而F+又是基于F推出的，所以该依赖也是由F推出的所以有XYF+,4.3 数据依赖的公理系统,91,定理4.9: F=G 的充分必要条件是FG+，和GF+。 （1）必要性 F和G等价，F+=G+，又FF+，FG+ 同

49、理，GG+，GF+。 （2）充分性 任取XYF+，则有YXF+ (定理4.6) 又FG+（已知），YXG+ XY(G+)+=G+，F+G+。 同理可证G+F+，F+=G+，即F和G等价。,4.3 数据依赖的公理系统,92,如何判断函数依赖集F和G是否等价？ 根据定理4.9: 只需FG+和GF+，即证 对每个TF,有TG+；对每个SG，有SF+，T和S是形如XY的属性依赖。 而验证XYG+,根据定理4.6：只需Y XG+ 转为计算XG+,4.3 数据依赖的公理系统,93,例：F=AB，BC，G=ABC，BC，判断F和G是否等价。 解：（1）先检查F中的每一个函数依赖是否属于G+。 AG+=ABC

50、，BAG+，ABG+ (定理4.6) 又BG+=BC，CBG+，BCG+ FG+ （2）然后检查G中的每一个函数依赖是否属于F+。 AF+=ABC，BCAF+，ABCF+ 又BF+=BC，CBF+，BCF+ GF+ 由（1）和（2）可得F和G等价。,4.3 数据依赖的公理系统,94,5.最小函数依赖集 定义4.17:若F满足下列条件，则称其为一个最小函数依赖集Fm。 (1) F中每个函数依赖的右部都是单属性； (2) 对于F的任一函数依赖XA，F-XA与F都不等价，即无多余函数依赖； (3) 对于F中的任一函数依赖XA和X的真子集X， (F-(XA)UXA与F都不等价,即左部无多余 属性。,最

51、小：（1）F中每个函数依赖的右部没有多余的属性； （2）F中不存在多余的函数依赖； （3）F中每个函数依赖的左部没有多余的属性。,4.3 数据依赖的公理系统,95,例：哪个是最小依赖集？ (1)F1=A D,BD C,C AD (2)F2=AB C,B A,B C (3)F3=BC D,D A,A D F1中第三个依赖的右部不是单属性 F2中第一个依赖左部有多余属性A F3满足最小依赖集的三个条件,4.3 数据依赖的公理系统,96,定理4.10: 每个F与Fm等价。 如何求最小函数依赖集Fm？ (1)分解：使F中任一函数依赖的右部仅含有单属性。 (2)删除冗余的函数依赖： 方法：对F中任一XA

52、，在F-XA中求X+， 若AX+，则XA为多余的。 (3)最小化左边的多余属性： 方法：对F中任一XYA，在F中求X+， 若AX+ ，则Y为多余的。,4.3 数据依赖的公理系统,97,例：设有F=BC，CAB，BCA，求与F等价的最小函数依赖集。 分解CAB，F=BC，CA，CB，BCA 判断BC是否冗余，F=CA，CB，BCA B+ = B, BC非冗余。 F=BC，CA，CB，BCA 判断CA是否冗余，F=BC, CB，BCA C+ = ABC, CA冗余。 F=BC，CB，BCA 判断CB是否冗余，F=BC, BCA C+ = C, CB非冗余。 F=BC，CB，BCA 判断BCA是否冗

53、余，F=BC，CB BC+ = BC, BCA非冗余。F=BC，CB，BCA 判断BCA。 B+ = ABC, AB+ ，则C在BCA中是多余的。 Fm=BC，CB，BA,注意： 对当前F求闭包,4.3 数据依赖的公理系统,98,例：设有函数依赖集F=AB,ABCDE,EFG,EFH,ACDFEG 求与F等价的最小函数依赖集。 注意：一个函数依赖集的最小集不是惟一的。 例如，F=AB，BA，BC，AC，CA Fm1=AB，BC，CA， Fm2=AB，BA，AC，CA。 方法1： 无多余属性；依次判断B-A, A-C是否冗余； 方法2： 无多余属性；依次判断B-C是否冗余。,Fm = AB,AC

54、DE, EFG,EFH,4.3 数据依赖的公理系统,99,关系模式的分解过程实际上就是将一个关系模式分解成一组等价的关系子模式的过程。 关系模式分解后会带来两个问题： （1）查询时的连接操作是否会丢失某些信息或多出某些信息。这引出了无损连接的概念。 （2）分解后的关系模式是否保持了原来的函数依赖。这是保持函数依赖性的问题。 对于一个关系模式的分解是多种多样的，但是分解后产生的模式应与原来的模式等价。 等价是指满足：无损连接性 + 依赖保持性,4.4 关系模式的分解,100,1. 等价模式分解 一个关系可以有多种分解方法，如何判断分解的好与坏呢？ 例：关系模式R(S#，SD，MN),F=S#SD

55、，SDMN 分解一：1=R1(S#)， R2(SD)， R3(MN) 不好！无法恢复r. 分解二：2=R1(S#，SD)，R2(S#，MN) 不好！丢失SD MN 分解三：3=R1(S#，SD)，R2(SD，MN) 好！,4.4 关系模式的分解,101,4.4 关系模式的分解,R(A, B, C),AB(R),BC(R),R(A, B, C),AB(R),BC(R),有损分解,无损分解,102,2.无损连接性与依赖保持性 衡量关系模式分解的标准： （1）分解具有无损连接性 （2）分解具有依赖保持性 （3）兼具（1）、（2） 我们希望得到第三种分解（等价分解）！,4.4 关系模式的分解,103,定义4.19 R，若R的分解=R1, R2.Rk对R中任何一个关系r，有： r=R1(r) R2(r) Rk(r) 称分解具有无损连接性 R1(r) 表示关系r在模式R1的属性上的投影 R1(r) R2(r) Rk(r)也记做m(r),4.4 关系模式的分解,104,定理4.11 R，若R的分解=R1, R2.Rk对R中任何一个关系r，ri=Ri(r)，则： (1)rm(r) (2)若s=m(r)，则Ri(s)=ri (3) m(m(r)=m(r),4.4