关系数据模式设计2PPT课件

1、为什么使用范式？ 如何得到“好”的数据库设计？ 判断一个关系是否“好”，是否有“坏”的数据依赖 属于哪一级别的范式？ 高级范式与低级范式相比，是“更好”的关系，因为“坏”数据依赖更少第1页/共63页范式 范式 满足一定要求的所有关系模式的全集 范式级别(从低级到高级) 第一范式 (1NF) 第二范式 (2NF) 第三范式 (3NF) BC范式 (BCNF) 第四范式 (4NF) 范式越高级，代表的关系模式就越“好”，要满足的要求也就越高第2页/共63页范式 不同范式之间的联系 4NF BCNF 3NF 2NF 1NF 高级范式是低级范式的子集 范式越高，满足的要求也就越高；满足高要求的关系肯定

2、能够满足低要求，所以高级范式中的关系模式肯定也在低级范式中1NF2NF3NFBCNF4NF第3页/共63页第一范式 要求 关系模式的每个属性都是原子的 原子属性 属性值不可再分 例如. age, sex 非原子属性 属性值可以再分，包括 复合属性，值是一个结构体。例如parents， 多值属性，值是一个集合。例如phone-numbers。第4页/共63页第一范式 例子 下面关系中，哪些在1NF中，哪些不在？学号学号姓名姓名课程号课程号S1JohnC1，C2，C3S2SmithC3，C5Student学号学号姓名姓名父母父母S1John(Tom, Angie)S2Smith (Mike, So

3、phie)Student学号学号姓名姓名性别性别年龄年龄S1JohnMale22S2SmithMale23Student第5页/共63页一些术语和解释 例子关系 R(ABCDE)。主键ABC，也是唯一候选键。 主属性（键属性） 一个属性，出现在某个候选键中 例如：A, B, C 非键属性（非键属性） 一个属性，不出现在任何一个候选键中 例如：D, E 键的一部分 就是候选键的真子集。 例如，AB, BC, AC, A, B, C等等第6页/共63页一些术语和解释 超键（含键） 具有唯一性的属性集。 从超键去掉多余属性，即得到候选键。所以直观上看，超键必然包含一个候选键。 例如：ABC, ABC

4、D, ABCE, ABCDE都是超键第7页/共63页第二范式 要求 关系模式在1NF中 每一个非键属性完全函数依赖于键 判断方法：检查每个非键属性A所依赖的X（即XA），若X是候选键的一部分，违反2NF。第8页/共63页第二范式 例子 以下关系在1NF中？在2NF中？为什么？ 它们有我们以前讨论过的四个问题吗？学号学号姓名姓名课程号课程号课程名课程名S1JohnC1databaseS2SmithC1databaseS1JohnC2algorithmS2SmithC2algorithmSC学号学号 课程号课程号 成绩成绩S1C177S2C180S1C290S2C282SC第9页/共63页第三范式

5、 要求 关系在1NF中 每个非键属性都非传递依赖于键 判断方法：检查键外每个属性A所依赖的X（即XA），若X不含键，违反3NF。 因为设键是K ，则KX（KU，而X必是U的子集 ），所以当XA成立时，A对键K是传递依赖第10页/共63页第三范式 例子 以下关系在3NF中？在2NF中？ 它们有我们以前讨论过的四个问题吗？学号学号姓名姓名班号班号班名班名S1小王小王C1会计班会计班S2小张小张C1会计班会计班S3小李小李C2电算班电算班S4小孙小孙C2电算班电算班Student学号学号姓名姓名班号班号S1小王小王C1S2小张小张C1S3小李小李C2S4小孙小孙C2Student第11页/共63页第

6、三范式 思考 如何证明3NF是2NF的子集?（或者，如何证明满足3NF的条件也就一定满足2NF的条件?） 要点：函数依赖 X Y 是非传递的 X Y是完全的 反证：如果 X Y 是部分的 X X Y X Y是传递的，与前提矛盾第12页/共63页BC范式 要求 关系在1NF中 每个属性都非传递依赖键 充要条件：每一个(非平凡的)函数依赖XY，X含键 可以证明：BCNF是3NF的真子集第13页/共63页BC范式 例子 考虑以下关系R(S, T, C) S: 学生; T: 教师; C: 课程STCSmithJonesJavaCurryJonesJavaSmithFrankC+CurryFrankC+

