7-关系数据库设计与范式理论

关系数据库设计 主要内容 什么样的关系数据库设计是好的 函数依赖范式判断模式分解及相关算法 问题的提出 问题针对一个具体问题 如何构造合适的 更好的 数据模式 思路讨论一个关系中属性间的依赖情况讨论如何根据属性间依赖关系来判定关系是否有某些不合适的性质掌握基于函数依赖概念的关系数据库设计的规范方法 银行数据库模式 branch branch name branch city assets customer customer id customer name customer street customer city loan loan number amount loan branch loan number branch name account account number balance account branch account number branch name employee employee id employee name telephone number start date dependent name employee id dname borrower customer id loan number depositor customer id account number cust banker customer id employee id type works for worker employee id manager employee id payment loan number payment number payment date payment amount savings account account number interest rate checking account account number overdraft amount 更大的模式 实例分析1 方案1 borrower customer id loan number loan loan number amount 方案2 bor loan customer id loan number amount 显然 方案2对应的表不必连接运算 但可能出现信息冗余 更大的模式 实例分析2 方案1 loan branch loan number branch name loan loan number amount 方案2 loan amt br loan number amount branch name 显然 方案2对应的表不必连接运算 且没有信息冗余 更大的模式 分析 试图将太多的属性放在一个表里 可能会导致异常 数据冗余 同样的信息在多条元组中重复出现插入异常 插入元组时可能由于部分属性的值未知而导致插入失败删除异常 部分元组的删除可能其他信息的丢失更新异常 存在数据冗余时 更新某元组而不是所有可能的元组 可能导致数据不一致 如 Movie Star数据库模式 更小的模式 实例分析1 假设已知模式bor loan customer id loan number amount 如何将模式分解成 borrower customer id loan number loan loan number amount 更小的模式 实例分析2 并不是所有的分解都是有益的如将employee表分解该分解是有损的 即无法通过自然连接重建原模式 更小的模式 实例分析3 模式S C M S学号 C班级 M班主任 该模式设计不好 存在数据冗余 插入异常 删除异常和更新异常 以下哪一个分解是好的呢 第一范式 FirstNormalForm 1NF 定义 关系R中每个属性域都是原子的 则R 1NF非1NF的例子employee表中的children属性域是若干名字的集合employeeID由6位字符串组成 其中前两个字母表示所属部门 后面四位数字表示部门内编号 数据库应用程序中 字符串通常被认为是原子的 应尽量避免利用应用程序对数据进行解析 模式中使用非原子属性会导致设计中存储冗余数据如 为每一个客户存储一个accounts集合 为每一个account存储一个owners集合我们假设所有关系满足1NF 范式理论 目的 通过属性间的依赖关系 分析关系模式设计是否 好 规范化 将一个低一级范式的关系模式分解为若干个高一级范式的关系模式的过程基本思想 通过模式分解 逐步消除关系模式的数据依赖 函数依赖范畴 中不合适的部分 部分函数依赖和传递函数依赖 但又不丢失原模式中的信息 无损连接 模式分解可以消除冗余 解决更新异常等问题 但也要付出做连接运算等昂贵的代价 函数依赖 定义设R U 是属性集U上的关系模式 X Y是U的子集 若对于R U 的任意一个可能的关系r r中不可能存在两个元组在X上的属性值相等 而在Y上的属性值不等 则称X函数确定Y或Y函数依赖于X 记作术语和记号 但 则称是平凡函数依赖 但 则称是非平凡函数依赖若 则X叫做决定因素 如 customer name loan number customer namecustomer name customer name均为平凡函数依赖 函数依赖 在R U 中 如果 并且对于X的任何一个真子集X 都有 则称Y对X完全函数依赖 记作若 但Y不完全函数依赖于X 则称Y对X部分函数依赖 记作在R U 中 如果 则称Z对X传递函数依赖 记作K是关系模式R的超码当且仅当K RK是关系模式R的候选码当且仅当K R 且forno K R F P 传递 第二范式 SecondNormalForm 2NF 定义 若R 1NF 且每个非主属性完全依赖于码 则R 2NF说明 不存在非主属性部分依赖于码的关系为2NF 例 学生 课程 成绩管理关系模式属性组U 学号SNO 系名SDEPT 系主任MN 课程号CNO 成绩G 数据依赖 该模式存在非主属性部分函数依赖 达不到2NF 属于1NF 分解方法 一个1NF 但非2NF的关系总是可以被分解成为一组2NF的关系方法 已知关系R A B C D A B 为主码 即 A B C A B D 且A D 则将R分解成为 R1 A D A为主码R2 A B C A B 为主码 A为外码 第三范式 ThirdNormalForm 3NF 定义 若R 2NF 且它的任何一个非主属性都不传递依赖于任何候选码 则R 3NF说明 即不存在非主属性部分依赖和传递依赖于码的关系为3NF S M中存在传递传递依赖 故该模式不是3NF 上例分解为 SC SNO CNO G S M SNO SDEPT MN 分解方法 一个2NF 但非3NF的关系总是可以被分解成为一组3NF的关系方法 已知关系R A B C A为主码 A B A C 且B C 则可将R分解为 R1 B C B为主码R2 A B A为主码 B为外码 函数依赖集的闭包 给定函数依赖集F 有一些函数依赖是在F中被逻辑蕴涵的如 如果A B且B C 推理可得A C函数依赖集F中逻辑蕴含的所有函数依赖 成为F的闭包 表示为F F 是F的超集 BCNF 已知函数依赖集合F对应的F 对任意 R和 R 若任意函数依赖 都满足 是平凡的 即 且 是R的超码 则关系R满足BCNF 例1 bor loan customer id loan number amount 有loan number amount但loan number不是超码 因此bor loan不是BCNF 定义 若每一个决定因素都包含 或是 码 则R BCNF Boyce CoddNormalForm BCNF 关系的关键字为 course teacher book 由于不存在非平凡的函数依赖 因此模式满足BCNF course teacher book databasedatabasedatabasedatabasedatabasedatabaseoperatingsystemsoperatingsystemsoperatingsystemsoperatingsystems AviAviHankHankSudarshanSudarshanAviAviPetePete DBConceptsUllmanDBConceptsUllmanDBConceptsUllmanOSConceptsStallingsOSConceptsStallings classes 例2 BCNF模式分解方法 给定关系模式R 假设其中的一个非平凡函数依赖 不符合BCNF约束 则将R分解为 U R 例如 已知bor loan customer id loan number amount 且loan number amount 即bor loan不满足BCNF设 loan number amount则bor loan可分解为 U loan number amount R customer id loan number BCNF模式分解算法 result R done false 计算F while notdone doif result中存在不属于BCNF的模式Ri thenbegin令 是Ri上的一个非平凡函数依赖 满足 Ri不存在F 中 且 result result Ri Ri endelsedone true 注 用这个算法产生的分解不仅是一个BCNF分解 而且是无损分解 例3 已知关系模式R和函数依赖集FR branch name branch city assets customer name loan number amount F branch name assets branch cityloan number amount branch name Key loan number customer name 可知 R不是BCNF 因为存在函数依赖 其决定因素不包含 是 码模式分解为 R1 branch name branch city assets R2 branch name customer name loan number amount R21 branch name loan number amount R22 customer name loan number 最终的分解 R1 R21 R22 练习 设计关于供应商供应零件的数据库 要求达到3NF最初的设计 R S Sname City Status P Pname Color Weight QTY 主码 S P 函数依赖 S Sname S Status S City City Status P Pname P Color P Weight 可见 其中有部分依赖 还有传递依赖 该模式仅为1NF 分解 第一步分解 消除部分依赖 得到 R1 S P QTY S P 为码R2 S Sname City Status S 为码R3 P Pname Color Weight P 为码R1和R3都已达到3NF 但R2存在传递依赖 仅是2NF第二步分解 消除R2中的传递依赖 得到 R2 1 S Sname City S 为码R2 2 City Status City为码R1 R2 1 R2 2和R3就是达到3NF的关系模式 此例中也已达到BCNF 判断是否BCNF 例2 SJP 学生S 课程J 名次P S J 和 J P 均为候选码函数依赖为 S J P J P S其中 两个决定因素均包含 是 候选码可见SJP BCNF 例3 STJ 学生S 教师T 课程J S T 和 S J 均为候选码函数依赖为 S J T S T J T J其中 T为决定因素 但不包含任何一个候选码可见STJ BCNF 规范化过程小结 函数依赖理论 已知函数依赖集 求解所有被逻辑蕴涵的函数依赖保持无损连接特性的BCNF或3NF模式分解算法保持依赖保持特性的BCNF或3NF模式分解算法 模式分解应满足的特性 无损连接性 Losslessjoin 保持函数依赖性 Preservedependency 相互独立性分解后的关系模式中 当修改某一个关系数据时 不会影响其他关系 Armstrong公理 Armstrong公理 if then reflexivity自反律 if then augmentation增补律 if and then transitivity传递律 这些规则是正确有效的完备的用于求解F 例子 R A B C G H I F A B A C CG H CG I B H F 中的部分成员A H通过传递律A B和B H可得AG I对A C进行增补 得到AG CG再通过传递律可得CG ICG HI对CG I进行增补 可得CG CGI 对CG H进行增补 可得CGI HI 再应用传递律可得 算法1 求属性集X关于函数依赖集F的闭包 计算属性闭包可用于检测超码 检测函数依赖 计算F的闭包 例1 例2 例3 R A B C G H I F A B A C CG H CG I B H 求 AG 1 result AG2 result ABCG A CandA B 3 result ABCGH CG HandCG AGBC result ABCGHI CG IandCG AGBCH AG是一个候选码吗 AG R AG是一个超码吗 A R G R 最小函数依赖集 函数依赖集合中可能存在冗余 如 A C对于 A B B C 来说 是冗余的 A B B C A CD 可以被简化为 A B B C A D A B B C AC D 可以被简化为 A B B C A D 最小函数依赖集是指没有任何冗余的函数依赖集 定义 如果函数依赖集F满足下列条件 则称F为一个极小函数依赖集 或称最小依赖集F 性质 函数依赖集F的最小函数依赖集不一定唯一 它与求解的次序有关定理 每一个函数依赖集F均等价于一个最小依赖集F 这样 R可以用R来取代 算法2 求函数依赖F的最小依赖集F 例子 1 考查A B 去掉它 计算A A C 不包含B 不能去掉2 考查B A 去掉它 计算B B C A 包含A 可去掉它3 考查B C 去掉它 计算B B 不包含C 不能去掉4 考查A C 去掉它 计算A A B C 包含C 可去掉它5 考查C A 去掉它 计算C C 不包含A 不能去掉 函数依赖集F的最小函数依赖集不一定唯一 它与求解的次序有关 R A B C F A BC B C A B AB C F可分解并简化 F A B A C B C A B AB C A B重复出现 去掉1个考虑到有A C B为多余属性 去掉AB C考虑到A C可由A B B C得到 去掉A C最小函数依赖集F 是 A B B C 例2 算法3 检验一个分解是否具有无损连接性 初始表 最后结果 R1 R2 R3 R1 R2 R3 例1 例2 R A B C F A B C B 分解1 A B A B A C 分解2 A B A B B C C B 分析两种分解的无损连接性 分解1只具有无损连接性 分解2不具有无损连接性 AB AC a2 AB BC 例3 设S C M 学号 班级 班主任 F 学号 班级 班级 班主任 学号 班主任 存在传递依赖 为2NF 有三种可能的分解 哪些具有无损连接性 该关系属于几范式 算法4 检验一个分解是否具有保持函数依赖性 例1 设S C M 学号 班级 班主任 F 学号 班级 班级 班主任 学号 班主任 三种分解 例2 R A B