2

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?

1
  • @ypercubeᵀᴹ Thank you for your interest! I think it's rather C. And I don't understand [AB]⁺ ∪ F³⁺ neither. Yet I've updated the definitions, maybe it helps... Commented May 8, 2016 at 21:22

2 Answers 2

4
+50

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 R1 and R3 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 Ri, 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 Ri, add to X+G the attributes obtained by calculating the closure of the attributes of X+G ∩ Ri with respect to F, and projecting the result again on Ri. In symbol: X+G := X+G ∪ ((X+G ∩ Ri)+F ∩ Ri)
  3. repeat 2 while X+G changes.

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

Initially:

BC+G = BC,

using R1(AB), BC ∩ AB = B, B+F = BD, so intersecting it with AB gives B, which is already in BC+G;

using R2(BC), BC ∩ BC = BC, BC+F = ABCDEG, so intersecting it with BC gives BC which is already in BC+G;

using R3(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 R3(ABDE), BCD ∩ ABDE = BD, BD+F = BD, we can not add anything;

using R4(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:

R1 < (ADE) , { AD → E } >

R2 < (BD) , { B → D } >

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

R4 < (EG) , { E → G } >

1

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

1
  • 1
    But why does F¹⁺=∅, F²⁺=∅ whereas F³⁺={AD → E, B → D, AB → D,AB → E} Shouldn't we have F¹⁺={AB → C} at least and even {AB → C, BC → A} through transitivity? Commented May 9, 2016 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.