Dependency preserving decomposition

Question

Let be the following relational scheme:

F={AB → C; AC → B; AD → E; B → D; BC → A;E → G}

Is the following decomposition without loss of dependency?

R¹=(A,B),R²=(B,C),R³=(A,B,D,E),R⁴=(E,G)

Looking then at their closures:

[AB]⁺={A,B,C,D,E,G}

[BC]⁺={B,C,A,D,E,G}

The teacher then did something about closures I don't perfectly understand:

F¹⁺=∅

F²⁺=∅

F³⁺={AD → E, B → D, AB → D,AB → E}

I know that F⁺={X → Y\F⊨X → Y}

and that [X]⁺= {A\F⊨X → A}

Then she did:

[AB]⁺⇔ AB → C; AB → D; AB → E; AB → G

[AB]⁺ ∪ F³⁺={A,B,D,E,G}, C isn't in [AB]⁺ ∪ F³⁺

Therefore it isn't a dependency preserving decomposition

Can you help me understand why?

Answer 1

The last two lines are an abbreviated way of solving the problem without recurring to the complete algorithm to check for dependency preservation. In particular the teacher noted that combining the dependencies that you can obtain from R₁ and R₃ you cannot obtain C, which is essential to get A in the dependency BC → A. This dependency can never be derived by the projection of F over the decomposed relations.

Here follows the complete explanation.

To check if a decomposition preserves the dependencies, one can use the Ullman algorithm that checks, for each dependency X → Y in F, if Y is contained in the closure of X with respect to the projection of F over the decomposition (formally, calling G the union of the projection of the dependencies over the decomposed relations R_i, that is G = ∪π_Ri(F), the algorithm checks if X → Y ∈ G⁺, the closure of G, by checking that Y ⊆ X⁺_G).

So, we must calculate X⁺_G for each dependency of F, to check if Y is contained in it.

Such a closure is computed with the following algorithm.

1. Initialize X⁺_G with X,
2. at each step, for each relation R_i, add to X⁺_G the attributes obtained by calculating the closure of the attributes of X⁺_G ∩ R_i with respect to F, and projecting the result again on R_i. In symbol: X⁺_G := X⁺_G ∪ ((X⁺_G ∩ R_i)⁺_F ∩ R_i)
3. repeat 2 while X⁺_G changes.

Let’s try it for the dependency BC → A.

Initially:

BC⁺_G = BC,

using R₁(AB), BC ∩ AB = B, B⁺_F = BD, so intersecting it with AB gives B, which is already in BC⁺_G;

using R₂(BC), BC ∩ BC = BC, BC⁺_F = ABCDEG, so intersecting it with BC gives BC which is already in BC⁺_G;

using R₃(ABDE), BC ∩ ABDE = B, B⁺_F = BD, so intersecting it with ABDE we obtain BD and we can add D to BC⁺_G, which now becomes BCD;

BC⁺_G is changed, so we must restart checking for the new value BCD. The first two relations do not give any contribute, since D is not present in them. The third one must be considered again:

using R₃(ABDE), BCD ∩ ABDE = BD, BD⁺_F = BD, we can not add anything;

using R₄(EG), BCD ∩ EG = ∅, nothing to add again.

So we have terminated, beacause no new attribute can be added to the closure, and since BC⁺_G = BCD does not contain A, we can conclude that at least this dependency is not preserved, and so that the decomposition does not preserve the dependencies.

And since you asked how to decompose a relation without losing dependencies, you can look at the synthesis algorithm to decompose a relation in Third Normal Form (3NF). You can find it on any good book on databases, and it guarantees to preserve both the dependencies as well as the data (lossless decomposition), while reducing redundancies and anomalies.

In this case a decomposition in 3NF is the following:

R₁ < (ADE) , { AD → E } >

R₂ < (BD) , { B → D } >

R₃ < (ABC) , { BC → A, AC → B, AB → C } >

R₄ < (EG) , { E → G } >

Answer 2

I'd better say
F¹⁺=∅

F²⁺=∅

F³⁺={AD → E, B → D, AB → D,AB → E}

F⁴⁺={E → G}

and

(F¹⁺ U F²⁺ U F³⁺ U F⁴⁺ ) != F