将关系分解为BCNF [英] Decomposing a relation into BCNF

问题描述

我在确定关系何时处于Boyce-Codd范式以及如何将其分解为BCNF时遇到麻烦。给出以下示例：

I'm having trouble establishing when a relation is in Boyce-Codd Normal Form and how to decompose it info BCNF if it is not. Given this example:

R（A，C，B，D，E）具有功能依赖性：A-> B，C-> D

R(A, C, B, D, E) with functional dependencies: A -> B, C -> D

如何分解？

我采取的步骤是：

A+ = AB  
C+ = CD  
R1 = A+ = **AB**  
R2 = ACDE (since elements of C+ still exist, continue decomposing)  
R3 = C+ = **CD**  

R4 = ACE （此关系中没有FD闭包）

R4 = ACE (no FD closures reside in this relation)

所以我现在知道ACE将构成整个关系，但是分解的答案是：AB，CD，ACE。

So now I know that ACE will compose the whole relation, but the answer for the decomposition is: AB, CD, ACE.

我想我正在努力将关系正确地分解为BCNF形式，以及如何知道何时完成。真的很感谢能解决这些问题的所有能引导我进行思考的人。谢谢！

I suppose I'm struggling with how to properly decompose a relation into BCNF form and how to tell when you're done. Would really appreciate anyone who can walk me through their thought process when solving these problems. Thanks!

推荐答案

尽管这个问题很旧，但其他问题/答案似乎并没有提供一个很明确的步骤确定和分解与BCNF的关系的一般步骤。

Although the question is old, the other questions/answers don't seem to provide a very clear step-by-step general answer on determining and decomposing relations to BCNF.

1。确定BCNF：

为了使关系R处于BCNF中，R中保存的所有功能依赖项（FD）都需要满足以下性质：行列式X都是R的超键。即，如果X -> Y在R中成立，那么X必须是R的超键才能在BCNF中。

1. Determine BCNF:
For relation R to be in BCNF, all the functional dependencies (FDs) that hold in R need to satisfy property that the determinants X are all superkeys of R. i.e. if X->Y holds in R, then X must be a superkey of R to be in BCNF.

在您的情况下，可以证明唯一的候选键（最小超键）是ACE。
因此，两个FD：A-> B和C-> D都违反了BCNF，因为A和C都不是超键或R。

In your case, it can be shown that the only candidate key (minimal superkey) is ACE. Thus both FDs: A->B and C->D are violating BCNF as both A and C are not superkeys or R.

2 。将R分解为BCNF形式：

如果R不在BCNF中，我们将R分解为一组在BCNF中的关系S。

这可以通过完成一个非常简单的算法：

2. Decompose R into BCNF form:
If R is not in BCNF, we decompose R into a set of relations S that are in BCNF.
This can be accomplished with a very simple algorithm:

Initialize S = {R}
While S has a relation R' that is not in BCNF do:   
   Pick a FD: X->Y that holds in R' and violates BCNF
   Add the relation XY to S
   Update R' = R'-Y
Return S

在您的情况下，迭代步骤如下：

In your case, the iterative steps are as follows:

S = {ABCDE}       // Intialization S = {R}
S = {ACDE, AB}    // Pick FD: A->B which violates BCNF
S = {ACE, AB, CD} // Pick FD: C->D which violates BCNF
// Return S as all relations are in BCNF

因此，R（A，B，C，D，E）分解为一组关系：R1（A，C， E），满足BCNF的R2（A，B）和R3（C，D）。

Thus, R(A,B,C,D,E) is decomposed into a set of relations: R1(A,C,E), R2(A,B) and R3(C,D) that satisfies BCNF.

还请注意，在这种情况下，保留了功能依赖性，但将其标准化为BCNF不保证这一点。

Note also that in this case, functional dependency is preserved but normalization to BCNF does not guarantee this.

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