Armstrong 公理 — 阿氏公理
1974年 1974年W.W.Armstrong提出的函数依赖的推理规则。 Armstrong提出的函数依赖的推理规则。 提出的函数依赖的推理规则 这些规则通常被称为阿氏公理 设关系模式R(U,F)，其中U 的属性全集， 设关系模式R(U,F)，其中U为R的属性全集，F为U上 R(U,F) 的一组函数依赖，则对R(U,F)有以下推理规则。 R(U,F)有以下推理规则 的一组函数依赖，则对R(U,F)有以下推理规则。 自反律（Reflexivity）若属性集Y包含于属性X, A1: 自反律（Reflexivity）若属性集Y包含于属性X, 属性X又包含于U 上成立。 属性X又包含于U，则X→Y在R上成立。 Y 增广律（Augmentation） A2：增广律（Augmentation） X→Y为 所蕴涵， XZ→YZ为 所蕴涵。 如 X→Y 为 F 所蕴涵 ， 且 Z⊆ U ， 则 XZ→YZ 为 F 所蕴涵 。 传递律（Transitivity） A3：传递律（Transitivity） X→Y和Y→Z为 所蕴涵， X→Z为 如X→Y和Y→Z为F所蕴涵，则X→Z为F所蕴涵
最小函数依赖集
目的：由于F 蕴含若干函数依赖， 目的：由于F 蕴含若干函数依赖，为得到最为精确 F,应去掉平凡的 无关的函数依赖和多余的属性。 应去掉平凡的、 的F,应去掉平凡的、无关的函数依赖和多余的属性。 定义 若函数依赖集F满足以下条件，那么F就是最小的， 若函数依赖集F满足以下条件，那么F就是最小的， 称为最小函数依赖集或最小覆盖。记做F 称为最小函数依赖集或最小覆盖。记做Fm 中的每一个函数依赖的依赖因素（右部） 1）F中的每一个函数依赖的依赖因素（右部）只 含有单个属性。 含有单个属性。 中没有冗余依赖，即在F 2）F中没有冗余依赖，即在F中不存在这样的函数 依赖X→Y,使得F与F-(X→Y)成立。 依赖X→Y,使得F (X Y)成立。 使得 Y)成立 3)每个函数依赖的左边没有冗余的属性 即在F 每个函数依赖的左边没有冗余的属性， 3)每个函数依赖的左边没有冗余的属性，即在F中 不存在这样的函数依赖X Y,X有真子集W Y,X有真子集 不存在这样的函数依赖X→Y,X有真子集W，使得 {X→Y}∪{W Y}与 等价。 Y}∪{W→Y} F-{X Y}∪{W Y}与F等价。
Armstrong公理的完备性 例题] Armstrong公理的完备性 [例题]
闭包） [例5.4]设R(A,B,C) F={A→B,B→C} 求：XF+（闭包） 5.4]设 根据A 推出： CD→AD,AD→AB,有CD→AB） 根据A3 推出：A→C (由CD→AD,AD→AB,有CD→AB） 根据定义5.5 5.5： 根据定义5.5： 当X=A时， XF+ = ABC X=A时 X=B时 当X=B时， XF+ = BC X=C时 当X=C时， XF+ = C 有(X→A, X→B, X→C) 有(X→B, X→C) 有(X→C)
Armstrong公理 — 阿氏公理推论
根据阿氏公理得到下面三条推论。 根据阿氏公理得到下面三条推论。 合并规则（ Rule）又称合成性。 A1’：合并规则（Union Rule）又称合成性。 如果X→Y，X→Z， X→YZ。 如果X→Y，X→Z，则X→YZ。 X→Y 伪传递规则（ Rule） A2’：伪传递规则（Pseudotransivity Rule） 如果X→Y、WY→Z，则XW→Z。 如果X→Y、WY→Z， XW→Z。 X→Y 分解规则（ Rule） A3’：分解规则（Decomposition Rule） 如果X→Y X→Z。 如果X→Y ，且Z⊆Y，则X→Z。 必定为F所逻辑蕴涵。 由阿氏公理推导出的每个 FD 必定为F所逻辑蕴涵。
规范化模式设计的三条原则
2.分离性 2.分离性 需要属性之间的“独立联系” 需要属性之间的“独立联系”使用不同的关系模式 表达，尽可能地消除数据冗余，具体来讲应达到3NF 表达，尽可能地消除数据冗余，具体来讲应达到3NF BCNF的范式级别 的范式级别。 或BCNF的范式级别。
初级关 系模式 规范化关系模式1 规范化关系模式1 投影 方法 规范化关系模式2 规范化关系模式2
最优规范化关系模式 关系u1 关系u1 关系u2 关系u2 关系u3 关系u3 关系u 关系ui
满足保持函数依赖性
最优规范化关系模式 满足无损连接性
满足3NF或 满足3NF或BCNF 3NF
满足保持函数依赖性
←同时满足→
规范化模式设计的三条原则
3.最小冗余性 3.最小冗余性 分离性需要在分解后的关系模式能表达原有信息的前 提下，实现模式个数和属性总数达到最小。 提下，实现模式个数和属性总数达到最小。
初级关 系模式 规范化关系模式1 规范化关系模式1 满足3NF或 满足3NF或 3NF BCNF 满足无损连接性 投影 方法 规范化关系模式2 规范化关系模式2 要有最小的分 解后模式个数 与属性总数
根据A3 由 CD→AD，AD→AB 根据A CD→AD， CD→AB
Armstrong公理的完备性 Armstrong公理的完备性 —属性集的闭包 属性集的闭包
定义： 定义： 设有关系模式R(U,F),U为属性全集， R(U,F),U为属性全集 的子集， 设有关系模式R(U,F),U为属性全集，X是U的子集，F 上的函数依赖集，则由阿氏公理可从F 为R 上的函数依赖集， 则由阿氏公理可从F推导出的所 有函数依赖（ 中的依赖因素（右部） 有函数依赖（X→Ai）中的依赖因素（右部）所形成的 属性集{A 属性集 {Ai ｜ i ＝ 1,2,…} 称为属性集 X 对于函数依赖 } 的闭包,记做(X) 集 F 的闭包,记做(X)F+。 引理1 引理1 ： 当且仅当Y 能根据阿氏公理由F 当且仅当 Y ⊆ XF+时 ， X→Y 能根据阿氏公理由F导出 阿氏公理是完备的。 阿氏公理是完备的。 即被F 一定能用公理推导出来。 即被F逻辑蕴涵的 FD 一定能用公理推导出来。
数据库原理
第五章 关系数据库的规范化设计 第二部分
1
第二部分内容概要
关系模式的设计问题 关系模式存在的问题 规范化理论 函数依赖 码 范式 Armstrong公理系统 Armstrong公理系统 公理系统推理规则 属性集的闭包 最小函数依赖集 规范化模式设计的三条原则
概念： 键（码）概念：
候选键（ 候选键（码）： f 定义： R(U,F)中的属性或属性组 中的属性或属性组， →U, 称为R 定义：设K为R(U,F)中的属性或属性组，若K→U,则K称为R的候选键 候选码或候选关键字） （候选码或候选关键字关系模式候选键中一个属性为主键（码） 主属性：包含任何一个候选键的属性。 主属性：包含任何一个候选键的属性。 非主属性：不包含在任一候选键中的属性。 非主属性：不包含在任一候选键中的属性。 若候选键包含所有的属性，称为R的全键。 全 键：若候选键包含所有的属性，称为R的全键。 为关系模式R中的属性或属性组，若其不是R的主键， 外 码：F为关系模式R中的属性或属性组，若其不是R的主键， 但却是另外一个关系模式S的主键，则称F 的外键。 但却是另外一个关系模式S的主键，则称F为R的外键。 关键字定义： 关键字定义： R(U)为一关系模式 为一关系模式， 的函数依赖集， 为属性集U 设R(U)为一关系模式，F为R的函数依赖集，X为属性集U的子 如果满足： 集，如果满足： 不存在Y （1）X→U∈F+；（2）不存在Y ⊂ X，使得 Y→U∈F+； 则称X 的关键字。 则称X是R的关键字。
规范化模式设计的三条原则
1.表达性 1.表达性 表达性分别用无损连接性和保持函数依赖性来衡量。 表达性分别用无损连接性和保持函数依赖性来衡量。
初级关 系模式 规范化关系模式1 规范化关系模式1 投影 方法 规范化关系模式2 规范化关系模式2
最优规范化关系模式 满足无损连接性
←同时满足→
满足保持函数依赖性
确定键的基本思路： 确定键的基本思路：
为空， 1、查找函数依赖集F：设未出现的属性集K’，若K’为空， 查找函数依赖集F 设未出现的属性集K ， 为空 转4； f 观察K , 为候选键。 2、观察K’,若K’→U,则K’为候选键。否则结束。 U 为候选键 否则结束。 可以分别与{U 3、K’可以分别与{U-K’}中的每个属性组成新的属性集， 可以分别与{U- }中的每个属性组成新的属性集， 看哪个属性集能完全决定U 看哪个属性集能完全决定U，合并一个属性不行就合 并多个（2,3,…） 直到找到所有的候选键，结束。 并多个（2,3, ）,直到找到所有的候选键，结束。 为空集， 4、若K’为空集，查找F中其他的决定因素，同样方法单 为空集 查找F中其他的决定因素， 匹配或组合形成属性集看是否完全决定U 匹配或组合形成属性集看是否完全决定U，查找出其 他的所有候选键。 他的所有候选键。
运用阿氏公理的例题
设有关系R(A,B,C,D,E,F) [例5.3] 设有关系R(A,B,C,D,E,F) 求证： 求证：由C→A,D→B 推出 CD→AB 证明：根据A 证明：根据A2 由 C→A 由 D→B 推出 增广律） 推出 CD→AD （增广律） 推出 AD→AB （增广律） 增广律） （传递律） 传递律）