第五章关系数据库理论.ppt

《第五章关系数据库理论.ppt》由会员分享，可在线阅读，更多相关《第五章关系数据库理论.ppt（43页珍藏版）》请在三一文库上搜索。

1、安财信工学院计算机系 第五章 关系数据库理论 安财信工学院计算机系 关系数据库设计中存在的问题 v示例： 考虑为管理职工的工资信息而设计一个关系模式。 安财信工学院计算机系 存在的问题分类 v插入异常 如果没有职工具有8级工资，则8级工资的工资数额就难以插入。 v删除异常 如果仅有职工赵明具有4级工资，如果将赵明删除，则有关4级工资 的工资数额信息也随之删除了。 v数据冗余 职工很多，工资级别有限，每一级别的工资数额反复存储多次。 v更新异常 如果将5级工资的工资数额调为620，则需要找到每个具有5级工资的 职工，逐一修改。 安财信工学院计算机系 关系数据库设计中存在的问题 v解决之道：模式分

2、解 安财信工学院计算机系 有关学生的关系模式S(S# , SN , SD , DEAN , C# , G) v问题：它有哪些数据冗余？ v问题：它有哪些不良的数据依赖？ 安财信工学院计算机系 讨论关系数据库逻辑设计问题: 1. 针对一个具体问题，应该 如何构造一个适合于它的数据库模式? 2. 即应该构造几个关系模式? 3. 每个关系由哪些属性组成? 安财信工学院计算机系 下面首先回顾一下关系模型的形式化定义。 v一个关系模式应当是一个五元组 R（U, D, DOM, F） v说明: 关系名R，它是符号化的元组语义； 一组属性U； 属性组U中属性所来自的域D； 属性到域的映射DOM； 属性组U上

3、的一组数据依赖F。 由于D和DOM对模式设计关系不大,因此我们在本章中把关系 模式看作是一个三元组：RU,F 当且仅当U上的一个关系r满足F时,r称为关系模式RU,F的 一个关系。 安财信工学院计算机系 v第一范式 关系,作为一张二维表,我们对它有一个最起码的要求：每一个分量必 须是不可分的数据项。满足了这个条件的关系模式就属于第一范式（ 1NF）。 我们的任务是研究模式设计，研究设计一个“好”的（没有“毛病”的） 关系模式的办法。 v数据依赖 数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的 相互关系。它是现实世界属性间相互联系的抽象,是数据内在的性质, 是语义的体现。 现在人们

4、已经提出了许多种类型的数据依赖,其中最重要的是函数依赖 (Functional Dependency简记为FD)和多值依赖(Multivalued Dependency简记为MVD)。 比如描述一个学生的关系,可以有学号(SNO),姓名(SNAME),系 名(SDEPT)等几个属性。由于一个学号只对应一个学生,一个学 生只在一个系学习。 因而当“学号”值确定之后,姓名和该生所在系的值也就被唯一地 确定了。就象自变量x确定之后,相应的函数值f(x)也就唯一地确 定了一样，我们说SNO函数决定SNAME和SDEPT,或者说 SNAME，SDEPT函数依赖于SNO,记为 SNOSNAME,SNOSD

5、EPT。 安财信工学院计算机系 建立一个描述学生的数据库 v分析: 面临的对象有 v学生(用学号SNO描述) v系(用系名SDEPT描述) v系负责人(用其姓名MN描述) v课程(用课程名CNAME描述) v成绩(G)。 现实世界的已知事实告诉我们 v1一个系有若干学生,但一个学生只属于一个系； v2一个系只有一名(正职)负责人； v3一个学生可以选修多门课程,每门课程有若干学生选修； v4每个学生学习每一门课程有一个成绩； 安财信工学院计算机系 v如果只考虑函数依赖这一种数据依赖,我们就得到了 一个描述学校的数据库模式SU，F，它由一个 单一的关系模式构成： U = SNO，SDEPT，MN

6、，CNAME，G F = SNOSDEPT，SDEPTMN，(SNO，CNAME)G 这组函数依赖如图5.l所示。 SNOCNAME SDEPT MN G 安财信工学院计算机系 前面的学生模式有下述三个“毛病”： v1.插入异常 如果一个系刚成立尚无学生,或者虽然有了学生但尚未安排课 程。那么我们就无法把这个系及其负责人的信息存入数据库 。 v2.删除异常 反过来,如果某个系的学生全部毕业了,我们在删除该系学生 选修课程的同时,把这个系及其负责人的信息也丢掉了。 v3.冗余太大 比如,每一个系负责人的姓名要与该系每一个学生的每一门功 课的成绩出现的次数一样多。这样,一方面浪费存储,另一方 面系

7、统耍付出很大的代价来维护数据库的完整性。比如某系 负责人更换后,就必须逐一修改有关的每一个元组。 安财信工学院计算机系 为什么会发生插入异常和删除异常呢 ? v这是因为这个模式中的函数依赖存在某些不好的性 质。假如我们把这个单一的模式改造一下,分成三个 关系模式： S（SNO,SDEPT, SNOSDEPT）； SG（SNO,CNAME,G, (SNO,CNAME)G）； DEPT（SDEPT,MN, SDEPTMN）； 这三个模式都不会发生插入异常、删除异常的毛病,数据 的冗佘也得到了控制。 一个模式的函数依赖会有哪些不好的性质,如何改造一个 不好的模式,这就是下一节规范化理论讨论的内容。

8、安财信工学院计算机系 定义5.1函数依赖 v定义5.1 设R(U)是属性集U上的关系模式。X,Y是U的子集。若对于R(U) 的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等, 而在Y上的属性值不等,则称X函数确定Y或Y函数依赖于X，记作XY。 v例如： 每个学生有且只有一个专业，即“学号”决定“专业” 。 因此，“专业”函数依赖于“学号”。学号专业 注意，AB时，A和B的关系通常是N：1。即有许多学生选修同一 个专业，但一个人只能有一个专业。 v函数依赖可包含属性组，如，（学号，课程名）成绩 v区别情况： 若X(Y,Z)，则XY,XZ。 v比如，学号（姓名，专业），则学号姓名，

9、学号专业 若（X,Y)Z，一般情况下，XZ和YZ都不成立 v比如， （学号，课程名）成绩，但“学号”或“课程名”本身都不能单独 决定“成绩” 安财信工学院计算机系 函数依赖：设R(U)是属性集U上的关系模式，X , Y U ， r是R(U) 上的任意一个关系，如果成立对t , s r， 若tX = sX，则tY = sY，那么称“X函数决定Y”，或 “Y函数依赖于X”，记作XY。称X为决定因素。 如：S# SN， （S#，C#） G 如果X Y，但Y X，则称其为非非平凡的函数依赖平凡的函数依赖，否 则称为平凡的函数依赖平凡的函数依赖。 如（S#，SN） SN是平凡的函数依赖 安财信工学院计算

