习题2:已知F={ A→D,B→D,BD→CA,CD→B },求 Fmin。
时间: 2024-05-26 18:17:36 浏览: 116
首先,我们需要使用 Armstrong's Axioms 将 F 转化为其等效的无冗余函数依赖集合。具体过程如下:
1. 消除冗余依赖
- 从 F 中删除可以由其他依赖推导出的依赖。在这个例子中,我们可以删除 BD→CA,因为它可以由 A→D 和 B→D 推导出来。
所以现在 F 为 { A→D,B→D,CD→B }。
2. 消除传递依赖
- 对于每个依赖 X→Y,在 F 中寻找可以推导出 X 的超键 K。
- 如果 K 中除了 X 还有其他属性,则将它们加入到 F 中,形成新的依赖 K-X→Y。
- 重复这个过程,直到不存在可以推导出 X 的超键为止。
在这个例子中,我们有:
- A→D,无需消除传递依赖,因为 A 是一个超键。
- B→D,无需消除传递依赖,因为 B 是一个超键。
- CD→B,找到一个超键 ABCD,将它分解为 BC→D 和 CD→B,然后删除 CD→B。
现在 F 为 { A→D,B→D,BC→D,CD→B }。
最后,我们需要找到 F 的最小等效依赖集合 Fmin。我们可以使用以下步骤:
1. 对于 F 中的每个依赖 X→Y,尝试删除 X 中的每个属性。
2. 如果删除后的集合能够推导出 Y,则删除 X 中的属性。
3. 重复这个过程,直到不能再删除属性为止。
在这个例子中,我们有:
- A→D,无法删除任何属性。
- B→D,无法删除任何属性。
- BC→D,尝试删除 B 和 C,但是都无法推导出 D。所以 BC→D 是 Fmin 的一部分。
- CD→B,尝试删除 C 和 D,但是都无法推导出 B。所以 CD→B 是 Fmin 的一部分。
因此,F 的最小等效依赖集合 Fmin 为 { A→D,B→D,BC→D,CD→B }。
阅读全文