数据库原理与程序设计第6章-逻辑数据库设计课件.ppt

1、第第6章章 逻辑数据库设计逻辑数据库设计生物医学软件工程生物医学软件工程v逻辑结构设计的任务逻辑结构设计的任务把概念结构设计把概念结构设计阶段设计好的阶段设计好的ER图转化为与选用的图转化为与选用的DBMS产品所支持的数据模型相符合的逻辑结构。产品所支持的数据模型相符合的逻辑结构。概念结构概念结构基本基本ER图图转换转换规则规则一般数据模型一般数据模型关系关系,网状网状,层次层次DBMS特特点和限制点和限制特定特定DBMS 支持下的数支持下的数据模型据模型优化的数优化的数据模型据模型优化优化方法方法本章概要本章概要v形成初始关系数据库模式形成初始关系数据库模式v关系数据库设计理论关系数据库设计

2、理论v关系模式作规范化方法关系模式作规范化方法 v关系模式的优化关系模式的优化v定义关系完整性和安全性约束定义关系完整性和安全性约束v逻辑数据库的性能估计逻辑数据库的性能估计6.1 形成初始关系数据库模式形成初始关系数据库模式v初始关系数据库模式初始关系数据库模式是指使用简单方法直是指使用简单方法直接由概念数据库模式生成的关系数据库模接由概念数据库模式生成的关系数据库模式。式。v从概念模式到初始关系模式的变换方法如从概念模式到初始关系模式的变换方法如下：下：普通实体型变换为关系模式普通实体型变换为关系模式 R 弱实体型弱实体型 W 变换为关系模式变换为关系模式 R 实体型实体型 E 的多值属性

3、的多值属性 A 变换为关系模式变换为关系模式 T 实体型之间的联系型实体型之间的联系型 R 的变换为关系模式的变换为关系模式 W 超类超类/子类联系型变换为关系模式子类联系型变换为关系模式 范畴和共享子类的变换范畴和共享子类的变换一、普通实体型的变换一、普通实体型的变换v概念模式中的实体型概念模式中的实体型 E 转换为关系转换为关系 S，S 包包含含 E 的所有简单属性和复合属性的简单子的所有简单属性和复合属性的简单子属性，属性，E 的键是的键是 S 的主键。的主键。教师教师姓名姓名证号证号工资工资地址地址课程课程教研室教研室市市 区区邮编邮编单位单位学校学校信箱信箱教师实体型教师实体型关系关

4、系T(姓名姓名,证号证号,工资工资,邮编邮编,市市,区区,学校学校,信箱信箱,课程课程,教研室教研室)二、弱实体的变换二、弱实体的变换v 概念模式中设概念模式中设 W 是以实体型是以实体型 E 为识别实为识别实体型的弱实体，建立一个与体型的弱实体，建立一个与W对应的关系对应的关系 R。v 规则规则：W 的所有简单属性和复合属性的的所有简单属性和复合属性的简单子属性映射为简单子属性映射为 R 的属性；的属性；E 的键属性的键属性也是也是 R 的属性；的属性；R的键由的键由E的键和的键和W的部的部分键组成。分键组成。v 根据规则：根据规则：R(父亲证号父亲证号,姓名姓名,性别性别,区号区号,房号房

5、号,床号床号)婴孩婴孩姓名姓名性别性别位置位置父亲父亲姓名姓名单位单位证号证号父子父子1NWE区号区号房号房号床号床号三、多值属性的变换三、多值属性的变换v具多值属性具多值属性 A 的实体的实体 E 变换为关系变换为关系 S。v方法是为属性方法是为属性A建立关系建立关系 T。设。设 E 的键为的键为k，则则 T 的结构如下：的结构如下：若若A是简单属性，则是简单属性，则T的属性为的属性为k,A；若若A是复合属性是复合属性(a1,a2)，则，则T的属性为的属性为 k,a1,a2v根据规则：根据规则：S(证号证号，姓名，姓名)T1(证号证号，年年，校校，学衔学衔)T2(证号证号，任课编号任课编号)

6、教师教师姓名姓名证号证号学历学历年年 校校 学衔学衔任课任课编号编号证号证号 年年 校校 学衔学衔 001 81 北大北大 学士学士 001 84 北大北大 硕士硕士 001 87 清华清华 博士博士 002 90 中大中大 学士学士 003 91 中大中大 学士学士 证号证号 课号课号 001 A11 001 A12 002 A11 002 A12证号证号 姓名姓名 001 陈大陈大 002 赵二赵二 003 张三张三四、实体间联系的变换四、实体间联系的变换v实体联系型实体联系型 R 变换为关系变换为关系 W，将联系相关是实体型将联系相关是实体型A,B变换为关系变换为关系 S,T;(1)1:

