04章 规范化理论

第4章规范化理论 数据库设计 任务针对给定的应用环境和用户需求 建立一个合理的数据库模式 使数据库系统能够高效地存储和管理数据 指导工具规范化理论它主要研究的是关系模式中各属性之间的依赖关系及其对关系模式的影响 探讨良好的关系模式应具备的特性 以及使关系模式达到良好的方法 4 1问题的提出 4 1 1关系模式中可能存在的问题 例4 1 设有一个订购关系模式R 订单编号orderID 订单日期orderDate 客户编号custID 送货地址orderAddress 客户名称custName 商品编号pdID 商品名称pdName 订购数量quantity 存在的问题 数据冗余是指相同数据在数据库中多次重复存放一个订单的订单日期 客户编号和送货地址重复存储多次 一个客户的客户名称重复存储多次 一个商品的商品名称重复存储多次 导致的问题 不仅会浪费存储空间 而且可能造成数据的不一致性 更新异常插入异常例如如果有一位新客户尚未订购任何产品 则该客户的编号及名称就无法插入 如果一个新产品尚未有任何客户订购 则该商品的编号及名称也无法插入 导致的问题希望保存的数据无法存入数据库 存在的问题 续 修改异常例如如果更改一个客户的名称 则需要修改多个元组 如果更改商品的名称 则对应此商品的所有元组都必须修改 导致的问题如果仅部分修改而另外部分不修改 就会造成数据的不一致性 删除异常例如如果删掉某种商品的全部订购信息 则该商品的相关信息也将全部丢失 如果删掉一个客户的订购信息 则该客户的相关信息也同样丢失了 导致的问题不想删除的数据删除了 结论 订购关系模式R不是一个好的模式 好 的模式 不会发生插入异常 删除异常 更新异常 数据冗余应尽可能少 原因 由存在于模式中的某些数据依赖引起的 4 1 2解决的方法 解决方法 通过分解关系模式来消除其中不合适的数据依赖 将例4 1中订购关系模式R分解为四个关系模式 商品信息Product pdID pdName 客户信息Customer custID custName 订单信息Order orderID orderDate custID orderAddress 订单细节OrderDetail orderID pdID quantity 4 2函数依赖 数据依赖同一关系中属性值之间存在相互依赖与相互制约的关系函数依赖数据依赖中最重要的一种它反映了同一关系中属性间一一对应的约束 4 2 1函数依赖的基本概念 1 函数依赖定义4 1设有关系模式R U U是R的属性集合 X和Y是U的子集 对于R U 的任意一个可能的关系r 如果r中不存在两个元组 它们在X上的属性值相同 而在Y上的属性值不同 则称 X函数决定Y 或 Y函数依赖于X 记做X Y 一个错误的表 说明 1 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件 而是指R的所有关系实例均要满足的约束条件 2 函数依赖是语义范畴的概念 只能根据数据的语义来确定函数依赖 3 数据库设计者可以对现实世界作强制的规定 例4 2 在订购关系模式R中 如下依赖函数成立 orderID orderDate orderAdress custID custName orderID pdID quantity但是pdID quantity若规定custName不重 则custName custID 当X Y成立时 则称X为决定因素 Determinant 称Y为依赖因素 Dependent 当Y不函数依赖于X时 记为X Y 如果X Y 且Y X 则记其为X Y 2 平凡函数依赖与非平凡函数依赖 定义4 2在关系模式R U 中 对于U的子集X和Y 如果X Y 但Y X 则称X Y是非平凡的函数依赖若X Y 但Y X 则称X Y是平凡的函数依赖 例4 3 在订购关系模式R中 orderID orderID custID custName custName 对于任一关系模式 平凡函数依赖都是必然成立的 它不反映新的语义 因此若不特别声明 我们总是讨论非平凡函数依赖 3 完全函数依赖与部分函数依赖 定义4 3在关系模式R U 中 如果X Y 并且对于X的任何一个真子集X 都有X Y 则称Y完全函数依赖于X 记作XFY 若X Y 但Y不完全函数依赖于X 则称Y部分函数依赖于X 记作XPY 例4 4 在订购关系模式R中 orderID pdID P orderDate orderAdress orderID pdID Fquantity 4 传递函数依赖 定义4 4在关系模式R U 中 如果X Y Y Z 且Y X Y X 则称Z传递函数依赖于X 记作XTY 如果Y X 即X Y 则Z直接依赖于X 例4 5 在订购关系模式R中 orderID custID custID custName orderIDTcustName 4 2 2函数依赖的推理规则 逻辑蕴含定义4 5设有关系模式R U F X和Y是属性集合U的两个子集 如果对于R中每个满足F的关系r也满足X Y 则称F逻辑蕴含X Y 例4 6 在订购关系模式R中 orderID orderDate orderAdress 蕴含下面两个函数依赖 orderID orderDate orderID orderAdress函数依赖集的闭包定义4 6设F是函数依赖集合 被F逻辑蕴含的函数依赖的全体构成的集合 称为函数依赖集F的闭包 记为F 1 Armstrong公理系统 3条基本公理自反律 如果Y X Z 则X Y在R上成立 增广律 如果X Y在R上成立 且Z U 则XZ YZ 传递律 如果X Y和Y Z在R上成立 则X Z在R上也成立 2 几条有用的推理规则 合并性规则 若X Y X Z 则X YZ 分解性规则 若X Y 则X Z 伪传递性规则 若X Y WY Z 则WX Z复合性规则 若X Y W Z 则WX YZ通用一致性规则 若X Y W Z 则X W Y YZ 例4 7 给定关系模式R U F X Y为U的子集 F X Y 则F X X X X Y X XY Y Y Y XY XY X XY Y XY XY 例4 8 给定关系模式R U F X Y Z为U的子集 F X Y Y Z 则依据上述关于函数依赖集闭包计算公式 可以得到F 由43个函数依赖组成 属性集的闭包 通过计算F的闭包F 判断某个函数依赖成立与否不仅效率较低 而且还会产生大量 无意义 或者意义不大的函数依赖 定义4 7设F为属性集U上的一组函数依赖 X U XF A X A能由F根据Armstrong公理导出 XF 称为属性集X关于函数依赖集F的闭包 关于闭包的引理 引理4 1设F为属性集U上的一组函数依赖 X Y U X Y能由F根据Armstrong公理导出的充分必要条件是Y XF 用途将判定X Y是否能由F根据Armstrong公理导出的问题 转化为求出XF 判定Y是否为XF 的子集的问题 算法4 1 算法4 1求属性集X关于函数依赖F的属性闭包X 输入 关系模式R的全部属性集U U的子集X U上的函数依赖集F 输出 X关于F的属性闭包X 步骤 设i 0 1 2 1 初始化 i 0 X i X 0 X 2 求属性集A A是这样的属性 在F中寻找尚未用过的左边是X i 子集的函数依赖Y i X i 并且在F中有Y i Z i 则A Z 1 Z 2 Z i 3 X i 1 X i A 4 判断以下条件之一是否成立 若有条件成立 则转向 5 否则 i i 1 转向 2 X i 1 X i X i 中已包含了R的全部属性 在F中的每个函数依赖的右边属性中已没有X i 中未出现过的属性 在F中未用过的函数依赖的左边属性已没有X i 的子集 5 输出X i 1 即为X 例4 9 设有关系模式R U F 其中U ABCDE F AB C B D C E E C A C 计算 BC 计算过程 1 设X 0 BC 2 在F中找出尚未用过的左边是BC子集的函数依赖 B D C E 3 X 1 X 0 D E BCDE 4 很明显 X 1 X 0 5 在F中找出尚未用过的左边是BCDE子集的函数依赖E C 6 X 2 X 1 C BCDE 7 X 2 X 1 算法结束 8 BC BCDE 例4 10 设有关系模式R U F 其中U ABCDEI F A D AB C BI C DE I C E 求 AC 计算过程 1 令X AC 则X 0 AC 2 在F中找出未用过的左边是AC子集的函数依赖A D C E 3 X 1 X 0 D E ACDE 4 很明显 X 1 X 0 5 在F中找未用过的左边是ACDE子集的函数依赖DE I 6 X 2 X 1 I ACDEI 7 虽然X 2 X 1 但是F中未用过的函数依赖的左边属性已没有X 2 的子集 算法结束 8 AC X 2 ACDEI 4 2 3码的函数依赖表示 超码定义4 8设K为关系模式R U F 中的属性或属性集合 若K U 则K称为R的一个超码 SuperKey 侯选码定义4 9设K为关系模式R U F 中的属性或属性集合 若KFU 则K称为R的一个侯选码 CandidateKey 主码若关系模式R有多个候选码 则选定其中的一个做为主码 Primarykey 码的函数依赖表示 续 主属性和非主属性组成候选码的属性称为主属性 PrimeAttribute 不参加任何候选码的属性称为非主属性 Non keyAttribute 单码和全码单个属性是码 称为单码 SingleKey 整个属性组都是码 称为全码 AllKey 外码定义4 10关系模式R中属性或属性组X并非R的码 但X是另一个关系模式的码 则称X是R的外码 ForeignKey 也称外部码 4 2 4最小函数依赖集 1 函数依赖集的覆盖与等价定义4 11设F和G是关系模式R上的两个函数依赖集 如果所有为F所蕴含的函数依赖都为G所蕴含 即F 是G 的子集 F G 则称G是F的覆盖 定义4 12如果G是F的函数覆盖 同时F又是G的函数覆盖 即F G 则称F和G是相互等价的函数依赖集 引理4 2F G 的充分必要条件是 F G 且G F 2 最小函数依赖集 定义4 13对于一个函数依赖集F 称函数依赖集Fmin为F的最小函数依赖集 当且仅当Fmin满足下述条件 Fmin与F等价 F Fmin中每个函数依赖X Y的依赖因素Y只含有一个属性 Fmin中每个函数依赖X Y的决定因素X没有冗余 即只要删除X中任何一个属性就会改变Fmin的闭包 这样的函数依赖称为是左边不可约的函数依赖 Fmin中每个函数依赖都不是冗余的 即删除Fmin中任何一个函数依赖 Fmin就将变为另一个不等价于Fmin的集合 3 求最小函数依赖集的算法 可以证明 对任何一个函数依赖集都存在一个与其等价的最小依赖集 算法4 2计算F的最小函数依赖集Fmin 输入 一个函数依赖集F 输出 F的一个等价的最小函数依赖集Fmin 步骤 1 函数依赖的右部单属性化 利用分解性规则 使F中的任何一个函数依赖的右部仅含有一个属性 2 去掉多余的函数依赖 逐一地检查F中的每一个函数依赖X A 令G F X A 求X关于函数依赖集G的闭包X 若A X 则从F中去掉X A 即F F X A 3 去掉各函数依赖左部多余的属性 逐一地检查左部非单个属性的函数依赖XY A 求X关于函数依赖集F的闭包X 若A X 则以X A代替F中的XY A 即F F XY A X A 4 最终得到的函数依赖集F即为最小函数依赖集Fmin 例4 11 设有关系模式R U F 其中U ABC F A BC B C AB C 求F的最小函数依赖集Fmin 求解过程 1 函数依赖的右部单属性化 F A B A C B C AB C 例4 11 续 求解过程 2 去掉多余的函数依赖 检查A B 令G A C B C AB C A关于函数依赖集G的闭包A AC B A A B不是冗余的 检查A C 令G A B B C AB C A关于函数依赖集G的闭包A ABC C A A C是冗余的 从F中去掉 则F A B B C AB C 检查B C 令G A B AB C B关于函数依赖集G的闭包B B C B B C不是冗余的 检查AB C 令G A B B C AB关于函数依赖集G的闭包 AB ABC C AB AB C是冗余的 从F中去掉 则F A B B C 例4 11 续 求解过程 3 去掉各函数依赖左部多余的属性 F中的函数依赖左部均为单属性 不存在冗余的属性 因此F的最小函数依赖集Fmin A B B C 例4 12 设有关系模式R U F 其中U ABC F AB C A B B A 求F的最小函数依赖集Fmin 求解过程 1 F中所有函数依赖右部已经是单属性 2 F中没有冗余的函数依赖 判断过程略 3 去掉各函数依赖左部多余的属性 考察AB C 对于AB的真子集A A C成立吗 A关于F的闭包A ABC C A 则说明A C成立 B是多余的 F A C A B B A 即为Fmin A C A B B A 例4 12 续 如果改变考察顺序 先来判定B C B关于F的闭包B ABC C B 则说明B C成立 A是多余的 F B C A B B A 由此得到另一个最小函数依赖集Fmin B C A B B A 最小函数依赖集不是唯一的 不同的处理顺序 可能会得到不同的最小函数依赖集 练习 已知关系模式R U F U A B C D E G F A BE CB D E CG 求关系R的候选码 请验证 关系R是否满足函数依赖C DH 为什么 CDHSC1D1H1S1C1D1H2S1C1D1H1S2C2D2H2S3关系模式R A B C D E F A BC CD E B D E A 确定侯选码求Fmin 4 3规范化 规范化的关系其分量都是不可分的数据项最基本的条件规范化程度可以有6个不同的级别6种范式 第一范式 第二范式 第三范式 BC范式 第四范式和第五范式 各种范式之间存在联系 1NF 2NF 3NF BCNF 4NF 5NF通常把某一关系模式R为第n范式简记为R nNF 规范化的概念 一个低一级范式的关系模式 通过模式分解可以转换为若干个高一级范式的关系模式集合 这种过程就叫关系模式的规范化 4 3 1范式 1 第一范式 1NF 定义4 14如果关系模式R中每个属性值都是一个不可分解的数据项 则称该关系模式满足第一范式 简称1NF 记为R 1NF 第一范式是对关系模式的最起码的要求 不满足第一范式的数据库模式不能称为关系数据库 例 非规范化关系 0NF 1NF的方法 纵横延伸 例4 1 订购关系模式R R的码 orderID pdID R 1NFR存在数据冗余 更新异常 插入异常 删除异常 修改异常 的问题R不是一个好的关系模式 2 第二范式 2NF 定义4 15如果一个关系模式R 1NF 且它的所有非主属性都完全函数依赖于R的码 则R 2NF 分析 订购关系模式R R的函数依赖图R 2NFR存在问题的原因 存在orderDate orderAddress pdName等属性对码的部分函数依赖 分析 续 解决方法 投影分解product pdID pdName order cust orderID orderDate custID custName orderAddress orderDetail orderID pdID quantity 分析 续 Product的函数依赖图 2NForder cust的函数依赖图 2NForderDetail的函数依赖图 2NF 分析 续 order cust存在的问题 数据冗余更新异常 插入异常 删除异常 修改异常 属于2NF的关系模式并不一定是一个好的关系模式 3 第三范式 3NF 定义4 16如果一个关系模式R 2NF 且所有非主属性都不传递函数依赖于码 则R 3NF 分析 order cust order cust 2NF 3NForder cust存在问题的原因custName传递函数依赖于orderID 分析 order cust 续 解决方法 投影分解customer custID custName order orderID orderDate custID orderAddress 分析 order cust 续 customer的函数依赖图 3NForder的函数依赖图 3NF 分析关系模式STC 3NF的关系模式就一定是好的关系模式 关系模式STC 学生学号Sno 教师编号Tno 课程课号Cno 成绩Grade 每个教师只教一门课 但一门课可由几个教师讲授 存在如下函数依赖 Sno Cno Tno Sno Cno Grade Sno Tno Cno Sno Tno GradeTno CnoSTC的候选码 SNO CNO 和 SNO TNO 分析关系模式STC 续 STC 3NFSTC存在的问题 数据冗余更新异常 插入异常 删除异常 修改异常 属于3NF的关系模式并不一定是一个好的关系模式 4 BCNF范式 BCNF 定义4 17关系模式R 1NF 对任何非平凡的函数依赖X Y X均包含码 则R BCNF 若R BCNF所有非主属性都完全函数依赖于每个候选码 所有主属性都完全函数依赖于每个不包含它的候选码 没有任何属性完全函数依赖于非码的任何一组属性 若R BCNF 则R 3NF 反之不成立 分析关系模式STC STC 3NFSTC BCNFF Sno Cno Tno Sno Cno Grade Sno Tno Cno Sno Tno Grade Tno Cno STC存在问题的原因 主属性CNO对不包含它的码 Sno Tno 间存在不良函数依赖 分析关系模式STC 续 解决方法 投影分解方法1 SC Sno Cno Grade TC Tno Cno 方法2 ST Sno Tno Grade TC Tno Cno 3NF与BCNF的关系与区别 如果关系模式R BCNF 必定有R 3NF如果R 3NF 且R只有一个候选码 则R必属于BCNF 3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度的测度 一个模式中的关系模式如果都属于BCNF 那么在函数依赖范畴内 它已实现了彻底的分离 已消除了插入和删除的异常 3NF的 不彻底 性表现在可能存在主属性对码的部分依赖和传递依赖 练习题 指明下列关系模式最高属于第几范式 R X Y Z F XY Z R X Y Z F Y Z XZ Y R X Y Z F Y Z Y X X YZ R X Y Z F X Y X Z R W X Y Z F X Z WX Y 4 3 2模式分解 把低一级的关系模式分解为若干个高一级的关系模式的方法不是唯一的只有能够保证分解后的关系模式与原关系模式等价 分解方法才有意义 模式分解的定义 定义4 18设有关系模式R U 取定U的一个子集的集合 U1 U2 Un 使得U U1 U2 Un 如果用一个关系模式的集合 R1 U1 R2 U2 Rn Un 代替R U 就称 是关系模式R U 的一个分解 关系模式分解时一般应遵循的原则 关系模式进行无损连接分解 保持原来模型的函数依赖关系 例4 13 给定关系R 部门名称 主任姓名 主任电话 R上成立的函数依赖集F 部门名称 主任姓名 主任姓名 主任电话 例4 13 分解方法一 R1 部门名称 R2 主任姓名 R3 主任电话 这种方法既不符合无损连接 也没有保持函数依赖 例4 13 分解方法二 R1 部门名称 主任姓名 R2 主任姓名 主任电话 这种方法既既符合无损连接 也保持了函数依赖 例4 13 分解方法三 R1 部门名称 主任姓名 R2 部门名称 主任电话 这种方法虽然符合无损连接 但没有保持函数依赖 例4 13 分解方法四 R1 部门名称 主任电话 R2 主任姓名 主任电话 这种方法虽然符合无损连接 但没有保持函数依赖 例4 13 综上所述第一种分解方法是错误的分解方法第二种分解方法是最好的分解方法第三种和第四种分解方法都不是好的分解方法 1 无损分解 定义4 19设R是一个关系模式 F是R上的一个依赖集 R分解为关系模式的集合 R1 U1 R2 U2 Rn Un 如果对于R中满足F的每一个关系r 都有则称分解 是满足函数依赖集F的无损连接分解或无损分解 算法4 3 算法4 3判别一个分解的无损连接性输入 1 关系模式R U 其中U A1 A2 An 2 R U 上成立的函数依赖集F 3 R U 的一个分解 R1 U1 R2 U2 Rn Un 而U U1 U2 Un 输出 相对于F是否无损分解 算法4 3 续 计算步骤 1 构造一个k行n列的表格 每列对应一个属性Aj j 1 2 n 每行对应一个模式Ri Ui i 1 2 k 的属性集合 如果Aj在Ui中 那么在表格的第i行第j列处添上记号aj 否则添上记号bij 2 重复检查F的每一个函数依赖 并且修改表格中的元素 直到表格出现全a行或者表格不再发生变化为止 取F中函数依赖X Y 如果表格总有两行在X上分量相等 在Y分量上不相等 则修改Y分量的值 使这两行在Y分量上相等 实际修改分为两种情况 如果Y分量中有一个是aj 另一个也修改成aj 如果Y分量中没有aj 就用标号较小的那个bij替换另一个符号 3 修改结束后的表格中有一行全是a 即a1 a2 an 则相对于F是无损分解 否则不是无损分解 例4 14 设有关系模式R U F 其中U A B C D E F A C B C C D DE C CE A R U F 的一个模式分解 R1 A D R2 A B R3 B E R4 C D E R5 A E 试判断是否为无损分解 求解过程 F A C B C C D DE C CE A 由于表格中出现了全a行 因此关系模式R U 的分解 是无损分解 b13 b13 b13 a4 a4 a4 a3 a3 a1 a1 定理4 1 定理4 1关系模式R U F 分解为关系模式R1 U1 F1 R2 U2 F2 是具有无损连接性的分解的充分必要条件是 U1 U2 U1 U2 F 或者 U2 U1 U2 U1 F 例4 15 设有关系模式R U F U ABCD F A B B C D B 若将R分解成 ACD BD 试判断该分解是否是无损分解 求解过程 U1 ACD U2 BD U2 U1 D U2 U1 B 显然D B成立 因此该分解是无损分解 2 保持函数依赖 设有关系模式R U F F是属性集U上的函数依赖集 Z是U的一个子集 F在Z上的一个投影用 Z F 表示 定义为 Z F X Y X Y F XY Z 且Y X 定义4 20设有关系模式R U 的一个分解 R1 U1 R2 U2 Rn Un F是R U 上的函数依赖集 如果F 则称分解 保持函数依赖集F 简称保持函数依赖 例4 16 设有关系模式R U F 其中U ABCD F A B B C C D D A R U 的一个模式分解 R1 U1 R2 U2 R3 U3 其中U1 AB U2 BC U3 CD 试判定 是否具有保持函数依赖性 求解过程如下 1 由题意可知 A B B A B C C B C D D C 令G A B B A B C C B C D D C 求解过程 续 2 逐一检查F中的每个函数依赖X Y X Y G 是否成立 A B G B C G C D G因此A B G B C G C D G D关于函数依赖集G的闭包D ABCD A D 因此D A G 因此 成立 求解过程 续 3 逐一检查G中的每个函数依赖X Y X 是否成立 A B F B C F C D F 因此A B F B C F C D F B C D关于函数依赖集G的闭包B C D ABCD A B B C C D 因此B A G C B G D C G 因此 G F 成立 综上可知 分解具有保持函数依赖性 算法4 4 判别一个分解的保持函数依赖性 输入 1 关系模式R U 其中U A1 A2 An 2 R U 上成立的函数依赖集F 3 R U 的一个分解 R1 U1 R2 U2 Rn Un 而U U1 U2 Un 输出 是否保持函数依赖 算法4 4 续 计算步骤 1 令G F F G Result Ture 2 对于F中的第一个函数依赖X Y 计算 并令F F X Y 3 若Y 则令Result False 转向 4 否则 若F 转向 2 否则转向 4 4 若Result Ture 则保持函数依赖 否则不保持