第六章关系数据库理论优秀课件.ppt

《第六章关系数据库理论优秀课件.ppt》由会员分享，可在线阅读，更多相关《第六章关系数据库理论优秀课件.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章关系数据库理论第1页，本讲稿共24页6.1 问题的提出例如：Student(Sno，Sdept，Mname，Cname，Grade)F=SnoSdept，Sdept Mname，(Sno,Cname)Grade存在问题：存在问题：数据冗余太大数据冗余太大插入异常插入异常删除异常删除异常更新异常更新异常分解成三个关系模式：分解成三个关系模式：S(Sno，Sdept，SnoSdept)；SG(Sno，Cname，Grade，(Sno,Cname)Grade)；D(Sdept，Mname，Sdept Mname)；第2页，本讲稿共24页6.2 6.2 规范化规范化 数据依赖：关系中属性值之间的

2、这种相互依赖又相互制约的联 系，称为数据依赖。包括：函数依赖、多值依赖。一、函数依赖定义1：设设R(U)R(U)是属性集是属性集U U上的关系模式。上的关系模式。X X，Y Y是是U U的子集。若对于的子集。若对于R(U)R(U)的任的任意一个可能的关系意一个可能的关系r r，r r中不可能存在两个元组在中不可能存在两个元组在X X上的属性值相等，而在上的属性值相等，而在Y Y上上的属性值不等，则称的属性值不等，则称X X函数决定函数决定Y Y或或Y Y函数依赖于函数依赖于X X，记作，记作XYXY。说明：1、函数依赖是语义范畴的概念 2、函数依赖关系是反映属性之间的一般规律根据函数依赖的定义

3、，可找出下面规律：根据函数依赖的定义，可找出下面规律：1、在一个关系模式中，如属性、在一个关系模式中，如属性X，Y有有1：1联系，则存在函数依赖联系，则存在函数依赖XYXY、YX YX，可记作，可记作X XY Y2 2、X X、Y Y是是1 1：m m联系，则存在联系，则存在YXYX，但，但XYXY3 3、X X、Y Y是是n:mn:m联系，则联系，则X X、Y Y之间不存在任何函数依赖之间不存在任何函数依赖第3页，本讲稿共24页XYXY，但，但Y Y X X则称则称XYXY是是平凡的函数依赖平凡的函数依赖。否则，称。否则，称非平凡的函数依赖非平凡的函数依赖。定义定义2：在：在R（U）中，如果

4、）中，如果XYXY，并且对于，并且对于X X的任何一个真子集的任何一个真子集XX，都有，都有 XY XY，则，则称称Y Y对对X X部分函数依赖部分函数依赖，记作，记作XpYXpY，否则，否则，称称Y Y完全函数依赖于完全函数依赖于X X，记作记作XfYXfY。定义定义3：在：在R（U）中，如果）中，如果XYXY，（，（Y Y X X），），Y XY X，YZYZ，则，则称称Z Z对对X X传递传递 函数依赖。函数依赖。定义定义4：设：设K为为R中的属性或属性组合，若中的属性或属性组合，若K fUU则则K K为为R R的的候选码候选码。若候选码多于一个，则选定其中的一个为主码（Primary

5、Key）。包含在任何一个候选码中的属性，叫做主属性。不包含在任何码中的属性称为非主属性或非码属性。整个属性组是码，称为全码。定义5：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的 码，则称X是R的外部码（Foreign Key），也称外码。二、码第4页，本讲稿共24页三、范式三、范式三、范式三、范式范式：是符合某一种级别的关系模式的集合。关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同 范式。1NF，2NF，3NF，BCNF，4NF，5NF定义：关系模式 R（U）中所有属性都不可再分的，则称R是第一范式，记作 R1NF。例如：SLC（SNO，SDEPT，SLOC，C

6、NO，GRADE）四、四、四、四、2NF2NF定义6：若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。SNOCNOGSDEPT SLOC第5页，本讲稿共24页五、五、五、五、3NF3NF定义7：若R2NF，且R中任一非主属性都不传递函数依赖于码，则R3NF。SNOCNOGSDEPT SLOCSNOSLSC上例 SL分解为：SD（SNO，SDEPT）DL（SDEPT，SLOC）由于第三范式有效地消除了非主属性对码的部分和传递依赖，因而消除了一大类操作异常问题。因此，3NF在数据库设计中得到了广泛应用。第6页，本讲稿共24页六、六、六、六、BCNFBCNF例：关系模式STJ（S，T，J）