7、N的联系的变换的联系的变换(包括包括1:1)方法方法1：取取1方的键方的键,添加到添加到 N方方,作为作为 N 方的外部键方的外部键;R层次结构中的全体简单属性添加到层次结构中的全体简单属性添加到N端。端。方法方法2：构造关系：构造关系W,至少含两个属性至少含两个属性,分别是分别是A、B的的键键,R层次结构中的全体简单属性。层次结构中的全体简单属性。(2)M:N联系的变换联系的变换 需要建立一个新关系需要建立一个新关系W，将，将S和和T的主键添入的主键添入W，即，即将它们作为外部键，也将它们组合起来作为将它们作为外部键，也将它们组合起来作为W的主的主键。键。W还需要包含还需要包含R的简单属性和

8、简单子属性。的简单属性和简单子属性。教师教师职称职称姓名姓名系属系属姓名姓名学生学生班主任班主任N1编编号号教教号号教师教师职称职称姓名姓名名称名称课程课程任教任教NM学时学时教教号号课课号号五、超类五、超类/子类联系的变换子类联系的变换v设超类实体型设超类实体型 C 的属性是的属性是 k,A1,An，其中，其中 k 是键。是键。E1,Em是是 C 的子类。的子类。方法1：建立超类对应的关系，其属性是建立超类对应的关系，其属性是C的属性，的属性，k是是键；建立子类键；建立子类Ei对应的关系，其属性是对应的关系，其属性是Ei的属性和的属性和k，k是键。要求各子类在是键。要求各子类在k的投影是超类

9、在的投影是超类在k投影的子集。投影的子集。方法方法2：建立子类：建立子类Ei对应的关系，其属性是对应的关系，其属性是C和和Ei的属的属性，性，k是键。适合于全域约束和正交约束的情况。是键。适合于全域约束和正交约束的情况。方法方法3：综合超子类所有属性建立关系，增添一个特殊：综合超子类所有属性建立关系，增添一个特殊属性属性t，用来说明元组所属的子类，用来说明元组所属的子类，k是键；适合于正是键；适合于正交约束的情况。交约束的情况。方法方法4：综合超子类所有属性建立关系，：综合超子类所有属性建立关系，k是键，增添是键，增添m个特殊属性个特殊属性ti，用来说明元组是否属于子类，用来说明元组是否属于子

10、类Ei。适合。适合于子类相交的情况。于子类相交的情况。超类超类员工员工对应的关系：员工对应的关系：员工(证号证号,姓名姓名,性别性别)子类子类医师医师对应的关系：医师对应的关系：医师(证号证号,学位学位)子类子类护士护士对应的关系：护士对应的关系：护士(证号证号,工龄工龄)子类子类医师医师对应的关系：医师对应的关系：医师(证号证号,姓名姓名,性别性别,学学位位)子类子类护士护士对应的关系：护士对应的关系：护士(证号证号,姓名姓名,性别性别,工工龄龄)建立关系：员工建立关系：员工(证号证号,姓名姓名,性别性别,学位学位,工龄工龄,职务职务)可以用下边关系表示：可以用下边关系表示：员工员工(证号证

11、号,姓名姓名,性别性别,课程课程,学时学时,业务业务,职位职位,a,b)a=1,表示该员工是教师；表示该员工是教师；b1表示该员工是行政人员。表示该员工是行政人员。员工员工o相交子类相交子类证证号号教师教师行政行政姓姓名名性性别别课程课程学时学时业务业务职位职位六、范畴和共享子类的变换六、范畴和共享子类的变换v设设C是是E1,Em的范畴或共享子类，的范畴或共享子类，若所有若所有Ei有相同的键有相同的键k，则用，则用C的所有属的所有属性连同性连同k建立一个关系建立一个关系L，k作为作为L的键。的键。若所有若所有Ei有不同的键，则用有不同的键，则用C的所有属性的所有属性及一个特殊属性及一个特殊属性

12、k建立一个关系建立一个关系L，k作为作为L的键，并将的键，并将k作为外部键加入到作为外部键加入到 E1,Em中。中。教师教师干部干部工人工人u住户住户 转换方法转换方法1教师教师(证号证号,姓名姓名,课程课程,时数时数)干部干部(证号证号,姓名姓名,业务业务,职务职务)工人工人(证号证号,姓名姓名,工种工种,工龄工龄)住户住户(证号证号,房号房号,水费水费,电费电费)转换方法转换方法2教师教师(教号教号,姓名姓名,课程课程,时数时数,编号编号)干部干部(证号证号,姓名姓名,业务业务,职务职务,编号编号)工人工人(工号工号,姓名姓名,工种工种,工龄工龄,编号编号)住户住户(编号编号,房号房号,水

13、费水费,电费电费)例：教务管理系统例：教务管理系统系系隶属隶属教师教师授课授课班级班级课程课程教学计划教学计划使用使用教材教材隶属隶属隶属隶属学生学生隶属隶属选修选修1111nnnnnn1mmm1nk成绩成绩学生学生学号学号姓名姓名性别性别出生年月出生年月班级号班级号入学时间入学时间家庭住址家庭住址教师教师教师编号教师编号姓名姓名性别性别出生年月出生年月系系职位职位家庭住址家庭住址邮政编码邮政编码电话电话课程课程课程号课程号课程名课程名书号书号总学时总学时学分学分教材教材书号书号书名书名出版社出版社作者作者书价书价班级班级班级号班级号班长班长学生人数学生人数系系系教师系教师人数人数系主任系主任

