数据库第四章2

1 4 4函数依赖的公理系统 4 4 1函数依赖的逻辑蕴涵4 4 2Armstrong公理系统4 4 3函数依赖集的等价和覆盖4 4 4函数依赖集的最小集 2 4 4 1函数依赖的逻辑蕴涵 一 逻辑蕴涵的定义研究的问题 对于给定的一组函数依赖 要判断另外的一些函数依赖是否成立 例如 对关系模式R A B C 已知A B B C 判断A C是否成立 这就是函数依赖的逻辑蕴涵所要研究的内容 定义4 1 设F是关系模式R的一个函数依赖集 X Y是R的属性子集 如果从F中的函数依赖能够推导出X Y 则称F逻辑蕴涵X Y 或X Y是F的逻辑蕴涵 3 二 F的闭包F 定义4 2 所有被F逻辑蕴含的函数依赖的集合称为F的闭包 Closure 记为F 即 F 是所有能从F中推导出来的函数依赖的集合 通常 F F 若F F 则称F是函数依赖的完备集 说明 F 的计算相当麻烦 即使F不大 但F 可能很大 4 4 1函数依赖的逻辑蕴涵 4 例 若有关系模式R X Y 它的函数依赖集F X Y 则F的闭包为 F X Y XY X X Y Y XY X X Y XY Y X XY XY XY 上述函数依赖中 很多是意义不大的 如X X X等 但借此可以了解F 的全貌 4 4 1函数依赖的逻辑蕴涵 5 三 关系的码定义4 3 设有关系模式R A1 A2 An F是它的函数依赖集 X是 A1 A2 An 的一个子集 如果 1 X A1A2 An F 且 2 不存在X的真子集Y 使得Y A1A2 An成立 且Y A1A2 An F 则称X是R的一个候选码 上述条件 1 表示X能唯一决定一个元组 条件 2 表示X是能满足 1 而又无多余的属性集 4 4 1函数依赖的逻辑蕴涵 6 4 4 2Armstrong公理系统 为了确定码和函数依赖的逻辑蕴涵 需要从F中的函数依赖出发 推出F 中的所有函数依赖 或者对于给定的F和X Y 判断X Y是否在F 中 为此 要求有一套正确和完备的推理规则 1974年 W W Armstrong总结了各种推理规则 将其中最主要 最基本的作为公理 形成了最著名的Armstrong公理系统 简称阿氏公理 公理系统是模式分解算法的理论基础 7 一 Armstrong公理设有关系模式R U F U A1 A2 An 为属性全集 F是R的函数依赖集 X Y Z U 则有 自反律 Reflexivity 若Y X 则X Y 增广律 Augmentation 若X Y Z U 则XZ YZ 传递律 Transitivity 若X Y Y Z 则X Z 4 4 2Armstrong公理系统 8 4 4 2Armstrong公理系统 二 Armstrong公理的正确性定理4 1 Armstrong公理是正确的 1 自反律 若Y X 则X Y 证明 设r是R的任意一个关系 s t是r的任意两个元组 若s X t X 全体相等 Y X 即Y是X的逻辑子集 已知条件 s Y t Y 部分也相等 则在s和t中的X的任何子集也必相等 根据函数依赖的定义 有X Y 9 2 增广律 若X Y Z U 则XZ YZ 证明 设r是R的任意一个关系 s t是r的任意两个元组 已知 X Y Z U又设s XZ t XZ 则有s X t X 且s Z t Z X Y 根据函数依赖定义 有s Y t Y s Y s Z t Y t Z 即s YZ t YZ 故在s XZ t XZ 的条件下 推出了s YZ t YZ 由函数依赖的定义 有XZ YZ 4 4 2Armstrong公理系统 10 3 传递律 X Y Y Z 则X Z 证明 设r是R的任意一个关系 s t是r的任意两个元组 若s X t X 由X Y 有s Y t Y 再由Y Z 有s Z t Z 由s X t X 能导出s Z t Z 根据函数依赖的定义有 X Z 4 4 2Armstrong公理系统 11 三 Armstrong公理的推论合成规则 若X Y X Z 则X YZ 分解规则 若X YZ 则X Y X Z 伪传递规则 若X Y YW Z 则XW Z 4 4 2Armstrong公理系统 12 四 Armstrong公理的推论正确性定理4 2 Armstrong公理的三个推论是正确的 证明 1 合成规则 若X Y X Z 则X YZ X Y由增广律得 XX XY 即X XY X Z由增广律得 XY YZ又由传递律得 X YZ 4 4 2Armstrong公理系统 13 2 分解规则 若X YZ 则X Y X Z Y YZ U YZ Y 自反律 同理YZ Z 自反律 X YZ X Y 传递律 同理X Z 传递律 3 伪传递规则 若X Y YW Z 则XW Z X Y XW YW 增广律 YW Z XW Z 传递律 4 4 2Armstrong公理系统 14 例 R U A B C G H I F A B A C CG H CG I B H A H CG HI AG I 定理4 3 如果Ai i 1 2 3 n 是关系模式R的属性 则X A1A2 An成立的充要条件是X Ai i 1 2 n 均成立 4 4 2Armstrong公理系统 15 五 属性闭包1 定义4 4 设有关系模式R A1 A2 An 及属性全集U X U F是U上的一个函数依赖集 则称所有用阿氏公理从F推导的函数依赖X Ai中所有Ai的属性集合为属性集X关于F的闭包 记为X 可表示为 X Ai X Ai能由F用阿氏公理推导出 显然 X X 例如 在关系模式R中 若U A B C F A B B C 则有 A ABCB BCC C 4 4 2Armstrong公理系统 16 2 X 与F 的关系通过X 判断函数依赖X Y是否能由阿氏公理推导出来 定理4 4 设F是关系模式R A1 A2 An 的函数依赖集 U是属性全集 X Y U 则X Y能由F用阿氏公理推导出来的充要条件是 Y X X 与F 的联系 根据已知F 判断函数依赖X Y是否被F 所逻辑蕴涵的问题转化为求属性闭包X 再判断Y X 是否成立 4 4 2Armstrong公理系统 17 证明 充分性 Y X X Y设Y A1A2 An 且Y X 根据属性闭包的定义 对于每个i i 1 2 n X Ai能由阿氏公理推出 根据合成规则 X Y 必要性 X Y Y X 设X Y能由F用阿氏公理推导出来 利用分解规则可得 X Ai i 1 2 n 根据X 的定义 有 Ai X i 1 2 n A1A2 An X 即Y X 4 4 2Armstrong公理系统 18 3 属性闭包的计算算法4 1 求属性集X关于函数依赖F的属性闭包X 输入 关系模式R的全部属性集U 在U上的函数依赖F U的子集X 输出 X关于F的属性闭包X 方法 计算X i i 0 1 4 4 2Armstrong公理系统 19 1 置初值 X 0 X 2 X i 1 X i A 其中A是这样的属性 在F中寻找尚未用过的左边是X i 的子集的函数依赖Yj Zj j 1 k 其中Yj X i 即在Z中寻找X i 中未出现过的属性集合A 若无这样的A 则转 4 3 判断是否有X i 1 X i 若是则转 4 否则转 2 4 输出X i 即为X 4 4 2Armstrong公理系统 20 例 设有关系模式R U F 其中U A B C D E F AB C B D C E EC B AC B 求 AB 解 由算法4 1 1 X 0 AB 2 在F中寻找左边是AB子集的函数依赖 结果是 AB C B D X 1 X 0 CD ABCD X 1 X 0 接着在F中寻找尚未用过的左边是ABCD子集的函数依赖 结果是 C E AC B 4 4 2Armstrong公理系统 21 X 2 X 1 E ABCDE X 2 X 1 接着在F中寻找尚未用过的左边是ABCDE子集的函数依赖 结果是 EC B B属性已经出现过了 所以输出X 2 X ABCDE 4 4 2Armstrong公理系统 22 例 设有关系模式R U F 其中U A B C D E F AB C B D C E EC B AC B 求 AB 解 由算法4 1 1 X 0 AB 2 所用依赖X i 1 X i AAB CX 1 X 0 C ABCX 1 X 0 B DX 2 X 1 D ABCDX 2 X 1 C EX 3 X 2 E ABCDEX 3 X 2 EC BB属性已经出现过了 输出X 3 AB ABCDE 4 4 2Armstrong公理系统 23 判断计算属性的闭包何时可以停止 以下四种方法是等价的 1 X i 1 X i 2 当发现X i 包含了全部属性时 3 在F中函数依赖的右边再也找不到X i 中未出现过的属性 4 在F中未用过的函数依赖的左边属性已没有X i 的子集 4 4 2Armstrong公理系统 24 例2 R U A B C G H I F A B A C CG H CG I B H 计算 AG 解 所用依赖 AG A BAGBA CAGBCCG HAGBCHCG IAGBCHI AG ABCGHI 4 4 2Armstrong公理系统 25 例3 R U A B C D E G F A E BE AG CE A G D 计算 AB 解 所用依赖 AB A EABEBE AGABEGG DABEGD AB ABDEG 4 4 2Armstrong公理系统 26 六 Armstrong公理的完备性定理4 5 Armstrong公理是完备的 凡是能从F中用公理推出的函数依赖都必定由F逻辑蕴涵 或者说 凡是不能从F中用公理推导的函数依赖都不由F逻辑蕴涵 从公理的完备性可以得到如下两个重要结论 1 所有由F逻辑蕴涵的X A的属性A的集合叫X的属性闭包X 2 用阿氏公理从F推出的所有函数依赖的集合叫函数依赖集F的闭包F 4 4 2Armstrong公理系统 27 六 Armstrong公理的完备性因此 判断某个函数依赖X Y是否由F逻辑蕴涵转化为计算X 若X 包含Y 则X Y是由F逻辑蕴涵 即若Y X 则X Y F 若X 不包括Y 则X Y不由F逻辑蕴涵 即若Y X 则X Y F 4 4 2Armstrong公理系统 28 4 4 3函数依赖集的等价和覆盖 一 定义等价 设F和G是R的两个函数依赖集 如果F G 则称F等价于G 覆盖 若F和G是R的两个等价的函数依赖集 则称F覆盖G 同时G也覆盖F 二 F和G等价的充要条件设F和G是R的两个函数依赖集 则F和G等价的充分必要条件是 F G 且G F 29 证明 1 必要性若F G 即若F G等价 则F F G 即F G 函数依赖闭包的定义 G G F 即G F 函数依赖闭包的定义 2 充分性若F G G F 则F G 即F G G F 即G F G F 4 4 3函数依赖集的等价和覆盖 30 三 F的另一种等价覆盖定理4 6 每个函数依赖集F都可以被一个右部只有单个属性的函数依赖集G所覆盖 例 已知R U F U A B C D F A BC A CD 解 对于F 由分解规则可得 F可分解为G A B A C A C A D 消去冗余FD 得G A B A C A D 对G 由合成规则可得 A BC A CD G等价于F 即G覆盖F 4 4 3函数依赖集的等价和覆盖 31 4 4 4函数依赖集的最小集 一 最小集定义对于给定的一个函数依赖集F 当满足下列条件时 则称为F的最小函数依赖集 或者称为F的最小集 记为F 1 F 的每个函数依赖的右部都是单个属性 2 对于F 的任一函数依赖X A来说 F X A 与F 都不等价 3 对于F 的任一函数依赖X A来说 F X A Z A 与F 都不等价 其中 Z为X的任一子集 32 定理4 7 每个函数依赖集F都与它的最小函数依赖集F 等价 二 F的最小依赖集求解算法算法4 2 1 用分解规则将F中所有依赖变为右边都是单属性的依赖 2 去掉F中多余的依赖 对每个依赖X Y 在F X Y 中求X 若Y X 则X Y多余 去掉 3 去掉各依赖左边的多余属性 对每个左边为多属性的依赖 如XY A 在F中求X 若A X 则Y是多余属性 用X A代替XY A 4 4 4函数依赖集的最小集 33 例 已知AB CD EGC ABE CBC DCG BDACD BCE AG求F 解 1 用分解规则 将F中所有函数依赖变为右边都是单属性的依赖 得 AB CD ECG BC AD GCG DBC DBE CCE AACD BCE G F F1 4 4 4函数依赖集的最小集 34 2 去掉F1中多余的函数依赖 对AB C 在F1 AB C 中计算 AB AB AB C AB AB C不能去掉对C A 在F1 C A 中计算C C C A C C A不能删掉对BC D 在F1 BC D 中计算 BC BC ABC D ABC BC D保留对ACD B 在F1 ACD B 中计算 ACD ACD ABCDEG B ABCDEG 即B ACD ACD B为多余依赖 去掉 4 4 4函数依赖集的最小集 35 AB C AB AB C a b C A C C A C BC D BC BCA D BCA ACD B ACD ABCDEG B ABCDEG deleteACD BD E D DG E DG D G D DE G DE BE C BE BE C BE CG B CG CGDA B CGDA CG D CG CGBADE D CGBADE deleteCG DCE A CE CEGABD A CEGABD deleteCE ACE G CE CEA G CEA 4 4 4函数依赖集的最小集 36 经上述计算 得 AB CD ECG BC AD GCE GBC DBE C F2 注意 F的最小函数依赖集不是唯一的 与计算顺序有关 4 4 4函数依赖集的最小集 37 3 去掉F2中函数依赖左边的多余属性 对AB C 在F2中分别计算 对A 求B B C B A不是多余属性 对B 求A A C A B不是多余属性 对BC D 在F2中分别计算 对B 求C AC D C B不是多余属性 对C 求B B D B C不是多余属性 对BE C 在F2中分别计算 对B 求E 对E 求B 最终F2中函数依赖的左边无多余属性 F2即为F的最小函数依赖集 4 4 4函数依赖集的最小集 38 4 5关系模式的分解 4 5 1模式分解的定义4 5 2模式分解中的问题4 5 3无损连接分解4 5 4保持函数依赖的分解4 5 5候选码的求解理论与算法4 5 6关系模式的分解算法 39 定义4 5 函数依赖集合Fi Fi X Y X Y F XY Ui 称为F在Ui上的投影 定义4 6 关系模式R的一个分解是指 R1 R2 Rn 其中 1 U U1 U2 Un 2 Ui与Uj可以相交 但不允许Ui Uj或Uj Ui i j 1 i j n 3 Fi是F在Ui上的投影 4 5关系模式的分解 40 分解的基本代数运算投影自然连接分解的目标无损连接分解保持函数依赖达到更高级范式 4 5关系模式的分解 4 5 2模式分解中存在的问题 A B B C 插入 违反B C 4 5 2模式分解中存在的问题 43 n 4 5 3无损连接分解 定义4 7 关系模式R U U1 U2 Un R1 R2 Rn 是R的一个分解 r是R的一个关系 定义m r Ri r 若对于R的任一个关系r 都有r m r 则称 是R的一个无损连接分解 i 1 44 算法4 3 判别一个模式分解的无损连接性 输入 关系模式R A1 A2 An 它的函数依赖集F 以及分解 R1 R2 Rn 输出 确定 是否具有无损连接性 方法 1 构造一个k行n列的表 第i行对应于关系模式Ri 第j列对应属性Aj 如果Aj Ri 则在第i行第j列上放符号aj 否则放符号bij 4 5 3无损连接分解 45 2 逐个检查F中的每一个函数依赖 并修改表中元素 方法是 取得F中一个函数依赖X Y 在X的分量中寻找相同的行 然后将这些行中Y的分量改为相同的符号 如果其中有aj 则将bij改为aj 若其中无aj 则改为bij 3 这样反复进行 如果发现某一行变成了a1 a2 an 则分解 具有无损连接性 如果直到检验完F中所有依赖也没有发现这样的行 则分解 不具有无损连接性 4 5 3无损连接分解 46 例1 设有关系模式R U F U A B C D E F AB C C D D E 判断分解 A B C C D D E 是否具有无损连接性 解 1 构造一个3行5列的表 4 5 3无损连接分解 AB C C D D E 4 5 3无损连接分解 F AB C C D D E 48 例2 设有关系模式R U F U A B C D E F A C B C C D DE C CE A 判断分解 AD AB BE CDE AE 是否具有无损连接性 解 1 构造一个5行5列的表 2 逐个检查F中的每一个函数依赖 并修改表中元素 4 5 3无损连接分解 B C C D A C F A C B C C D DE C CE A C D F A C B C C D DE C CE A DE C CE A 3 这样反复进行 因为有一行变成了a1 a2 an 所以分解 具有无损连接性 51 定义4 8 分解为两个关系模式 关系模式R U U1 U2 U U1 U2 U r是R上的一个关系 r1 U1 r r2 U2 r 若r r1r2 则称 r1 r2 是r的一个无损连接分解 注 r U1 r U2 r R A B C AB R BC R AB R BC R 4 5 3无损连接分解 52 定理4 8 设 R1 R2 是关系模式R的一个分解 F是R上的函数依赖集 则对于F来说 具有无损连接性的充要条件是 R1 R2 R1 R2 或 R1 R2 R2 R1 例1 设R U F U A B C F A B C B 分解 1 AB BC R1 R2 BR1 R2 AB A FR2 R1 CB C F所以 1不具有无损联接性 分解 2 AC BC R1 R2 CR1 R2 AC A FR2 R1 BC B F所以 2具有无损联接性 4 5 3无损连接分解 53 例2 设R U F U A B C D E F F A B C F E A CE D 分解 R1 ABE R2 CDEF R1 R2 ER1 R2 ABE AB F但E A F A B F 由传递规则 E B由合成规则 E AB F 所以 具有无损联接性 注意 若表达式 R1 R2 R1 R2 F为假 则继续判断表达式 R1 R2 R2 R1 F的真假 表达式可推广为 R1 R2 R1 R2 F R1 R2 R2 R1 F 4 5 3无损连接分解 54 定义4 5 设有关系模式R Z是U的子集 函数依赖集合F在Z上的投影定义为 Z F X Y X Y F XY Z 定义4 9 设关系模式R的一个分解为 R1 R2 Rn F是R的依赖集 如果F等价 R1 F R2 F Rn F 则称分解 具有函数依赖保持性 4 5 4依赖保持分解 55 例1 设R1 U A B C F A B C B 判断 1 AC AB 是否具有依赖保持性 解 AC F AB F A B AC F AB F 与F不等价 1不具有依赖保持性 例2 设R2 U A B C D E F F A B E A C F CE D 判断 2 ABE CDEF 是否具有依赖保持性解 ABE F A B E A CDEF F C F CE D ABE F U CDEF F F 2具有依赖保持性 4 5 4依赖保持分解 56 例3 已知R U CITY ST ZIP F CITY ST ZIP ZIP CITY 判断分解 R1 ST ZIP R2 CITY ZIP 是否具有无损连接性 是否具有依赖保持性 解 R1 R2 ZIP R2 R1 CITY R1 R2 R2 R1 分解 具有无损连接性 R1 F R2 F ZIP CITY R1 F R2 F 与F不等价丢失了函数依赖 CITY ST ZIP 不具有依赖保持性 4 5 4依赖保持分解 57 对于给定的关系模式R A1 A2 An 和函数依赖集F 可将其属性分为四类 L类 仅出现在F的函数依赖的左部的属性R类 仅出现在F的函数依赖的右部的属性N类 在F的函数依赖的左右两边均未出现的属性LR类 在F的函数依赖的左右两边均出现的属性定理4 9 对于给定的关系模式R及其函数依赖集F F中不包括平凡函数依赖 若X X R 是L类属性 则X必为R的任一候选码的成员 4 5 5侯选码的求解理论与算法 58 定理4 10 对于给定的关系模式R及其函数依赖集F 若X X R 是R类属性 则X不在任何候选码中 定理4 11 对于给定的关系模式R及其函数依赖集F 若X X R 是N类属性 则X必包含在R的任一候选码中 推论4 1 对于给定的关系模式R及其函数依赖集F 若X X R 是L类属性 且X 包含了R的全部属性 则X必为R的唯一候选码 推论4 2 对于给定的关系模式R及其函数依赖集F 如果X是R的N类和L类组成的属性集 且X 包含了R的全部属性 则X是R的唯一候选码 4 5 5侯选码的求解理论与算法 59 例1 设有关系模式R A B C D 其函数依赖集F D B B D AD B AC D 求R的所有候选码 解 L类 A CR类 无N类 无LR类 B D L N AC ABCDAC为R的唯一候选码 4 5 5侯选码的求解理论与算法 60 例2 设有关系模式R A B C D E P R的函数依赖集 F A D E D D B BC D DC A 求R的所有候选码 解 L类 C ER类 无N类 PLR类 B D L N CEP ABCDEPCEP是R的唯一候选码 4 5 5侯选码的求解理论与算法 61 一 达到3NF且保持函数依赖的分解算法4 5 将R分解为3NF 且具有依赖保持性 输入 关系模式R和R的最小依赖集F 输出 R的一个分解 R1 R2 Rk Ri为3NF i 1 2 k 具有依赖保持性 1 求R的最小依赖集F 2 若F 中有一FD X A 且XA U R 则 R 转5 3 若R中某些属性在F 中所有依赖的左部和右部均不出现 则将它们构成一个关系模式 从R中将它们分出去 4 对F 中的每一个Xi Ai 都构成一个关系子模Ri XiAi 5 停止分解 输出 它是3NF且具有依赖保持性 4 5 6关系模式的分解算法 62 例 已知 R U F R C T H R S G 最小集F C T CS G HT R HR C HS R 将R分解为3NF且具有依赖保持性 解 1 求F 题目已给2 在F 中找X A 且XA R 没有3 找在F 中不出现的属性 没有4 对F 中的每个Xi Ai 构成一个关系子模式Ri XiAi CT CSG HTR HRC HSR 此分解 为3NF 且具有依赖保持性 4 5 6关系模式的分解算法 63 二 达到3NF且具有无损连接性和函数依赖保持性的分解算法4 6 将R分解为3NF 使它既具有无损连接性又具有依赖保持性 输入 关系模式R和R的最小依赖集F 输出 R的一个分解 R1 R2 Rk Ri为3NF i 1 2 k 具有无损连接性和依赖保持性 1 根据算法4 5求出依赖保持性分解 R1 R2 Rk 2 判定 是否具有无损连接性 若是 则转4 3 令 X 其中X是R的候选码 4 输出 它具有无损连接性和依赖保持性 4 5 6关系模式的分解算法 64 三 结果为BCNF的无损连接性分解算法4 4 将R分解为BCNF 且具有无损联接性 输入 关系模式R及R上的函数依赖集F 输出 R的一个无损联接分解 R1 R2 Rk