7、LarryDavidC+R第14页/共63页BC范式 假设一个教师只教一门课程，但是一门课程有多个教师。也就是TC 假设给定一个学生和一门课程，只有一个老师给他上这门课程。也就是SCT 所以函数依赖集为: F= TC, SCT STCSmithJonesJavaCurryJonesJavaSmithFrankC+CurryFrankC+LarryDavidC+R第15页/共63页BC范式R(S, T, C), F= TC, SCT 问题1: R的候选键是什么？ 候选键: ST, SC 证明: (ST)+=(STC), (SC)+=(STC),所以ST, TC是超键. 而(S)+=(S), (T

8、)+=(TC), (C)+=(C), 所以ST, SC的真子集都不是超键STCSmithJonesJavaCurryJonesJavaSmithFrankC+CurryFrankC+LarryDavidC+R第16页/共63页BC范式R(S, T, C), F= TC, SCT , 候选键: ST, SC 问题2: R在3NF中么？在BCNF中么？ R在3NF中，因为R中没有非键属性 R不在BCNF中，因为TC的左边T不含键。STCSmithJonesJavaCurryJonesJavaSmithFrankC+CurryFrankC+LarryDavidC+R第17页/共63页BC范式R(S,

9、 T, C), F= TC, SCT , 候选键: ST, SC 问题3: 它们有我们以前讨论过的四个问题吗？ 是的，因为组合(T, C)的值重复STCSmithJonesJavaCurryJonesJavaSmithFrankC+CurryFrankC+LarryDavidC+R第18页/共63页三种范式的比较 结论 2NF保证了这样的函数依赖：右边非键属性的情况下，左边!=键（含键） BCNF在3NF的基础上，进一步保证：右边不管是还是非键属性，左边=键。 到BCNF为止，任何有意义（非平凡）的函数依赖都是好的，即右边不管是什么，左边都具有唯一性（含键）。第19页/共63页三种范式的判断检

10、查每个检查每个属性属性A上的可能上的可能函数依赖函数依赖X AA是非键属性是非键属性A是主属性是主属性X不含键不含键违反违反3NF违反违反BCNFX是键的一部分是键的一部分违反违反2NF违反违反BCNF第20页/共63页在学习这么多的范式以后 认识 高级范式的问题比低级范式要少 但即使是非常高级的范式，仍然可能还是有问题 所以我们不能期望没有任何问题的“完美”关系。只能尽量让关系达到尽可能高的范式，使问题尽可能的少第21页/共63页如何让关系达到更高的范式? 分解 把一个属于低级范式的“坏”关系，分解为几个属于高级范式的 “好”关系（更小的关系） 但是某些情况下分解会带来新的问题，比如信息丢失

11、，这样的分解是不正确的。 两个要点 1. 什么样的分解方案才是正确的（不丢失信息的）? 无损连接分解 2. 怎么找到正确的分解方案? 规范化第22页/共63页无损连接分解 无损连接分解 不会丢失信息的分解 判定“一分二”是否无损连接分解的充分必要条件 将关系R分解为R1和R2 。则当以下两个函数依赖之一能够成立时，这种是无损的 R1 R2 R1R2 R1 R2 R2R1第23页/共63页无损连接分解R(C, T, H, R, S) F = CT, HRC, HTR, HSR 问题1: R R1(C, H, S), R2(C, T, H, R). 这一分解是无损的么? 是的，因为 CH+ (CT

12、HR) CH TR R1 R2 R2R1 R 分解为 R1, R2 是无损的 思考:R R1(C, H, S), R2(C, T), R3(C, H, R). 这一分解是无损的么第24页/共63页规范化 规范化 将一个属于低级范式的“坏”关系，分解为多个属于高级范式的“好”关系，且无信息丢失的过程 根据目标范式的级别，又有 规范化到1NF 规范化到3NF 规范化到BCNF第25页/共63页规范化到1NF 非1NF的关系变为1NF的关系 方法：将关系中每个非原子的属性转化成原子的 复合属性的处理：转化成相应的多个原子属性学号学号姓名姓名父母父母S1John(Tom, Angie)S2Smith

13、(Mike, Sophie)Student学号学号姓名姓名父亲父亲母亲母亲S1JohnTomAngieS2SmithMikeSophieStudent第26页/共63页规范化到1NF 多值属性的处理：移出去生成一个新关系，同时还包含原来的主键（新关系的主键为这两者的和）学号学号姓名姓名课程号课程号S1John C1，C2，C3S2SmithC3，C5Student学号学号姓名姓名S1JohnS2SmithStudent学号学号课程号课程号S1C1S1C2S1C3S2C3S2C5SC第27页/共63页规范化到3NF 1NF关系分解为3NF关系的算法 输入 : R（属于1NF）, F（R满足的函数

14、依赖集合） 输出 : R1, R2, R3Rn（都属于3NF）第28页/共63页规范化到3NF1- n=0; (n是输出关系个数) for F 中每一个X Y doif XY已经在某个输出关系Ri (1 i n)中 then什么也不做 else if X是某一个输出关系Ri (1 i n) 的主键 then Ri := Ri + Y; else n := n+1; Rn := XY ; (增加一个新关系，X 作为主键) end if 2- if R每个候选键都不出现在输出关系Ri (1i n) 中 then n := n+1; Rn := R的任何一个候选键 end if步骤步骤步骤步骤第29