14、系名系名系号系号七、确定函数依赖集七、确定函数依赖集v已形成初始关系数据库模式，但其中某些已形成初始关系数据库模式，但其中某些关系模式可能存在后边指出的冗余问题、关系模式可能存在后边指出的冗余问题、插入问题、更新问题和删除问题。插入问题、更新问题和删除问题。v需要对所产生的初始关系数据库模式进行需要对所产生的初始关系数据库模式进行后边介绍的后边介绍的规范化处理规范化处理。本章概要本章概要v形成初始关系数据库模式形成初始关系数据库模式v关系数据库设计理论关系数据库设计理论v关系模式作规范化方法关系模式作规范化方法 v关系模式的优化关系模式的优化v定义关系完整性和安全性约束定义关系完整性和安全性约

15、束v逻辑数据库的性能估计逻辑数据库的性能估计6.2 关系数据库设计理论关系数据库设计理论一、问题的提出一、问题的提出v考虑关系模式考虑关系模式：学生：学生(学号学号,系名系名,系主任系主任,课名课名,成绩成绩)假定学校的教学环境有以下假定学校的教学环境有以下的基本情况：的基本情况：一个系有多名学生，但一个学生属于一个系有多名学生，但一个学生属于并只属于某一个系；并只属于某一个系；一个系有且只有一名主任；一个系有且只有一名主任；每个学生可选多门课程，每门课程供每个学生可选多门课程，每门课程供多名学生选修；多名学生选修；每个学生修每门课程都有一个成绩。每个学生修每门课程都有一个成绩。v这意味上述关

16、系属性之间存在如下的这意味上述关系属性之间存在如下的决定决定关关系：学号决定系名，系名决定系主任，系：学号决定系名，系名决定系主任，(学号学号,课课名名)决定成绩。对决定成绩。对决定决定关系进行形式化描述，关系进行形式化描述，就得出函数依赖概念。就得出函数依赖概念。v上述关系模式有以下四个问题：上述关系模式有以下四个问题：插入异常插入异常：系刚成立，没有学生，使系名和主：系刚成立，没有学生，使系名和主任信息无法存入；任信息无法存入；删除异常删除异常：全体学生毕业，资料删除，系名和：全体学生毕业，资料删除，系名和主任信息随之删除；主任信息随之删除；数据冗余数据冗余：主任数据重复存储，降低时空效率

17、，：主任数据重复存储，降低时空效率，增加维护复杂性增加维护复杂性;数据更新数据更新：更新冗余数据容易引起数据不一致。：更新冗余数据容易引起数据不一致。四个问题的产生原因是：四个问题的产生原因是：关系模式的属性之间存在较复杂关系模式的属性之间存在较复杂的的决定决定关系关系解决方法：解决方法：对属性集合作适当分组，即后边对属性集合作适当分组，即后边介绍的规范化处理。介绍的规范化处理。二、函数依赖二、函数依赖v定义定义1：设设 R 是关系模式，是关系模式，U 是其属性集，是其属性集，X、Y 是是 U 的子集。对的子集。对 R 任取实例任取实例 r，对，对 r任取两个元组任取两个元组 t1和和t2，若

18、若 t1X=t2X，则，则t1Y=t2Y，则称，则称 Y函数函数地依赖于地依赖于X，或，或X函数地确定函数地确定Y；记；记XY。v若若XY，YX，即，即X和和Y互相函数依赖互相函数依赖，则记作则记作XY。学号学号身份证号身份证号v注意：注意：函数依赖实际是对现实世界某些强制性函数依赖实际是对现实世界某些强制性约束的抽象描述。约束的抽象描述。若若XY,而且而且Y是是X的子集，称为的子集，称为平凡函平凡函数依赖数依赖；若若XY,而且而且Y不是不是X的子集，称为的子集，称为非平非平凡的函数依赖凡的函数依赖。关系模式上全体函数依赖由两部分组成：关系模式上全体函数依赖由两部分组成：基本部分直接由语义得到

19、，其它部分由基本部分直接由语义得到，其它部分由公理系统导出。公理系统导出。学号学号 姓名姓名 课程课程 分数分数M01 陈大陈大 数学数学 81M01 陈大陈大 英语英语 82M02 赵二赵二 物理物理 91M02 赵二赵二 化学化学 92关系实例关系实例1学号学号 姓名姓名 课程课程 分数分数 P01 张三张三 数学数学 83 P01 张三张三 英语英语 84 P02 李四李四 物理物理 93 P02 李四李四 化学化学 94关系实例关系实例2例：例：v考虑关系模式；学生考虑关系模式；学生(学号学号,姓名姓名,课程课程,分数分数)设有函数依赖：学号设有函数依赖：学号姓名姓名v该函数依赖意味着

