当属性有相同的机会不需要时，如何找到最小的覆盖？

Question

我有一个由6个属性组成的模式：t,s,r,w,e,g。

对于模式，我有以下函数依赖项：

s,w --> r;t,w,g --> r,e;s,r --> t,g; e -->w; g --> t,s;r,w,e --> s

我不太确定在其中一方有3个属性的情况下如何处理依赖关系。例如，对于t,w,g --> r,e，我是否应该检查所有可能的t,w,g组合(2^3-2=6例)？

例如，我选择要检查t在t,w,g --> r,e中是否不必要的情况。实际上，{w,g}的闭包是{w,g,t,s,r,e}，它包含{r,e}。

如果我继续在w,g --> r,e中寻找不必要的属性，那么我有：

w,g --> r或w,g --> e.所以，我可以在这里选择一个随机的结果，还是有一些关于r是不必要的还是e的规则？

Answer 1

在函数依赖项中，左部分和右部分都是集，因此属性的顺序并不重要。

为了找到一组函数依赖关系的规范(或最小)覆盖，经典算法(在几乎所有关于数据库的书籍中都有)由三个步骤组成：

1. 首先，重写依赖项，以便它们在正确的部分上有一个属性(例如，t,w,g -> r,e被t,w,g -> r和t,w,g -> e替换)。
2. 然后，对于左侧的每个属性，查看剩余属性的闭包是否包括右侧属性。在这种情况下，属性是不必要的，应该删除。
3. 最后，如果有的话，消除多余的依赖关系。如果一个依赖项的右部分包含在左侧部分的闭包中，则该依赖项是多余的，该闭包是根据所有其他依赖项计算的。

例如，在您的示例中，可以这样计算可能的最小覆盖。

在第一步结束时，我们有：

{ e → w
  e r w → s
  g t w → e
  g t w → r
  g → s
  g → t
  r s → g
  r s → t
  s w → r }

在第二步结束时：

{ e r → s
  e → w
  g → t
  g → s
  g w → r
  g w → e
  r s → t
  r s → g
  s w → r }

最后，最低限度的掩护是：

{ e → w
  e r → s
  g w → e
  g → s
  g → t
  r s → g
  s w → r }