功能依赖性，属性集关闭

与功能有关的闭包

定义: 如果F是关系模型R（U）的一个功能相关的集合，我们称F和F的逻辑所隐含的所有功能相关的集合称为F的闭包.

即: F + = {X→Y | X→Y∈F∨“使用Armstong公理从F派生的任何X→Y”}

△F包含在F +中，如果F = F +，则F是函数依赖的完整集合.

△规定: 如果X是U的子集，则X→Φ属于F +.

关系模式R 如果存在n个属性，则可以在模式R中建立4n个函数依赖关系，其中2个属性组合为X，2n属性组合为Y.

示例: 知道关系模式R（ABC），F = {A→C，B→C}，找到F +

解决方案: ∵U= {A，B，C}，左侧有23 = 8种不同的属性集组合:

Φ，A，B，C，AB，BC，AC，ABC

（1）∴Φ→Φ

（2）∵（A）F + = AC

∴A→Φ，A→A，A→C，A→AC.

（3）∵（B）F + = BC

∴B→Φ，B→B，B→C，B→BC.

（4）∵​​（C）F + = C

∴C→Φ，C→C.

（5）∵（AB）F + = ABC

∴AB→Φ，AB→AB，AB→A，AB→B，AB→C，AB→BC，AB→AC，AB→ABC.

（6）∵（BC）F + = BC

∴BC→Φ，BC→BC，BC→B，BC→C.

（7）∵（AC）F + = BC

∴AC→Φ，AC→BC，AC→B，AC→C.

（8）∵（ABC）F + = ABC

∴ABC→Φ，ABC→ABC，ABC→A，ABC→B，ABC→C，ABC→BC，ABC→AB，ABC→AC.

因此，F +有35个细节，如下所示:

∴Φ→Φ，A→∅，A→A，A→C，A→AC

B→Φ，B→B，B→C，B→BC

C→Φ，C→C，AB→∅，AB→AB，AB→A，AB→B，AB→C，AB→BC，AB→AC，AB→ABC，

BC→Φ，BC→BC，BC→B，BC→C，

AC→Φ，AC→BC，AC→B，AC→C，

ABC→Φ，ABC→ABC，ABC→A，ABC→B，ABC→C，ABC→BC，ABC→AB，ABC→AC

转载于:

功能依赖集关闭

F: FD的集合称为函数相关的集合.

F闭包: 可以从F中的所有FD派生所有FD的集合，记为F +.

示例1，对于关系模式R（ABC），F = {A→B，B→C}，找到F +.

根据FD的定义，F + = {φ→φ，A→φ，A→A，A→B，A→C，A→AB，A→BC，A→ABC，…}，是43 FD其中，φ表示空属性集.

属性集关闭

属性集关闭定义:

对于F，F +，所有X→A的A的集合称为X的闭包，并表示为X +. 可以理解，X +代表X可以确定的所有属性.

属性集关闭算法:

A +: 将A放入A +. 对于每个FD，如果左部分属于A +，则将右部分放入A +，然后重复直到A +无法扩展.

超级键，候选键

如果X +包含R的所有属性，则X是超键. 当X不可约时，它是一个候选键. 如上例所示: A + = ABC，则A是超键，因为A是不可约的，则它是候选键.

在关系模型R中让U = ABC .......等待N个属性. U中的属性在FD中具有四个范围:

（1）出现在周围；

（2）仅出现在左侧；

（3）仅显示在右侧；

（4）没有出现；

找到候选密钥算法:

1.R: 仅出现在FD右侧的属性，不属于候选代码；

2.L: 仅出现在FD左侧的属性必须存在于候选代码中；

3.N: 任何候选代码中都必须存在外部属性；

4. 其他属性与2、3的属性逐一组合，以找到属性闭包，直到X的闭包等于U为止. 如果等于U，则X为候选代码.

示例2: 对于关系模式R（ABCD），F = {A→B，B→C，D→B}，找到候选键.

根据属性集闭包的算法，找到每个闭包关系 闭包是什么意思，然后获得候选键.

（1）找到A +.

①A+ = A.

②从A→B，然后从A€A +，然后从A + = AB.

③从B→C，知道B A +，则A + = ABC.

④A+是闭合的，即A + = ABC.

（2）查找B +，C +，D +.

根据步骤（1）: B + = BC，C + = C，D + = BCD.

（3）查找候选键. 显然，R的候选键是AD.

示例3，对于关系模式R（ABC），F = {A→BC，BC→A}，找到候选键.

