CSCI 5333 DBMS
Spring 2020
Solution to Homework #8

(1) F = {A->B, CD->E, AC->D, E->F}

implies AC-> F

Proof.

[1] AC-> D (given)
[2] CD-> E (given)
[3] ACC-> E (pseudo-transitivity on [1] and [2])
[4] AC -> E ( simplification of [3]
[5] E->F (given)
[5] AC -> F (transitivity on [4] and [5])

QED

(2) F = {RS->PQ, QR->S, S->P, U->ST, STU->R, Q->U}

(a)

P+=P
Q+= PQRSTU
R+ = R
S+ = SP
T+ = T
U+ + PQRSTU

(b) CK: Q, RS and U.

(c) Prime: QRSU; non-prime: PT

(d) Canonical Cover: {RS-> Q, Q->RSTU, S-> P, U->Q}, or {RS-> Q, Q->RU, S-> P, U->QST}

(e) The decompoistion into R1(Q,R,S,T,U) {RS-> Q, Q->RSTU, S-> P, U->Q} and R2(P,S) {S-> P} are lossless and FD preserving. R1 and R2 are in BCNF. Durther decomposition of R1(Q,R,S,T,U) is also acceptable but not preferrable.

(3) R(A, B, C, D, E) with F = {A->BCE, BC->D, AB->E, DE->C, AE->CD}:

(a) A+=ABCDE, B+=B, C+= C, D+=D, E+=E

(b) The candidate key is A

(c) Prime: A, non-prime: BCDE

(d) {A->BCE, BC->D, DE->C} or {A->BDE, BC->D, DE->C}

(e) 2NF since BC->D violates 3NF: D is non-prime and BC is not a superkey. DE->C is also a violation.

(f) Yes, the decomposition to R1(A,B,C,E) {A->BCE}, R2(B,C,D) {BC->D} and R3(C,D,E) {DE->C} satisfy the requirement.

(4)

(a) A relation R(A,B,C) can only have one minimal cover.

False. R(A,B,C) may have {A->B, B->A, A->C} and {A->B, B->A, B->C} both as its minimal covers.

(b) If R(A,B,C) is in 2NF and has only one simple candidate key, it is also in 3NF.

False R(A,B,C) {A->B, B->C} is in 2NF and has only one simple candidate key. However, it is not in 3NF.

(c) For R(A,B,C,D), it is known that AB and BC are candidate keys (and there may be others). It is possible that R may have 12 superkyes.

True. It is possible that R(A,B,C,D) has four CK: AB, BC, AC, and D. It has 12 CK.

(d) If R(A,B,C) is in 3NF, it is also in BCNF.

False. R with {A->B, BC->A} is in 3NF but not in BCNF.

(5) Minimum: 9, e.g. ACDE is the other candidate key.

Maximum: 20, e.g. C is the other candidate key.

(6) R(A,B,C,D,E) {A->C, BC->D, AC->D, BD->E} The decomposition into R1(A,C,D), R2(B,C,D) and R3(B,D,E) is lossy.

We start by obtaining a canonical cover of F:

{A->CD, BC->D, BD->E}

Using the chase matrix algorithm:

We use the canonical form: {A->CD, BC->D, BD->E}

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. While changes can be made with a FD X-> Y, with two rows in the table having the common X values in the following manner:

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->CD, no change.

Applying BC->D, no change.

Applying BD->E

Applying A->CD, no change.

Applying BC->D, no change.

Since no more changes are possible, the algorithm halts and declares that the decomposition is lossy as there is no row with entirely a's.