计算闭包

输入：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) \quad B →CD分解为B→C,B→D$

$ (2) \quad 依次消除冗余函数依赖 $

$ 考察AB→D，G={B→C,B→D， DE→B，C→D，D→A} (AB)G+=ABCD,因为D属于ABCD，冗余$
$考察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 \rightarrow D，G={B-C,DE-B,D-A}不冗余
$

$ 考察D \rightarrow A,不冗余$

F={B→c， DE→B，C→D

$(3) s消除函数依赖左边的冗余属性\
(D)F+=AD，E不冗余\
(E)F+=E,D不冗余\
Fm={B→C， DE→B，C→D，D→A} $

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

求候选码

$(1)根据函数依赖将属性分为四种，L(只出现在左侧的属性),R(只出现在右侧的属性),N(两侧都没有出现的属性),LR(两侧都出现的属性)$

$(2) 令X = LN,Y = LR$

$(3)求X在F上的闭包，如果X在F上的闭包是全集那就说明X是候选码，如果不是，就从Y中取一个属性加到X中，\ 然后再次判断X的闭包是否为全集，按照上述说法，一直重复，直到找出所有的候选码$

转换为三范式的保持函数依赖的分解

  1. $ 求最小函数依赖集$
  2. $ 合并相同的左部，如果存在 AB \rightarrow D 和 AB \rightarrow C 那么将他合并为 AB \rightarrow CD$
  3. $ 以上操作进行完成后，把左部进行分类（如果有不存在的属性，把这个属性单独放）$