BCNF分解算法不起作用 [英] BCNF Decomposition algorithm not working

问题描述

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

I have the following problem: R(ABCDEFG) and F ={ AB->CD, C->EF, G->A, G->F, CE ->F}. Clearly, B & G should be part of the key as they are not part of the dependent set. Further, BG+ = ABCDEFG, hence candidate key. Clearly, AB->CD violates BCNF. But when I follow the algorithm, I do not end up in any answer. Probably doing something wrong. Can anyone show me how to apply the algorithm correctly to reach the decomposition?

预先感谢。

推荐答案

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

First, you should calculate a canonical cover of the dependencies. In this case it is:

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

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

Since the (unique) candidate key is B G, no functional dependency satisfies the BNCF. Then, starting from any functional dependency X → Y that violates the BCNF, we calculate the closure of X, X+, and replace the original relation R<T,F> with two relations, R1<X+> and R2<T - X+ + X>. So, chosing in this case the dependency A B → C, we replace the original relation with:

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

和：

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

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

Then we check each decomposed relation to see if it satisfies the BCNF, otherwise we apply recursively the algorithm.

在这种情况下，例如，在 R1 中，键为 AB ，因此 C-> E 违反了BCNF，我们将 R1 替换为：

In this case, for instance, in R1 the key is A B, so C -> E violates the BCNF, and we replace R1 with:

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

和：

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

两个满足BCNF的关系。

two relations that satisfy the BCNF.

最后，由于 R2 也不满足BCNF（因为密钥是 BG ），因此我们分解 R2 in：

Finally, since R2 too does not satisfy the BCNF (beacuse the key is B G), we decompose R2 in:

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

和：

R6 < (B G) ,
      { } >

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

So the final decomposition is constituted by the relations: R3, R4, R5, and R6. We can also note that the dependency G → F on the original relation is lost in the decomposition.

这篇关于BCNF分解算法不起作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！