15、页/共63页规范化到3NF 例1 输入: R(A, B, C, D, E), F = (AB, CD, D E) 候选键: AC 1. R1(AB) 2. R1(AB), R2(CD) 3. R1(AB), R2(CD), R3(DE) 4. R1(AB), R2(CD), R3(DE), R4(AC) Output: R1(AB), R2(CD), R3(DE), R4(AC)第30页/共63页规范化到3NF 例2 输入: R(A, B, C, D, E, F), F = (ABD, CE, AB C, CF) 候选键: AB 1. R1(ABD) 2. R1(ABD), R2(CE) 3.

16、 R1(ABCD), R2(CE) 4. R1(ABCD), R2(CEF) Output: R1(ABCD), R2(CEF)第31页/共63页规范化到BCNF 1NF关系分解为BCNF关系的算法 输入 : R（属于1NF）, F（R1满足的函数依赖集合） 输出 : R, R1, R2, R3Rn（都属于BCNF）第32页/共63页规范化到BCNF n=0; (除自己外没有输出关系) for F 中每个XY do for 每个输出关系R/Ri doif XY 在Ri中，且X不是Ri的超键 then Ri = Ri Y if X是另一个输出关系Rj (1 i n) 的主键 then Rj :=

17、 Rj + Y; else n := n+1; Rn := XY ; (增加一个新关系，X 作为主键) end if end if第33页/共63页规范化到BCNF 例1 输入: R (A, B, C, D, E, F), F = (ABD, CE, AB C, CF) 候选键: AB 1. R(ABCDF), R1(CE) 处理CE 2. R(ABCD), R1(CEF) 处理CF Output: R(ABCD), R1(CEF)第34页/共63页规范化到BCNF 例2 输入: R (A, B, C, D), F = (ABC, CA, C D) 候选键: AB, BC 1. R(BCD),

18、 R1(CA) 处理CA 2. R(BC), R1(CAD) 处理CD Output: R (BC), R1(CAD) 思考 把上面的关系规范化到3NF，结果如何？试与BCNF的结果作比较 此时原来的函数依赖ABC, CA, C D在规范化的结果关系上是否还成立？第35页/共63页 规范化到BCNF与规范化到3NF的对比 规范化到BCNF得到的关系问题更少，但是可能丢失某些函数依赖（在原来的关系上成立，但在分解后的关系上不成立） 规范化到3NF得到的关系可能不是很好，但往往已经足够好了。而且不会丢失任何函数依赖第36页/共63页练习 R (C, T, H, R, S) F = CT, HRC,

19、 HTR, HSR 问题： 1. HT是否R的候选键? HS呢? 2. R最高属于第几范式? 试证明之 3. 把R规范到BCNF级别 4. 证明你在3中使用的分解是无损分解第37页/共63页答案 R (C, T, H, R, S) F = CT, HRC, HTR, HSR 问题： 1. HT是否R的候选键? HS呢?答:HT不是R的候选键，推理如下： (HT)+=(HTRC) U (HT)+ HT U HT不是超键 HT不是候选键 HS是R的候选键，推理如下： (HS)+=(HSRTC) U (HS)+ HS U HS是超键 (H)+=(H) U (H)+ H U H不是超键 (S)+=(S

20、) U (S)+ S U S不是超键 综合 HS是最小的超键即候选键第38页/共63页答案 R (C, T, H, R, S) F = CT, HRC, HTR, HSR 问题： 2. R最高属于第几范式? 试证明之答: R最高属于第二范式，推理如下： R属于第二范式（思路：证明全部非键属性: C、T、R，对候选键HS的依赖都是完全的，即不会函数依赖于HS的一部分：H或S，也就是不在H+或者S+中） (H)+=(H), (S)+=(S) 所有非键属性: T, C, R都不函数依赖于主键HS的一部分 R属于第二范式 R不属于第三范式，推理如下：由CT可知，非键属性C函数依赖T，而T又函数依赖于候

21、选键HS HSC, CT 非键属性T对候选键HS的函数依赖是传递的 R不属于第三范式 综上可知，R最高属于第二范式第39页/共63页答案 R (C, T, H, R, S) F = CT, HRC, HTR, HSR 问题： 3. 把R规范到BCNF级别规范化的分解过程如下 1. R(HSRC), R1(CT) 2. R(HSR), R1(CT), R2(HRC)所以规范化的输出为： R(HSR), R1(CT), R2(HRC)第40页/共63页答案 R (C, T, H, R, S) F = CT, HRC, HTR, HSR 问题： 4. 证明你在3中使用的分解是无损分解首先证明R分解为

