闭包

闭包的定义

在关系模式R<U,F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包,记为F+

计算闭包

输入:X,F

输出:XF+
步骤:
(1)令X(0) = X,i = 0
(2)求B,这里B = { A |($${\exists}$$ V)($${\exists}$$ W)(V→W$${\in}$$F∧V $${\subseteq}$$ X (i)∧A$${\in}$$ W)};
(3)X(i+1)=B∪X(i)
(4)判断X(i+1)= X (i)?
(5)若相等或X(i)=U , 则X(i)就是XF+ , 算法终止。
(6)若否,则 i = i + 1,返回第(2)步

这种方法看起来太过于麻烦了,简单点说就是再函数依赖集F中寻找X子集可以推导出的属性

例如:关系模式R<U,F>,其中U={A,B,C,D,E},F={AB→C,B→D,C→E,EC→B,AC→B},求(AB)再函数依赖集F中的闭包

第一步,令X(0)=AB。

第二步,求X(1)。先列出X(0)的非空子集,即AB的非空子集为{A,B,AB}。然后扫描F集合,寻找{A,B,AB}可能存在的函数依赖,就可以得到:AB→C,B→D。于是就可以求得X(1)=X(0)∪C∪D=ABCD。然后判断X(0)如果等于X(1)就结束,如果X(0)不等于X(1)就继续计算。后面继续寻找ABCD的自己再F中存在的函数依赖最后得出答案(AB)+ = ABCDE

Tip:感觉不需要分这么多步骤的,每次把得到的属性写下来,最后按照顺序排一下就好了

最小函数依赖集定义

如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。

(1)F中任一函数依赖的右部仅含有一个属性。

(2)F中不存在这样的函数依赖X→A,使得F与F-{X→A}等价。

(3)F中不存在这样的函数依赖X→A, X有真子集Z使得F-{X→A}∪{Z→A}与F等价。

计算最小函数依赖集

(1)将F中的所有函数依赖的右边化为单一属性;
$$
对于(1)来说:如果依赖集F中存在类似于A \rightarrow BC 这样的函数依赖,将其化为A\rightarrow B ,A \rightarrow C
$$
(2)去掉F中的所有函数依赖左边的冗余属性;
$$
\quad \quad对于(2)来说,如果依赖集F中存在类似于AB \rightarrow C这样的函数依赖,要判断是否A \rightarrow C,或
B \rightarrow C,\如果满足任意一个条件,去除另一个属性
$$
(3)去掉F中所有冗余的函数依赖。
$$
对于(3)来说,如果依赖集F为A \rightarrow B \quad AB \rightarrow C \quad A \rightarrow C,去除任意一组函数依赖,判断剩下\的函数依赖是否可以推出该函数依赖,如果可以说明冗余,需要去除,这样依次判断每一组函数依赖
$$

例题:

设有关系模式R(A,B,C,D,E),R的函数依赖集F={AB→D,B→CD,DE→B,C→D,D→A},计算最小依赖函数集

(1)B →CD分解为B→C,B→D
(2)依次消除冗余函数依赖
考察AB→D,G={B→C,B→D, DE→B,C→D,D→A} (AB)G+=abcd,因为D属于,冗余
考察B→C,G ={B→D, DE→B,C→D,D→A}不冗余
考察B→D, G ={B→c, DE→B,C→D,D→A}冗余
考察DE-B,G= {B→c,C→D,D→A}不冗余
考察C-D,G={B-C,DE-B,D-A}不冗余
考察D-A,不冗余
F={B→c, DE→B,C→D,D→A}
(3)消除函数依赖左边的冗余属性
(D)F+=AD,E不冗余
(E)F+=E,D不冗余
Fm={B→C, DE→B,C→D,D→A}

Tip:步骤2与步骤三可以颠倒