BCNF分解算法说明

Question

我看了将一个关系分解为BCNF答案，并在作业中进行了尝试，但是我没有得到正确的答案，所以我寻求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)和R'=(BCE)，但最终答案(AD,AG,CGE,BC)。什么出了问题？还是更好的算法？

Answer 1

要将一个关系R和一组函数dependencies（FD's）转换成3NF您可以使用Bernstein的Synthesis。应用伯恩斯坦综合-

• 首先，我们确保给定的FD's一组是最小覆盖
• 其次，我们将每一个FD都设为自己的子模式。
• 第三，我们尝试将这些子方案结合起来

例如，在您的情况下：

R = {A，B，C，D，E，G}
FD = {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从CD->A和的LHS中删除，CD->E因为这D是无关紧要的属性（D从C 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 ₁ = { B，G，C}
R ₂ = { G，A}
R ₃ = { C，E}
R ₄ = { C，G}
R ₅ = { A，D}

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

S ₁ = {B，G，C}
S ₂ = {A，G}
S ₃ = {C，E，G}
S ₄ = {A，D}

这是在3NF中。现在检查BCNF，我们检查这些关系（S ₁，S ₂，S ₃，S ₄）是否违反BCNF的条件（即，对于每个功能依赖项X->Y，左手边（X）必须是一个超键）。在这种情况下，这些都没有违反BCNF，因此也被分解为BCNF。

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