22、R(HSRC), R1(CT)是无损分解:C T R R1R1R R分解为R, R1是无损的再证明R分解为R(HSR), R2(HRC)是无损的:HR CRR2R2RR分解为R,R2无损所以R分解为R(HSR), R1(CT), R2(HRC)是无损的第41页/共63页目录* 4.1 模式设计与数据冗余 4.2 函数依赖 4.4 范式 4.4.1 函数依赖与范式 4.1.2 多值依赖与4NF第42页/共63页多值依赖：例子 例子问题 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。 所以这里，课程教师，参考书课程等任何函数依赖统

23、统不成立第43页/共63页多值依赖：例子 非规范关系课 程 C教 员 T参 考 书 B 物理数学 计算数学李 勇王 军 李 勇张 平 张 平 周 峰 普通物理学光学原理 物理习题集数学分析微分方程高等代数数学分析. Teaching第44页/共63页多值依赖：例子 规范化关系普通物理学光学原理物理习题集普通物理学光学原理物理习题集数学分析微分方程高等代数数学分析微分方程高等代数李 勇李 勇李 勇王 军王 军王 军李 勇李 勇李 勇张 平张 平张 平 物 理物 理物 理物 理物 理物 理数 学数 学数 学数 学数 学数 学 参考书B教员T课程CTeaching第45页/共63页多值依赖：例子 T

24、eaching具有唯一候选键(C，T，B)， 也是全键。 TeachingBCNF（不存在函数依赖）。 Teaching模式中存在的问题 (1) 数据冗余度大 (2) 插入操作复杂 (3) 删除操作复杂 (4) 修改操作复杂第46页/共63页多值依赖：定义 多值依赖的定义(1) 设有关系模式设R(U)， X, Y是U的子集。多值依赖 XY成立，当且仅当对R(U)上的任一关系r，以下条件成立 (r在)X上的一个确定值，都对应在Y上的一组值 Y上的这组对应值，与(r在)Z上的值无关，其中Z=UXY第47页/共63页多值依赖：定义 课程参考书。无论教师取何值，一门课程总是对应相同的一组参考书普通物理

25、学光学原理物理习题集普通物理学光学原理物理习题集数学分析微分方程高等代数数学分析微分方程高等代数李 勇李 勇李 勇王 军王 军王 军李 勇李 勇李 勇张 平张 平张 平 物 理物 理物 理物 理物 理物 理数 学数 学数 学数 学数 学数 学 参考书B教员T课程CTeaching第48页/共63页多值依赖：定义 多值依赖的定义(2) 在R（U）的任一关系r中，如果存在元组t，s 使得tX=sX，那么就必然存在元组 w，v r，（w，v可以与s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记

26、为XY。 这里，X，Y是U的子集，Z=U-X-YX1Y1Z1tX1Y2Z2sX1Y2Z1vX1Y1Z2w第49页/共63页多值依赖：定义 平凡多值依赖和非平凡的多值依赖若XY，而Z UXY =，则称 XY为平凡的多值依赖否则称XY为非平凡的多值依赖第50页/共63页多值依赖：性质（1）多值依赖具有对称性若XY，则XZ，其中ZUXY（2）多值依赖具有传递性若XY，YZ， 则XZ Y（3）函数依赖是多值依赖的特例(后者是前者的推广)若XY，则XY。（4）若XY，XZ，则XY Z。（5）若XY，XZ，则XYZ。（6）若XY，XZ，则XY-Z，XZ -Y第51页/共63页第四范式 要求 关系在1NF中

27、 任意非平凡的多值依赖XY，X含候选键 4NF中的多值依赖要么是平凡的，要么是函数依赖 可证：4NF是BCNF的真子集。第52页/共63页第四范式 分解Teaching1课程课程C教员教员T物理物理李勇李勇物理物理王军王军数学数学李勇李勇数学数学张平张平课程课程C参考书参考书B物理物理普通物理学普通物理学物理物理光学原理光学原理物理物理物理习题集物理习题集数学数学数学分析数学分析数学数学微分方程学微分方程学数学数学高等代数高等代数Teaching2第53页/共63页第四章 作业与练习 作业（下周交） 教材P1445, 10, 11题12题的(1), (2), (3) 小题 课后练习 1（注意全键）, 2, 3, 9 12题的(4), (5), (6), (7) 小题第54页/共63页范式 不同范式之间的联系 4NF BCNF 3NF 2NF 1NF 高级范式是低级范式的子集 范式越高，满足的要求也就越高；满足高要求的关系肯定能够满足低要求，所以高级范式中的关系模式肯定也在低级范式中1NF2NF3NFBCNF4NF第55页/共63页第二范式 要求 关系模式在1NF中 每一个非键属性完全函数依赖于键 判断方法：检查每个非键属性A所依赖的X（即XA），若X是候选键的一部分