For the following relations and FDs 1 10 pts Indicate all th

For the following relations and FDs,

1) (10 pts.) Indicate all the 3NF violations

2) (20 pts.) Indicate all the BCNF violations and decompose the relations, as necessary, into collections of relations that are in BCNF.

a. R(A, B, C, D) and FDs: AB->C, C->D, and D->A

b. R(A, B, C, D) and FDs: B->C and B->D

c. R(A, B, C, D) and FDs: AB->C, BC->D, CD->A, and AD->B

d. R(A, B, C, D) and FDs: A->B, B->C, C->D, and D->A

e. R(A, B, C, D, E) and FDs: AB->C, DE->C, and B->D

Solution

1) The 3NF voilations:

Checking whether R is in BCNF or not .

According to Definition:

Relation R is in BCNF iff whenever there is a non trivial FD A1 A2 … An -> B1 B2 … Bn for R { A1 A2 … An } is a superkey.

AB->C: The set closure of AB+ is { A, B, C, D } therefore the left hand side of this FD is a superkey.

C->D: The set closure of C+ is { C, D, A } therefore the left hand side is not a superkey. which shows BCNF Violation here

D-> A: The set closure of D+ is { D, A } therefore the left hand side is not a superkey. BCNF Violation is shown here.

2)

a)

Finding all the keys in this relation by finding the set closures of the combinations of attributes.

A+ = { A }

AB+ = { A,B,C,D }

BC+ = { B,C,D,A }

CD+ = { C,D,A }

B+ = { B }

AC+ = { A,C,D }

BD+ = { B,D,A,C }

C+ = { C,D,A }

AD+ = { A,D }

D+ = { D,A }

Now checking all the FD’s for a violation of the 3NF condition

. AB->C: AB is a superkey, C is prime because it is a member of key BC.

C->D: D is prime because it is a member of key BD.

D->A: A is prime because it is a member of key AB.

hence there is No 3NF violations. which means that No decomposition needed.

b)

Finding all the keys in this relation by finding the set closures of the combinations of attributes.

A+ = { A }

AB+ = { A,B,C,D }

BC+ = { B,C,D }

CD+ = { C,D }

B+ = { B,C,D }

AC+ = { A,C }

BD+ = { B,D }

C+ = { C }

AD+ = { A,D }

D+ = { D }

Now checking all the FD’s for a violation of the 3NF condition.

B->C: B is not a superkey, C is not prime.hence 3NF Violation takes place

B->D: B is not a superkey. D is not prime.which leads to 3NF Violation

Now Decompose on violation B->C. Results to following steps

R1 = { B,C }

and

R2 = { B,A,D }

Now recursively checking for 3NF violations on R2 Finding all the keys in R2 by find the set of closures of the combinations of attributes that exist in R2. The only FD that exists for R2 is B->D.

B+ = { B,D }

BA+ = { B,A,D }

AD+ = { A,D }

A+ = { A }

BD+ = { B,D }

D+ = { D }

Again checking all FD’s for a violation of the 3NF condition. In this case only one FD exists.

B->D: B is not a superkey and D is not prime.

3NF Violation Decompose into two relations:

R2.1 = { B,D } and R2.2 = { B,A }

Answer is as follows:

R1 = { B,C }

R2.1 = { B,D }

R2.2 = { B,A }

Rest all the 3 parts can be done in same way.