《数据库系统原理及应用-电子教案-李晓峰 第3章 关系数据库设计理论》由会员分享，可在线阅读，更多相关《数据库系统原理及应用-电子教案-李晓峰 第3章 关系数据库设计理论（24页珍藏版）》请在金锄头文库上搜索。
1、第3章 关系数据库设计理论,3.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)；,3.2 规范化,数据依赖：关系中属性值之间的这种相互依赖又相互制约的联 系，称为数据依赖。包括：函数依赖、多值依赖。,一、函
2、数依赖,定义1：设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任 意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上 的属性值不等，则称X函数决定Y或Y函数依赖于X，记作XY。,说明：1、函数依赖是语义范畴的概念 2、函数依赖关系是反映属性之间的一般规律,根据函数依赖的定义，可找出下面规律： 1、在一个关系模式中，如属性X，Y有1：1联系，则存在函数依赖XY、 YX，可记作XY 2、X、Y是1：m联系，则存在YX，但XY 3、X、Y是n:m联系，则X、Y之间不存在任何函数依赖,XY，但YX则称XY是平凡的函数依赖。否则，称非平凡的函数依赖。,定义2：在
3、R（U）中，如果XY，并且对于X的任何一个真子集X，都有 XY，则称Y对X部分函数依赖，记作XpY，否则，称Y完全函数依赖于 X，记作XfY。,定义3：在R（U）中，如果XY，（YX），Y X，YZ，则称Z对X传递 函数依赖。,定义4：设K为R中的属性或属性组合，若K fU则K为R的候选码。,若候选码多于一个，则选定其中的一个为主码（Primary Key）。,包含在任何一个候选码中的属性，叫做主属性。不包含在任何码中的属性称 为非主属性或非码属性。整个属性组是码，称为全码。,定义5：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的 码，则称X是R的外部码（Foreign Key）
4、，也称外码。,二、码,三、范式,范式：是符合某一种级别的关系模式的集合。 关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同 范式。1NF，2NF，3NF，BCNF，4NF，5NF,定义：关系模式 R（U）中所有属性都不可再分的，则称R是第一范式，记作 R1NF。,例如：SLC（SNO，SDEPT，SLOC，CNO，GRADE）,四、2NF 定义6：若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。,五、3NF,定义7：若R2NF，且R中任一非主属性都不传递函数依赖于码，则R3NF。,SL,SC,上例 SL分解为： SD（SNO，SDEPT） DL（SDEPT，SLOC）,
5、由于第三范式有效地消除了非主属性对码的部分和传递依赖，因而 消除了一大类操作异常问题。因此，3NF在数据库设计中得到了广泛 应用。,六、BCNF,例：关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示教师，J表 示课程。每一教师只教一门课。每门课有若干教师，某一学生选定某门课， 就对应一个固定的教师。,由语义可得到如下的函数依赖： （S，J）T； （S，T）J； T J,关系有两个候选键，是（S，J）和（S，T）,S、T、J都是主属性，不存在非主属性，更不会有非主属性对键的传递依赖、 部分依赖了，因此，STJ关系满足第三范式。 但仍然存在问题：,定义8：R BCNF，当且仅当每个决
6、定因素都是码（候选键）。,上例分解为：ST（S，T）、TJ（T，J）,七、多值依赖,例：学校中某一门课程由多个教员讲授，他们使用相同的一套参考书。每个教 员可以讲授多门课程，每种参考书可以供多门课程使用。如下表：,课程C 教员T 参考书B 物理 李勇 普通物理学 物理 李勇 光学原理 物理 李勇 物理习题集 物理 王军 普通物理学 物理 王军 光学原理 物理 王军 物理习题集 数学 李勇 数学分析 数学 李勇 微分方程 数学 李勇 高等代数 数学 张平 数学分析 数学 张平 微分方程 数学 张平 高等代数 ,定义9：关系模式R（U），X，Y，Z是U的子集，并且Z=U-X-Y。关系模式R(U)
7、中多值依赖XY成立，当且仅当对R（U）的任一关系r，给定的一对（x，z） 值，有一组Y的值，这组值仅仅决定于x值而与z值无关。,若XY ，而Z=即Z为空，则称XY为平凡的多值依赖。,多值依赖性质： 对称性。若XY ，则XZ，其中Z=U。 传递性。若XY， ，则XY。 函数依赖可看作是多值依赖的特殊情况。若XY，则XY。 若XY， X，则XY。 若XY， X，则XY。 若XY， X，则XY， XY。,八、4NF,定义10：关系模式R1NF，如果对于R的每个非平凡多 值依赖XY（ Y X ），X都含有码，则称R 4NF。,九、规范化小结,1NF 消除非主属性对码的部分函数依赖 2NF 消除非主属性
8、对码的传递函数依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NF,3.3 数据依赖的公理系统,定义11：对于满足一组函数依赖F的关系模式R，其任何一个关系r，若函 数依赖XY都成立，则称F逻辑蕴含XY。,Armstrong公理系统：设U为属性集总体，F是U上的一组函数依赖，于是有关系 模式R。对R来说有以下的推理规则： A1自反律：若YX U，则XY为F所蕴含。 A2增广律：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。 A3传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。,推论： 合并规则：由XY， XZ，有XYZ。 伪传递规则：由XY
9、， WYZ，有XWZ。 分解规则：由XY及ZY，有XZ。,根据合并规则和分解规则，得到一重要事实： 引理1： XA1A2 Ak成立的充分必要条件是XAi成立（i= 1,2,k）。,定义12：在关系模式 R中为F所逻辑蕴含的函数依赖的全体叫做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+ 。,算法3.1：求属性集X（ X U ）关于U上的函数
10、依赖集F的闭包XF+ 。,步骤：令X(0)=X，i=0 求B，这里B=A | ( V) ( W) (V W F V X(i) AW); X(i+1) =B X(i) 判断X(i+1) =X(i) 吗？ 若相等或X(i+1) =U，则X(i+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+。,定义14：如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。,引理3： F+ = G+的充分必要条件是F G+ ，和G F+ 。,定义15
11、：如果函数依赖集F满足下列条件，则称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 A Fm2=A B，B A，A C，C A,算法3.2 计算最小函数依赖集。 输入：一个函数依赖集F。 输出：F的一个等价的最小函数依赖集Fmin。 步骤： 1用分解规则，是F中的任何一个函数依赖的右部仅含一个属性。 2去掉多余的函数依赖：逐一
12、检查F中的各函数依赖XY,并将XY从F中去掉，然后再剩余的函数依赖集F中求属性X的闭包XF+,看XF+是否包含Y，若是，则去掉XY，否则不能去掉。依次做下去，直到找不到冗余的函数依赖。 3去掉各个依赖左部多余的属性：一个一个地检查左部非单个属性的函数依赖。例如XYA,要判断Y是否多余，则以XA代替XYA，并判断是否等价。若AXF+，则Y是多余的，可以去掉。 4用Armstrong公理或步骤2的方法检查F中是否还有多余的函数依赖，若有则去掉。,3.4 模式的分解,分解具有“无损连接性” 分解要“保持函数依赖” 分解既要“保持函数依赖”，又要具有“无损连接性”。,定义16：关系模式R的一个分解是指
13、 R1， R2， Rn 其中U=Ui，并且没有UiUj，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。,分解： 1R1， R2， R3 2R1， R2 3R1， R2,二、分解的无损连接性和保持函数依赖性,定义18: R1，Rk是R的一个分解，若R的任何一个关系r均有r=m (r)成立，则称分解具有无损连接性。简称为无损分解。,算法3.3：判别一个分解的无损连接性。 R1，Rk是 R的一个分解，U=A1, ,An ，FFD1,FD2, ,FD，F是一极小依赖 集,记FDi为Xi A1i。 建立一张n列k行的表。每一列对应一个属性，每一行对应分解中的一个关系 模式。若属性Aj属于Ui，则在j列i行交叉处填上aj，否则填上bij ； 对每一个FDi做下列操作：找到Xi所对应的列中具有相同符号的那些行。考察 这些行中li列的元素，若其中有ali，则全部改为ali ；否则全部改为bmli ；m是 这些行的行号最小值。 比较扫描前后，表有无变化。如有变