20、应用领域有这么一个约束：关该函数依赖意味着应用领域有这么一个约束：关系模式的任意实例系模式的任意实例(例如下边列出的两个实例例如下边列出的两个实例)，实例中的任意两行，只要这两行在学号等值，那实例中的任意两行，只要这两行在学号等值，那么这两行在姓名也必须等值。么这两行在姓名也必须等值。学生学生(学号学号,姓名姓名,课程课程,分数分数)v定义定义2：若：若XY，而，而X 的任何真子集的任何真子集 Z，ZY不成立，则称不成立，则称X完全函数确定完全函数确定Y，或或Y完全函数依赖于完全函数依赖于X；若若XY,但但Y不完全函数依赖于不完全函数依赖于X,则称则称X部部分函数确定分函数确定Y，或称，或称Y

21、部分函数依赖于部分函数依赖于X。v例：考虑关系模式：学生例：考虑关系模式：学生(学号学号,姓名姓名,课程课程,分数分数)。设有函数依赖：。设有函数依赖：学号学号姓名，姓名，学号学号,课程课程分数分数 学号学号,课程课程姓名姓名显然，若显然，若X仅包含一个仅包含一个属性，则属性，则XY意味着意味着Y完全函数依赖于完全函数依赖于X。v定义定义3：设：设R是关系模式，是关系模式，U是其属性集，是其属性集，X、Y、Z是是U的子集，的子集，YX不成立，不成立，Z-X、Z-Y、Y-X非空。若非空。若XY，YZ，则称，则称X传传递地函数确定递地函数确定Z，或，或称称Z传递地函数依赖传递地函数依赖X。v例例1

22、：考虑关系模式；学生：考虑关系模式；学生(学号学号,系系,主任主任)。设有函数依赖：学号设有函数依赖：学号系系主任。主任。由于系由于系学号不成立，主任学号不成立，主任-学号、主任学号、主任-系、系系、系-学号均非空，故主任传递地函数学号均非空，故主任传递地函数依赖于学号。依赖于学号。考虑关系模式；学生考虑关系模式；学生(身份证号身份证号,学号学号,系系)设有函数依赖：身份证号设有函数依赖：身份证号学号学号系；系；虽可推出身份证号虽可推出身份证号系，但不能说系传递地函数依系，但不能说系传递地函数依赖于身份证号。赖于身份证号。考虑关系模式；学生考虑关系模式；学生(学号学号,姓名姓名,性别性别)令令

23、X=学号，学号，Y=(姓名姓名,性别性别)，Z=姓名姓名。设有函数依赖设有函数依赖XY，虽然虽然YX不成立，且可推出不成立，且可推出YZ，但因，但因Z-Y为空，为空，故不能说故不能说Z传递地函数依赖于传递地函数依赖于X。v定义定义4：设：设R是关系模式，是关系模式，U是其属性集，是其属性集，K U。若。若K完全函数确定完全函数确定U，则称，则称K是是R的的候选键候选键。v包含在任意候选键内的属性称为包含在任意候选键内的属性称为键属性键属性，不是键属性的属性称为不是键属性的属性称为非键属性非键属性。在最简。在最简单的情况下，候选键只包含一个属性，在单的情况下，候选键只包含一个属性，在最复杂的情况

24、下，候选键包含关系模式的最复杂的情况下，候选键包含关系模式的所有属性所有属性,称为称为全键全键。v定义定义5 若关系若关系R的属性子集的属性子集X是另一关系是另一关系S的的候选键，则称候选键，则称X是是R关于关于S的的外部键外部键。主键和外部键主键和外部键描述了关系之描述了关系之间的联系间的联系学学号号 姓名姓名 班别班别0001 陈大陈大 01980002 赵二赵二 01980003 张三张三 02980004 李四李四 02981：学生名册：学生名册学学号课号号课号 成绩成绩0001 001 780001 002 870002 001 900002 002 652：学生选课表：学生选课表课

25、号课号 课名课名 教师教师001 政治政治 王东王东002 语文语文 马南马南003 数学数学 冯西冯西004 物理物理 杨北杨北3：课程清单：课程清单例例v下边三个关系实例表中，有下划线的属性下边三个关系实例表中，有下划线的属性子集是主键。子集是主键。v表表2的学号是关于表的学号是关于表1的外部键，课号是关的外部键，课号是关于表于表3的外部键。的外部键。三、数据依赖的公理系统三、数据依赖的公理系统v定义定义6：设关系模式：设关系模式 R 有属性集有属性集 U 和函数和函数依赖集依赖集 F。若对。若对 R 任一个使任一个使 F 成立的关系成立的关系实例实例 r，函数依赖，函数依赖 XY 都成立

