1

我查看了Decomposing a relationship into BCNF answers 并在我的作业中尝试过，但我没有得到正确的答案，所以我在 BCNF 分解中寻求帮助

考虑R=(ABCDEG)& F={BG->CD, G->A, CD->AE, C->AG, A->D}。
我开始挑选A->D。
现在我得到了S=(AD), R'=(ABCEG).
我的选择G->A。
现在我得到了S=(AD,AG) R'=(BCEG)。
我挑C->G。现在我想我需要得到S=(AD,AG,CG)and R'=(BCE)，但最终的答案是(AD,AG,CGE,BC)。出了什么问题？或者，一个更好的算法？

4

2 回答 2

11

要将关系R和一组函数依赖项（FD's）转换为3NF您可以使用伯恩斯坦的综合。应用伯恩斯坦的综合 -

  • 首先我们确保给定的集合FD's是最小覆盖
  • 其次，我们采用每一个FD并使其成为自己的子模式。
  • 第三，我们尝试结合这些子模式

例如在你的情况下：

R = {A,B,C,D,E,G}
FD's = {BG->CD,G->A,CD->AE,C->AG,A->D}

首先我们检查是否FD's是最小覆盖（单例右侧，没有多余的左侧属性，没有多余的 FD）

  • Singleton RHS：所以我们可以把我们的 FD 写成 { BG->C, BG->D, G->A, CD->A, CD->E, C->A, C->G, A->D }。
  • 没有无关的 LHS 属性：我们可以D从 LHS 中删除CD->Aand CD->EsinceD是一个无关的属性（正如我们可以D从C since C->A 和 A->D中得到的那样）。所以我们现在有 {BG->C, BG->D, G->A, C->A, C->E, C->G, A->D}
  • 没有多余的 FD：我们注意到这里有很多多余的依赖项。删除它们我们有 {BG->C, G->A, C->E, C->G, A->D}

其次，我们使每个子模式都有FD自己的子模式。所以现在我们有了 - （每个关系的键都是粗体的）

R 1 ={ B,G ,C}
R 2 ={ G ,A}
R 3 ={ C ,E}
R 4 ={ C ,G}
R 5 ={ A ,D}

第三，我们看看是否可以组合任何子模式。我们看到R 3和R 4可以组合，因为它们具有相同的密钥。所以现在我们有 -

S 1 = {B,G,C}
S 2 = {A,G}
S 3 = {C,E,G}
S 4 = {A,D}

这是在3NF中。现在要检查BCNF，我们检查这些关系（S 1，S 2，S 3，S 4）是否违反BCNF的条件（即，对于每个函数依赖X->Y，左侧 ( X)必须是超键）。在这种情况下，这些都没有违反BCNF，因此它也被分解为BCNF。

注意我上面的最终答案是(AD,AG,CGE,BCG)。您期望的解决方案是(AD,AG,CGE,BC)，但这是错误的。这里的最后一个关系（S 1）也应该具有G如上所示的属性。

于 2015-12-18T07:04:07.303 回答
1

给出输入：与 FD 的 S0 的集合（最小）的关系 R0。

输出：将 R 分解为关系集合，所有这些关系都在 BCNF 中

算法：R <- R0，并且 S <- S0 重复直到 R 在 BCNF 中。如果存在违反 BCNF 条件的 FD X -> Y。计算 {X}+ ，并选择 {X}+ 作为一个关系作为 R1，另一个 R2 作为 {(R - X + ) UX} 在 R1 和 R2 上映射 FD 集 S（确定 R1 和 R2 上的 FD）。在 R1 和 R2 上递归地重复算法。

规则： 1.应该是属性保留。2.应该是无损的 3.应该是FD保存的

示例：R(xyz) FD xy -> z; key : xy z-> y;

求解：z->y 紫罗兰色 BCNF 条件。

所以分解关系R {z}+= yz; R1(yz) where key is z and R2(xz) key is x

于 2016-04-07T09:40:02.480 回答