Consider the set of attributes R ABCDEF and the FD set X A

Consider the set of attributes R = {ABCDEF}, and the FD set X = {AB C, AC B, AD E, B D, BC A, E F}. For each of the following decompositions, check if it is dependency-preserving and satisfies the lossless-join property and determine the normal form for each relation: (a) {AB, BC, ABDE, EF}, (b) {ABC, ACDE, ADF}.

Solution

(a)

The decomposition. { AB, BC, ABDE, EF } is not lossless. To prove this consider the following instance of R: {(a1, b, c1, d1, e1, g1), (a2, b, c2, d2, e2, g2)}

Because of the functional dependencies BC A and AB C, a1 _= a2 if and only if c1 _= c2.

It is easy to that the join AB __ BC contains 4 tuples:

{(a1, b, c1), (a1, b, c2), (a2, b, c1), (a2, b, c2)}

So the join of AB, BC, ABDE and EF will contain at least 4 tuples, (actually it contains 8 tuples)

so we have a lossy decomposition here. This decomposition does not preserve the FD, AB C (or AC B)

(b)

The decomposition {ABC, ACDE, ADF } is lossless.

Intuitively, this is because the join of ABC, ACDE and ADF can be constructed in two steps;

first construct the join of ABC and ACDE: this is lossless because their (attribute) intersection is AC which is a key for ABCDE (in fact ABCDEF) so this is lossless. Now join this intermediate join with ADF. This is also lossless because the attribute intersection is is AD and AD ADF. So by the test mentioned in the text this step is also a lossless decomposition. The projection of the FD’s of R onto ABC gives us: AB C, AC B and BC A. The projection of the FD’s of R onto ACDE gives us: AD E and The projection of the FD’s of R onto ADF gives us: AD F (by transitivity) The closure of this set of dependencies does not contain E F nor does it contain

B D. So this decomposition is not dependency preserving.