CSCI 5333.4 DBMS
Solution to Homework #7

Due date: 11/16 at the beginning of the class.

(1) Proof.

[1] A->BC (given)
[2] A->C (decomposition rule on (1).
[3] AA->AC (augmentation axiom: adding A on [2].
[4] A->AC (simplification of [3])
[5] AC->D (given)
[5] A->D (transitivity axiom on [3] and[5])

Use Armstrong's axioms and rules to prove that

F = {A-> BC, BD->C, AC->D}

implies A->D.

(2)

(a) A+ = ABCD; B+= B; C+ = C and D+ = D.

(b) Only one candidate key: A. Since A+ = ABCD, A is a candidate key. Since A does not appear in the RHS of any FD, A must be a part of any candidate key. Thus, A is not only candidate key.

(c) Prime: A; Non-prime: B,C and D.

(d) {A->BD; BD->C}

(e) 2NF. BD->C violates 3NF as BD is not a superkey and C is not prime. Since all keys are simple, R is in 2NF.

(f) Yes, (R1(A,B,C), {A->BD}) and (R2(B,C,D), {BD->C}

(3) Consider R(A,B,C,D,E,F) with

F= {A->C, CD->B, BC->E, EF->AB, AB->E, AB->F, ABC->D}

(a) A+=AC; B+=B, C+=C, D+=D, E+=E, F+=F and (BC)+=BCE.

(b) We have:

For sets with one attribute:

A+=AC; B+=B, C+=C, D+=D, E+=E, F+=F. Thus, there is no simple candidate key.

For sets with two attribute:s

AB+=ABCDEF. Thus, AB is a candidate key and it is not necessary to consider any proper superset of AB as candidate keys.

AC+=AC;

AD+=ABCDEF. Thus, AD is a candidate key and it is not necessary to consider any proper superset of AD as candidate keys

AE+= ACE

AF+ = ACF

BC+ = BCE

BD+ = BD

BE+ = BE

BF+ = BF

CD+ = BCD

CE+ = CE

CF+ = CF

DE+ = DE

DF+ = DF

EF+ = ABCDEF. Thus, EF is a candidate key and it is not necessary to consider any proper superset of EF as candidate keys

For sets with three attribute:s: we don't need to consider superset of AB, AD and EF.

ACE+ = ACE

ACF+ = ACF

BCD+ = BCDE

BCE+ = BCE

BCF+ ABCDEF. Thus, BCF is a candidate key and it is not necessary to consider any proper superset of BCF as candidate keys

BDE+ = BDE

BDF+ = BDF

CDE+ = BCDE

CDF+ = ABCDEF. Thus, CDF is a candidate key and it is not necessary to consider any proper superset of CDF as candidate keys

For sets with four attribute:s: we don't need to consider superset of AB, AD, EF, BCF and CDF. There is only one such set.

BCDE+ = BCDE

Thus, there are a total of five candidate keys: AB, AD, EF, BCF and CDF. T

(c) All attributes are prime. There is no non-prime attribute.

(d) {A->C, CD->B, BC->E, EF-> AB, AB->DF}

(e) 3NF. Since all attributes are prime, R is in 3NF. On the other hand, A->C is a violation of BCNF since A is not a superky.

(f) Yes:

R1(A,C), {A->C}

R2(B,C,D), {CD->B}

R3(B.C.E), {BC->E}

R4(A,B,D,E,F), {EF-> AB, AB->DEF}

(4) No, there is not enough information to infer whether R is in BCNF or not.

Proof. R1(A,B,C) with {A->B} satisfy the assumption but is not in BCNF. On the other hand, R2(A,B) with {A->B} also satisfy the assumption but is in BCNF.

(5) The maximum case is when there are three candidate keys: A, B and C.

In this case, both the LHS or RHS of a FD in F+ can be one of {A, B, C, AB, AC, BC, ABC}

Thus, the total number of FDs are 7 * 7 or 49.

(6) It is lossless.

A canonical cover of F is {A->B, CD->E, E->AC, BD->CE, AD-> C}

The decomposition of R(A,B,C,D,E) into R1(A,B,C) and R'(B,C,D,E) is lossless since BC->A as BC is the common attributes and A is R1-BC,

The decomposition of R'(B,C,D,E) into R2(B,C,D) and R3(B,D,E) is also lossless since BD->E as BD is the common attributes and E is R3-BD.

Note, however, that the decomposition of R' is harmful as the FD CD-> E is not preserved.

You can also use the algorithm.

Step 1. Create a table of 5 columns (number of columns and 4 rows (number of relations). Populate it with b(i,j).

Step 2. For each relation Ri, set all attribute Aj that appears in Ri from b(i,j) to a(j).

Step 3. For each FD X-> Y, with two rows have the common X values, for every attribute W in Y:

• If one cell is an a and the other cell is an b, change the b to the a.
• If both cells are b's, change them to the same b.

Applying A-> B: no change.

Applying CD -> E: no change.

Applying BC ->A:

Applying BD->CE

Applying ABD->C: no change.

The decomposition is lossless since the second row (R2) conatins all a's.