BCNF分解算法的解释 [英] BCNF decomposition algorithm explanation

问题描述

我在分解关系到BCNF 答案，并尝试了我的家庭作业，但我没有得到正确的答案，所以我请求帮助BCNF分解

考虑 R =（ABCDEG）& F = {BG-> CD，G-> A，CD-> AE，C-> AG，A-> D} 。

我开始选择 A-> D 。

现在我得到 S =（AD） =（ABCEG）。

我选择 G-> A 。

S =（AD，AG）R'=（BCEG）。

我选择 C-> G 。
现在我想我需要得到 S =（AD，AG，CG）和 R'=（BCE），但是答案到底是（AD，AG，CGE，BC）。什么错了？或者，一个更好的算法？

解决方案

要转换关系 R 和一组函数依赖 FD's ）转换成 3NF ，您可以使用 Bernstein's Synthesis 。要应用Bernstein的综合 -

• 首先，确保给定的 / $>

• 第三，我们尝试合并这些子模式






R = {A，B，C，D，E，G}

FD's = {BG-> CD，G-> A，CD-> AE，C-> AG，A- > D}






首先，我们检查 FD的覆盖（单侧右侧，无多余的左侧属性，无冗余FD ）






<因此，我们可以将我们的FD写成{BG-> C，BG-> D，G-> A，CD-> A，CD-> E，C-> A， <> 我们可以删除 D CD <> $ 和 CD-> E 的LHS， / code>是一个额外的属性here（因为我们可以从 C 得到 D - > 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 < sub> = {A，D}






这在 3NF 。现在检查 BCNF ，我们检查这些关系（S ，S ，S S 函数依赖性 X> Y 的条件的 BCNF / code>左侧（ X ）必须 超级键 。在这种情况下，这些都不会违反 BCNF ，因此也会分解为 BCNF 。





我最后的答案是（AD，AG，CGE，BCG）。你期望的解决方案是（AD，AG，CGE，BC）但是错了。这里的最后一个关系（S ₁ ）也应该具有如上所示的 G 属性。




I looked in Decomposing a relation into BCNF answers and tried it on my homework, but i don't get the correct answers, so i ask for help in BCNF decomposition

Consider R=(ABCDEG) & F={BG->CD, G->A, CD->AE, C->AG, A->D}.
I start pick A->D.
Now i got S=(AD), R'=(ABCEG).
I pick G->A.
Now i got S=(AD,AG) R'=(BCEG).
I pick C->G. Now i think i need to get S=(AD,AG,CG) and R'=(BCE), But the answer in the end is (AD,AG,CGE,BC) .what went wrong? or perhaps, a better algorithm?

解决方案

To convert a relation R and a set of functional dependencies(FD's) into 3NF you can use Bernstein's Synthesis. To apply Bernstein's Synthesis -


• First we make sure the given set of FD's is a minimal cover
• Second we take each FD and make it its own sub-schema.
• Third we try to combine those sub-schemas

For example in your case:


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


First we check whether the FD's is a minimal cover (singleton right-hand side , no extraneous left-hand side attribute, no redundant FD)


• Singleton RHS: So we can write our FD's as { BG->C, BG->D, G->A, CD->A, CD->E, C->A, C->G, A->D}.
• No extraneous LHS attribute: We can remove D from LHS of CD->A and CD->E since D is an extraneous attribute here (As we can get D from C since C->A and A->D). So we now have {BG->C, BG->D, G->A, C->A, C->E, C->G, A->D}
• No redundant FD's: We note that there are a lot of redundant dependencies here. Removing them we have {BG->C, G->A, C->E, C->G, A->D}

Second we make each FD its own sub-schema. So now we have - (the keys for each relation are in bold)


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


Third we see if any of the sub-schemas can be combined. We see that R₃ and R₄ can be combined as they have the same key. So now we have -


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


This is in 3NF. Now to check for BCNF we check if any of these relations (S₁,S₂,S₃,S₄) violate the conditions of BCNF (i.e. for every functional dependency X->Y the left hand side (X) has to be a superkey) . In this case none of these violate BCNF and hence it is also decomposed to BCNF.

Note My final answer above is (AD,AG,CGE,BCG). The solution you expect is (AD,AG,CGE,BC) but that's wrong. The last relation here (S₁) should also have the G attribute as shown above.

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