26、，则称都成立，则称 F逻逻辑蕴含辑蕴含XY。vF蕴含蕴含XY意味着意味着关系实例只要满足关系实例只要满足F就必然满足就必然满足XY。学号学号系，系系，系系系主任主任 逻辑蕴涵逻辑蕴涵学号学号系主任，系主任，因为任意两元组，只要在学号等值，就必在系等值，因为任意两元组，只要在学号等值，就必在系等值，从而在系主任等值。从而在系主任等值。vArmstrong公理系统公理系统：设关系模式：设关系模式 R 具有具有属性集合属性集合 U 和函数依赖集合和函数依赖集合 F。Armstrong公理系统包含如下三条推理规则：公理系统包含如下三条推理规则：自反律自反律：若：若 Y X U，则，则F蕴含蕴含 XY.

27、(XY是平凡依赖是平凡依赖,与与F无关无关)增广率增广率：若：若F蕴含蕴含XY,Z U,则则F蕴含蕴含XZYZ.传递率传递率：若：若F蕴含蕴含XY,YZ,则则F蕴含蕴含XZ.v定理定理1：Armstrong推理规则是正确的。推理规则是正确的。(简简称为称为A规则规则)我们下面从函数依赖和蕴含的定义来证我们下面从函数依赖和蕴含的定义来证明明A公理的三条推理规则公理的三条推理规则tsYXY X UYZtsXXYYZtsXXYYZv定理定理2：三条推理规则：三条推理规则：合并规则合并规则:若若XY，XZ，则，则XYZ；伪传递规则伪传递规则:若若XY，YWZ，则，则XWZ；分解规则分解规则:若若XY，

28、Z Y，则，则XZ。v证证1：由：由XY和增广率得和增广率得XXY，由由XZ和增广和增广率得率得XYYZ，最后由传递率得，最后由传递率得XYZ.v证证2：由：由XY和增广率得和增广率得XWYW，由，由YWZ和传递率得和传递率得XWZ.v证证3：由：由Z Y及自反率得及自反率得YZ，再由，再由XY和和传递传递率得率得XZ.XY PQMN HKF+Fv引理引理1：XAB成立的充分必要条件是成立的充分必要条件是XA，XB.v引理引理1的推广形式是的推广形式是：XA1A2 Ak成立的成立的充分必要条件是充分必要条件是XAj(1 j k)v定义定义7：设关系模式：设关系模式 R 有属性集有属性集 U 和

29、函数和函数依赖集依赖集 F，由，由 F 蕴含的所有函数依赖称为蕴含的所有函数依赖称为 F的闭包的闭包F+。v定义定义8：设关系模式：设关系模式 R 有属性集有属性集 U 和函数和函数依赖集依赖集 F，X U。定义。定义X+=A|XA能由能由F通过通过Armstrong准则导出准则导出为为属性子集属性子集X 关关于函数依赖集于函数依赖集 F 的闭包的闭包。v引理引理2：设关系模式：设关系模式R有属性集有属性集U和函数依和函数依赖集赖集F，则，则XY能由能由F按按A规则导出的充要规则导出的充要条件是条件是Y X+.XABCXF+U例：关系模式例：关系模式R(A,B,C)，函数，函数依赖集依赖集FA

30、B,BC若若X=A,则则X+=A,B,C若若X=B,则则X+=B,C若若X=C,则则X+=C计算闭包计算闭包X+的算法：的算法：v 算法算法1：给出属性子集：给出属性子集 X 及函数依赖集及函数依赖集 F，计算计算X+。1.X0:=X;/*属性子集属性子集X0从从X开始沿依赖集开始沿依赖集F扩张扩张*/2.B:=A|VW F,V X0,A W;/*扫描扫描F中决定因素中决定因素V含于含于X0的函数依赖的函数依赖VW，取，取W的所有属性的所有属性*/3.X1:=X0 B;4.if X1 X0 then X0:=X1;goto 2else X+:=X1 endif例：闭包的计算举例例：闭包的计算举

31、例v已知关系模式已知关系模式R的属性集合的属性集合U=A,B,C,D,E,函数依赖集合函数依赖集合F=ABC,ACB,BD,CE,ECB，求，求(AB)+.v定理定理3：上面的算法能够正确的计算出：上面的算法能够正确的计算出 X 关关于于 F 的闭包的闭包X+.v定理定理4：Armstrong公理系统是有效且完备公理系统是有效且完备的。的。v定义定义9：设：设G、F是两个函数依赖集，若是两个函数依赖集，若G+=F+，则称，则称G、F等价。等价。v引理引理3：函数依赖集：函数依赖集G、F等价的充要条件等价的充要条件是：是：F G+，G F+。A公理的有效性是指公理的有效性是指:由由F出出发发,按

