数据依赖的公理系统-read.pptVIP

6.4 数据依赖的公理系统 6.4.1定义 关系模式R U, F ，对于其上任意一个关系r，若函数依赖X?Y都成立，则称F逻辑蕴涵X?Y。 在关系模式R U, F 中，为F所逻辑蕴涵的函数依赖的全体称作F的闭包，记作F+。 例：F={X?Y，Y?Z}，则{X?Z} ? F+。 6.4.2.1Armstrong公理 X，Y，Z是属性集， 自反律。若Y ? X， 则X ? Y。 增广律。若X ? Y ，则XZ ? YZ。 传递律。若X ? Y， Y ? Z，则X ? Z 。 6.4.2.2 Armstrong公理的有效性及完备性 A = { f | 可用Armstrong公理从F中导出的函数依赖f} B = {f | 被F所逻辑蕴涵的函数依赖f} 有效性：用Armstrong公理从F中导出的函数依赖必为F所蕴涵。 A ? B 完备性：F所蕴涵的函数依赖都能用Armstrong公理从F中导出。 B ? A 由Armstrong公理导出的推理规则 合并律。若X ? Y，X ? Z，则X ? YZ。 分解律。若X ? YZ ，则X ? Y，X ? Z 。 伪传递律。若X ? Y，WY ? Z，则XW ? Z 。 示例 R U, F , U = (A, B, C, G, H, I), F = {A?B, A?C, CG?H, CG?I, B?H}, A? H？ Y CG ? HI？Y AG ? I？ Y 思考：若属性组合是码，则函数依赖会有何特征？？ 问题：有没有一般性的算法判定X?Y是否能由F根据Armstrong公理导出？ 6.4.3 属性集的闭包 设F为属性集U上的一组函数依赖，X ? U， = {A | X?A能由F根据Armstrong公理导出} 称 为属性集X关于函数依赖集F的闭包。 引理一： X?A1 A2 ?Ak成立 ? X?Ai成立(i=1, 2, ? ,k) 证明： 由合并律 ? 由分解律 ? 引理二 Y ? ? F 逻辑蕴涵X?Y 算法（求属性集的闭包） 由引理二，判定X?Y是否能由F根据Armstrong公理导出，可转化为求 ，判定Y? 是否成立。 Input：X，F Output： := X; while ( 发生变化）do for each 函数依赖 A?B in F do begin if A ? then := ?B end 示例1 R U, F , U = (A, B, C, G, H, I), F = {A?B, A?C, CG?H, CG?I, B?H},计算 。 所用依赖 A?B AGB A?C AGBC CG?H AGBCH CG?I AGBCH I = AGBCHI 示例2 R U, F , U = (A, B, C, D, E), F = {AB?C, B?D, C?E, CE?B, AC?B},计算 。 所用依赖 AB?C ABC B?D ABCD C?E ABCDE = ABCDE 思考：若属性组合是码，则码的闭包会有何特征？？ 快速热身 R U, F , U = (C, T, H, R, S), F = {C?T, HR?C, HT?R, HS?R}，HR是码吗？(N) HS呢？(Y) 补充：后选关键字的求解理论和算法 对与给定关系R和函数依赖集，可将属性分为四类。 L类：仅出现在F的函数依赖左边的属性。 R类：仅出现在F的函数依赖右边的属性。 N类：在F的函数依赖左右两边均未出现的属性。 LR类：在F的函数依赖左右两边均出现的属性。 快速求解后选关键字的一个充分条件。 定理1：若X是L类属性，则X包含在R的任一后选关键字中。 推论1：若X是L类属性，且X包含了R的全部属性，则X必为R的唯一后选关键字。 定理2：若X是R类属性，则X不在任一后选关键字中。 定理3：若X是N类属性，则X包含在R的任一后选关键字中。 推论2：若X是R的N类和L类组成的属性集，且X+包含了R的全部属性，则X是R的唯一后选关键字。 快速热身：设R={A,B,C,D,E,P}，F={A?D,E?D,D?B,BC?D,DC?A} 求R的所有后选关键字。 6.4.4 函数依赖集的等价性 函数依赖集F，G，若F+= G+，则称F与G等价。 F+ = G+