7、中，S表示学生，T表示教师，J表示教师，J表 示课程。每一教师只教一门课。每门课有若干教师，某一学生选定某门课，就对应一个固定的教师。由语义可得到如下的函数依赖：由语义可得到如下的函数依赖：（S，J）TT；（S S，T T）JJ；T J T J关系有两个候选键，是（S，J）和（S，T）S、T、J都是主属性，不存在非主属性，更不会有非主属性对键的传递依赖、部分依赖了，因此，STJ关系满足第三范式。但仍然存在问题：定义8：R BCNF，当且仅当每个决定因素都是码（候选键）。上例分解为：ST（S，T）、TJ（T，J）第7页，本讲稿共24页七、多值依赖七、多值依赖七、多值依赖七、多值依赖例：学校中某一

8、门课程由多个教员讲授，他们使用相同的一套参考书。每个教 员可以讲授多门课程，每种参考书可以供多门课程使用。如下表：课程C 教员T 参考书B 物理 李勇 普通物理学 物理 李勇 光学原理 物理 李勇 物理习题集 物理 王军 普通物理学 物理 王军 光学原理 物理 王军 物理习题集 数学 李勇 数学分析 数学 李勇 微分方程 数学 李勇 高等代数 数学 张平 数学分析 数学 张平 微分方程 数学 张平 高等代数 第8页，本讲稿共24页定义定义定义定义9 9：关系模式关系模式关系模式关系模式R R（U U），），），），X X，Y Y，Z Z是是是是U U的子集，并且的子集，并且的子集，并且的子集，

9、并且Z=U-X-YZ=U-X-Y。关系模式。关系模式。关系模式。关系模式R(U)R(U)中多值依赖中多值依赖中多值依赖中多值依赖X XY Y成立，当且仅当对成立，当且仅当对成立，当且仅当对成立，当且仅当对R R（U U）的任一关系）的任一关系）的任一关系）的任一关系r r，给定的一对（，给定的一对（，给定的一对（，给定的一对（x x，z z）值，有一组值，有一组值，有一组值，有一组Y Y的值，这组值仅仅决定于的值，这组值仅仅决定于的值，这组值仅仅决定于的值，这组值仅仅决定于x x值而与值而与值而与值而与z z值无关。值无关。值无关。值无关。若XY，而Z=即Z为空，则称XY为平凡的多值依赖。多值

10、依赖性质：多值依赖性质：对称性。若XY，则XZ，其中Z=U。传递性。若XY，则XY。函数依赖可看作是多值依赖的特殊情况。若XY，则XY。若XY，X，则XY。若XY，X，则XY。若XY，X，则XY，XY。第9页，本讲稿共24页八、八、八、八、4NF4NF定义10：关系模式R1NF，如果对于R的每个非平凡多值依赖XY（Y X），X都含有码，则称R 4NF。九、规范化小结九、规范化小结九、规范化小结九、规范化小结1NF 消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖2NF 消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖3NF 消除主属性对码的部分和传递函数依赖消除主属性对

11、码的部分和传递函数依赖BCNF 消除非平凡且非函数依赖的多值依赖消除非平凡且非函数依赖的多值依赖4NF第10页，本讲稿共24页6.3 6.3 数据依赖的公理系统数据依赖的公理系统数据依赖的公理系统数据依赖的公理系统定义定义11：对于满足一组函数依赖对于满足一组函数依赖F的关系模式的关系模式R，其任何一个关系，其任何一个关系r，若函，若函数依赖数依赖XYXY都成立，则称都成立，则称F F逻辑蕴含逻辑蕴含XYXY。Armstrong公理系统：设U为属性集总体，F是U上的一组函数依赖，于是有关系模式R。对R来说有以下的推理规则：A1自反律：若YX U，则XY为F所蕴含。A2增广律：若XY为F所蕴含，

12、且Z U，则XZYZ为F所蕴含。A3传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。推论：合并规则：由XY，XZ，有XYZ。伪传递规则：由XY，WYZ，有XWZ。分解规则：由XY及ZY，有XZ。根据合并规则和分解规则，得到一重要事实：引理引理1：XA1A2 Ak成立的充分必要条件是成立的充分必要条件是XAi成立（成立（i=1,2,k）。）。第11页，本讲稿共24页定义定义定义定义1212：在关系模式在关系模式在关系模式在关系模式 RR中为中为中为中为F F所逻辑蕴含的函数依赖的全体叫做所逻辑蕴含的函数依赖的全体叫做所逻辑蕴含的函数依赖的全体叫做所逻辑蕴含的函数依赖的全体叫做F F的闭包的闭包