32、按A公理推导的函数依公理推导的函数依赖一定在赖一定在F+中中;A公理的完备性是指：公理的完备性是指：F+中所有函数依赖必可中所有函数依赖必可由由F出发按出发按A公理推出公理推出.v定义定义10：满足以下条件的函数依赖集：满足以下条件的函数依赖集F称为称为极小函数依赖集极小函数依赖集:F 任一依赖的右边是简单属性；任一依赖的右边是简单属性；XA F,F-XA与与F不等价；不等价；XA F，Z X(真子集真子集)，(F-XA)ZA 与与 F 不等价。不等价。例例：v关系模式关系模式S:U=S#,SD,MN,CN,G,F=S#SD,SDMN,(S#,CN)G,F=S#SD,S#MN,SDMN,(S#

33、,CN)G,(S#,SD)SD.F是最小覆盖是最小覆盖 F不是最小覆盖不是最小覆盖v定理定理5：每个函数依赖集：每个函数依赖集F都等价于一个极都等价于一个极小函数依赖集。小函数依赖集。v例：求例：求A-B,B-A,B-C,A-C,C-A的的极小函数依赖集极小函数依赖集 结果结果1：A-B,B-C,C-A 结果结果2：A-B,B-A,A-C,C-A四、关系模式的规范形式四、关系模式的规范形式v基于函数依赖概念的关系模式的范式基于函数依赖概念的关系模式的范式(简称简称范式范式)主要有四种，即主要有四种，即第一范式、第二范式、第一范式、第二范式、第三范式和第三范式和BCNF范式范式.v关系模式满足这

34、些约束可在一定程度上避关系模式满足这些约束可在一定程度上避免本节开头提到的四个异常问题：免本节开头提到的四个异常问题：冗余问冗余问题、插入问题、更新问题和删除问题题、插入问题、更新问题和删除问题。v第一范式定义第一范式定义：若关系模式每个属性的值若关系模式每个属性的值都是不可分的简单数据项，则称该关系模都是不可分的简单数据项，则称该关系模式为满足第一范式，式为满足第一范式，简写为简写为1NF.v第二范式定义第二范式定义：满足：满足1NF的关系模式，若的关系模式，若所有非主属性完全地依赖于键所有非主属性完全地依赖于键，则称之为，则称之为满足第二范式，满足第二范式，简写为简写为2NF.v反例反例:

35、学生学生(学号学号,系名系名,系主任系主任,课名课名,成绩成绩)S(S#,SD,MN,C#,G)F=(S#,C#)-G,S#-SD,SD-MNv该例存在的问题该例存在的问题:插入问题插入问题,删除问题删除问题,冗余冗余和更新问题和更新问题解决方法：解决方法：分解分解 S (S#,SD,MN,C#,G)成为两个关系模式成为两个关系模式 使得分解后的子关系满足第二范式使得分解后的子关系满足第二范式分解结果：分解结果：SC(S#,C#,G),SSS(S#,SD,MN)Fsc=(S#,C#)-G Fsss=S#-SD,SD-MN2NF部分解决了各种问题部分解决了各种问题v第三范式定义第三范式定义：满足

36、：满足2NF的关系模式，若的关系模式，若不存在非键属性传递地依赖于任何候选键，不存在非键属性传递地依赖于任何候选键，则称之为满足第三范式，则称之为满足第三范式，简写为简写为3NF.反例：反例：SC(S#，C#，G)，SSS(S#，SD，MN)Fsc=(S#，C#)-G Fsss=S#-SD，SD-MN解决方法：解决方法：把把SSS分解为满足第三范式的多个子关系模式分解为满足第三范式的多个子关系模式分解结果分解结果:SSD(S#,SD),SSM(SD,MN)vBCNF范式定义范式定义：满足：满足1NF的关系模式，若的关系模式，若每个函数依赖每个函数依赖XY(Y不是不是X的子集的子集)的决定的决定

37、因素因素X都含有候选键，则称之为都含有候选键，则称之为满足满足BCNF范式范式.例例v关系模式关系模式 Course(cno,cname,pcno)是否满足是否满足2NF？是否满足是否满足3NF？是否满足是否满足BCNF？v关系模式关系模式 Student(sno,sname,sdept,sage)其中学生的姓名也满足唯一性其中学生的姓名也满足唯一性v关系模式关系模式 选课选课(学生，教师，课程学生，教师，课程)每个教师只教一门课程每个教师只教一门课程 每门课程有多个教师授课每门课程有多个教师授课 每个学生选定某课程，就对应一个固定每个学生选定某课程，就对应一个固定的教师的教师例例候选码候选码

38、(学生，课程学生，课程)(学生，教师学生，教师)函数依赖关系有：函数依赖关系有：(学生学生,教师教师)课程课程(学生学生,课程课程)教师教师教师教师课程课程v存在什么问题？冗余？插入或删除异常？存在什么问题？冗余？插入或删除异常？v是否满足是否满足3NF？v是否满足是否满足BCNF？v解决方法：解决方法：把选课关系模式分解为满足把选课关系模式分解为满足BCNF的多个的多个子关系模式子关系模式 选课选课1(学生，教师学生，教师)授课授课2(教师，课程教师，课程)v满足满足2NF：每一个每一个非主属性非主属性都都完全完全依赖于键依赖于键v满足满足3NF：不仅每一个不仅每一个非主属性非主属性完全完全

39、依赖于键依赖于键 并且每一个并且每一个非主属性非主属性不传递不传递依赖于键依赖于键v满足满足BCNF：非主属性非主属性对键的对键的完全的和不传递的完全的和不传递的依赖依赖 主属性主属性对键的对键的完全的和不传递的完全的和不传递的依赖依赖vBCNF-3NF-2NF-1NFv如果一个关系数据库的所有关系模式都属如果一个关系数据库的所有关系模式都属于于BCNF，那么在函数依赖范围内，它已达，那么在函数依赖范围内，它已达到了最高的规范化程度，已消除了到了最高的规范化程度，已消除了插入和插入和删除异常删除异常。v第四范式和多值依赖第四范式和多值依赖v例：设学校中某一门课程由多个教师讲授，例：设学校中某一

40、门课程由多个教师讲授，每门课程的参考书是相同的。考虑如下关每门课程的参考书是相同的。考虑如下关系模式：系模式：v授课授课(课程，教师，参考书课程，教师，参考书)v存在哪些问题？存在哪些问题？课程课程教师教师参考书参考书物理物理张明张明普通物理学普通物理学物理物理张明张明光学原理光学原理物理物理张明张明物理习题集物理习题集数学数学张平张平微分方程微分方程数学数学李勇李勇微分方程微分方程化学化学张强张强无机化学无机化学化学化学王薇王薇有机化学有机化学化学化学张强张强无机化学无机化学化学化学王薇王薇有机化学有机化学v多值依赖多值依赖：设：设R是一个具有属性集合是一个具有属性集合U的关的关系模式，系模

41、式，X,Y和和Z是是U的子集，的子集，并且并且 Z=U-X-Y，多值依赖，多值依赖XY成立当且仅当成立当且仅当对对R的任意关系的任意关系r，r在在(X,Z)上的每个值对上的每个值对应一组应一组Y的值，这组值仅决定与的值，这组值仅决定与X，而与，而与Z值无关。值无关。v例子中的问题是由于它具有多值依赖的数例子中的问题是由于它具有多值依赖的数据依赖而引起的。据依赖而引起的。v4NF：设：设R是一个关系模式，是一个关系模式，D是是R上的多上的多值依赖集合。如果对于值依赖集合。如果对于R的每个多值依赖的每个多值依赖XY(其中，其中，Y-X非空，非空，XY为包含为包含R的全的全部属性部属性)，X都含有都

42、含有R的候选键，则的候选键，则R是第四是第四范式关系模式，简记为范式关系模式，简记为4NF。v授课授课(课程，教师，参考书课程，教师，参考书)是否满足是否满足4NF？课程课程教师教师是多值依赖是多值依赖 关系的候选键是全键关系的候选键是全键 故而，不满足故而，不满足4NFv问题在于问题在于：关系模式有多值依赖，却不满足关系模式有多值依赖，却不满足4NFv问题的解决问题的解决：授课授课(课程，教师课程，教师)，参考书，参考书(课程，参考书课程，参考书)本章概要本章概要v形成初始关系数据库模式形成初始关系数据库模式v关系数据库设计理论关系数据库设计理论v关系模式作规范化方法关系模式作规范化方法 v

43、关系模式的优化关系模式的优化v定义关系完整性和安全性约束定义关系完整性和安全性约束v逻辑数据库的性能估计逻辑数据库的性能估计6.3关系模式规范化方法关系模式规范化方法v关系模式可划分为关系模式可划分为 静态静态关系模式关系模式 动态动态关系模式关系模式v关系模式的规范化关系模式的规范化关系模式的分解。关系模式的分解。具有具有无损连接性无损连接性要要保持函数依赖保持函数依赖v例例1，设，设 R 是一个关系模式。是一个关系模式。属性集合属性集合U=学号学号,系系,系主任系主任，函数依赖集合函数依赖集合F=学号学号系，系系，系系主任系主任。v分解为分解为R1(学号学号),R2(系系),R3(系主任系

44、主任);v分解为分解为R1(学号，系学号，系),R2(学号，系主任学号，系主任);v分解为分解为R1(学号，系学号，系),R2(系，系主任系，系主任);学号学号 系系系主任系主任S1D1张红张红S2D1张红张红S3D2李微李微S4D3王力王力一、分解的无损连接性一、分解的无损连接性v关系模式关系模式 R(U,F)的一个分解的一个分解是指是指 =R1,R2,Rn v其中其中Ri的属性集是的属性集是Ui，而且，而且U=UivFi 是是 F 在在 Ui 上的投影上的投影Fi=XY|XY F+,X,Y Ui v关系实例的分解的投影连接关系实例的分解的投影连接：设设=R1Rn是是R的一个分解，的一个分解

45、，r是是R的一个实例，称的一个实例，称 m(r)=R1(r)Rn(r)v是是r在在 中各子模式的投影连接。中各子模式的投影连接。v若对任意实例若对任意实例 r 有有 r=m(r)，则称则称分解分解 具无损连接性具无损连接性。判别一个分解的无损连接性判别一个分解的无损连接性输入：关系模式输入：关系模式R(A1,A2,An)，R的分解的分解 =R1,R2,Rk.输出：输出：分解是否具有无损连接性。分解是否具有无损连接性。A1A2AnR1R2Rkfor i=1 to k do for j=1 to n do if Ri 包含属性包含属性Aj then Si,j=aj;else Si,j=bij;En

46、dfor;Endfor;v依次考虑函数依赖集依次考虑函数依赖集F的每个函数依赖的每个函数依赖XY，在，在X对应的列上考虑相同元素所在对应的列上考虑相同元素所在的行的行,在在Y对应列上考虑上述行的元素子列，对应列上考虑上述行的元素子列，并改为相同符号。并改为相同符号。v如果矩阵如果矩阵S中存在一行全为中存在一行全为a类符号，则类符号，则分分解具有无损连接。否则，不具有无损连接。解具有无损连接。否则，不具有无损连接。算法的例题算法的例题v设关系设关系R(A,B,C,D,E)有函数依赖集有函数依赖集F=AC,BC,CD,DEC,CEA，v试判断模式分解试判断模式分解=R1(AD),R2(AB),R3

47、(BE),R4(CDE),R5(AE)是否具有无损连接性。是否具有无损连接性。(1)=R1,R2是关系模式是关系模式R的一个分解；的一个分解；(2)U1、U2和和U分别是分别是R1、R2和和R的属性集的属性集合；合；(3)F是是R的函数依赖集，的函数依赖集，则则 具具无损连接性的充要条件是无损连接性的充要条件是U1 U2U1-U2 F+或或 U1 U2U2-U1 F+。定理定理2二、函数依赖保持性二、函数依赖保持性v定义定义5：设关系模式：设关系模式R具有属性集具有属性集U和函数和函数依赖集依赖集 F，=(R1,Rk)是是 R 的一个分解，的一个分解，Ui 是是 Ri 的属性集，的属性集，Fi

48、 是是 F 在在 Ui 的投影。若的投影。若F+=(Fi)+，则称分解，则称分解 具函数依赖保持性。具函数依赖保持性。函数依赖保持性的判断算法函数依赖保持性的判断算法(1)for 每个每个XY F do if Y 不属于不属于X关于关于G的闭包的闭包 then 输出输出 F+G+endfor;(2)输出输出F+=G+停止停止.输入：函数依赖集合输入：函数依赖集合F,F1,F2,Fk，记，记G=(Fi)输出：是否输出：是否F+=G+关系模式分解的例子关系模式分解的例子学生学生(学号学号,系属系属,主任主任)F=学号学号系属系属，系属系属主任主任分解分解1：1=P(学号学号)，Q(系属系属)，R(

49、主任主任).F1=F2=F3=,G+=(F1 F2 F3)+=，因因F+G+，故故 1不具有函数依赖保持性。不具有函数依赖保持性。分解分解2：2=P(学号，系属学号，系属)，R(学号，主任学号，主任).F1=学号学号系属系属，F2=学号学号主任主任,因因G+缺少缺少系属系属主任主任,故故F+G+,从而从而 2不具有函数依赖保持性。不具有函数依赖保持性。分解分解3：3=P(学号，系属学号，系属)，R(系属，主任系属，主任).F1=学号学号系属系属，F2=系属系属主任主任，容易看到容易看到G=(F1 F2)=F,故故F+=G+，故故 3具有函数依赖保持性。具有函数依赖保持性。三、关系模式的分解算法

50、三、关系模式的分解算法v这里仅讨论有关这里仅讨论有关3NF、BCNF的分解算法。的分解算法。研究关系模式的分解，必须考虑分解是否研究关系模式的分解，必须考虑分解是否满足无损连接性和函数依赖保持性。满足无损连接性和函数依赖保持性。分解算法分解算法 无损连接性无损连接性 依赖保持性依赖保持性3NF(法法1)不保证不保证 保证保证3NF(法法2)保证保证 保证保证 BCNF 保证保证 不保证不保证v输入输入：关系模式：关系模式R(U,F)v输出输出：具有函数依赖保持性的分解具有函数依赖保持性的分解，中的所有子关系中的所有子关系模式都满足模式都满足3NFv方法方法：对函数依赖集合对函数依赖集合F，找到