第5章 关系数据库理论

《第5章 关系数据库理论》由会员分享，可在线阅读，更多相关《第5章 关系数据库理论（118页珍藏版）》请在金锄头文库上搜索。

1、第5章 关系数据库理论,5.1 关系模式设计中的问题 5.2 函数依赖 5.3 函数依赖的公理系统 5.4 关系模式规范形式 5.5 关系模式的规范化 习 题 5,5.1 关系模式设计中的问题,随着时间的不断变化， 关系也会有所变化。 从理论上能否找到判断设计好的数据库模式的标准?,例如:在校大学生的学习情况会涉及的属性： 学号（S）、 姓名（SN）、 性别（SS）、 身份证号（ID）、 系别（SD）、 学籍类型（SL）、 专业（SG）、 班级(SC)、 课程号（CB）、 课程名（CN）、 学期数（T）、 学分（CG） 、成绩（G）， 其属性集合表示为 U=S, SN, SS, ID, SD,

2、 SL, SG, SC, CB, CN, T, CG, G。 有人给出了如表5.1所示的表:,表 5.1 关 系 r 关系r存在问题? 学号 课程号 课程名 学期数 学分 成绩,关系r存在的弊病： (1) 冗余。 课程号为J1的课程在第4学期开， 课程名是“数据库系统”， 在关系r的5个元组中都有记载-冗余。 (2) 插入异常。 如果有一门课， 课程号为J5， 课程名为“编译原理”， 学分为3， 计划在第5学期开， 但因为学生还未选课,学号没有确定值， 构不成一个元组， 无法插入到关系r中去。 存在计划开设的课程因为暂时没有学生选， 无法将这些课程号和课程名等信息保存到数据库中-插入异常。,(

3、3) 删除异常。 如果学号1110703的学生考J2课时违纪， 分数作废， 应在关系r中删去这个元组。 但这个元组还包含课程号为J2， 课程名为数据结构， 学分为3的信息。 要删除只能删除整个元组. 因学号为1110703的学生的J2课分数作废， 而把课程号为J2， 课程名为“数据结构”， 学分为3的信息也给“冤枉”地删除掉了-删除异常。 不管目前有无学生学习“数据结构”这门课程， 这门课程的相关信息应保留在数据库中，,在数据库模式中， 针对关系模式的某一关系r为什么会存在上述弊端呢？ 怎样才能在同一个属性集U上给出没有这些弊端的数据库模式呢？,5.2 函数依赖,在现实世界中最广泛存在的一种数

4、据依赖是函数依赖。 例如，表 5.1 关 系 r 的关系模式 R=S, CB, CN, T, CG, G 存在的函数依赖有： T函数依赖于CB， CN函数依赖于CB， CG函数依赖于CB， G函数依赖于(S， CB)等。 学号（S） 、课程号（CB）、 课程名（CN）、 学期数（T）、 学分（CG） 、成绩（G），,5.2.1 函数依赖的概念 函数依赖（Functional Dependency， 简记为FD） 定义5.1 设R(U)是属性集U上的一个关系模式， X， YU。 若对R(U)中任意一个可能关系r， r中不可能有两个元组在X的属性分量值相等， 而在Y的那些属性分量值不相等， 则称“

5、X函数决定Y”， 或“Y函数依赖于X”， 记作XY。 X称为决定因子， 或称为函数依赖的左部， Y称为函数依赖的右部。,另一种等价定义为： 设R(U)是属性集U上的一个关系模式， X， YU。 对R(U)中任意一个可能关系r中的任意两个元组t和s， 若有tX=sX， 则有tY=sY， 就称“X函数决定Y”， 或“Y函数依赖于X”。 对函数依赖， 需要强调几点： (1) 当确定关系模式R中的某个函数依赖时， 是指R的所有可能关系r都必须满足这个函数依赖； 反之， 如果R中只要有一个关系r不满足这个函数依赖， 就认为R不存在这个函数依赖。,(2) 当在确定一个关系模式中的函数依赖时， 只能从属性含