10、机系 定义5.2 完全函数依赖 v定义5.2 在R(U)中，如果XY，且对于任意X的真 子集X，都有XY ，则称Y对X完全函数依赖， 记作X Y ，否则称为Y对X部分函数依赖，记 作X Y。 例如：（S#，C#） Grade 找出S中的另一部分函数依赖。 U = SNO，SDEPT，MN，CNAME，G F = SNOSDEPT，SDEPTMN，(SNO，CNAME)G 安财信工学院计算机系 定义5.3 传递函数依赖 v定义5.3 在R(U)中,如果XY,(Y X)，Y X,YZ,则称Z 对X传递函数依赖。 v加上条件YX,是因为如果YX,则XY,实际上是直接函 数依赖而不是传递函数依赖。 v

11、例如： S（SNO,SDEPT, SNOSDEPT）； SG（SNO,CNAME,G, (SNO,CNAME)G）； DEPT（SDEPT,MN, SDEPTMN） 则，SNO SDEPT，SDEPT MN v想一想还有没有别的例子？ 安财信工学院计算机系 v检验：AC？CA？ABD？ v辨识： 满足依赖的关系： v依赖在模式的某个关系实例上成立。 模式上成立的依赖： v依赖在模式的所有关系实例上都成立。 ABCD a1b1c1d1 a1b2c1d2 a2b2c2d2 a2b3c2d3 a3b3c2d4 安财信工学院计算机系 ABC 123 423 533 练习 找出可能的函数依赖。 安财信工

