数据库系统原理 Database System Principles 四川大学计算机学院 段磊 leiduan@scu.edu.cn 2014.9
第六章关系数据库理论 意义 提供分析和判断数据库模式好坏的准则 指导设计好的数据库模式 难易度 本章是本书最难的部分之一 对于应用设计十分有用
本章目录 6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 6.4 模式的分解 2014-11-19 数据库系统概论 - 第 6 章 3/84
6.1 问题的提出 -- 什么是不好的数据库设计 我们目前为止掌握的知识尚无法解决大量的具体设计问题, 即关系模式该如何选择 应用数据库应该由多少个表组成? 每个表有哪些字段? 本章从理论上解决关系数据库的逻辑设计问题 2014-11-19 数据库系统概论 - 第 6 章 4/84
关系模式 一个关系模式应当是一个五元组 R(U, D, DOM, F) F 是本章开始引入的数据依赖集 由于 D 和 DOM 对模式设计关系不大, 因此我们在本章中把关系模式看作是一个三元组 :R<U, F> 当且仅当 U 上的一个关系 r 满足 F 时,r 称为关系模式 R<U, F> 的一个关系 关系, 作为一张二维表, 我们对它有一个最起码的要求 : 每一个分量必须是不可分的数据项 满足了这个条件的关系模式就属于第一范式 (1NF) 2014-11-19 数据库系统概论 - 第 6 章 5/84
数据依赖 我们的任务是研究模式设计, 研究设计一个 好 的 ( 没有 毛病 的 ) 关系模式的办法 数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系 它是现实世界属性间相互联系的抽象, 是数据内在的性质, 是语义的体现 现在人们已经提出了许多种类型的数据依赖, 其中最重要的是函数依赖 (Functional Dependency, FD) 和多值依赖 (Multivalued Dependency, MVD) 2014-11-19 数据库系统概论 - 第 6 章 6/84
函数依赖 函数依赖极为普遍地存在 例如, 描述学生的关系, 可以有学号 (SNO), 姓名 (SNAME), 系名 (SDEPT) 等几个属性 由于一个学号只对应一个学生, 一个学生只在一个系学习 因而当 学号 值确定之后, 姓名和该生所在系的值也就被唯一地确定了 上述值的确定就象数学函数 : 自变量 x 确定之后, 相应的函数值 f(x) 也就唯一地确定 我们说 SNO 函数决定 SNAME 和 SDEPT, 或者说 SNAME, SDEPT 函数依赖于 SNO, 记为 :SNO SNAME, SNO SDEPT 2014-11-19 数据库系统概论 - 第 6 章 7/84
例 : 学生选课模型的关系模式 例如, 前面介绍的学生选课模型, 可以用一个关系模式表示 : SC(Sno, Sname, Sage, Sgendar, Sdept, Cno, Cname, Grade) 一个可能的关系为 : S1 赵一 18 男 CS 1 C 语言 80 S1 赵一 18 男 CS 2 数据库原理 82 S2 钱二 19 男 CS 1 C 语言 80 可以看出, 该模式存在的主要问题是冗余 2014-11-19 数据库系统概论 - 第 6 章 8/84
冗余带来的问题 冗余是不可避免的 在一定程度内也是合理的 但是, 过度的冗余则会给数据库带来三类大的问题 : 插入异常 ( 学生不选课, 其基本信息就无法插入 ) 删除异常 ( 删除学生选课信息, 其基本信息也被删除 ) 修改复杂 ( 修改某学生的基本信息, 要随选课多次被修改 ) 2014-11-19 数据库系统概论 - 第 6 章 9/84
解决冗余的方法 解决的方法 一个大关系分解为若干个小关系 感性经验 : 多用小关系, 少用字段 如前面的 SC 大关系分解为第三章的 Student, SC 和 Course 三个小关系, 即可消除三类异常 2014-11-19 数据库系统概论 - 第 6 章 10/84
问题的引出 为什么小关系比大关系好呢? 现在我们要讨论的就是这个问题 从上面的分解观察到 : 如果在一个关系模式内, 函数依赖形式上如果只有 : 码 非主属性 的形式, 冗余就较小, 三类异常就没有了 2014-11-19 数据库系统概论 - 第 6 章 11/84
本章目录 6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 6.4 模式的分解 2014-11-19 数据库系统概论 - 第 6 章 12/84
6.2 规范化 目的 将具有不合适性质的关系转换为更合适的形式 要求 掌握函数依赖的定义及判定 ; 掌握 1NF 到 BCNF 的定义及判定 ; 了解多值依赖, 理解 4NF 的定义 2014-11-19 数据库系统概论 - 第 6 章 13/84
6.2.1 函数依赖 ( 注意 : 现在还不能用到码的概念 ) 定义 6.1 设 R(U) 是属性集 U 上的关系模式 X, Y 是 U 的子集 若对于 R 的任何一个可能的关系 r,r 中不可能存在两个元组在 X 属性值上相等而在 Y 属性值上不等, 则称 X 函数确定 Y 或 Y 函数依赖于 X, 记作 :X Y 2014-11-19 数据库系统概论 - 第 6 章 14/84
6.2.1 函数依赖 X Y, 且 Y X, 则称 X Y 是非平凡的函数依赖 若不特别声明, 我们总是讨论非平凡的函数依赖 X Y, 但 Y X 则称 X Y 是平凡的函数依赖 理解为 : 整体一致, 部分一致, 没有特殊意义 ( 过于 平凡 ) 2014-11-19 数据库系统概论 - 第 6 章 15/84
6.2.1 函数依赖 若 X Y, 则 X 叫做决定因素 (Determinant) 若 X Y,Y X, 则记作 X Y 在这种情况下,X 和 Y 在 R(U) 中地位相同 若 Y 不函数依赖于 X, 则记作 X Y 2014-11-19 数据库系统概论 - 第 6 章 16/84
6.2.1 函数依赖 定义 6.2 ( 完全函数依赖和部分函数依赖的定义 ) 在 R(U) 中如果 X Y, 并且对 X 的任何一个真子集 X, 都有 X Y, 则称 Y 对 X 完全函数依赖, 记作 : F X Y 若 X Y, 但 Y 不完全函数依赖于 X, 则称 Y 对 X 部分函数依赖, 记作 : P X Y 2014-11-19 数据库系统概论 - 第 6 章 17/84
6.2.1 函数依赖 定义 6.3( 传递函数依赖 ) 在 R(U) 中, 如果 X Y,(Y X),Y X, Y Z, 则称 Z 对 X 传递函数依赖 记作 : 传递 X Z 2014-11-19 数据库系统概论 - 第 6 章 18/84
6.2.2 码 定义 6.4 设 K 为 R<U,F> 中的属性或属性组, 若 F K U, 则 K 为 R 的候选码 (Candidate Key) 若候选码多于一个, 则选定其中一个作为主码 (Primary Key) 主属性 (Prime attribute): 包含在任何候选码中的属性 非主属性 (Nonprime attribute) : 不包含在任何候选码中的属性 也称非码属性 (Nonkey attribute). 2014-11-19 数据库系统概论 - 第 6 章 19/84
6.2.2 码 定义 6.5 ( 外码的定义 ) 关系模式 R 中的属性或属性组 X 并非 R 的码, 但 X 是另一个关系模式的码, 则称 X 是 R 的外部码, 简称外码 2014-11-19 数据库系统概论 - 第 6 章 20/84
6.2.3 范式 满足最低要求的关系, 叫第一范式, 简称 1NF 关系表的每一分量是不可分的数据项 1NF 不允许表中出现嵌套或复合的属性 5NF 4NF BCNF 3NF 2NF 1NF 2014-11-19 数据库系统概论 - 第 6 章 21/84
6.2.4 2NF 定义 6.6 若 R 1NF, 对 R 的每一个非平凡的函数依赖 X Y, 要么 Y 是主属性, 要么 X 不是任何码的真子集, 则 R 2NF 2NF 在 1NF 基础上消除了非主属性对码的部分函数依赖 2014-11-19 数据库系统概论 - 第 6 章 22/84
6.2.4 2NF 例 : 前面的大表 SC 不是 2NF 的关系模式 例 4: 关系模式 S-L-C(Sno, Sdept, Sloc, Cno, Grade) 存在函数依赖 Sno Sdept Sdept Sloc (Sno,Cno) Grade 唯一候选码 (Sno, Cno) 则 Sno Sdept 是非主属性对码的部分函数依赖 2014-11-19 数据库系统概论 - 第 6 章 23/84
6.2.4 2NF 如果一个关系模式不是 2NF 的, 一定存在过度冗余, 带来 3 类异常 解决方法 : 分解为多个小表 如 S-L-C 分解为 {S-L(Sno, Sdept, Sloc), SC(Sno, Cno, Grade)} 2NF 仅仅具有历史意义 2014-11-19 数据库系统概论 - 第 6 章 24/84
6.2.5 3NF 定义 6.7 若 R 1NF, 对 R 中的每一个非平凡的函数依赖 X Y, 要么 Y 是主属性, 要么 X 中含有码, 则 R 3NF 2014-11-19 数据库系统概论 - 第 6 章 25/84
6.2.5 3NF 3NF 与 2NF 相比, 条件更强 因为 X 中含有码, 则 X 不会是任何码的真子集 ; 而 2NF 定义中,X 不是任何码的真子集, 还可能是非主属性组 即 3NF 在 2NF 的基础上消除了非主属性对码的传递函数依赖 2014-11-19 数据库系统概论 - 第 6 章 26/84
6.2.5 3NF 判断 3NF 例子 S-L(Sno, Sdept, Sloc) 唯一候选码 Sno 函数依赖 Sno Sdept, Sdept Sloc 非主属性 非主属性 没有非主属性对码的部分函数依赖, 满足 2NF 存在非主属性对非主属性的函数依赖, 不满足 3NF 2014-11-19 数据库系统概论 - 第 6 章 27/84
6.2.5 3NF 满足 2NF, 不满足 3NF, 仍有过度冗余及其带来的 3 类异常 S1 CS B01 S2 CS B01 S3 CS B01 S100 MA B02 2014-11-19 数据库系统概论 - 第 6 章 28/84
6.2.5 3NF 解决方法, 分解成小关系 S-D(Sno, Sdept) D-L(Sdept, Sloc) 2014-11-19 数据库系统概论 - 第 6 章 29/84
6.2.6 BCNF 由 Boyce 和 Codd 共同提出, 属于修正的 3NF 定义 6.8 若 R 1NF, 对 R 中的每一个非平凡的函数依赖 X Y,X 中均含有码, 则 R BCNF 2014-11-19 数据库系统概论 - 第 6 章 30/84
6.2.6 BCNF BCNF 与 3NF 相比, 条件更强 不允许主属性对码的部分和传递函数依赖 到 BCNF 为止, 完全消除了由于函数依赖带来的过度冗余及相应的三类异常 2014-11-19 数据库系统概论 - 第 6 章 31/84
6.2.6 BCNF 例 7 (BCNF 的例子 ) 关系模式 SPJ( 学生, 课程, 名次 ) 每个学生选每门课程有一定名次 每门课程中每一名次只有一个学生 2014-11-19 数据库系统概论 - 第 6 章 32/84
6.2.6 BCNF 例 7 (BCNF 的例子 ) 关系模式 SPJ( 学生, 课程, 名次 ) 每个学生选每门课程有一定名次 每门课程中每一名次只有一个学生 ( 学生, 课程 )-> 名次 ( 课程, 名次 )-> 学生 2014-11-19 数据库系统概论 - 第 6 章 33/84
6.2.6 BCNF 例 7 (BCNF 的例子 ) 关系模式 SPJ( 学生, 课程, 名次 ) 每个学生选每门课程有一定名次 每门课程中每一名次只有一个学生 ( 学生, 课程 )-> 名次 ( 课程, 名次 )-> 学生 候选码 2014-11-19 数据库系统概论 - 第 6 章 34/84
6.2.6 BCNF 例 8 ( 是 3NF, 但不是 BCNF 的例子 ) 关系模式 STJ( 学生, 教师, 课程 ) 每一教师只教一门课 一个学生选定某门课程, 就对应一个固定的教师 2014-11-19 数据库系统概论 - 第 6 章 35/84
6.2.6 BCNF 例 8 ( 是 3NF, 但不是 BCNF 的例子 ) 关系模式 STJ( 学生, 教师, 名次 ) 每一教师只教一门课 一个学生选定某门课程, 就对应一个固定的教师 教师 -> 课程 ( 学生, 课程 )-> 教师 2014-11-19 数据库系统概论 - 第 6 章 36/84
6.2.6 BCNF 例 8 ( 是 3NF, 但不是 BCNF 的例子 ) 关系模式 STJ( 学生, 教师, 课程 ) 每一教师只教一门课 一个学生选定某门课程, 就对应一个固定的教师 教师 -> 课程 ( 学生, 课程 )-> 教师 教师, 学生 候选码 2014-11-19 数据库系统概论 - 第 6 章 37/84
6.2.6 BCNF 例 8 存在的过度冗余 教师学生课程 每个教师上一门课 随选课学生的增加而被重复存储 王红李明数据库 王红刘晨数据库 王红 王敏 数据库 刘军 张立 C 语言 刘军 刘晨 C 语言 2014-11-19 数据库系统概论 - 第 6 章 38/84
6.2.6 BCNF 解决方法 还是分解 分解为两个小关系模式 ( 都是 BCNF 的 ) ST( 学生, 教师 ) TJ( 教师, 课程 ) 或 SJ( 学生, 课程 ) TJ( 教师, 课程 ) 2014-11-19 数据库系统概论 - 第 6 章 39/84
6.2.6 BCNF 解决方法 还是分解 分解为两个小关系模式 ( 都是 BCNF 的 ) ST( 学生, 教师 ) TJ( 教师, 课程 ) 或 SJ( 学生, 课程 ) TJ( 教师, 课程 ) 两种分解都损失了 : 一个学生选定某门课程, 就对应一个固定的教师 语义 2014-11-19 数据库系统概论 - 第 6 章 40/84
6.2.6 BCNF 解决方法 还是分解 分解为两个小关系模式 ( 都是 BCNF 的 ) ST( 学生, 教师 ) TJ( 教师, 课程 ) 或 SJ( 学生, 课程 ) TJ( 教师, 课程 ) 两种分解都损失了 : 一个学生选定某门课程, 就对应一个固定的教师 语义 函数依赖 ( 学生, 课程 )-> 教师 在分解后没有保持! 2014-11-19 数据库系统概论 - 第 6 章 41/84
6.2.6 BCNF 事实上, 关系模式即使到了 BCNF, 还可能存在由于非函数依赖带来的冗余及三类异常 这些数据依赖有多值依赖和连接依赖 我们只简单要求多值依赖 在多个实体间联系为 1 对多联系时可能出现多值依赖带来的问题 2014-11-19 数据库系统概论 - 第 6 章 42/84
6.2.7 多值依赖 多值依赖定义 : 设有关系模式 R(U),X, Y, Z 是 U 的非空子集 对于 R 的任一关系 r, 给定一对 (x, z) 值, 就有一组 Y 的值与之对应, 这组值仅仅决定于 x 值而与 z 值无关, 则称 Y 多值依赖于 X 或 X 多值决定 Y 记作 X Y 或记忆为 : 设有关系模式 R(U),X, Y, Z 是 U 的非空子集 对 R(U) 的任一关系 r, 任意两元组 s 和 t, 如果 s[x]=t[x], 则交换 s 和 t 的 Y 值所得两个新元组必在 r 中 2014-11-19 数据库系统概论 - 第 6 章 43/84
6.2.7 多值依赖 翻译情况 A B C ( 姓名, 东方语言, 西方语言 ) 王红 日语 法语 王红 汉语 英语 王红 日语 英语 王红 汉语 法语 是 BCNF, 其中只有 ABC 才是关键字 但有冗余, 又有删除异常 例如删除 ( 王红 汉语 法语 ) 2014-11-19 数据库系统概论 - 第 6 章 44/84
6.2.7 多值依赖 衣着 ( 姓名, 衣服, 裤子 ) 类似, 可称为完全搭配依赖 ( 课程, 教师, 参考书 ) 类似, 看书上 2014-11-19 数据库系统概论 - 第 6 章 45/84
6.2.7 多值依赖 不是多值依赖的例子 : 学生选课表 SC(Sno,Cno,G) 中 一个 Sno( 一个学生 ) 有一组 Cno( 选了一组课程 ) 和一组 G( 有一组成绩 ), 但 Cno 与 G 有关 ( 成绩与课程有关 ), 所以没有 Sno Cno, 以及 Sno G 也就是说一个学生选的一组课程和一组成绩没有形成完全搭配 2014-11-19 数据库系统概论 - 第 6 章 46/84
6.2.7 多值依赖 平凡的多值依赖 : 若 X Y, 而 Z= ; 则称 X Y 是平凡的多值依赖 多值依赖的性质 : 1 对称 ( 互补 ) 性 : 若 X Y; 则 X Z, 其中 Z=U-X-Y 2 传递性 : 若 X Y,Y Z; 则 X Z-Y 3 函数依赖是多值依赖的特殊情况 : 若 X Y, 则 X Y 4 若 X Y,X Z; 则 X YZ,X Z-Y, X Y-Z, X Y Z 2014-11-19 数据库系统概论 - 第 6 章 47/84
6.2.8 4NF 定义 6.10 若关系模式 R(U,F) 1NF, 如果对于 R 的每个非平凡多值依赖 X Y(Y 不包含于 X),X 都含有码, 则称 R(U,F) 4NF 实质上 4NF 消除了多值依赖 为什么? 2014-11-19 数据库系统概论 - 第 6 章 48/84
6.2.9 规范化小结 1NF: 每个分量是不可分的数据项 2NF: 非主属性完全函数依赖于码 3NF: 非主属性既不部分依赖于码也不传递依赖于码 BCNF: 所有属性都不部分依赖于码也不传递依赖于码 所有决定因素 ( 属性集 ) 都包含码 4NF: 所有非平凡的多值依赖都是函数依赖 2014-11-19 数据库系统概论 - 第 6 章 49/84
本章目录 6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 6.4 模式的分解 2014-11-19 数据库系统概论 - 第 6 章 50/84
函数依赖公理系统的背景 为了求得给定关系模式的码, 为了从一组函数依赖求得蕴含的函数依赖, 例如已知函数依赖集 F, 要问 X Y 是否为 F 所蕴含, 就需要一套推理规则, 这组推理规则是 1974 年首先由 Armstrong 提出来的 它是关系模式分解算法的理论基础 要求得给定关系模式的所有候选码对于关系模式的范式级别判定具有决定作用 : 范式级别的判定需要知道关系模式的所有候选码 ; 有的范式级别还需确定主属性和非主属性, 也需要知道所有候选码 2014-11-19 数据库系统概论 - 第 6 章 51/84
数据依赖的公理系统 逻辑蕴含 : 定义 6.11 对于关系模式 R<U,F>, 其任何一个关系 r, 若函数依赖 X Y 都成立 ( 即 r 中任意两元组 s,t, 若 t[x]=s[x], 则 t[y]=s[y]), 则称函数依赖集 F 逻辑蕴含 X Y 2014-11-19 数据库系统概论 - 第 6 章 52/84
Armstrong 公理系统 A1 自反律若 Y X U, 则 X Y 为 F 所蕴含 ( 给出平凡的函数依赖 ) A2 增广律若 X Y 为 F 所蕴含, 且 Z U, 则 XZ YZ 为 F 所蕴含 A3 传递律如 X Y 及 Y Z 为 F 所蕴含, 则 X Z 为 F 所蕴含 证明见定理 6.1 2014-11-19 数据库系统概论 - 第 6 章 53/84
Armstrong 公理系统 Armstrong 公理的推论 : 合并规则 : 若 X Y,X Z, 有 X YZ 分解规则 : 由 X Y 及 Z 包含于 Y, 有 X Z 伪传递规则 : 若 X Y,WY Z, 有 XW Z 根据合并规则和分解规则, 得到一个重要事实 : X A 1 A 2 A K 成立的充分必要条件是 X A i (i=1, 2,, k) 成立 2014-11-19 数据库系统概论 - 第 6 章 54/84
Armstrong 公理系统 定义 6.12 F 的闭包 : 函数集闭包 ( 找亲戚的亲戚 ) 在关系模式 R<U,F> 中为 F 所逻辑蕴含的函数依赖的全体叫做 F 的闭包, 记作 F + Armstrong 公理是有效的, 完备的 : 有效性 : 由 F 出发根据 Armstrong 公理推导出来的每个函数依赖一定在 F + 中 有效性的证明书上定理 6.1 Armstrong 推理规则是正确的 可直接得证 完备性 : F + 中的每一个函数依赖, 必定可以由 F 出发根据 Armstrong 公理推导出来 经典证明 2014-11-19 数据库系统概论 - 第 6 章 55/84
Armstrong 公理系统 定义 6.13 ( 属性集闭包 ) X F + 的定义设 F 是属性集 U 上的一组函数依赖集,X U,X F + = {A X A 能由 F 根据 Armstrong 公理导出 } 引理 6.2 设 F 为属性集 U 上的一组函数依赖, X,Y U,X Y 能由 F 根据 Armstrong 公理导出的充分必要条件是 Y X F + 2014-11-19 数据库系统概论 - 第 6 章 56/84
算法 6.1 求 X F + 的方法 -- 非常重要 计算 X F+, 滚雪球算法 result := X; // 从 X 开始 while (changes to result ) do for each V W in F do begin if V result then result := result W end return result 2014-11-19 数据库系统概论 - 第 6 章 57/84
例 例 1 关系模式 R<U,F>,U={A,B,C,D,E}, F={ AB C, B D, C E, EC B, AC B}, 求 (AC) F + 0. 初始化令 result=ac 1. 第一次循环计算 result =ACEB=ABCE 2. 第二次循环计算 result = ABCDE 即得结果 定义 6.13, 引理 6.2 和算法 6.1 非常重要, 可用于求码 如 K F + = U, 而 K F +!= U, 即求得 K 为一候选码 2014-11-19 数据库系统概论 - 第 6 章 58/84
求码方法要点 ( 自己的总结 ) 1. 找出不出现在非平凡函数依赖右部的属性组 X, 它们一定包含于所有候选码 2. 求 X F+, 判断 =U? 成立结束, 否则转 3 3. ( 自底向上 ) 扩展 X 的 X, 求 X F+, 判断 = U? 直到所有情况找完为止 2014-11-19 数据库系统概论 - 第 6 章 59/84
例 应用举例, 对书上 P184 例 1, 求所有候选码 要点 : 不出现在任何函数依赖右部的只有 A; 求 A F+ =A; 扩展 AB,AB F+ =U; AC,AC F+ =U; AD,AD F+!=U;( 需再扩展 ) AE, AE F+!=U;( 需再扩展 ) 再扩展 ADE,ADE F+!=U 2014-11-19 数据库系统概论 - 第 6 章 60/84
6.3 数据依赖的公理系统 要证明完备性首先解决如何判定一个函数依赖是否属于由 F 根据 Armstrong 公理推导出来的函数依赖的集合 如果能求出这个集合就很容易判断, 但是求这样的集合是一个 NP 完全问题 所以该判定转换为 : 任一个函数依赖 X Y 是 F + 中成员的充分必要条件是 : Y X F + 证明完备性转换为证明它的逆否命题为真 即若函数依赖不能由 F 从 Armstrong 公理导出, 那么它必然不为 F 所蕴含 证明分 3 步 ( 略 ) 证明用到了构造 ( 特殊的二维表 ) 反证, 十分巧妙 2014-11-19 数据库系统概论 - 第 6 章 61/84
6.3 数据依赖的公理系统 完备性证明 要证原命题, 只需证明其逆否命题 : 若函数依赖 X Y 不能由 F 出发从 Armstrong 公理导出, 则它本身不为 F 所蕴含 (1) 若 V W 成立, 且 V X F +, 则 W X F + V X + F, 则由引理 6.2, 有 X V 由 X V,V W, 有 X W 再由引理 6.2, 有 W X + F 2014-11-19 数据库系统概论 - 第 6 章 62/84
6.3 数据依赖的公理系统 (2) 构造如下二维表 r,r 必是 R<U, F> 的一个关系 用反证法 X F + U- X F + ------------- 11. 1 00 0 11. 1 11 1 若 r 不是 R<U, F> 的关系, 必是由 F 中的函数依赖 V W 在 r 上不成立所致 观察 r,v X F +, 而 W X F + 与 (1) 矛盾 2014-11-19 数据库系统概论 - 第 6 章 63/84
6.3 数据依赖的公理系统 (3) 若 X Y 不能由 Armstrong 公理导出 则 Y 不是 X F + 的子集, 必有 Y Y, 且 Y U-X F + ( 推 ) X Y 本身不为 F 所蕴含 ( 观察 r) 得证 2014-11-19 数据库系统概论 - 第 6 章 64/84
6.3 数据依赖的公理系统 定义 6.14 函数依赖集等价 : 如果 G + =F +, 就说函数依赖集 F 覆盖 G(F 是 G 的覆盖或 G 是 F 的覆盖 ), 或 F 与 G 等价 有相应的判定算法 引理 6.3 的充分性证明的过程实际上给出了判断两函数依赖集等价的方法 引理 6.3 F + =G + 的充分必要条件是 F G +, 和 G F + 2014-11-19 数据库系统概论 - 第 6 章 65/84
6.3 数据依赖的公理系统 定义 6.15 最小依赖集 右部唯一 无多余函数依赖 无部分函数依赖定理 6.3 每一个函数依赖集都等价于一个极小函数依赖集 Fm (Fm 一定存在, 可能不唯一 ) 定理 6.3 的证明过程给出了检验 ( 或构造 )Fm 的方法 2014-11-19 数据库系统概论 - 第 6 章 66/84
求解极小函数依赖集的过程 1. 用分解规则将 F 中每一函数依赖分解为若干个右部唯一的函数依赖, 新函数依赖集仍命名为 F 2. 判断当前 F 中有没有多余的函数依赖 注意, 检查 X A, 要在 G 集 ( 其中 G=F-{X A}) 下考察 X A 是否被蕴含 (G 集下计算 X G+, 看 A 是否包含在其中 ) 处理后的函数依赖集不妨仍命名为 F 3. 判断当前 F 中每一函数依赖左部有没有多余的属性 注意, 检查 AB Y 中 B 是否多余时, 令 G=F- {AB Y} {A Y}, 需要考察 A Y 是否为 F 所蕴含 (F 集下计算 X F+, 看 Y 是否包含在其中 ) 最后得到 F 的函数依赖集 Fm 2014-11-19 数据库系统概论 - 第 6 章 67/84
6.3 数据依赖的公理系统例子 : 设 F={AB C,A B}, 求 Fm Fm={B C,A B}? 对不对? 为什么? 2014-11-19 数据库系统概论 - 第 6 章 68/84
6.3 数据依赖的公理系统 上面的 F 与 Fm 根本不等价 Fm={A C,A B} 2014-11-19 数据库系统概论 - 第 6 章 69/84
本章目录 6.1 问题的提出 6.2 规范化 6.3 数据依赖的公理系统 6.4 模式的分解 2014-11-19 数据库系统概论 - 第 6 章 70/84
6.4 模式的分解 要求了解 前面我们为了解决设计得不好 ( 范式级别不够高 ) 的数据库模式带来的问题, 我们采用了大关系分解为小关系的方法来提高范式级别 本节给出分解的理论指导 2014-11-19 数据库系统概论 - 第 6 章 71/84
6.4.1 模式分解的三个定义 1. 具有无损连接性 分解后的 ( 几个 ) 小模式可自然连接恢复为原来的模式 2. 保持函数依赖分解前后函数依赖集等价 3. 既保持无损连接, 又保持函数依赖 ( 理想情况 ) 2014-11-19 数据库系统概论 - 第 6 章 72/84
6.4.2 分解的无损连接性和保持函数依赖性 m ρ (r)=π R1 (r) π R2 (r) π Rk (r) 定义 5.18 ρ={r 1 <U 1,F 1 >,R 2 <U 2,F 2 > R k <U K,F K >} 是 R<U,F> 上的一个分解, 若对于 R<U,F> 的任一关系 r, 均有 r= m ρ (r) 成立, 则 ρ 具有无损连接性 此定义无法用于判断, 无损连接性只能通过算法 6.2 或定理 6.5 来判断 2014-11-19 数据库系统概论 - 第 6 章 73/84
6.4.2 分解的无损连接性和保持函数依赖性 算法 6.2 要求会做 ( 通过例子来学习 ) 例 1 R(S,A,I,P) 分解为 R1(S,A),R2(S,I,P) F = {S A, SI P} S A I P -------------------- a1 a2 b13 b14 a1 b22 a3 a4 由于有 S A, 使第二行第二列变成 a2 S A I P -------------------- a1 a2 b13 b14 a1 a2 a3 a4 2014-11-19 数据库系统概论 - 第 6 章 74/84
6.4.2 分解的无损连接性和保持函数依赖性 补充例 R(A,B,C,D,E), 分解 R1=AD, R2=AB, R3=BE, R4=CDE, R5=AE F={A C, B C, C D, DE C, CE A} A B C D E -------------------------------------------- a1 b12 b13 a4 b15 a1 a2 b23 b24 b25 b31 a2 b33 b34 a5 b41 b42 a3 a4 a5 a1 b52 b53 b54 a5 A C (b23 变 b13,b53 变 b13), B C (b33 变 b13), C D (b24,b34,b54 变 a4), DE C(C 列变 a3) CE A(A 列变 a1) 第三行出现了 a1 到 a5. 2014-11-19 数据库系统概论 - 第 6 章 75/84
6.4.2 分解的无损连接性和保持函数依赖性 定理 6.5 R<U,F> 的一个分解 ρ= {R 1 <U 1,F 1 >,R 2 <U 2,F 2 >} 具有无损连接性的充分必要条件是 U 1 U 2 U 1 -U 2 F + 或 U 1 U 2 U 2 -U 1 F + 可用于简单情况 ( 分解为两个小关系模式 ) 的快速判断 例如 :R=ABC, F={A B,B C} R1=AB, F1={A B}, R2=AC, F2={A C} U 1 U 2 U 1 -U 2 即 A B 为 F 所蕴含 2014-11-19 数据库系统概论 - 第 6 章 76/84
分解的无损连接性和保持函数依赖性 定义 6.19 ( 保持函数依赖的定义 ) 若 F + = (F 1 F 2 F k ) +, 则 R<U,F> 的分解 ρ= {R 1 <U 1,F 1 >,R 2 <U 2,F 2 > R k <U K,F K> } 保持函数依赖 注 : 实际上只需判断分解后是否有函数依赖的损失, 只需判断 F (F 1 F 2 F k ) + 2014-11-19 数据库系统概论 - 第 6 章 77/84
6.4.3 模式分解算法 要记住的三个事实 1. 要求分解保持函数依赖, 模式分解总可以达到 3NF, 不一定能达到 BCNF 2. 要求分解既保持函数依赖有具有无损连接性, 可以达到 3NF, 不一定能达到 BCNF 3. 要求分解具有无损连接性, 可以达到 4NF 分解算法, 要求掌握算法 6.3( 合成法 ) 和 6.4 2014-11-19 数据库系统概论 - 第 6 章 78/84
6.4.3 模式分解算法 算法 6.3 合成法要点 1. 函数依赖集极小化处理 2. 处理不出现在 F 中的属性 3. 对 F 按相同左部原则分组, 每组的全部属性为一个分解后的关系模式 算法 6.4 在合成法基础上进行调整 1. 增加 R*(X,Fx) ( 构成码的属性 ) 2. 如果分解后的模式有属性包含的情况, 只保留大的 2014-11-19 数据库系统概论 - 第 6 章 79/84
作业 一. 设 R<U,F>,U={B, O, I, S, Q, D}, F= {S D, I B, IS Q, B O}. 1. 求 R 的所有候选码 2. 判断 R 满足的最高范式级别 ( 到 BCNF 为止 ) 3. 若 R 满足的最高范式级别不到 3NF, 试将其分解为一组既具有无损连接性, 又保持函数依赖的 3NF 关系模式 二. P195, 2 2014-11-19 数据库系统概论 - 第 6 章 80/84
作业 三. 分析设有以下关系 R: 工厂名 产品号 产品名 车间名 车间地点 单价 W1 P1 M1 J1 D1 100 W2 P1 M1 J1 D2 110 W2 P2 M2 J1 D2 80 W2 P3 M3 J2 D3 75 W3 P1 M1 J1 D4 90 2014-11-19 数据库系统概论 - 第 6 章 81/84
作业 试分析上述数据, 并充分利用常识, 完成以下要求 : 分析 R 的函数依赖, 求 R 的候选码 求 R 的最高范式级别 ( 到 BCNF 为止 ), 说明理由 分析 R 存在的主要问题 将 R 分解为一组合适的 3NF 关系模式 2014-11-19 数据库系统概论 - 第 6 章 82/84
作业 作业通过发送电子邮件附件形式提交到助教老师邮箱 : 653703162@qq.com 作业文件名命名要求 : DB_ 学号 _ 姓名 _n.doc (n 为当章节序号 ) 如一个合法文件名 : DB_95002_ 张三 _3.doc 11 月 30 日前 Email 提交 2014-11-19 数据库系统概论 - 第 6 章 83/84
Any Question? Thank you! 2014-11-19 数据库系统概论 - 第 6 章 84/84