database - 功能依赖的最小覆盖

Question

我有以下问题:

AB -> CD
H->B
G ->DA
CD-> EF
A -> HJ
J>G

我理解第一步(分解右侧)并得到以下结果:

AB -> C
AB -> D
H -> B
G -> D
G -> A
CD -> E
CD -> F
A -> H
A -> J
J -> G

我理解 A -> h 和 h -> b，因此我可以从 AB -> c 和 ab -> D 中删除 B，得到:

A -> C
A -> D
H -> B
G -> D
G -> A
CD -> E
CD -> F
A -> H
A -> J
J -> G

接下来的步骤是我无法计算的(减少左侧)

任何帮助将不胜感激。

Answer 1

您已经缩小了封面中每个 FD 的左侧。下一步是将该封面中的 FD 数量减少到最少。

通过忽略一个 FD 来做到这一点时间，然后看看是否您仍然可以使用其他方法得出相同的一组依赖属性(闭包)封面中的 FD 使用被忽略的 FD 的 LHS 作为起点。如果你可以，那么你忽略的 FD 是多余的，可能会从封面上掉下来。做这个对于每个剩余的 FD。剩下的是最小的封面。

首先，使用起始封面中的所有 FD，导出属性集由您将忽略的 FD 的 LHS 决定。对于 A，闭包是:

A, B, C, D, E, F, G, H, J

尝试移除 A -> D 并重新计算闭包...

initial   closure: A
use A -> C    closure: A, C
use A -> H    closure: A, C, H
use A -> J    closure: A, C, H, J
use J -> D    closure: A, C, D, H, J
use J -> G    closure: A, C, D, G, H, J
use H -> B    closure: A, B, C, D, G, H, J
use CD -> E   closure: A, B, C, D, E, G, H, J
use CD -> F   closure: A, B, C, D, E, F, G, H, J

可以在不引用FD A -> D 所以这个 FD 是多余的，可能会从封面上掉下来。实际上我们可以一旦 D 出现在派生的属性集中就停止了进程 - 但为了完整性继续该过程以证明使用或不使用都可以实现完全相同的属性集A -> D。

请注意，给定 FD 集的最小覆盖不必是唯一的。然而，任何给定的最小覆盖必须包含与原始覆盖相同的一组依赖关系，这样从最小覆盖中删除任何一个依赖都无法产生相同的闭包。