12、学院计算机系 定义码 v定义5.4 设K为RU，F中的属性或属性组合，若K U则 K为R的候选码候选码（Candidate key）。若候选码多于一个，则 选定其中的一个为主码主码（Primary key）。 v包含在任何一个候选码中的属性，叫做主属性主属性(Prime attribute)。 不包含在任何码中的属性称为非主属性非主属性(Nonprime attribute)或非 码属性(Non-key attribute)。最简单的情况,单个属性是码。最极端 的情况,整个属性组是码,称为全码全码(All-key)。 v例如； 关系模式R(P,W,A),属性P表示演奏者,W表示作品,A表示听众

13、。假设 一个演奏者可以演奏多个作品,某一作品可被多个演奏者演奏。听众也 可以欣赏不同演奏者的不同作品,这个关系模式的码为(P,W,A),即All- key。 安财信工学院计算机系 定义5.5 外码 v定义5.5 关系模式R中属性或属性组X并非R的码， 但X是另一个关系模式的码，则称 X是R的外部码 (Foreign key)也称外码。 主码与外部码提供了一个表示关系间联系的手段。 v主码：若R(U , F)有多个候选码，则可以从中选定 一个作为R的主码。 v主属性：包含在每一个候选码中的属性，称作主属 性。 v全码：关系模式的码由整个属性组构成。 安财信工学院计算机系 范例 关系模式S(S#

14、, SN , SD , DEAN , C# , G) 主码：（S#，C#） 函数依赖： （S#，C#）G S# SN，（S#，C#）SN S# SD，（S#，C#）SD SD DEAN 安财信工学院计算机系 范式 v定义 范式是对关系的不同数据依赖程度的要求。 通过模式分解将一个低级范式转换为若干个高级 范式的过程称作规范化（概念的纯粹化）。 1NF 2NF 3NF 4NF BCNF 5NF 安财信工学院计算机系 定义 1NF v定义 关系中每一分量不可再分。即不能以集合、序列等作为 属性值。 S#C# S1C1，C2，C3 S#C# S1C1 S1C2 S1C3 安财信工学院计算机系 1NF

15、 分量是否需要再分，与具体应用有关！如果用 到值的一部分，则需要进一步分割。 如果只是查询出生日期，则它满足1NF。 如果查询两人生日是否相同，则只比较月、日， 需要将生日分解，就不满足1NF。 如果比较两人的生肖呢？ 姓名出生日期 王军68.7.10 张立69.7.10 李明80.3.28 姓名年月日 王军687.10 张立697.10 李明803.28 安财信工学院计算机系 关系模式 S(S# , SN , SD , DEAN , C# , G) v不良特性 插入异常：如果学生没有选课，关于他的个人信息及所 在系的信息就无法插入。 删除异常：如果删除学生的选课信息，则有关他的个人 信息及所

16、在系的信息也随之删除了。 更新异常：如果学生转系，若他选修了k门课，则需要修 改k次。 数据冗余：如果一个学生选修了k门课，则有关他的所在 系的信息重复 安财信工学院计算机系 2NF v定义5.6 若R1NF，且每个非主属性完全依赖于码，则称R2NF。（即消除 非主属性对码的部分依赖）。 关系模式 S( S# , C# , SN , SD , DEAN , G) S2NF，因为（S#，C#） SN， （S#，C#） CN v改造 非主属性有两种，一种完全依赖于码，一种部分依赖于码。 将S分解为：SC(S# , C# , G) S_SD(S# , SN , SD , DEAN) v练习 关系模式

17、R（A，B，C，D），码为AB，给出它的一个函数依赖集 ，使得R属于1NF而不属于2NF。 安财信工学院计算机系 S_SD(S# , SN , SD , DEAN) v不良特性 插入异常：若系中没有学生，则有关该系的信息就无法插入。 删除异常：如果学生全部毕业了，则在删除学生信息的同时有 关该系的信息也随之删除了。 更新异常：如果学生转系，不但要修改SD，还要修改DEAN， 如果换系主任，则该系每个学生元组都要做相应修改。 数据冗余：每个学生都存储了所在系的系主任的信息。 安财信工学院计算机系 定义 3NF v定义5.7 关系模式R中，若不存在这样的码X，属性组Y及 非主属性非主属性Z(Z Y

18、)，使得下式成立， XY , YZ , YX 则称R3NF（即消除非主属性对码的传递依赖）。 如S_SD 3NF，因为有S#SD，SDDEAN v改造 将S分解为：STUDENT(S# , SN , SD) DEPT(SD , DEAN) 安财信工学院计算机系 3NF v练习 关系模式R（A，B，C，D），码为AB，给出它 的一个函数依赖集，使得R属于2NF而不属于 3NF。 安财信工学院计算机系 示例 vSPC(S# , P# , C#)，即(学号，教师编号，课程号) 假设每位老师只教授一门课， 则P# C# （S#，P#） C# （S#，C#） P#，某学生选定一门课，就对应一位老师 （S

19、#，P#），（S#，C#）为候选码。 v思考： 这三个属性是否都是主属性？ SPC 3NF ？请参考课本Page 176上的3NF定义 提示： v注意定义5.7中的一词“非主属性” 安财信工学院计算机系 v不良特性 插入异常：如果没有学生选修某位老师的任课，则该 老师担任课程的信息就无法插入。 删除异常：删除学生选课信息，会删除掉老师的任课 信息。 更新异常：如果老师所教授的课程有所改动，则所有 选修该老师课程的学生元组都要做改动。 数据冗余：每位学生都存储了有关老师所教授的课程 的信息。 v症由：主属性对码的不良依赖。 安财信工学院计算机系 定义 BCNF v定义 5.8 关系模式R中，对于

20、属性组X，Y，若XY 且Y X时X必含有码，则R BCNF。 即每一个决定因素都包含码。 如SPC BCNF，因为P# C#，而P#不是码。 v改造 将S分解为（S#，P#），（P#，C#）。 v思考 关系模式SCO(S# , C# , ORDER)，表示学生选修课程的名次， 有函数依赖(S#，C#) ORDER， 假定同一课程每个名次只有一 人则(C#，ORDER) S#，它属于哪个范式？它的码是什么？该 关系模式有何不良特性？ 关系模式STJ（S#，T#，J#），一个教师只教一门课，一门课有 若干教师，则(S#,J#)T#,(S#,T#)J#,T#J#。STJ BCNF 安财信工学院计算机

21、系 v例如 ：关系模式TEACH（C#，P#，B#），一门课程由多个教员担 任，一门课程使用相同的一套参考书。它的码是（C#，P#，B#）， 所以属于BCNF。 C#P#B# C1P1B1 C1P1B2 C1P2B1 C1P2B2 C2P1B3 C2P1B4 C2P3B3 C2P3B4 C#P#B# C1P1,P2B1,B2 C2P1,P3B3,B4 v不良特性 插入异常：当某门课程增加一名教 员时，该门课程有多少本参考书就 必须插入多少个元组；同样当某门 课程需要增加一本参考书时，它有 多少个教员就必须插入多少个元组 。 删除异常：当删除一门课程的某个 教员或者某本参考书时，需要删除 多个元

22、组。 更新异常：当一门课程的教员或参 考书作出改变时，需要修改多个元 组。 数据冗余：同一门课的教员与参考 书的信息被反复存储多次。 安财信工学院计算机系 定义多值依赖 v定义 描述型：关系模式R(U)，X、Y、Z U，并且Z = U X Y，多值依赖X Y成立当且仅当对R(U)的任一关系r ，给定的一对（x，z）值有一组Y的值，这组值仅仅决定 于x值而与z值无关。 如在关系模式TEACH中，对(C1 , B1)有一组P#值(P1 , P2)，对(C1 , B2)也有一组P#值(P1 , P2)，这组值仅取决 于C#的取值，而与B#的取值无关。因此，P#多值依赖于 C#，记作C# P#，同样有

23、C# B#。 安财信工学院计算机系 多值依赖() 形式化：关系模式R(U)，X、Y、ZU，Z=UX Y，对于 R(U)的任一关系r，若存在元组t1，t2，使得t1X = t2X ，那么就必然存在元组t3，t4，使得： t3X = t4X = t1X = t2X t3Y = t1Y， t4Y = t2Y t3Z = t2Z， t4Z = t1Z 则称Y多值依赖与X，记作X Y。 若(C#, P#, B#)满足C#P#，含有元组t1=(C1, P1, B1) ，t2=(C1, P2, B2)，则也一定含有元组t3=(C1, P1, B2)， t2=(C1, P2, B1)。 安财信工学院计算机系

24、多值依赖() v找出关系上所满足的多值依赖。 ABC a1b1c1 a1b1c2 a2b1c1 a2b1c3 CB？若使BC成立，需加入哪些元组？ ABC a1b1c1 a2b1c1 t1 t2 ABC a2b1c1 a1b1c1 ABC t2.At1.Bt1.C t1.At2.Bt1.C t3 t4 t3 t4 安财信工学院计算机系 多值依赖() v性质 多值依赖具有对称性，即 若XY，则XZ，其中Z=UXY。 函数依赖是多值依赖的特例，即 若XY，则XY。 若XY，UXY=，则称XY为平凡的多 值依赖。 安财信工学院计算机系 多值依赖 Vs 函数依赖() v区别 函数依赖规定某些元组不能出

25、现在关系中，也称为相等 产生依赖。 多值依赖要求某种形式的其它元组必须在关系中，称为 元组产生依赖。 v有效性范围 XY的有效性仅决定于X、Y属性集上的值，它在任何属 性集W（XY W U）上都成立。 若XY在R(U)上成立，则对于任何Y Y，均有XY 成 立。 安财信工学院计算机系 多值依赖 Vs 函数依赖() XY的有效性与属性集范围有关。 XY在属性集W（XY W U）上成立，但在U上不 一定成立。 XY在U上成立 XY在属性集W（XY W U ）上成立。 若在R(U)上，XY在属性集W(XY W U)上成立， 则称XY为R(U) 的嵌入式多值依赖。 若XY在R(U)上成立，则不能断言对

26、于Y Y，是否有 XY 成立。 安财信工学院计算机系 4NF v定义 关系模式R 1NF，若XY（YX）是非平 凡的多值依赖，且X含有码，则称R4NF。 如关系模式CPB，C#P#，C#B#，码为(C#, P#, B#)，所以CPB4NF。 如果一门课Ci有m个教员，n本参考书，则关系中分量为 Ci的元组共有mn个，数据冗余非常大。 v改造 将CPB分解为CP（C#，P#），CB（C#，B#），在分 解后的关系中分量为Ci的元组共有m + n个。 安财信工学院计算机系 范式之间的关系() v3NF 2NF 反证：若R3NF， 但R2NF，则按2NF定义，一定有非 主属性部分依赖于码， 设X为R

27、的码，则存在X的真子集X，以及非主属性Z（Z X），使得XZ。 于是在R中存在码X，属性组X，以及非主属性Z（Z X) ，使得XX， XZ，XX成立，这与R3NF矛盾。 所以R2NF。 安财信工学院计算机系 范式之间的关系() vBCNF 3NF 反证：若RBCNF， 但R3NF，则按3NF定义，一定有 非主属性对码的传递依赖，于是存在： R的码X ，属性组Y，以及非主属性Z（Z Y），使得 XY， Y Z，YX成立 。 由YZ，按BCNF定义，Y含有码，于是YX成立，这 与YX矛盾。 所以R3NF。 v4NF BCNF 安财信工学院计算机系 函数依赖 非平凡的函数依赖 平凡的函数依赖 决定因素 完全函数依赖 部分函数依赖 传递函数依赖 候选码 主码 主属性 非主（码）属性 全码 外部码 多值依赖 非平凡的多值依赖 总结：总结： 关系数据理论关系数据理论 1NF 2NF 3NF BCNF 4NF 5NF