decomposition - BCNF分解算法不起作用

Question

我有以下问题：R(ABCDEFG) 和 F ={ AB->CD, C->EF, G->A, G->F, CE ->F}。显然，B & G 应该是键的一部分，因为它们不是依赖集的一部分。此外，BG+ = ABCDEFG，因此是候选键。显然，AB->CD 违反了 BCNF。但是当我遵循算法时，我没有得到任何答案。可能是做错了什么。谁能告诉我如何正确应用算法来达到分解？

提前致谢。

Answer 1

首先，您应该计算依赖项的规范覆盖。在这种情况下，它是：

{ A B → C
  A B → D
  C → E
  C → F
  G → A
  G → F } >

由于（唯一）候选键是B G，所以没有函数依赖满足 BNCF。然后，从任何X → Y违反 BCNF 的函数依赖开始，我们计算 , 的闭包X，并用两个关系和X+替换原始关系。因此，在这种情况下选择依赖项，我们将原始关系替换为：R<T,F>R1<X+>R2<T - X+ + X>A B → C

R1 < (A B C D E F) ,
     { A B → C
       A B → D
       C → E
       C → F} >

和：

R2 < (A B G) ,
     { G → A } >

然后我们检查每个分解的关系，看它是否满足 BCNF，否则我们递归地应用该算法。

在这种情况下，例如，在R1key is 中A B，因此C -> E违反了 BCNF，我们替换R1为：

R3 < (C E F) ,
     { C → E
       C → F } >

和：

R4 < (A B C D) ,
     { A B → C
       A B → D } >

两个满足 BCNF 的关系。

最后，由于R2too 不满足 BCNF（因为 key 是B G），我们分解R2为：

R5 < (A G) ,
     { G → A } >

和：

R6 < (B G) ,
      { } >

在 BCNF 中。

所以最终的分解由以下关系构成：R3、R4、R5和R6。我们还可以注意到，G → F对原始关系的依赖在分解中丢失了。