数据库原理及应用 第4章 关系数据库规范化理论

4章 关系数据库规范化理论 关系数据理论是关系数据库的理论基础，也是设计关系数据库的指南。本章计论关系数据理论的基本概念、方法和题解。 如何设计数据库模式 1) 设计一个好的关系数据库模式（概念模式） 逻辑设计 2) 凭经验设计？ 3) 什么是好的关系数据库模式？ 4) 好的关系数据库模式应该包括多少关系模式？ 5) 每个关系模式应该包含哪些属性？ 6) 借助数学工具规定设计的理论和方法 规范化 假设有如下关系 示 学号 ,姓名 ,性别 ,课程 ,成绩 其中 这个关系模式存在如下问题 : 数据冗余 一个学生选修多门课程 ,导致 不一致性 由于数据存储冗余 ,当更新某些数据项时 ,就有可能一部分修改了 ,而另一部分未修改 ,造成数据不一致性 插入异常 如果某个学生未选课 ,他的信息 (无法插入 删除异常 当要删除所有学生成绩时 ,将所有(都删除了 ,这便是删除异常 为了克服上述这些异常 ,将 O,O,这是因为 数据依赖是现实世界事物之间的相互关联性的一种表达 ,是属性固有语义的体现 才能归纳与客观事实相符合的数据依赖 数依赖 数依赖 (定义 函数依赖 定义 4设 R(U)是一个关系模式 ,X,的两个属性集合 ,X,YR,RX,Y是关系 当任何时刻 RX,Y中的任意两个元组中的 则它的 则称 ,或称为 ,记作 XY 例子 (1) S(N,(2) (3) 函数 (赖于 (4) 函数依赖的推导公理 姆斯特朗公理） 设有关系模式 R（ U）， X， Y， Z， WU，则： 反性）：若 YX，则 XY 广性）：若 XY ，则 递性）：若 XY ， YZ ，则 XZ 由 合成规则：若 XY ， XZ ，则 X 分解规则：若 X则 XY ， XZ ； 伪传递规则：若 XY ， Z ，则 Z 数依赖的分类 1) 平凡函数依赖与非平凡函数依赖 定义 2 在关系 R(U)中 ,对于 和 Y,如果 XY , 但 则 XY 是非平凡函数依赖 是 则称XY 为平凡函数依赖 2)完全函数依赖与部分函数依赖 设 XY 是一个 且对于任何一个 XX,X Y 不成立 ,则称 XY 是一个完全函数依赖 ,记作 X Y 设 XY 是一个 且存在一个 XX,使 X Y 成立 ,则称XY 是一个部分函数依赖 ,记作 X Y 示例 1) ) (G 是完全函数依赖 (2) (G 所以存在部分函数依赖 3)传递函数依赖 设 X,Y,互不相同的属性集合 X Y， Y X,且 Y Z 则称属性集合 数依赖于 X ,记作 X Z (1) N,G,M) (学号 ,课程名 ,成绩 ,系名 ,系主任 ) (2) (3) (4) 引理： XA 1 A A I=1,2,3 如果 之间是 1系，则存在 XY ， YX 如果 之间是“多对 1”关系，则存在 XY 如果 之间是“多对多”，则 不存在函数依赖 结 1) 函数依赖是完整性约束的一种特殊形式 2) 函数依赖分为 (1) 完全函数依赖 (2) 部分函数依赖 (3) 传递函数依赖 3) 函数依赖是规范化理论的依据 4) 函数依赖是规范化程度的准则 函数依赖的闭包 F+ 属性闭包及其计算 函数依赖的闭包 F+ 定义 4关系模式 R(U,F)中为 的闭包 ,记为 :F+ 例 :关系模式 S(U,F),其中 U=F= 义 4关系模式 R(U),则称所有用 推出的函数依赖XA 的属性闭包 ,记作X+ 例 : 有关系模式 S(N,有 有N,理 设关系模式 R(U),X,YU,则从 Y 的充分必要条件是 Y X+ 法 4属性集 的属性闭包 X+ 算法 求属性的闭包 X+ 输入 X,F 输出 X+ 步骤 (1)令 X(0)=X,I=0 (2)求 B,B=A|(E)(W)(V W F V X(I) A W (在 (I)的子集的函数依赖 ) (3)X(I+1)=B X(I) (4)判断 X(I+1)=X(I)吗 ? (5)若相等 ,或 X(I)=U,则 X(I)为属性集 且算法终止 (6)若不相等 ,则 I=I+1,返回第 2步 . 性闭包计算示例 例 1 已知关系模式 R(U,F),U=A,B,C,D,E; F=AB, DC,E,B 求 ( ,( 解 求 ( 设 X(0)=计算 X(1) : 逐一扫描 找出左部为 A,得到一个 : AB. 故有 X(1)=B=计算 X(2): 逐一扫描 找到左部为 A,B,B,E,示发现有新的函数依赖 X(2)=X(1) =有 X(1)=X(2),算法终止 , ( = (注 :因为找不到新的函数依赖 ,即 (1)的子集 ,所以 ,不必再计算下去 ,算法终止 ) 练习 求 ( 解 求 ( X(0)=求 X(1):逐一扫描 找出左部为 A,得到 : AB,D C, 故有 X(1)=求 X(2):逐一扫描 找出左部为 得到 : ,B, 故有X(2)=因为 X(2)=U,故算法终止 , (= 2 设有关系模式 R(U,F),其中 U=A,B,C,D,E,I; F=AD,E, ,I,E C 计算 ( 解 : 设 X(0)=求 X(1) 在 有 AD,E C 所以 X(1)=求 X(2) 在 新的依赖有 所以 X(2)=求 X(3) 因为在 (2)的子集 ,所以不必再计算 ,即 X(3)=X(2),算法终止 (=习 设有函数依赖集 F=DG,C A,E,A B 计算闭包 D+ ,C+, A+ ,( ,(, (, ( 最小函数依赖集及其算法 1. 等价与覆盖 定义 : 一个关系模式 R(U)上的两个依赖集 ,如果 F+=G+,则称 是等价的 ,记作 F G. 如果函数依赖集 F是 反之亦然 两个等价的依赖集在表示能力上是完全相同的 . 最小函数依赖集及其算法 定义 :对于给定的函数依赖 F,当满足下列条件时 ,称为 记作 F: 1) F的每个依赖的右部都是单个属性 2) 对于 F中的任何一个函数依赖 XA, F -XA 与 F都不等价 3) 对于 F中的任何一个 XA 和 ,(F-XA) ZA 与 F都不等价 说明 :条件 (2)保证了在 条件 (3)保证了 最小函数依赖集及其算法 算法 4 输入 :一个函数依赖集 F 输出 : 方法 : (1)应用分解规则 ,使 (2)去掉各依赖左部多余的属性 一个一个地检查 例如 , 现在要判断 则以 XA 代替 是否等价 ?只要在 若 X+包含 A,则 否则 依次判断其他属性即可消除各依赖左边的多余属性 . (3)去掉多余的依赖 从第一个依赖开始 ,从 假设该依赖为 XY), 然后在剩下的依赖中求 X+,看X+是否包含 Y,若是 ,则去掉 XY; 若不包含 Y,则不能去掉XY. (4)这样依次做下去 . 例 设有依赖集 : F=,C A,D,B,D E C,E 计算其等价的最小依赖集 . 解 : (1)将依赖右边属性单一化 ,结果为 C C C A B D D B A D E G D G (2)在 因为有 C A, 则对 A,E 是多余的 ,对于 B, 若去掉 A,由于 (= 删除依赖左部多余的依赖后 : C C C A B D D B C A D E G D G (3)在 对于 B, 去掉他 ,仍有(=是多余的 ,删除多余的依赖后 : C D G C A C D D B G D E C C C A B D D B C A D E G D G 注意： 与对各函数依赖 A 中 候选关键字的求解理论与算法 候选关键字 : 属性或属性的最小组合 ,其值能够惟一地标识一个元组 . 对于给定的关系 R(2,和函数依赖集 F,可将其属性分为四类 : 仅出现在 仅出现在 在 在 例 :有关系模式 R(A,B,C,D,E,F,P) R 的函数依赖集为 F=AD,E D,D B,D,A,D F 则 C E F P 1. 快速求解候选关键字的充分条件 定理 对于给定的关系模式 ,若 X(X R)是 则 的任一候选关键字的成员 ,若 Y(Y R)是 则 若 Z (Z R)是 则的任一候选关键字中 . 推论 1 对于给定的关系模式 ，如果 类属性，且 的全部属性；则 的惟一候选关键字 推论 2 对于给定的关系模式及其函数依赖集 F，如果 的 类组成的属性集，且 X+包含了 的惟一候选关键字 例 1 设有关系模式 R（ A,B,C,D),其函数依赖集 F=DB,BD, ,D, 求 解 :在 L 类属性有 A,则 又 (=以 例 2 设有关系模式 R(A,B,C,D,E,P)及其函数依赖集 F=A D,E D,D B,D,A, 求 解 :考察 L 类属性有 C,E ,则 又 (=以 的惟一候选关键字 定义 :在一个函数依赖图中有下列术语 (1)引出线 /引入线 :若 A B, 则 是连接的 ,则 (A,B)是引出线 ,对 (2)原始点 :只有引出线而无引入线的结点 ,它表示 (3)终结点 :只有引入线而无引出线的结点 ,它表示 (4)途中点 :即有引入线又有引出线的结点 ,对应 (5)孤立点 :既无引入线又无引出线的结点 ,对应 (6)关键点 :原始点和孤立点统称为关键点 (7)关键属性 :关键点对应的属性称为关键属性 (8)独立回路 :不能被其他结点到达回路 数依赖图示例 A B C D E F 原始点 途中点 终结点 孤立点 独立回路 算法 单属性依赖集图论求解法 输入 :关系模式 R, 输出 : 方法 (1)求 (2)构造函数依赖图 (3)从图中找出关键属性集 X( (4)查看图中有无独立回路 ,若无则输出 的惟一候选关键字 ,转 (6);若有 ,则转 (5) (5)从各独立回路中各取一结点对应的属性与 并重复这一过程取尽所有可能的组合 ,即为 (6)结束 . 例 3 设 R=O,B,I,S,Q,DF=SD,D S,I B,B I,B O,O B 求 解 : (1)F=F= SD,D S,I B,B I,B O,O B (2)构造函数依赖图如图所示 S D O I B Q (3)关键属性 Q (4)共有两个独立回路 ,以共有 2*3=6个候选关键字 (5) 3. 多属性依赖集候选关键字求解法 算法 多属性依赖集候选关键字求解法 输入 :关系模式 输出 : 方法 : (1)将 ,R,并令 ,(2)求 X+,若 X+包含了 则 的惟一候选关键字 ,转 (4),否则转 (3) (3)在 ,求 (,若它包含了 则为一个候选关键字 ,否则依次取两个 ,三个 .的全部属性 (4)结束 ,输出结果 例 4 有一关系模式 R(求其全部候选关键字 解 :由生活常识可知 F=( (1) X= Y=(2)X+= (3)从 =从 =(4)所有 ( 述 关系数据库中的关系必须满足一定的规范化要求，对于不同的规范化程度可用范式（ 衡量。范式是符合某一种级别的关系模式的集合，是衡量关系模式规范化程度的标准，达到的关系才是规范化的。函数依赖的范围主要有 4种范式：第一范式、第二范式、第三范式、足最低要求的叫第一范式，简称为 1第一范式基础上进一步满足一些要求的为第二范式，简称为 2余以此类推。显然各种范式之间存在联系。 1 通常把某一关系模式 关系模式的级别 1) 全键 (1) 整个属性组合是关系键 2) 主属性 (键属性 ) (1) 包含在任何一个候选键中的属性 3) 非主属性 (非键属性 ) (1) 不包含在任何候选键中的属性 例子 1) S(N,(1) 2) 2) ) (1) (2) 3) 奏者 P,作品 W,听众 A) (1) 之间为多对多关系，无函数依赖 (2) 全属性集 (P,W,A)是键、主键、全键 (3) P,W,范式 1. 范式 ( 1) 定义 (1) 符合某种级别的关系模式的集合 (2) 如果一个关系满足某个特定的约束值，则称它属于某种特定的范式 2) 各级范式的要求 (1) 第一范式：关系满足只包含原子值的约束 (2) 第二范式：每个非主属性都完全函数依赖于 (3) 第三范式：每个非主属性都不传递依赖于 (4) (5) 第四范式：对于 Y ， (6) 第五范式：投影 连接范式 3) 各级范式的关系 (1) 5(2) 如果关系满足某个范式要求，也会满足级别较低的所有范式的要求 (3) 较高层次的范式比较低层次的范式具有更合乎要求 4) 模式分解（也叫规范化） 将一个低一级范式的关系模式通过投影运算转化为若干个高一级范式的关系模式的集合的过程 一范式 (1 1) 定义 (1) 若关系模式 (2) 则 R1 2) 说明 (1) 1 (2) 若 R1 3) 例子 (1) n,m,G) (2) (n)为关系键、候选键、主键 (3) 函数依赖关系 1. (N) G 2. n 3. m 4. m (4) 存在的问题 1. 插入异常 2. 删除异常 3. 冗余太大 4. 修改异常 二范式 (2 1) 定义 (1) 在关系模式 R1(2) 且每个非主属性都完全依赖于 (3) 则 R2 2) 例子 (1) S(N,1(2) (3) (4) (5) (6) (7) S2 3) 注意 (1) 如果关系 的主属性，或者 么 R2 (2) 从 1可获得2 4) 三个问题的解决 1. 插入异常有所改善 2. 删除异常仍然存在 3. 冗余得到改善 示例 :现有关系模式其属于第几 学号 ,课程号 ,课程名 ,教师名 ,教师住址 ,成绩 范式 ,为什么 ? 三范式 (3 11) 定义 若关系模式 R(U,F)中若不存在这样的码 X,属性组 (ZY),使得 X Y,Y Z 且 ,则 R3即 (1) 若 R2(2) 且每个非主属性都不传递依赖于 (3) 则 R3 2) 说明 (1) 每个非主属性既不部分依赖，也不传递依赖于 (2) 从 1消除非主属性对键的部分函数依赖 (3) 从 2消除非主属性对键的传递函数依赖 3) 3设有关系 R(课程名 ,教师名 ,教师地址 )(注 :每门课程只由一名教师讲解 ) 问 :它为第几范式 ,为什么 ? 称 1) 3(1) 3(2) 把能够分离的属性尽可能地分解为单独的关系 (3) 但 3 2) (1) 若 R1(2) 如果对于 Y ， (3) 决定因素 )决定属性集 (4) 则 R 3) 说明 (1) 在满足 候选键之外没有其他的决定因素 (决定属性集 ) (2) 满足 主属性或非主属性 )对键的部分依赖或传递依赖 (3)属于 属于 3例 有一关系模式 R(问其最高属于第几范式 解 :1）求候选关键字 F=( (1) X= Y=(2)X+= (3)从 =从 =(4)所有 (2）因有 而 在主属性对码的部分函数依赖，所以 R 3 关系模式的分解 无损连接性 无损连接性指的是对关系模式分解时 ,原关系模式下的任一合法的关系实例在分解之后应能通过自然连接运算恢复起来 . 函数依赖保持性 函数依赖的保持性是指关系模式 注 :一个无损连接分解不一定具有依赖保持性 ;同样 ,一个依赖保持性分解不一定具有无损连接性 、 分解到 2采用投影分解运算 ,将部分依赖分解出去 示例 学号 ,课程号 ,课程名 ,教师名 ,教师住址 ,成绩 要求将其分解成