13、的闭包的闭包，记为记为记为记为F F+。定义13：设F为属性集U上的一组函数依赖，X U，XF+=A|XA能由F根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F的闭包。引理2：设F为属性集U上的一组函数依赖，X，Y U，XY能由F根据 Armstrong公理导出的充分必要条件是 Y XF+。算法6.1：求属性集X（X U）关于U上的函数依赖集F的闭包XF+。步骤步骤：令令X(0)=X，i=0 求求B，这里，这里B=A|(V)(W)(V W F V X(i)A W);X(i+1)=B X(i)判断判断X(i+1)=X(i)吗？吗？若相等或若相等或X(i+1)=U，则，则X(i+

14、1)就是就是XF+，算法终止。，算法终止。若否，则若否，则i=i+1，返回第，返回第步。步。例1 已知关系模式 R，其中U=A，B，C，D，E；F=AB C，B D，C E，EC B，AC B。求（AB）F+。第12页，本讲稿共24页定义定义1414：如果如果GG+=F=F+，就说函数依赖集，就说函数依赖集F F覆盖覆盖GG（F F是是GG的覆盖，或的覆盖，或GG是是F F的覆盖），或的覆盖），或F F与与GG等价。等价。引理引理3：F F+=G=G+的充分必要条件是的充分必要条件是F GG+，和，和G F F+。定义定义15：如果函数依赖集如果函数依赖集F满足下列条件，则称满足下列条件，则称

15、F为一个极小函数依赖集。为一个极小函数依赖集。亦称为最小依赖集或亦称为最小依赖集或最小覆盖最小覆盖。F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。F中不存在这样的函数依赖中不存在这样的函数依赖X A，使得，使得F与与FX A等价。等价。F中不存在这样的函数依赖中不存在这样的函数依赖X A，X有真子集有真子集Z使得使得 FX A Z A与与 F 等价。等价。例：F=A B，B A，B C，A C，C A 求Fm 。Fm1=A B，B C，C AFm2=A B，B A，A C，C A第13页，本讲稿共24页6.4 6.4 模式的分解模式的分解模式的分解模式的分解分解具有

16、分解具有“无损连接性无损连接性”分解要分解要“保持函数依赖保持函数依赖”分解既要分解既要“保持函数依赖保持函数依赖”，又要具有，又要具有“无损连接性无损连接性”。定义定义16：关系模式关系模式R的一个分解是指的一个分解是指 R1，R2，Rn 其中其中U=Ui，并且没有，并且没有Ui Uj，1，j n，Fi是是F在在Ui上的投影。上的投影。定义定义17：函数依赖集合函数依赖集合X Y|X Y F+XY Ui的一个覆盖的一个覆盖Fi叫做叫做F在在属性属性Ui上的投影。上的投影。一、模式分解的三个定义例：已知关系模式R，其中U=SNO,SDEPT,MN,F=SNO SDEPT,SDEPT MN。分解

17、：分解：1R1，R2，R32R1，R23R1，R2第14页，本讲稿共24页二、分解的无损连接性和保持函数依赖性二、分解的无损连接性和保持函数依赖性二、分解的无损连接性和保持函数依赖性二、分解的无损连接性和保持函数依赖性定义定义18:RR1 1U，R Rk kU是是R的一个分解，若的一个分解，若R R的任何一个关系的任何一个关系r均有均有r=m(r)成立，则称分解成立，则称分解具有无损连接性。简称具有无损连接性。简称为无损分解。为无损分解。算法算法6.2：判别一个分解的无损连接性。判别一个分解的无损连接性。RR1 1U，R Rk kU是是R R的一个分解，的一个分解，U=A1,An，FFD1,F

18、D2,FD,FD，F是一极小依赖是一极小依赖集集,记记FDi为为Xi A1i。建立一张建立一张n列列k行的表。每一列对应一个属性，每一行对应分解中的一个关系行的表。每一列对应一个属性，每一行对应分解中的一个关系 模式。若属性模式。若属性Aj属于属于Ui，则在，则在j列列i行交叉处填上行交叉处填上aj，否则填上，否则填上bij；对每一个对每一个FDFDi i做下列操作：找到做下列操作：找到X Xi i所对应的列中具有相同符号的那些行。考察所对应的列中具有相同符号的那些行。考察这些行中这些行中l li i列的元素，若其中有列的元素，若其中有a alili，则全部改为，则全部改为a alili ；否

