证明分解成 3 个关系是无损的

Question

给定具有属性集 R 和依赖集 F 的关系方案：

R = (ABCD) F = {AB -> C, B -> D; C -> A}

函数依赖 B -> D 违反了 BCNF，因为 B 不是超键，所以我通过使用此算法将其分解为 3 个关系来转换 BCNF 中的关系：

Given a schema R.

    Compute keys for R.
    Repeat until all relations are in BCNF.
        Pick any R' having a F.D A --> B that violates BCNF.
        Decompose R' into R1(A,B) and R2(A,Rest of attributes).
        Compute F.D's for R1 and R2.
        Compute keys for R1 and R2.

我得到的结果（我检查了可用的解决方案是正确的）是：

R1:(BD), R2:(CA), R3:(BC).

我知道一个属性的转换算法是分解保留数据，我想证明一下作为练习。

通常分解为两个关系 R1 和 R2 的过程是：检查 R1 和 R2 之间的共同属性，对找到的结果进行闭包，如果闭包包含 R1 或 R2 的所有属性R2则分解保留数据，否则不保留。

在这个练习的情况下，R1、R2 和 R3 之间没有共同的属性，所以我不能做闭包来确定分解是否保留数据，我不知道我还能怎么办可以继续。怎么证明分解是无损的？

Answer 1

为了证明分解是无损的，您可以按照分解算法的步骤分两步进行。

从您的模式开始，让我们应用算法的第一步。

(1) R = (ABCD) F = {AB -> C, B -> D; C -> A}

考虑到 B -> D 违反了 BCNF（因为候选键是 AB 和 BC），我们将 R 分解为：

(2) R1 = (BD), F1 = {B -> D} and R2 = {ABC}, F2 = {C -> A, AB -> C}

这里我们可以证明R1和R2是无损分解，因为它们的交集是{B}，它是F1的候选键（根据你引用的定理）。

现在，由于C -> A，R2不在BCNF中，根据算法我们必须在R3 = (CA)和R4 = (CB)中分解R2，所以最终分解为{R1 = (BD), R3 = (CA), R4 = (CB)}。为了证明 R 的分解是无损的，我们可以使用另一个定理：

If ρ = {R₁,..., R_m} is a lossless decomposition of R<T,F> (where T are the attributes of R and F are a cover of the dependencies of R), and σ = {S₁, S₂} a lossless decomposition of R₁ with respect to π_(T₁)(F), then the decomposition {S₁, S₂, R₂, ..., R_m) is lossless with respect to F.

在定理中，π_(T₁)(F)是依赖F在属性T[=上的投影37=]1 的 R₁.

在这种情况下，我们分解 R2(ABC) 和 π_(T₂)(F) = {C -> A , AB -> C}，因此可以应用该定理，因为 R3 和 R4 是关于这些依赖项的无损分解。

证明分解成 3 个关系是无损的

Proof that a decomposition into 3 relations is lossless

database-normalization

decomposition