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

第5章关系数据库理论 5 1关系模式的一般表示及设计中的问题5 2函数依赖5 3函数依赖的公理系统5 4关系模式规范形式5 5关系模式的规范化习题5 5 1关系模式的一般表示及设计中的问题 随着时间的不断变化 在不同的时刻关系模式的关系也会有所变化 但是现实世界的许多已知的事实 却限定了关系模式的所有可能的关系必须满足一定的约束 这些约束或者通过对属性取值范围的限定 如小学生的年龄要求大于等于6岁并且小于18岁 或者通过数据间的互相关联反映出来 后者称为数据依赖 数据依赖是数据库理论中最主要的组成部分 是数据库模式的理论基础 数据依赖是现实世界属性间相互联系的抽象 它表示数据间存在的一种限制或制约关系 人们已经提出了许多种类型的数据依赖 如函数依赖 多值依赖 连接依赖等 其中最重要的是函数依赖 是数据库模式设计中的关键所在 首先介绍什么是数据库模式 设任一关系模式用Ri表示 X R1 R2 Rn 则 R1 R2 Rn 就是X上的一个数据库模式 并不是任意一个数据库模式都是好的模式 我们研究函数依赖 其目的之一就是要从理论上找到判断设计好的数据库模式的标准 函数依赖普遍地存在于现实生活中 例如描述一个在校大学生的学习情况会涉及以下一些属性 学号 S 姓名 SN 性别 SS 身份证号 ID 系别 SD 学籍类型 SL 专业 SG 班级 SC 课程号 CB 课程名 CN 学期数 T 学分 CG 和成绩 G 其属性集合表示为U S SN SS ID SD SL SG SC CB CN T CG G 有人给出了以下两种数据库模式 第一种 1 R11 R12 其中 关系模式R11 S SN SS ID SD SL SG SC 关系模式R12 S CB CN T CG G 第二种 2 R21 R22 R23 其中 关系模式R21 S SN SS ID SD SL SG SC 关系模式R22 S CB G 关系模式R23 CB CN T CG 虽然它们都是符合定义的数据库模式 但使用起来的实际效果却大不相同 下面我们先来看 1 假设r是R12上的一个关系 如表5 1所示 表5 1关系r 这个关系r存在以下一些弊病 1 冗余 课程号J1的课程在第4学期开 课程名是 数据库系统 均在关系r的5个元组中都有记载 这显然是一种冗余 2 插入异常 如果有一门课 课程号为J5 课程名为 编译原理 学分为3 计划在第5学期开 但因为学号目前均没有确定值 构不成一个元组 所以无法插入到关系r中去 也即存在有计划开设的课程因为暂时没有学生上 就无法将这些课程号和课程名等信息保存到数据库中 这就产生了插入异常 3 删除异常 如果学号1110703的学生考J2课时违纪 分数作废 我们应在关系r中删去对应的这个元组 但这个元组其实还包含课程号为J2 课程名为数据结构 学分为3这样的信息 要删除只能删除整个元组 所以因学号为1110703的学生的J2课分数作废 而把课程号为J2 对应课程名为 数据结构 学分为3的信息也给 冤枉 地删除掉了 事实上 不管目前有无学生学习 数据结构 这门课程 这门课程的相关信息均应能保留在数据库中 上述这种关系模式则不能保证做到这一点 它可能产生删除异常 在数据库模式 1中 针对关系模式R12的某一关系r为什么会存在上述弊端呢 怎样才能在同一个属性集U上给出没有这些弊端的数据库模式呢 为了解决这些问题 我们先讨论几个重要的概念 5 2函数依赖 在现实世界中最广泛存在的一种数据依赖是函数依赖 例如 关系模式R12 S CB CN T CG G 中存在的函数依赖有 T函数依赖于CB CN函数依赖于CB CG函数依赖于CB G函数依赖于 S CB 等 下面给出相关概念的定义 5 2 1函数依赖的概念1 函数依赖 FunctionalDependency 简记为FD 定义5 1设R U 是属性集U上的一个关系模式 X Y U 若对R U 中任意一个可能关系r r中不可能有两个元组在X的属性分量值相等 而在Y的那些属性分量值不相等 则称 X函数决定Y 或 Y函数依赖于X 记作X Y X称为决定因子 或称为函数依赖的左部 Y称为函数依赖的右部 另一种定义为 设R U 是属性集U上的一个关系模式 X Y U 对R U 中任意一个可能关系r中的任意两个元组t和s 若有t X s X 则有t Y s Y 就称 X函数决定Y 或 Y函数依赖于X 对函数依赖 我们需要强调几点 1 当我们确定关系模式R中的某个函数依赖时 是指R的所有可能关系r都必须满足这个函数依赖 反之 如果R中只要有一个关系r不满足这个函数依赖 我们就认为R不存在这个函数依赖 2 当在确定一个关系模式中的函数依赖时 我们只能从属性含义上加以说明 而不能在数学上加以证明 3 只有数据库设计者才能决定是否存在某种函数依赖 这就使得数据库系统可以根据设计者的意图来维护数据库的完整性 例如 关系模式R12 S CB CN T CG G 中的函数依赖可表示为 CB T S CB G CB CN CB CG等等 2 函数依赖模式定义5 2设关系模式R U F是关于R的函数依赖集合 即若X Y F 则X Y U 则称 R F 为一个函数依赖模式 5 2 2几种特定的函数依赖1 非平凡函数依赖和平凡函数依赖定义5 3设关系模式R U X Y U 如果X Y 且Y不是X的子集 则称X Y为非平凡的函数依赖 如果X Y 且Y X 则称X Y为平凡的函数依赖 2 完全函数依赖和部分函数依赖定义5 4设关系模式R U X Y U 如果X Y 并且对于X的任何一个真子集Z Z Y都不成立 则称Y完全函数依赖于X 若X Y 但对于X的某一个真子集Z 有Z Y成立 则称Y部分函数依赖于X 例如 关系模式R12 S CB CN T CG G 中 CB T说明T完全函数依赖于CB 又因为 S CB G S CB CN G 则G部分依赖于 S CB CN 3 传递函数依赖定义5 5设关系模式R U X U Y U Z U 如果X Y Y Z成立 但Y X不成立 且Z X Z Y和Y X均不空 则称X Z为传递函数依赖 例如 关系模式R A B C D 其上的函数依赖集F A B B C A C AB D 则A C为传递函数依赖 注 在函数依赖中还有两种特殊的函数依赖 X 和 Y 它们对于任意关系都是成立的 在后面的介绍中我们不考虑这样的函数依赖 5 2 3逻辑蕴涵我们在讨论函数依赖时 有时需要从一些已知的函数依赖去判断另一些函数依赖是否成立 这个问题称为逻辑蕴涵问题 1 F逻辑蕴涵X Y定义5 6设关系模式R U X Y U F是关于R的函数依赖集合 又设X Y为R中的一个函数依赖 若对R的每一个关系r 满足F中每一个依赖 则r也必须满足X Y 我们就说F逻辑蕴涵X Y 或称X Y从F推导出来的 或称X Y逻辑蕴涵于F 2 函数依赖集合F的闭包定义5 7所有被F逻辑蕴涵的那些函数依赖组成的集合称为F的闭包 记为F 设关系模式R U U A B C F AB C C B 是R U 上的一组函数依赖 则F A A AB A AC A ABC A B B AB B BC B ABC B C C AC C BC C ABC C AB AB ABC AB AC AC ABC AC BC BC ABC BC ABC ABC AB C AB AC AB BC AB ABC C B C BC AC B 5 3函数依赖的公理系统 5 3 1Armstrong公理系统1 Armstrong公理系统的三条推理规则设关系模式R U X Y Z W U F是R的一个函数依赖集合 则Armstrong公理系统包含如下三条推理规则 1 自反律 Reflexivity 若Y X U 则F蕴涵X Y 2 增广律 又称外延性 augmentation 若F蕴涵X Y Z U 则F蕴涵XZ YZ 3 传递律 transitivity 若F蕴涵X Y和Y Z 则F蕴涵X Z Armstrong公理提供一整套推理规则 它能从F推导出F 中的所有依赖 所谓完备性 从F推不出任何不属于F 的依赖 所谓正确性 例如 关系模式R CITY ST ZIP 其中CITY表示城市 ST表示城市的街道 ZIP表示街道所在地区的邮政编码 函数依赖集合F CITY ST ZIP ZIP CITY 证明 ST ZIP 和 CITY ST 是候选键 证 因为ZIP CITY 由给定条件得出 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 是候选键 同理可证 CITY ST 也是候选键 证毕 2 Arestrong公理的三个推论由Arestrong公理可得到下面三个推论 1 合并规则 若X Y Y Z 则X YZ 2 分解规则 若X Y且Z Y 则X Z 3 伪传递规则 若X Y YZ W 则XZ W 3 Armstrong公理系统的正确性和完备性在证明Armstrong公理系统的正确性和完备性之前 有必要引入一个定义和两个引理 属性集合X关于函数依赖集F的闭包 记为X 定义5 8设关系模式R U U A1 A2 An Ai U X U X Ai X Ai能由F根据Armstrong公理系统导出且Ai U 则称X 是属性集合X关于函数依赖集F的闭包 例 设有关系模式R U U A B C D E F A BC CD E B D E A 则B F B D A F A B C D E 算法5 1计算属性集X的闭包X 输入 属性集X和函数依赖集F 输出 关于F的X的闭包X 方法 令X 0 X i 0 令X i 1 X i A V X i V W F A W 若已经没有V W F 能使X i 1 X I 则X X i 输出X 算法结束 否则 令i i 1 转去执行第 2 步 例 设关系模式R U 上的函数依赖集为F U A B C D E I F A D AB E BI E CD I E C 试计算 AE 解 令X 0 AE i 0 在F中找出左边是AE子集的函数依赖 因A D 则X 1 AED 因E C 则X 2 AEDC 因CD I 则X 3 AEDCI 因已没有V W F 能使X 3 1 X 3 则X X 3 即 AE ACDEI 引理5 1设关系模式R U U A1 A2 An Ai U X U X A1A2 An成立的充分必要条件是X Ai i 1 2 n 都成立 根据合并规则和分解规则 很容易得到这个引理的证明 留给读者自己证明 引理5 2设F是关系模式R U 上的函数依赖集 X Y U X Y能由F根据Armstrong公理系统导出的充分必要条件是Y X 证明 设Y A1A2 An A1 A2 An为属性 假设Y X F 根据X F的定义 对所有i 1 n X Ai可用Armstrong公理系统从F推出 根据合并规则 X Y也能从F推出 反之 假设X Y能用Armstrong公理系统推出 根据分解规则 对于所有i 1 2 n X Ai成立 根据X 的定义有Ai X F 故有A1A2 An X F 即Y X F 证毕 定理5 1Armstrong公理系统是正确的和完备的 证明 正确性 设r是关系模式R U 上的任一关系 t1 t2是r的任意元组 X Y Z U 若t1 X t2 X 则X的任意子集在t1 t2上的属性值也相等 因Y X 即有t1 Y t2 Y 根据函数依赖的定义 则X Y成立 设t1 XZ t2 XZ 则有t1 X t1 Z t2 X t2 Z 则t1 X t2 X t1 Z t2 Z 由X Y可知 t1 Y t2 Y 因此有t1 YZ t1 Y t1 Z t2 Y t2 Z t2 YZ 根据函数依赖的定义 XZ YZ成立 设X Y Y Z 若t1 X t2 X 若有t1 Y t2 Y 若t1 Y t2 Y 则有t1 Z t2 Z 显然若t1 X t2 X 则有t1 Z t2 Z 因此X Z成立 完备性 设关系模式R U 上的函数依赖集为F 我们采用证明完备性的逆否命题来证明完备性 即 如果函数依赖X Y不能由F根据Armstrong公理导出 它必然不为F蕴涵 设关系模式R U 上的函数依赖集为F 函数依赖X Y不包含在F 中 给出R上的一个关系r 该关系满足要求F 但不满足X Y 据此 须证明两点 1 r不满足X Y 2 r满足F中的所有的函数依赖 设关系模式R U U A1 A2 An Ai U 且ai bi是Ai域中的两个不同元素 1 i n 假设关系r中仅有两个元组t1和t2 元组t1 a1a2 an 元组t2被定义为 t2 Ai ai若Ai属于X bi若Ai不属于X 先证明r不满足X Y 若t1 X t2 X 假定t1 Y t2 Y 那么t2 Y 必全部为ai 并且Y X 但由于X X F 通过投影可得X Y在F 中 这一结果与X Y不包含在F 中的假设矛盾 因此 t1 Y t2 Y 不成立 即r不满足X Y 再证明r满足F中的所有的函数依赖 设W Z是F中任一函数依赖 W在r中有两种情况 1 W是X 的子集 根据属性闭包的定义 有X W 又因W Z 由函数依赖的传递性 则有X Z 所以根据引理5 2知 Z X 即W X 和Z X 同时成立 由r的构造可知 W Z在r上是成立的 2 W不是X 的子集 因此在r中 t1 W t2 W 从而W Z在r上总是成立的 Armstrong公理系统的正确性和完备性说明了 通过F推导出的函数依赖 与 F所蕴涵的函数依赖 两种说法是完全等价的 所以 F 也可以说成是由F出发经Armstrong公理系统导出的函数依赖集合 定理5 2合并规则 分解规则 伪传递规则是正确的 证明 若X Y 根据增广律得 XX XY 即X XY 若X Z 根据增广律得 XY YZ 根据传递律得 X YZ 若Z Y 根据自反律得 Y Z 又已知X Y 根据传递律得 X Z 若X Y 根据增广律得 XZ YZ 又已知YZ W 根据传递律得 XZ W 5 3 2函数依赖集合F的极小函数依赖集在实际应用中 经常需要将一个已知的函数依赖集变换为其它的或更简洁的表示形式 例如 需要把一个大的关系模式分解为几个小的关系模式 这时就需要将相应的函数依赖也投影到分解后的模式上 这就涉及一个函数依赖集的等价问题 下面 从蕴涵 或导出 的概念出发 再引出两个概念 这些概念在关系模式规范化处理中十分重要 1 两个函数依赖集F和G等价定义5 9设模式R上的两个函数依赖集F和G 如果有F G 则称F和G等价 记作F G 若F G 则F是G的一个覆盖 同样 G是F的一个覆盖 定理5 3设G和F是两个函数依赖集 F与G等价的充分必要条件是F G 且G F 证明 先证必要性 设G F 由于F F 所以有F G 同理可得G F 再证充分性 设F G 且G F 对于每个X Y F 则有X Y由F出发使用Armstrong公理导出 由F G 则X Y就可以由G 使用Armstrong公理导出 所以X Y G G 即X Y G 所以F G 同理可证G F 所以F G 即F与G等价 2 函数依赖集F的极小 或最小 函数依赖集 记为F 定义5 10如果函数依赖集F满足下列三个条件 1 F中任一函数依赖的右部仅含有一个属性 2 F中不存在这样的函数依赖X A 使得F与F X A 等价 3 F中不存在这样的函数依赖X A X包括真子集Z 使得 F X A Z A 与F等价 称此函数依赖集为F的极小 或最小 函数依赖集 记作F F的极小依赖集不一定是惟一的 例 设关系模式R U 上的函数依赖集为F U A B C D E G F AB C BC D ACD B D EG C A BE C CG BD CE AG F1 AB C BC D D E BE C CG D CE G C A D G CD B 可以验证F1是F的最小函数依赖集 定理5 4每个函数依赖集F都与它的极小依赖集F 等价 证明 采用构造性证明的方法 分三步进行 1 逐一对函数依赖集F中的各函数依赖X Y进行检查 只要有Y A1A2 Am m 2 则用 X Ai i 1 2 m 来取代X Y 2 依次检查F中各函数依赖X A 令G F X A 若A X G 则从F中删除X A 这是根据F与G等价的充分必要条件是A X G 上述操作循环进行 直到F不再改变为止 3 循环检查F中各函数依赖X A 若X B1B2 Bn 则逐一考查Bi i 1 2 n 如果A X Bi F 则用 X Bi A取代X A 因为F与 F X A X Bi A 等价的充分必要条件是A X Bi F 直到F不再改变为止 这时得到的就是一个与F等价的极小函数依赖集 算法5 2计算函数依赖集F的极小依赖集F 输入 一个函数依赖集F 输出 F的一个等价极小依赖集F 方法 1 应用分解规则 使F的每一个函数依赖的右部属性单一化 2 去掉各函数依赖左部多余的属性 具体办法是 逐个循环检查F中左边是非单属性的依赖X Y 设X B1B2 Bn 若Y X Bi F 则以 X Bi Y取代X Y 直到F不再改变为止 3 去掉多余的函数依赖 具体办法是 循环检查F中各函数依赖X Y 令G F X Y 若Y X G 则从F中去掉X Y 否则 不能去掉X Y 直到F不再改变为止 例 设关系模式R U 上的函数依赖集为F U A B C D E G F AB C BC D ACD B D EG C A BE C CG BD CE AG 试计算其等价的极小函数依赖集F 解 1 应用分解规则 使F的每一个函数依赖的右部属性单一化 结果为 F1 AB C BC D ACD B D E D G C A BE C CG B CG D CE A CE G 2 去掉各函数依赖左部多余的属性 因为CE A C A 则E是多余的 对于ACD B 由于 CD F1 ABCDEG 则A是多余的 其它函数依赖中无左部多余的属性 删除函数依赖左部多余的函数依赖后的结果为 F2 AB C BC D CD B D E D G C A BE C CG B CG D CE G 3 在F2中去掉多余的函数依赖 对于CG B 由于 CG ABCDEG 则是多余的 其等价的极小函数依赖集F 的结果为 F AB C BC D CD B D E D G C A BE C CG D CE G 5 4关系模式规范形式 5 4 1第一范式 1NF 定义5 11设R是一个关系模式 如果R的每个属性的值域 更确切地说是R的每一个关系r的属性值域 都是不可分的简单数据项 即是原子 的集合 则称这个关系模式属于第一范式 firstnormalform 简记作R 1NF 不满足1NF的关系称为非规范化的关系 满足1NF的关系称为规范化的关系 在任何一个关系数据库系统中 关系至少应该是第一范式 不满足第一范式的数据库模式不能称为关系数据库 在以后的讨论中 我们假定所有关系模式都是1NF 但注意 第一范式不能排除数据冗余和异常情况的发生 例 如表5 2描述的是学生选课的情况 表5 2学生选课关系 表5 2描述的学生选课关系不是1NF 因为课程一列包含多门课 不是原子值 而表5 3所示学生选课1关系是1NF 表5 3学生选课1关系 5 4 2第二范式 2NF 1 2NF定义5 12若关系模式R是1NF 而且每一个非主属性都完全函数依赖于R的候选键 则R称为第二范式 记作R 2NF 2 求出一个关系模式的所有候选键的方法一个关系模式候选键的定义前面已经给出 但还存在如何求出一个关系模式的所有候选键的问题 下面给出几种方法 供读者参考 3 若X是N类属性 则X必包含在R的任一候选键中 4 若X是R类属性 则X不在任一候选键中 5 若X是N类和L类组成的属性集 且X 包含了R的全部属性 则X是R的惟一候选键 例如 描述一个在校大学生的学习情况涉及以下一些属性 学号 S 姓名 SN 性别 SS 身份证号 ID 系别 SD 学籍类型 SL 专业 SG 班级 SC 课程号 CB 课程名 CN 学期数 T 学分 CG 和成绩 G 其属性集合表示为U S SN SS ID SD SL SG SC CB CN T CG G 有人给出了以下两种数据库模式 第一种 1 R11 R12 其中 关系模式R11 S SN SS ID SD SL SG SC 关系模式R12 S CB CN T CG G 第二种 2 R21 R22 R23 其中 关系模式R21 S SN SS ID SD SL SG SC 关系模式R22 S CB G 关系模式R23 CB CN T CG 对关系模式R11 S SN SS ID SD SL SG SC R11 上的函数依赖集合F11 S SN S SS S ID S SD S SL S SG S SC 显然 S 是关系模式R11的候选键 而且容易验证函数依赖模式 R11 F11 再没有其它关键字 于是 对于函数依赖模式 R11 F11 有 候选键集合KEY S 主属性集合PA S 非主属性集合NPA SN SS ID SD SL SG SC 由于对于关系模式R11 每个非主属性都完全函数依赖于候选键 所以 R11 属于2NF 对关系模式R12 S CB CN T CG G R12 上的函数依赖集合F12 CB T S CB G CB CG CB CN 对于函数依赖模式 R12 F12 由Armstrong公理系统 可以从F12 推出以下函数依赖 S CB CG S CB G S CB T S CB CB S CB CN S CB S 并且 由F12 推不出S G CB G 所以 S CB 是关系模式R12 的一个候选键 容易验证函数依赖模式 R12 F12 再没有其它候选键 于是 对于函数依赖模式 R12 F12 有 候选键集合KEY S CB 主属性集合PA S CB 非主属性集合NPA T CG CN G 因为CB T T NPA 而没有一个属性集合X KEY 能使X CB 非主属性T部分函数依赖于候选键 S CB 所以R12 不属于2NF 同理可得 关系模式R21 R22 R23 均属于2NF 请同学们自己验证 3 2NF的关系模式可能引发的问题及解决办法从上面例子可以看出 R12 不属于2NF R12 存在以下几个问题 1 冗余 某门课有400人选修 那么R12的关系中就会存在400个元组 相同的课程名 学期数和学期号均会出现400次 2 插入异常 假如新增一门课程 其CB 1011 CN 多媒体技术 学分 3 但因此课程还没有学生选修 则这样的元组不能插入R12 的关系中 3 删除异常 假如有一门课 如课程号为C5 目前只有一位学生选修了 但这位学生又不选了 那么C5这个数据项就要删除 由于C5是主属性 删除了C5 整个元组就不存在了 也必须删除 但这样也把不应该删除的信息删除了 造成删除异常 4 修改复杂 假如有400个学生选修的某门课 如课程号为C4 进行了调换 课程号和学期都发生了变化 则需要对相关的400元组中的课程号 课程名及学期均进行修改 造成修改的复杂化 关系模式R12 出现上述问题的原因是非主属性T CN CG部分函数依赖于候选键 S CB 为了消除这些部分函数依赖 可以采取投影分解的办法 此方法后面将详细进行介绍 5 4 3第三范式 3NF 定义5 13如果关系模式R是1NF 而且它的任何一个非主属性都不传递地依赖于任何候选键 则R称为第三范式 记作R 3NF 例 证明如果R是3NF的关系模式 则R也是2NF 证明 思路 关系模式中的非主属性对候选键的部分函数依赖的存在蕴涵着传递依赖的存在 设A是R的一个非主属性 K是R的一个候选关键字 且K A是一个部分依赖 那么 R中必存在某个K K 有K A成立 由于A是非主属性 因此A KK 从K K 可知K不函数依赖与K 但K K 成立 所以从K K 和K A可知 K A是一个传递依赖 从而 如果R是3NF的关系模式 则它的任何一个非主属性都不传递地依赖于任何候选键 也就不可能存在它的任何一个非主属性部分依赖于任何候选关键字 所以R也是2NF 证毕由此例可知 若R 3NF 则R的每一个非主属性既不部分函数依赖于候选键 也不传递函数依赖于候选键 根据第三范式的定义可得 若X A A不包含在X中 违反第三范式的条件 则下列两种情况之一会发生 X是某一个候选关键字的真子集或X是非关键字的真子集 例 我们仍然以描述一个在校大学生的学习情况的两种数据库模式的第一种数据库模式 1 R11 R12 为例 对关系模式R11 S SN SS ID SD SL SG SC R11 上的函数依赖集合F11 S SN S SS S ID S SD S SL S SG S SC 我们已经知道对于函数依赖模式 R11 F11 有 候选键集合KEY S 主属性集合PA S 非主属性集合NPA SN SS ID SD SL SG SC 且R11 2NF 又因为每个非主属性都不存在传递依赖于候选键 所以R11 3NF 对于关系模式R12 S CB CN T CG G R12 的函数依赖集合F CB T S CB G CB CG CB CN 我们已经知道对于函数依赖模式 R12 F12 有 候选键集合KEY S CB 主属性集合PA S CB 非主属性集合NPA T CG CN G 因为 S CB CB CB T 所以有 S CB T 即非主属性T传递函数依赖于候选键 S CB 所以R12 不属于3NF 也可以根据R12 不属于2NF 所以R12 也不属于3NF 同理可得 关系模式R21 R22 R23 均属于3NF 请同学们自己验证 部分依赖和传递依赖是产生数据冗余和插入 删除异常的两个主要原因 在3NF中不存在非主属性对候选关键字的部分依赖和传递依赖 所以满足3NF的关系模式可以消除很大一部分数据的异常和冗余 但是 3NF并没有排除主属性对候选关键字的传递依赖 因此 仍有可能存在数据的异常现象 例 有一个关系模式R U U S T C 设S表示学生 T表示教师 C表示课程 这些数据的语义描述如下 一名教师只能教一门课程 若干教师可以教同一门课程 一旦某一个学生选定了某门课程 就确定了一个固定的一个教师 R上的函数依赖集合F S C T S T C T C 对于函数依赖模式 R F 有 候选键集合KEY S C S T 主属性集合PA S C T 非主属性集合NPA 该关系模式的非主属性没有任何对候选键的传递依赖和部分依赖 所以R 3NF 但存在主属性C对候选键 S T 的部分依赖 并由此使得关系模式R存在如下一些问题 1 数据冗余较大 虽然一个教师只教一门课程 但每个选修该教师教授的这门课程的学生对应的元组都要记录这个教师的信息 从而产生一定的冗余 2 插入异常 如果出现某个学生刚刚入校 还未选修课程或某个教师开设了某门课程 但暂时没有学生选修的情况 由于受主属性不能为空的限制 导致有关该学生或教师的信息无法存入数据库中 造成插入异常 3 删除异常 如果选修了某门课程的学生全部毕业了 在删除与这些学生有关的元组的同时 可能将相应教师开设该门课程的信息也同时丢掉了 造成删除异常 5 4 4Boyce Codd范式 BCNF 定义5 14设关系模式R是1NF 如果对于R的每个函数依赖X Y X必为候选键 则R是BCNF 根据BCNF的定义可得 R中没有任何属性传递依赖于R的任一关键字 即属于BCNF的关系模式都具有如下三个性质 1 所有非主属性都完全函数依赖于每个候选键 2 所有主属性都完全函数依赖于每个不包含它的候选键 3 没有任何属性完全函数依赖于非候选键的任何一组属性 例 我们以描述一个在校大学生的学习情况的两种数据库模式的第二种数据库模式 2 R21 R22 R23 为例 对关系模式R21 S SN SS ID SD SL SG SC R21 上的函数依赖集合F21 S SN S SS S ID S SD S SL S SG S SC 我们已经知道对于函数依赖模式 R21 F21 有 候选键集合KEY S 主属性集合PA S 非主属性集合NPA SN SS ID SD SL SG SC 且R21 3NF 根据R21 3NF 且不存在主属性对候选键的部分依赖和传递依赖 所以R21 BCNF 对关系模式R22 S CB G R22上的函数依赖集合F22 S CB G 对于函数依赖模式 R22 F22 有 候选键集合KEY S CB 主属性集合PA S CB 非主属性集合NPA G 显然不存在主属性及非主属性对候选键的部分依赖和传递依赖 所以R22 BCNF 对关系模式R23 CB CN T CG R23 上的函数依赖集合F23 CB CN CB T CB CG 对于函数依赖模式 R23 F23 有 候选键集合KEY CB 主属性集合PA CB 非主属性集合NPA CN T CG 显然不存在主属性及非主属性对候选键的部分依赖和传递依赖 所以R23 BCNF 显然 BCNF的定义包含了3NF的定义 但是 反过来 如果R是3NF R未必是BCNF 根据以上给出的定义 我们可以看出各种范式之间的联系有BCNF 3NF 2NF 1NF 它们之间的转换方法为 对于1NF 通过消除它中任何非主属性对候选键的部分依赖 可以变成2NF 对于1NF 通过消除它中任何非主属性对候选键的部分依赖和传递依赖 可以变成3NF 对于3NF 通过消除它中任何主属性对候选键的部分依赖和传递依赖 可以变成BCNF 前面已经介绍过 不好的数据库模式中可能存在如下现象 某些关系模式存在冗余弊 插入弊 删除弊 修改弊等 产生这些弊端的主要原因是因为它们不属于3NF或BCNF 一般说来 如果一个关系数据库中的所有关系模式都属于BCNF 那么在函数依赖范畴内 它已实现了模式的彻底分解 达到了最高的规范化程度 消除了插入异常和删除异常 那么 对于不好的数据库模式 怎样才能清除这些弊端呢 其方法就是对存在弊端的关系模式进行分解 通过对关系模式的分解 可以达到使关系模式变成第三范式或更高级范式的要求 5 4 5多值依赖和第四范式 4NF 当我们完全在函数依赖的范畴内讨论关系模式的范式问题 仅仅考虑的是函数依赖这一种数据依赖 关系数据库中的关系模式能达到BCNF我们就认为很完美了 但如果考虑其他数据依赖 如多值依赖 就可能发现 属于BCNF的关系模式仍存在问题 那么 什么叫做多值依赖呢 1 多值依赖定义5 15设关系模式R U X Y Z U 并且Z U X Y 当且仅当R的任一关系r r在 X Z 上的每一个值对应一组Y的值 这组值仅仅决定于X值而与Z值无关时 称多值依赖X Y成立 例如 设某中学某一门课程由多个教师讲授 他们都使用一套相同的参考书 我们用关系模式R U 表示 U C T B 其中C表示课程 T表示教师姓名 B表示参考书名 表5 4表示了关系模式R的一个关系实例 表5 4表示了关系模式R的一个关系实例 关系模式R具有惟一的候选键 C T B 显然R BCNF 但关系模式R存在下列一些问题 当某一门课程 如数学 增加一名新教师 需要插入多个 针对数学是四个 元组 增加了插入操作的复杂性 当某门课 如英语 根据需要 要去掉一本参考书 也要去掉多个 针对英语是两个 元组 带来删除操作的复杂性 而且数据冗余也是很明显的 存在这些问题的原因是什么呢 经过分析我们发现 在这个关系模式R中 每个 C B 上的值对应一组T值 而且这种对应与B无关 例如 虽然与 C B 对应的两个元组 数学 初等几何 和 数学 初等代数 在B属性上的值不同 但它们对应同一组T值 王辉 张强 由此得出T多值依赖于C 即C T 就是关系模式R中存在的这种多值依赖的数据依赖 造成上述问题 多值依赖具有下面性质 设U是一个关系模式R的属性集合 X Y Z V W都是U的子集合 1 替代性 若X Y 则X Y 2 对称性 若X Y 则X U X Y 3 多值增广性 若X Y V W 则WX VY 4 多值传递性 若X Y Y Z 则X Z Y 5 聚集性 若X Y Z Y W Y W Z 则X Z 6 多值合并性 若X Y X Z 则X YZ 7 多值伪传递性 若X Y WY Z 则WX Z WY 8 多值分解性 若X Y X Z 则X Y Z X Y Z X Z Y 9 混合伪传递性 若X Y XY Z 则X Z Y 2 第四范式定义5 16如果关系模式R是1NF 对于R的每个非平凡多值依赖X Y Y不是X的子集 XY未包含R的全部属性 X都含有R的候选键 则R是第四范式 记为R 4NF 如果一个关系模式是4NF 则它一定是BCNF 反之不然 函数依赖是多值依赖的一种特殊情况 这两种依赖是最重要的数据依赖 事实上 数据依赖中除函数依赖和多值依赖之外 还有一种连接依赖 多值依赖是连接依赖的一种特殊情况 关于连接依赖的概念在此不再介绍 有兴趣的读者可以参阅有关书籍 5 5关系模式的规范化 根据需求分析中得到的用户要求 我们可以把关系分为两类 1 静态关系 其特点是一旦数据已加载 用户只能在这个关系上运行查询操作 这种关系的要求是必须属于1NF 2 动态关系 其特点是当数据加载后 经常对数据进行增 删 改操作 这种关系的要求是至少属于3NF 一旦关系模式不满足要求 就要对此关系模式进行分解 这是关系模式规范化的主要方法 但问题是 分解后的多个模式是否与原来的模式完全一样呢 即所表示的信息是否与原来的信息一致呢 所表达的函数依赖集是否与原来的函数依赖集等价呢 这就涉及分解的概念和原则 5 5 1关系模式分解的概念1 关系模式分解设关系模式R U U A1 A2 An F是R U 上的函数依赖的集合 R1 R2 Rn 是R的一个分解 使得R1 R2 Rn R 其中Ri Ui 且U U1 U2 Un F在Ri的属性集合Ui上的投影是Fi X Y X Y F X Y Ui 2 关系模式分解的主要目的其目的是为了解决关系模式中可能存在的插入 删除和修改时的异常情况 注 一般此工作由数据库设计者来进行的 3 关系模式分解的原则关系模式分解和原则 分解后产生的模式应与原模式等价 仅当下述三种情况之一 才能保证分解后产生的模式与原模式等价 1 分解具有 无损连接性 2 分解具有 保持函数依赖性 3 分解既要 保持函数依赖性 又要具有 无损连接性 5 5 2具有无损连接性的关系模式分解1 分解 具有无损连接性设关系模式R U F是R上的函数依赖集合 R1 R2 Rn 是R的一个分解 如果对R的任一满足F的关系r下式成立 则称分解 为具有无损连接性或分解 为无损连接分解 一般把关系r在分解 上的投影连接记为m r 即 满足无损连接的条件可表示为 r m r 无损连接分解的特性说明 关系模式分解后所表示的信息应与原模式等价 即分解后的多个关系再连接得到的新关系不能 丢失 信息 实际上 连接后的关系不会少了任何元组 而是可能多出一些元组 因与原来的关系不等价 所以是有损的 下面的引理表明了r和m r 间的关系 引理5 3设关系模式R U 及R上的关系r R1 R2 Rn 是R的一个分解 则有 1 r m r 2 3 m m r m r 2 判定一个分解的无损连接性算法算法5 3判定一个分解的无损连接性算法 输入 关系模式R A1 A2 An R上的分解 R1 R2 Rn R上的函数依赖集为F 输出 分解 是否具有无损连接性 方法 1 构造一个k行n列的初始表 第i行对应于关系模式Ri 第j列对应于属性Aj 如果Aj Ri 则在第i行第j列上填符号ai 否则填符号bij 2 逐个检查F中的每一个函数依赖 并修改表中的元素 具体办法如下 从函数依赖集F中取一个函数依赖X Y 在X的分量中寻找相同的行 然后将这些行中Y的分量改为相同的符号 如果其中有aj 则将bij 改为aj 否则 改为bij 指用其中的一个bij 替换另一个 通常是把下标改为较小的那个数 3 这样反复进行 如果发现某一行变成了a1 a2 an 即存在某一行全为a类符号 则分解 具有无损连接性 如果F中所有函数依赖都不能再修改表中的内容 且没有发现这样的行 则分解 不具有无损连接性 例 已知关系模式R U U A B C D E R上的函数依赖集F A C B C C D DE C CE A 分解 R1 A D R2 A B R3 B E R4 C D E R5 A E 判定 是否具有无损连接性 解 1 首先构造初始表 见表5 5 表5 5 2 检查A C 因为R1 A R2 A R5 A 修改b13 b23 b53 使其均用b13代替 修改结果如表5 6 表5 6 3 检查B C 因为R2 B R3 B 修改b13 b33 使其均用b13代替 修改结果如表5 7 表5 7 4 检查C D 因为R1 C R2 C R3 C R5 C 修改b24 b34 b54 使其均用a4代替 修改结果如表5 8 表5 8 5 检查DE C 因为R3 DE R4 DE R5 DE 修改R3 C R5 C 使其均用a3代替 修改结果如表5 9 表5 9 6 检查CE A 因为R3 CE R4 CE R5 CE 修改R3 A R4 A 使其均用a1代替 修改结果如表5 10 表5 10 定理5 5算法5 3能正确判断分解 是否是无损连接分解 证明 假设算法5 3的输出结果是false 即构造表 设为T 不可能出现全a行 可将算法5 3最后得到的表T看做R上的一个关系r 关系r是满足函数依赖集F的 由表T的构造知 表T中Ri对应行的Ri所含列Aj上应为aj 因此 r在分解 中的每一个Ri上投影连接后应有全a的行 但r中没有 这也就是说 m r r 即存在连接有损的反例 所以 分解 是连接有损的 定理5 6设关系模式R的一个分解 R1 R2 U1 U2和U分别是R1 R2和R的属性集合 F是R上的函数依赖集 具有无损连接性的充分必要条件是 U1 U2 U1 U2 F 或 U1 U2 U2 U1 F 证明 对这个分解应用算法5 3 构造初始表如表5 11所示 但省略了a和b的角标 因为忽略它们不影响证明的正确性 表5 11 容易证明 如果在属性A上的分量b能够被修改成a 则属性A属于 U1 U2 也容易利用由Armstrong公理导出 U1 U2 Y的步数归纳证明 如果 U1 U2 Y成立 则在Y上的那些b都将改成a 于是 对应R1的行全变成a当且仅当 U2 U1 U1 U2 或 U1 U2 U2 U1 类似地 对应于R2的行全变成a当且仅当 U1 U2 U1 U2 或 U1 U2 U1 U2 证毕 5 5 3具有保持函数依赖的关系模式分解1 分解 具有保持函数依赖设关系模式R U R1 R2 Rn 是R的一个分解 Ui是Ri的属性集合 Fi是F在Ui上的投影 如果F等价于F1 F2 Fn 则称分解 具有函数依赖保持性或 具有保持函数依赖的分解 2 判断分解是函数依赖保持性算法算法5 判断分解的函数依赖保持性 输入 关系模式R上的函数依赖集F R的一个分解 R1 R2 Rn 输出 确定 是否具有函数依赖保持性 方法 1 计算F到每一个Ri上的投影 i 1 2 k 2 FOR每一个X Y FDOZ1 X Z0 DOWHILEZ1 Z0Z0 Z1 FOR每一个RiDO Z1 Z1 Z1 Ri Ri ENDFORENDDOIFY Z1 RETURN true ENDFORRETURN false 例 给定关系模式R U U A B C D R上的函数依赖集F A B B C C D D A 关系模式R上的分解 R1 R2 R3 其中R1 AB R2 BC R3 CD 注 R1 AB是关系模式R1 U1 U1 A B 的简写 后面凡再出现 含义相同 试判断 分解 是否具有保持函数依赖性 解 1 先计算F到每一个Ri上的投影 AB F A B B A BC F B C C B CD F C D D C 2 显然 A B B C C D均得以保持 下面应用算法来判断D A是否会保持 初始 Z1 D Z0 第一遍 对R1 Z0 D Z1 D D A B A B D 对R2 Z0 D Z1 D D B C B C D 对R3 Z0 D Z1 D D C D C D D A B C D C D C D 第二遍 对R1 Z0 C D Z1 C D 对R2 Z0 C D Z1 C D C D B C B C B C D 对R3 Z0 B C D Z1 B C D B C D C D C D B C D 第三遍 对R1 Z0 B C D Z1 B C D B C D A B A B A B C D 对R2 Z0 A B C D Z1 A B C D 对R3 Z0 A B C D Z1 A B C D 第四遍 Z0 Z1 A B C D 根据算法5 4 下一步应该执行IF语句 因为A Z1 返回true 综上所述 分解 是具有保持函数依赖性 5 5 4通过分解实现关系模式的规范化关系模式分解的两个重要目标是 无损连接性和函数依赖保持性 任一个不是3NF的关系模式通过分解总可以成为3NF 只要关系模式在分解中保持函数依赖 或既保持函数依赖又具有无损连接性 就一定能达到3NF 但不一定能达到BCNF 算法5 5把一个关系模式R分解为3NF 使它具有函数依赖的保持性 输入 关系模式R和关系模式R的函数依赖F的极小依赖集F 输出 R的一个分解 R1 R2 Rn Ri为3NF i 1 2 n 具有函数依赖保持性 方法 1 如果极小依赖集F 中有一个依赖X A 且XA R 则输出 R 转向 4 2 如果R中某些属性与F 中所有函数依赖的左部和右部都无关 则将它们构成一个关系子模式Rj 并从R中将它们分出去 3 对于F 中的每一个Xi Ai 都构成一个关系子模式Ri XiAi 4 停止分解 输出 定理5 7设关系模式R U 的分解 R1 R2 Rn 是算法系模式都是3NF 证明 首先证明 具有函数依赖保持性 由算法5 5知 F 中的每个函数依赖都出现在 的某个关系模式中 所以 对于F 具有函数依赖保持性 而F 是F的极小函数依赖集 所以F 与F等价 于是 对于F具有函数依赖保持性 例 设关系模式R U 其中U C T H R S G R上的函数依赖集F CS G C T TH R HR C HS R 试将其保持函数依赖性分解为3NF 解 先求出F的极小函数依赖集 F CS G C T TH R HR C HS R 又因为 HS C T H R S G 所以HS是关系模式R的惟一候选键 根据Armstrong公理推论可得HS C 而C T 所以可得HS T 说明T传递依赖于候选键 所以该关系模式不满足3NF 利用算法5 5得 R1 CSG R2 CT R3 THR R4 HRC R5 HSR于是 求出的其保持函数依赖性分解 R1 R2 R3 R4 R5 满足3NF 算