19、则全部改为；否则全部改为b bmlimli ；m m是是 这些行的行号最小值。这些行的行号最小值。比较扫描前后，表有无变化。如有变化，则返回第比较扫描前后，表有无变化。如有变化，则返回第步，否则算法终止。步，否则算法终止。第15页，本讲稿共24页例：例：已知已知已知已知 R R R R，U U U UA,B,C,D,EA,B,C,D,EA,B,C,D,EA,B,C,D,E，F=AB F=AB F=AB F=AB C C C C，C C C C D D D D，D D D D E E E E ，R R R R的一个的一个的一个的一个 分解为分解为分解为分解为R R R R1 1 1 1(A,B,

20、C)(A,B,C)(A,B,C)(A,B,C)，R R R R2 2 2 2(C,D)(C,D)(C,D)(C,D)，R R R R3 3 3 3(D,E)(D,E)(D,E)(D,E)。首先构造初始表，如图 A B C D E a1 a2 a3 b14 b15 b21 b22 a3 a4 b25 b31 b32 b33 a4 a5 对AB C，因各元组的第1、2列没有相同的分量，所以表不改变。由C D D 可以把b14改为a4，再由D E可使b15，b25全改为a5。A B C D E a1 a2 a3 a4 a5 b21 b22 a3 a4 a5 b31 b32 b33 a4 a5第16页

21、，本讲稿共24页定理：定理：定理：定理：R R R R的一个分解的一个分解的一个分解的一个分解 RRRR1 1 1 1UUU ，R R R R2 2 2 2UUU具有无损连接性的充具有无损连接性的充具有无损连接性的充具有无损连接性的充 分必要条件是：分必要条件是：分必要条件是：分必要条件是：U U1 1UU2 2 U U1 1U U2 2 F F+或或或或 U U1 1UU2 2 U U2 2U U1 1 F F+。l 若要求分解保持函数依赖，那么模式分离总可以达到若要求分解保持函数依赖，那么模式分离总可以达到3NF，l 但不一定能达到但不一定能达到BCNF;l 若要求分解既保持函数依赖，又具

22、有无损连接性，可以达若要求分解既保持函数依赖，又具有无损连接性，可以达l 到到3NF，但不一定能达到，但不一定能达到BCNF;l 若要求分解具有无损连接性，那一定可达到若要求分解具有无损连接性，那一定可达到4NF;当关系模式R分解为两个关系模式R1，R2时有下面的判定准则。定义定义1919：若若F F+（F Fi i），则，则 R R 的分解的分解RR1 1U，R Rk kU保持函数依赖。保持函数依赖。三、模式分解的算法关于模式分解的几个重要事实是：第17页，本讲稿共24页算法算法算法算法6.3 6.3 转换为转换为转换为转换为3NF3NF的保持函数依赖的分解的保持函数依赖的分解的保持函数依赖

23、的分解的保持函数依赖的分解l 对对 R 中的函数依赖集中的函数依赖集F进行进行“极小化处理极小化处理”，l 仍记为仍记为F。l 找出不在找出不在F中出现的属性，把这样的属性构成一个中出现的属性，把这样的属性构成一个l 关系模式。把这些属性从关系模式。把这些属性从U中去掉，剩余的属性仍中去掉，剩余的属性仍l 记为记为U。l 若有若有 X A F，且，且XA=U，则，则 R，算法终止。，算法终止。l 否则，对否则，对F按具有相同左部的原则分组（假定分为按具有相同左部的原则分组（假定分为l k组）组）,每一组函数依赖每一组函数依赖Fi所涉及的全部属性形成所涉及的全部属性形成l 一个属性集一个属性集U

24、i。若。若Ui Uj(ij)就去掉就去掉Ui 。第18页，本讲稿共24页算法算法算法算法6.4 6.4 转换为转换为转换为转换为3NF3NF既有无损连接性又保持函数依赖的分解既有无损连接性又保持函数依赖的分解既有无损连接性又保持函数依赖的分解既有无损连接性又保持函数依赖的分解l 设设 X X 是是 R R 的码。的码。R R 已由算法已由算法5.35.3分解为分解为l RR1 1U，R R2 2U，R Rk kU，l 令令 R Rx xU,F 。l 若有某个若有某个U Ui i ，X X U Ui i,将将 R Rx xU,F 从从 中去掉。中去掉。l 把这些属性从把这些属性从U U中去掉，剩

