BCNF分解算法讲解
BCNF decomposition algorithm explanation
我查看了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)。哪里出了问题？或者，更好的算法？
要将关系 R 和一组函数依赖项 (FD's) 转换为 3NF，您可以使用 Bernstein 的综合。应用伯恩斯坦的综合 -
- 首先我们确保给定的
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 属性： 我们可以从
CD->A 和 CD->E 的 LHS 中删除 D，因为 D 是一个这里是无关属性（因为我们可以从 C 得到 D，因为 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 都有自己的子模式。所以现在我们有 - （每个关系的键以粗体显示）
R1={B,G,C}
R2={G,A}
R3={C,E}
R4={C,G}
R5={A,D}
第三我们看看是否有任何子模式可以组合。我们看到R3和R4可以合并，因为它们具有相同的密钥。所以现在我们有 -
S1 = {B,G,C}
S2 = {A,G}
S3 = {C,E,G}
S4 = {A,D}
这在3NF中。现在检查 BCNF 我们检查是否有这些关系 (S1,S2,S 3,S4)违反了BCNF的条件（即对于每个函数依赖X->Y左侧（X）必须一个超级键)。在这种情况下，其中 none 违反了 BCNF 因此它也被分解为 BCNF.
注意我上面最后的答案是(AD,AG,CGE,BCG)。您期望的解决方案是 (AD,AG,CGE,BC) 但这是错误的。此处的最后一个关系 (S1) 也应具有如上所示的 G 属性。
给出输入：R0 与 FD 的 S0 的集合（最小）的关系。
输出：将 R 分解为一组关系，所有这些都在 BCNF 中
算法：
R <- R0，S <- S0
重复直到 R 在 BCNF 中。
如果存在违反 BCNF 条件的 FD X -> Y。
计算 {X}+ ，并选择 {X}+ 作为一个关系作为 R1，并且
另一个 R2 作为 {(R - X + ) U X}
在 R1 和 R2 上映射 FD 集 S（确定 R1 和 R2 上的 FD）。
递归地重复 R1 和 R2 上的算法。
规则：
1.Should是属性保留。
2.Should 无损
3.Should为FD保存
示例：
R(xyz) FD xy -> z; key : xy
z-> y;
求解：
z-> y BCNF 条件为紫色。
所以分解关系R
{z}+= yz;
R1(yz) where key is z
and R2(xz) key is x
我查看了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)。哪里出了问题？或者，更好的算法？
要将关系 R 和一组函数依赖项 (FD's) 转换为 3NF，您可以使用 Bernstein 的综合。应用伯恩斯坦的综合 -
- 首先我们确保给定的
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 属性： 我们可以从
CD->A和CD->E的 LHS 中删除D，因为D是一个这里是无关属性（因为我们可以从C得到D，因为 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 都有自己的子模式。所以现在我们有 - （每个关系的键以粗体显示）
R1={B,G,C}
R2={G,A}
R3={C,E}
R4={C,G}
R5={A,D}
第三我们看看是否有任何子模式可以组合。我们看到R3和R4可以合并，因为它们具有相同的密钥。所以现在我们有 -
S1 = {B,G,C}
S2 = {A,G}
S3 = {C,E,G}
S4 = {A,D}
这在3NF中。现在检查 BCNF 我们检查是否有这些关系 (S1,S2,S 3,S4)违反了BCNF的条件（即对于每个函数依赖X->Y左侧（X）必须一个超级键)。在这种情况下，其中 none 违反了 BCNF 因此它也被分解为 BCNF.
注意我上面最后的答案是(AD,AG,CGE,BCG)。您期望的解决方案是 (AD,AG,CGE,BC) 但这是错误的。此处的最后一个关系 (S1) 也应具有如上所示的 G 属性。
给出输入：R0 与 FD 的 S0 的集合（最小）的关系。
输出：将 R 分解为一组关系，所有这些都在 BCNF 中
算法： R <- R0，S <- S0 重复直到 R 在 BCNF 中。 如果存在违反 BCNF 条件的 FD X -> Y。 计算 {X}+ ，并选择 {X}+ 作为一个关系作为 R1，并且 另一个 R2 作为 {(R - X + ) U X} 在 R1 和 R2 上映射 FD 集 S（确定 R1 和 R2 上的 FD）。 递归地重复 R1 和 R2 上的算法。
规则： 1.Should是属性保留。 2.Should 无损 3.Should为FD保存
示例：
R(xyz) FD xy -> z; key : xy
z-> y;
求解： z-> y BCNF 条件为紫色。
所以分解关系R
{z}+= yz;
R1(yz) where key is z
and R2(xz) key is x