6、义上加以说明， 而不能在数学上加以证明。 (3) 只有数据库设计者才能决定是否存在某种函数依赖。 这就使得数据库系统可以根据设计者的意图来维护数据库的完整性。 例如： 关系模式R=S, CB, CN, T, CG, G中的函数依赖可表示为： CBT; (S, CB)G; CBCN; CBCG等等。 学号（S） 、课程号（CB）、 课程名（CN）、 学期数（T）、 学分（CG） 、成绩（G），,5.2.2 几种特定的函数依赖 1. 非平凡函数依赖和平凡函数依赖 定义5.3 设关系模式R(U)， X、 YU: 如果XY， 且Y不是X的子集， 则称XY为非平凡的函数依赖； 如果XY， 且YX， 则称

7、XY为平凡的函数依赖。 (S, CB)G为非平凡的函数依赖 (S, CB) CB为平凡的函数依赖,2. 完全函数依赖和部分函数依赖 定义5.4 设关系模式R(U)， X， YU： 如果XY， 并且对于X的任何一个真子集Z， ZY都不成立， 则称Y完全函数依赖于X; 若XY， 但对于X的某一个真子集Z， 有ZY成立， 则称Y部分函数依赖于X。 例如： 关系模式R=S, CB, CN, T, CG, G中， CBT T完全函数依赖于CB； (S, CB, CN)G， G部分依赖于（S, CB, CN）因为(S, CB)G， 。,3 传递函数依赖 定义5.5 设关系模式R(U)， XU， YU， Z

8、U。 如果XY， YZ成立， 但YX不成立， 且Z-X、 Z-Y和Y-X均不空， 则称XZ为传递函数依赖。 例如： 关系模式R=A, B, C， 其上的函数依赖集F=AB, BC, AC， 则AC为传递函数依赖。 A:学号, B:学院, C:宿舍,学生按学院分宿舍 注： 在函数依赖中还有两种特殊的函数依赖： X和Y， 它们对于任意关系都是成立的。 不考虑这样的函数依赖。,5.2.3 逻辑蕴涵 在讨论函数依赖时， 有时需要从一些已知的函数依赖去判断另一些函数依赖是否成立。 这个问题称为逻辑蕴涵问题。 1 F逻辑蕴涵XY 定义5.6 设关系模式R(U)， X， YU ， F是关于R的函数依赖集合。

9、 又设XY为R中的一个函数依赖， 就说F逻辑蕴涵XY， 或称XY可从F推导出来的， 或称XY逻辑蕴涵于F。,2 函数依赖集合F的闭包 定义5.7 所有被F逻辑蕴涵的那些函数依赖组成的集合称为F的闭包， 记为F+。 设关系模式R(U)， U=A, B, C, F=ABC, CB是R(U)上的一组函数依赖， 则F+=AA, BB, CC,CB, CBC, ABA, ABB, ABC, ABAB, ABAC, ABBC, ABABC, ACA, ACB ,ACC, ACAC, BCB, BCC, BCBC, ABCA, ABCB, ABCC, ABCAB, ABCAC, ABCBC, ABCABC,

10、5.3 函数依赖的公理系统,5.3.1 Armstrong公理系统 1 Armstrong公理系统的三条推理规则 设关系模式R(U)， X， Y， Z， WU， F是R的一个函数依赖集合， 则Armstrong公理系统包含如下三条推理规则：,（1） 自反律（Reflexivity）: 若Y X U， 则F蕴涵XY。 （2） 增广律（又称外延性， augmentation）: 若F蕴涵XY， Z U， 则F蕴涵XZYZ。 （3） 传递律（transitivity）: 若F蕴涵XY和YZ， 则F蕴涵XZ。 Armstrong公理提供一整套推理规则， 它能从F推导出F+中的所有依赖（完备性）， 从F

