database - BCNF分解和数据库的无损联接

Question

嘿，我所有的作业都说:

令R(ABCD)为具有功能依赖性的关系
A→B，C→D，AD→C，BC→A
R中的无损连接分解为Boyce-Codd范式(BCNF)？

我一直在研究和观看youtube上的视频，但似乎找不到如何启动它的方法。我认为我应该将其分解为子方案，然后填写表格以查找哪个是无损的，但是我在开始时遇到了麻烦。任何帮助，将不胜感激!

Answer 1

你的问题

Which of the following is a lossless-join decomposition of R into Boyce-Codd Normal Form (BCNF)?

建议您具有一组选项，并且必须选择其中的一个是无损分解，但是由于您没有提到这些选项，因此我首先将( PART A )将关系分解为BCNF(首先分解为3NF，然后分解为BCNF)然后( PART B )说明了如何检查给定的分解是否是无损联接分解。如果您只是想知道如何检查给定的BCNF分解是否无损，请直接跳到我答案的B部分。

零件A

要将关系R和一组功能依赖项(FD's)转换为3NF，可以使用 Bernstein的Synthesis 。应用伯恩斯坦综合-

首先，我们确保给定的FD's组为最小覆盖率

第二个我们采用每个FD并将其设为自己的子模式。

第三个，我们尝试将这些子方案

合并

例如，您的情况下的:

R = {A，B，C，D}
FD = {A-> B，C-> D，AD-> C，BC-> A}

首先，我们检查FD's是否为最小覆盖范围(单例右侧，无多余左侧属性，无冗余FD)

Singleton RHS:所有给定的FD已经具有Singleton RHS。

没有无关紧要的LHS属性:FD都没有要删除的无关紧要的LHS属性。

没有冗余FD:没有冗余FD。

因此，给定的FD集已经很小。

第二个，我们使每个FD都有自己的子模式。现在我们有了-(每个关系的键都以粗体显示)

R1 = { A，D ，C}
R2 = { B，C ，A}
R3 = { C ，D}
R4 = { A ，B}

第三个，我们查看是否可以组合任何子方案。我们看到 R1 和 R2 已经具有R的所有属性，因此可以省略R3和R4。所以现在我们有-

S1 = {A，D，C}
S2 = {B，C，A}

这在 3NF 中。现在检查 BCNF 是否为 BCNF 的条件(即对于 BCNF (即对于的每个功能依赖项X->Y而言，左侧(X))的 super 键必须为 )。在这种情况下，这些都不违反 BCNF ，因此也将其分解为 BCNF 。

PART B

当您如上所述应用Bernstein Synthesis分解R时，分解始终是依赖项保留。现在的问题是，分解是否无损？要检查是否可以遵循以下方法:

创建一个如图1所示的表，其行数等于分解后的关系数，而列数等于我们原始给定R中的属性数。



如图1所示，我们在各自分解关系中存在的所有属性中都添加和。现在，我们遍历所有FD的{C-> D，A-> B，AD-> C，BC-> A}一步一步地添加和。例如，第一个FD是C-> D。由于C列中的两行都具有和，并且D列的第二行中有一个空插槽，因此我们如图所示，在其中放置了和。一旦其中一行完全用和填充，我们就会停止，这表明这是无损分解。如果我们遍历所有FD，并且表的所有行都没有完全用和填充，那么这是有损分解。

另外，请注意，如果这是有损分解，则可以通过在由主键的所有属性组成的一组分解关系中添加一个以上的关系来始终使其无损。

我建议您查看this视频，以获取有关此方法的更多示例。还other way检查涉及关系代数的无损联接分解。