分解为BCNF和超级密钥集 [英] Decomposition to BCNF and set of super key

问题描述

所以我有这套关系

AB-> CDEF

G-> H，I

ABJ-> K

C-> L

如何分解这个？我感到很困惑。我应该先找到一组超级键。

解决方案

我们可以先转换关系 R 到3NF，然后到BCNF。

要转换关系 R 的函数依赖（ FD's ）转换为 3NF ，你可以使用 / strong>。要应用Bernstein的综合 -

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

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






R = {A，B，C，D，E，F，G，H，I，J，K，L}

FD's = {AB-> CDEF，G-> ABJ-> K，C-> L}






首先，我们检查 c $ c>是最小的覆盖（单面右侧，无多余的左侧属性，无冗余FD ）







• Singleton RHS：我们用单例RHS编写FD。所以现在我们有FD's为{AB-> C，AB-> D，AB-> E，AB-> F，G-> H，G-> I，ABJ-> K，C-> L} >
  
• 没有无关的LHS属性：我们删除无关的LHS属性（如果有）。这里没有额外的LHS属性。


• 没有冗余的FD：我们删除冗余的依赖项，如果有的话。现在FD是{AB-> C，AB-> D，AB-> E，AB-> F，G-> H，G-> I，ABJ-> K，C-> L}






第二，我们使每个 FD 自己的子模式。现在我们有 - （每个关系的键都是粗体）






R ₁ { A，B ，C}

R ₂ = { A，B ，D}

R ₃ = { A，B ，E}

R ₄ = { A，B ，F}

R ₅ = { G ，H}

R <sub>6 < sub> = { G ，I}

R 7 = { A，B，J ，K} >
R 8 = { C ，L}</sub>






/ strong>我们将所有子模式与相同的LHS相结合。现在我们有 -






S ₁ = { A，B ，C，D，E ，F}

S ₂ = { G ，H，I}

S ₃ = { A，B，J ，K}

S ₄ = { C ，L}





由于上述分解的关系都不包含 R 的键，因此我们需要创建一个附加的关系模式，其中包含由 R 。这是为了确保保留依赖性的无损连接分解。所以我们添加 -





S ₅ = { A，B，G，J }





ABGJ是原始关系的键





这是 3NF <强>。现在检查 BCNF ，我们检查这些关系（S ，S ，S S 的功能依赖 条件的 _{c 超级键 ）。在这种情况下，这些都不会违反 BCNF ，因此也会分解为 BCNF 。}





- 在此示例中，某些步骤的重要性可能不清楚。请查看其他示例此处和在这里。




So I have this set of relation

AB->CDEF

G->H,I

ABJ->K

C->L

How should I decompose this? I am so confused. Am I supposed to find the set of super key first?

解决方案

We can first convert the relation R to 3NF and then to BCNF.

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,F,G,H,I,J,K,L}
FD's = {AB->CDEF,G->HI,ABJ->K,C->L}


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: We write the FD's with singleton RHS. So now we have FD's as {AB->C, AB->D, AB->E, AB->F, G->H, G->I, ABJ->K, C->L}
• No extraneous LHS attribute: We remove the extraneous LHS attribute if any. There are no extraneous LHS attributes here.
• No redundant FD's: We remove the redundant dependencies if any. Now FD's are {AB->C, AB->D, AB->E, AB->F, G->H, G->I, ABJ->K, C->L}

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


R₁={A,B,C}
R₂={A,B,D}
R₃={A,B,E}
R₄={A,B,F}
R₅={G,H}
R₆={G,I}
R₇={A,B,J,K}
R₈={C,L}


Third we combine all sub-schemas with the same LHS. So now we have -


S₁ = {A,B,C,D,E,F}
S₂ = {G,H,I}
S₃ = {A,B,J,K}
S₄ = {C,L}

Since none of the above decomposed relations contain contain a key of R, we need to create an additional relation schema that contains attributes that form of a key of R. This is to ensure lossless join decomposition that preserves dependencies. So we add -

S₅ = {A,B,G,J}

ABGJ is the key of the original relation R

This is in 3NF. Now to check for BCNF we check if any of these relations (S₁,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 - The importance of some of these steps may not be clear in this example. Have a look at other examples here and here.

这篇关于分解为BCNF和超级密钥集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！