最小函数依赖求解

最小函数依赖解法总结

考研复试要学习数据库数据库里面好多算法和知识点单看教科书很难理解,然后我就结合网上的博客和课本(数据库系统概论)对一些常考算法做一些总结,欢迎各位批评指正。

最小函数依赖集概念:如果函数依赖集F满足下列条件,则称F为一个极小函数依赖集。

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

F中不存在这样的函数依赖 $ X \rightarrow A$ ,使得\(F\)\(F - \{X\rightarrow A\}\) 等价。意思就是\(X\rightarrow A\)是不可或缺的。

\(F\)中不存在这样的函数依赖\(X \rightarrow A\) ,\(X\)有真子集\(Z\)使得\(F-\{X \rightarrow A\}\cup\{Z \rightarrow A\}\)\(F\)等价。意思就是\(X\)中没有多余的元素。

最小依赖集的求法:

逐一检查\(F\)中各函数依赖\(FD_i: X \rightarrow Y\) ,若\(Y=A_1A_2.......A_k, k \geq 2\) 则用 \(\{X \rightarrow A_j | j = 1, 2, .......,k\}\) 来去带\(X \rightarrow Y\)。通过这个算法我们要\(F\)中的函数依赖的右属性全部拆为单个属性。经过这一步算法F变为\(F_1\)

逐一检查\(F_1\)中各函数依赖\(F_1D_i: X \rightarrow A\) ,令\(G = F_1 - \{X \rightarrow A\}\) ,若\(A\in X_G ^+\) ,则从\(F_1\) 中去掉此函数依赖。我们检查\(F_1\) 中的每个函数依赖:\(X \rightarrow A\)\(F_1\) 中去掉此函数依赖得到函数依赖集G然后在求X关于G的属性闭包得到\(X_G^+\) 如果A属于该属性闭包则删掉次函数依赖。经过这一步算法\(F_1\) 变为\(F_2\)

逐一取出\(F_2\) 中各函数依赖\(F_2D_i:X \rightarrow A\),设\(X = B_1B_2........B_m, m \geq 2\), 逐一考察\(B_i(i =1,2,..,m)\) ,若\(A \in (X - B_i)^+_F{_2}\) ,则以\(X - B_i\) 这一步我们要检查\(F_2\)中的所有左属性,将左属性化成最简。一定要注意在求解的过程中\(F_2\) 是不变的。经过这一步算法\(F_2\) 化成最小函数依赖\(F_m\) .

例题:

\(R(U,F)中,U = \{A,B,C,D,E,G\}, F = \{B \rightarrow D, DG \rightarrow C, BD \rightarrow E, AG \rightarrow B, ADG \rightarrow BC\}\) 求最小依赖集。

执行第一步将F中的所有函数依赖的右属性拆成单个属性,例如:\(ADG \rightarrow BC,拆分成 ADG \rightarrow B 和 ADG \rightarrow C\) 拆分后\(F = \{B \rightarrow D, DG \rightarrow C, BD \rightarrow E, AG \rightarrow B, ADG \rightarrow B, ADG \rightarrow C\}\)

执行第二部算法检查每一个函数依赖。

检查\(B \rightarrow D\) : \(G = F - \{B \rightarrow D\} = \{DG \rightarrow C, BD \rightarrow E, AG \rightarrow B, ADG \rightarrow B, ADG \rightarrow C\}\) .然后求B关于G的属性闭包\(B_G^+ = \{B\}\)其中不包含D不用删掉

检查\(DG \rightarrow C\) : \(G = \{B \rightarrow D, BD \rightarrow E, AG \rightarrow B, ADG \rightarrow B, ADG \rightarrow C\}\) , \((DG)_G^+ = \{D,G\}\) 不包含C不删。

检查\(BD \rightarrow E\) :\(G = \{B \rightarrow D, DG \rightarrow C, AG \rightarrow B, ADG \rightarrow B, ADG \rightarrow C\}\) , \((BD)^+_G = \{B,D\}\) 不包含E不删。

检查\(AG \rightarrow B\) :\(G = \{B \rightarrow D, DG \rightarrow C, BD \rightarrow E, ADG \rightarrow B, ADG \rightarrow C\}\) , \((AG)^+_G = \{A,G\}\) 不包含B不删。

检查\(ADG \rightarrow B\) : \(G = \{B \rightarrow D, DG \rightarrow C, BD \rightarrow E, AG \rightarrow B, ADG \rightarrow C\}\) , \((ADG)^+_G = \{A,D,G,B,C,E\}\) 包含B删掉。

检查\(ADG \rightarrow C\) : \(G = \{B \rightarrow D, DG \rightarrow C, BD \rightarrow E, AG \rightarrow B, ADG \rightarrow B\}\) , \((ADG)^+_G = \{A,D,G,B,C,E\}\) 包含C删掉。

经过第二步算法的计算\(F = \{B \rightarrow D, DG \rightarrow C, BD \rightarrow E, AG \rightarrow B\}\) .

执行第三步检查每一个函数依赖的左属性:

检查\(DG \rightarrow C\) : 先去掉D即为\(G \rightarrow C\) \(G^+_F = \{G\}\) 不包含C留D,在去掉G, \(D \rightarrow C\) \(D_F^+ = \{D\}\)

检查\(BD \rightarrow E\) : 去掉B,\(D \rightarrow E\) \(D^+_F = \{D\}\) 不包含E留B,去掉D, \(B \rightarrow E\) \(B_F^+ = \{B,D,E\}\) 含E,去掉D。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zygzsp.html