25、余的属性仍记为中去掉，剩余的属性仍记为U U。l 就是所求的分解。就是所求的分解。算法算法算法算法6.5 6.5 转换为转换为转换为转换为BCNFBCNF的无损连接的分解的无损连接的分解的无损连接的分解的无损连接的分解l 令令RURFl 检查检查中各关系模式是否均属于中各关系模式是否均属于BCNFBCNF。若是，则算法终止。若是，则算法终止。l 设设中中R Ri iU 不属于不属于BCNF,BCNF,那么必有那么必有X A Fi+(A X)，l 且且X非非R Ri i的码。因此，的码。因此，XAXA是是U Ui i的真子集。对的真子集。对R Ri i进行分解：进行分解：l SS1 1,S,S2

26、 2,U,Us1s1=XA,U=XA,Us2s2=U=Ui i-A-A，以，以 代替代替R Ri iU 返回第返回第l 步。步。第19页，本讲稿共24页算法算法算法算法6.6 6.6 达到达到达到达到4NF4NF的具有无损连接性的分解的具有无损连接性的分解的具有无损连接性的分解的具有无损连接性的分解l 令令RRl 检查检查中所有关系模式，如均为中所有关系模式，如均为4NF4NF，则转，则转。l 中找非中找非4NF4NF的关系模式的关系模式S S，S S中必有一个多值依中必有一个多值依l 赖赖 X Y，其中其中X不包含不包含S的关键字，的关键字，Y既非既非l 空又不是空又不是X的子集，且的子集，

27、且XYS。用。用 S1=XY 和和 l S2=SY代替代替S。返回。返回。l 停止分解，输出停止分解，输出。第20页，本讲稿共24页例子：例子：例子：例子：关系模式关系模式CTHRSGCTHRSG，其中，其中C C表示课程，表示课程，T T表示教师，表示教师，H H表示时表示时间，间，R R表示教室，表示教室，S S表示学生，表示学生，G G表示成绩。函数依赖集表示成绩。函数依赖集F F及及其所反映的语义分别为：其所反映的语义分别为：C CT T 每门课程仅有一位教师担任。每门课程仅有一位教师担任。HT HTR R 在任一时间，一个教师只能在一个教室上课。在任一时间，一个教师只能在一个教室上课

28、。HR HRC C 在任一时间，每个教室只能上一门课。在任一时间，每个教室只能上一门课。HS HSR R 在任一时间，每个学生只能在一个教室听课。在任一时间，每个学生只能在一个教室听课。CSCSG G 每个学生学习一门课程只有一个成绩。每个学生学习一门课程只有一个成绩。第21页，本讲稿共24页解：解：解：解：HSHSCTHRSGCTHRSG，HSHS是关系模式的关键字。是关系模式的关键字。是关系模式的关键字。是关系模式的关键字。面向面向面向面向3NF3NF3NF3NF且保持函数依赖的分解。且保持函数依赖的分解。且保持函数依赖的分解。且保持函数依赖的分解。最小函数依赖集为最小函数依赖集为F=CF

29、=CT,CSG,HRC,HSR,THR 分解为：分解为：CT，CSG，HRC，HSR，THR 面向面向面向面向3NF3NF3NF3NF既有无损连接性又保持函数依赖的分解。既有无损连接性又保持函数依赖的分解。既有无损连接性又保持函数依赖的分解。既有无损连接性又保持函数依赖的分解。HS是关键字，是关键字，HS ，HS是是HSR的一个子集的一个子集 分解仍为：分解仍为：CT，CSG，HRC，HSR，THR第22页，本讲稿共24页 面向面向面向面向BCNFBCNF且具有无损连接性的分解。且具有无损连接性的分解。且具有无损连接性的分解。且具有无损连接性的分解。CTHRSGKey=HSCSGKey=CSC

30、SGCTHRS Key=CSCT，THRHRC，HSRCTKey=CCTCTRS Key=HSCHR，HRCHSRCHRKey=CH，HRCHR，HRCCHSKey=HS HSC分解树第23页，本讲稿共24页 面向面向面向面向4NF4NF且具有无损连接性的分解。且具有无损连接性的分解。且具有无损连接性的分解。且具有无损连接性的分解。关系模式关系模式R中存在多值依赖中存在多值依赖C HR，T HR，显然由于，显然由于C或或T都不含该关系模式的码都不含该关系模式的码HS，R 4NF。选择选择C HR将它分解为将它分解为CHR和和CTSG;再将再将CTSG分解为分解为CT和和CSG。关系模式关系模式CTHRSG最后无损地分解为最后无损地分解为CHR、CT和和CSG，其中，其中每一个关系模式都属于每一个关系模式都属于4NF。第24页，本讲稿共24页