2

我有以下问题：

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

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

任何帮助将不胜感激。

4

1 回答 1

2

您已经减少了封面中每个 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 集的最小覆盖不必是唯一的。但是，任何给定的最小覆盖必须包含与原始覆盖相同的依赖项集，这样从最小覆盖中删除任何一个依赖项都不会产生相同的闭包。

于 2013-11-12T18:35:33.477 回答