计算最小函数依赖

计算（或构造）一个最小函数依赖集（也称为极小函数依赖集或最小覆盖）的步骤如下：

要从给定的函数依赖集 F 构造一个最小函数依赖集 Fm，可以采用以下三步处理方法 [1]:

1. 右部单一化：逐一检查 F 中的函数依赖 X→Y。如果 Y 是多个属性 A1A2…Ak (k>1)，则用{X→A1, X→A2, …, X→Ak}来取代 X→Y。这一步确保所有函数依赖的右部都只有一个属性。

2. 去除多余的函数依赖：逐一检查当前 Fm 中的每个函数依赖 X→A。令 G 为 Fm 去掉 X→A 后得到的函数依赖集。检查属性 A 是否能由 X 在函数依赖集 G 下推出（即 A 是否属于 X 关于 G 的闭包 XG+）。如果 A∈XG+，则 X→A 是多余的，可以从 Fm 中去掉。重复此步骤直到没有函数依赖可以被去除。

3. 左部最小化：逐一检查当前 Fm 中的每个函数依赖 X→A。假设 X 由多个属性 $B_1,B_2,\dots B_m$ 组成。逐一考察每个属性 $B_i(i=1,2,\dots ,m)$。检查属性 A 是否能由 X 去掉 Bi 后得到的属性集（$X-Bi$）在函数依赖集 $F_m$ 下去推出（即 A 是否属于 $(X-B_i)F_m^{+}$）。如果 $A\in (X-B_i)F_m^{+}$，则可以将 X 中的 Bi 去掉，用 X-Bi 取代 X 作为函数依赖的左部。对每个函数依赖的左部重复此步骤直到不能再简化。

经过以上三步处理后得到的函数依赖集就是一个最小函数依赖集 Fm [1]。需要注意的是，对于同一个原始函数依赖集 F，其最小函数依赖集 Fm 可能不是唯一的 [1]。

进行步骤 2 和步骤 3 时，需要用到计算属性集闭包 XF+ 的算法 [1]。引理 2 指出，X→Y 能由函数依赖集 F 根据 Armstrong 公理导出的充要条件是 Y⊆XF+ [1]。因此，判断 X→A 是否能从某个函数依赖集 G 推出（即是否 A∈XG+），可以通过计算 X 关于 G 的闭包 XG+ 并检查 A 是否包含在其中来完成 [1]。