11、推不出任何不属于F+的依赖（正确性）。,2 Arestrong公理的三个推论 由Arestrong公理可得到下面三个推论： (1) 合并规则: 若XY， XZ， 则XYZ。 (2) 分解规则: 若XY且ZY， 则XZ。 (3) 伪传递规则: 若XY， YZW， 则XZW。,定理5.2 合并规则、 分解规则、 伪传递规则是正确的。 证明： 合并规则: 若XY， XZ， 则XYZ。 若XY， 根据增广律得， XXXY， 即XXY。 若XZ， 根据增广律得， XYYZ， 根据传递律得， XYZ。 分解规则: 若XY且ZY， 则XZ。 若ZY， 根据自反律得， YZ， 又已知XY， 根据传递律得， X

12、Z。 伪传递规则: 若XY， YZW， 则XZW。 若XY， 根据增广律得， XZYZ， 又已知YZW， 根据传递律得， XZW。,属性集合X关于函数依赖集F的闭包 定义5.8 设关系模式R(U)， U=A1, A2, , An， AiU， XU， X+=Ai|XAi能由F根据Armstrong公理系统导出且AiU， 则称 X+是属性集合X关于函数依赖集F的闭包。,算法5.1 计算属性集X的闭包X+。 输入： 属性集X和函数依赖集F。 输出： 关于F的X的闭包X+。 方法： 令X(0)=X， i=0; 令X(i+1)=X(i)A|VX(i)， VWF, AW; 若已经没有VWF， 能使X(i+

13、1)X(i)， 则X+=X(i),输出X+， 算法结束； 否则， 令i=i+1， 转去执行第(2)步。,【例】 设关系模式R(U)上的函数依赖集为F, U=A, B, C, D, E, I; F=AD, ABE, BIE, CDI, EC， 试计算(AE)+。 解： 令X(0)=AE， i=0; 在F中找出左边是AE子集的函数依赖， AD, ， 因则X(1)=AED; 因EC，则X(2)=AEDC； 因CDI, 则X(3)=AEDCI; 因已没有VWF， 能使X(3+1)X(3)， 则X+=X(3), 即(AE)+=ACDEI。,【例】 设有关系模式R(U)， U=A, B, C, D, E，

14、 F=ABC, CDE, BD, EA， 求B+F? A+F? B+F=B, D， A+F=A, B, C, D, E,引理5.1 设关系模式R(U), U=A1, A2, , An, AiU, XU， XA1A2An成立的充分必要条件是XAi(i=1, 2, , n)都成立。 根据合并规则和分解规则， 很容易得到这个引理的证明。 引理5.2 设F是关系模式R(U)上的函数依赖集， X、 YU， XY能由F根据 Armstrong公理系统导出的充分必要条件是YX+。,例: 关系模式R(CITY, ST, ZIP)， 其中CITY表示城市， ST表示城市的街道， ZIP表示街道所在地区的邮政编码

15、， 函数依赖集合F=(CITY, ST)ZIP, ZIPCITY， 证明ST, ZIP和CITY, ST是候选键。 ST, ZIP +=? CITY, ST +=?,证： 因为ZIPCITY （由给定条件得出） (ST, ZIP)(CITY, ST) （由增广律得出） (CITY, ST)ZIP （由给定条件得出） (CITY, ST)(CITY, ST, ZIP) （由增广律得出） (ST, ZIP)(CITY, ST, ZIP) （由传递律得出） 并且， ST(CITY, ST, ZIP)和 ZIP(CITY, ST, ZIP) 均不成立， 所以(ST, ZIP)是候选键。 同理可证 (C

16、ITY, ST)也是候选键。 证毕。 另:ST, ZIP +=? CITY, ST +=?,5.3.2 函数依赖集合F的极小函数依赖集 实际应用中， 经常需要将一个已知的函数依赖集变换为更简洁的表示形式。 例如， 把一个大的关系模式分解为几个小的关系模式， 就需要将相应的函数依赖也投影到分解后的模式上。 这涉及一个函数依赖集的等价问题。,1. 两个函数依赖集F和G等价 定义5.9 设模式R上的两个函数依赖集F和G， 如果有F+=G+， 则称F和G等价， 记作FG。 若FG， 则F是G的一个覆盖， 同样， G是F的一个覆盖。,2. 函数依赖集F的极小（最小）函数依赖集（Fmin） 定义5.10 如果函数依赖集F满足下列三个条件：