database - BCNF分解算法讲解

Question

我查看了 Decomposing a relation into 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和一组功能依赖项( FD's )到 3NF你可以使用 Bernstein's 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₄ 可以组合，因为它们具有相同的 key 。所以现在我们有 -

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

这属于3NF。现在检查 BCNF 我们检查这些关系中的任何一个 (S₁,S₂,S₃, S₄) 违反了 BCNF 的条件(即对于 每个 函数依赖 X->Y 左侧 ( X ) 必须是一个 super 键)。在这种情况下，这些都不违反 BCNF，因此它也被分解为 BCNF。

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