（1）查找属性的闭包.

根据示例2: A + = ABC，B + = B，C + = C.

（2）查找属性集的闭包.

从BC→A，然后是（BC）+ = ABC，其余的属性集闭包是属性闭包的并集.

（3）查找候选键. 显然，R的候选键是A和BC.

最小功能依赖集

定义: 如果功能依赖集F满足以下条件，则F被称为最小功能依赖集. 也称为最小依赖集或最小覆盖率.

（1）F中任何函数的右侧仅包含一个属性.

（2）F中没有依赖X→A的函数，因此F等效于F- {X→A}.

（3）F中的X→A中没有这种函数依赖性. X具有真实的子集Z，因此F- {X→A} U {Z→A}等效于F.

最小依赖集通用算法:

①使用分解规则使F中任何函数的正确部分仅包含一个属性；

②删除冗余功能依赖项: 从F中删除第一个功能依赖项X→Y，然后在其余功能依赖项中找到X的闭包X +，以查看X +是否包含Y. 否则无法将其删除并依次执行. 直到找不到多余的功能依赖项为止；

③删除依赖于左侧部分的其他属性. 逐一检查函数依赖性，以检查左侧的非单个属性依赖性. 例如，如果要判断XY→A为冗余，是否等效用X→A替换XY→A？如果A属于（X）+，则Y是多余的属性关系 闭包是什么意思，可以将其删除.

示例4.查找F = {A→B，B→A，B→C，A→C，C→A}，最小（最小）函数相关集

1. 使用分解规则将所有功能依赖关系转换为右侧具有单个属性的功能依赖关系. 从角度来看，F中任何功能依赖项的右侧都只包含一个属性:

{A→B，B→A，B→C，A→C，C→A}

2. 删除F中多余的功能依赖项

（1）设A→B冗余，从F中删除A→B，然后F1 = {B→A，B→C，A→C，C→A}. 计算（A）F1 +: 设置X（0）= A，计算X（1）: 扫描F1中的每个功能相关性，在左侧找到A或A子集的功能相关性，A→C.因此，X（1 ）= X（0）UC = AC;扫描F1中的每个功能相关性，找到其左侧为AC或AC的子集的功能相关性，C→A，X（2）= X（1）UC = AC. 但是AC不包含B，因此A-> B无法从F中删除.

（2）令B→A冗余，从F中删除B→A，然后F2 = {A→B，B→C，A→C，C→A}. 计算（B）F2 +: 设置X（0）= B，计算X（1）: 扫描F2中的每个功能依赖性，找到B或B子集的左侧部分的功能依赖性，即B→C. 因此有X （1）= X（0）UC = BC;扫描F2中的每个功能依赖项，找到其左侧为BC或BC的子集的功能依赖项，C-> A，X（2）= X（1）UA = ABC.X（2）包括所有属性，因此B→A可以从F中删除.

（3）令B→C冗余，从F中删除B→C，然后F3 = {A→B，A→C，C→A}. 计算（B）F3 +: 扫描F3中的每个功能依赖项，并且找不到左侧部分是B或B的子集的功能依赖项. 因为找不到这样的功能依赖项，所以X（1）= X（0）= B，（B）F1 + = B不包含C，因此B→C不是冗余的功能依赖性，不能从F1中删除.

（4）令A→C冗余，从F中删除A→C，然后F4 = {A→B，B→C，C→A}. 计算（A）F4 +: 设置X（0）= A，计算X（1）: 扫描F4中的每个功能依赖性，在左侧找到A或A子集的功能依赖性，即A→B.因此有X（ 1）= X（0）UB = AB;扫描F4中的每个功能依赖项，找到左侧是AB或AB的子集的功能依赖项，即B→C，X（2）= X（1）UC = ABC.X（2）包含所有属性，因此A →可以从F中删除C.

（5）令C→A为冗余，并从F中删除C→A，则F4 = {A→B，B→C}. 计算（C）F5 +: 设置X（0）= C，计算X（1）: 扫描F5中的每个功能依赖项，找到左部分的功能依赖项是C或C子集，找不到左部分的功能依赖项C或C子函数依赖项集，因为找不到此类函数依赖项，因此X（1）= X（0）= C，（B）F1 + = C不包含A，因此C→A不是冗余函数依赖性，不能从F中移除.

（6）到目前为止，所有依赖项均已检查，因此F的最小（最小）功能依赖项集为: {A→B，B→C，C→A}

转载于:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-170629-1.html