时间戳

首页 > 解决方案 > 如何找到最小封面的数量？

database-design - 如何找到最小封面的数量？

问题描述

考虑 R(A, B, C, D, E, F, G) 是具有以下函数依赖关系的关系模式：AC → G, D → EG, BC → D, CG → BD, ACD → B, CE → AF .
可能的不同最小覆盖的数量是

我该如何解决上述问题？

我尝试了什么：
---------------------------------- ----------------
我找到可能的最小覆盖数量的方法是首先使用算法（如下所示），然后通过运行找到可以找到最小覆盖的不同方法算法（因此给出了可能的最小覆盖数）。问题是我不确定我应该如何考虑“找到最小封面的不同方法”。例如：

找到最小覆盖的算法（教科书：“数据库系统基础” - Elmasri，Navathe）：

输入：一组函数依赖 E。

  1. 设置 F := E。

  2. 将 F 中的每个函数依赖 X → {A1, A2, ..., An} 替换为 n 个函数依赖 X →A1, X →A2, ..., X → An。


  3. 对于每个作为 X 的元素的属性 B在 F 中的每个函数依赖 X → A如果 { {F – {X → A} } ∪ { (X – {B} ) → A} } 等价于 F 然后替换 X → 带有 (X – {B} ) 的 A → F 中的 A。

  4. 对于 F 中每个剩余的函数依赖 X → A，如果 {F – {X → A} } 等价于 F，则从 F 中删除 X → A。

在应用该算法时，在 ACD → B 处，我发现 A 和 D 在第 3 步是无关的（用 C → B 替换 ACD → B 会给出一组等效于 F 的函数），但我不确定是否必须替换ACD → B 与 C → B 或 ACD → B 与 AC → B 或 ACD → B 与 CD → B。假设我用 AC → B 或 CD → B 替换 ACD → B，我不确定是否替换 ACD → B 与 AC → B 可能导致一个可能的最小覆盖，并且用 CD → B 替换 ACD → B 可能导致另一个可能的最小覆盖。
-------------------------------------------------- ------------
注意：

标签： database-designdatabase-normalizationfunctional-dependencies

解决方案

我不确定是否必须将 ACD → B 替换为 C → B 或 ACD → B 替换为 AC → B 或 ACD → B 替换为 CD → B。

实际上该算法必须按顺序应用。因此，您可以从该依赖项中删除 A 或 D，但是您必须再次根据算法规则检查生成的功能依赖项集。

实际上，例如，如果您删除 A，则生成的依赖项是CD → B，并且如果您重复该步骤，您会发现现在在此依赖项中不再有多余的属性。同样，如果删除 D，则生成的依赖AC → B项也不包含无关属性。

因此，您可以看到，根据您在此步骤中检查属性的顺序，理论上您可以生成不同的最小覆盖（并非总是如此，在本例中）。

对于找到所有可能的最小覆盖的问题，我不知道是否有算法或巧妙的技术可以找到它们。一种方法是尝试通过考虑所有可能顺序中的依赖关系以及所有可能顺序中依赖关系的左侧部分来尝试应用该算法，但这当然是一个指数过程。

推荐阅读