Alan K. Dippel
CSC 570/671
November 9,1998
Professor: Fred Sadri

University of North Carolina at Greensboro
Department of Mathematical Sciences
Assignment 5

http://www.cs.indiana.edu/~adippel/csc671/assignment5.htm


Question 1 (25%)

Consider the relational scheme

Library = { branch, address, isbn, title, author, publisher, copyNo }
with the following FDs

branch à address
isbn à title, publisher

(a) (5%) find all candidate keys of library. Show your work.

 

F = {branch à address; isbn à title, publisher }

Solving for canonical cover

{isbn}+ = {isbn, title, publisher},

F1 = {branch à address; branch à publisher }
testing to see if title is extraneous {isbn}+(wrt F1) = {isbn, publisher}, title is not extraneous,

F2 = {branch à address; branch à title }
testing to see if publisher is extraneous {isbn}+(wrt F2) = {isbn, title}, publisher is not extraneous,

therefore Fc = F.

R = {branch, address, isbn, title, author, publisher, copyNo}

Fc = {branch à address, isbn à title, publisher}

Looking at the right sides of the Functional Dependencies we see that the missing fields are branch, isbn, author, copyNo.

Checking to see if this is a candidate key.

{branch, isbn, author, copyNo}+ = {branch, address, isbn, title, author, publisher, copyNo} = R

Since this is a candidate key for Library and it has been proven that if the attributes that are missing on the right side of the Functional dependencies are in the key then only one unique candidate key exists, the following is true:

Candidate Key = {branch, isbn, author, copyNo}

 

(b) (10%) Give a lossless and dependency preserving decomposition of library into 3NF relations. Show your work

R is not in 3NF since the Functional dependencies are not all trivial. The canonical cover of the relations is Fc. We can decompose the table into three tables using the attributes of Fc and the candidate key per the 3NF algorithm. The candidate key must be used since it is not contained on the left side of the FDs.

Fc = {branch à address, isbn à title, publisher}
Candidate Key = {branch, isbn, author, copyNo}

R1 = {branch, address}
R2 = {isbn, title, publisher}
R3 = {branch, isdn, author, copyNo}

 

(c) (5%) For each scheme in your decomposition of part (b), determine whether it is in BCNF or not. Show your work.

R1 = {branch, address}
F1 = {branch à address}

{branch}+ = {branch,address} OK branch is a superkey of R1.

R2 = {isbn, title, publisher}
F2 = {isbn à title, publisher}

{isbn}+ = {isbn, title, publisher} OK isbn is a superkey of R2.

R3 = {branch, isdn, author, copyNo}
F3 = {} OK since all functional dependencies are trivial.

(d) (5%) Do any of the 3NF relation schemes in your decomposition of part (b) have the possibility of having redundancy in their data (instances)? If so, give examples that demonstrate redundancies.

No, if the 3NF algorithm is used to decompose a relation and the relations are also BCNF it has been proven there will be no redundancy in the data.

Question 2. (25%)

Consider the relation scheme

R = {A, B, C, D, E, F, G, H }
With the FDs
A à BC
ABE à CDGH
C à GD
D à G
E à F

(a) (15%) find a canonical cover of the given set of FDs. Show your work.

R = {A, B, C, D, E, F, G, H}

F = {
A à BC
ABE à CDGH
C à GD
D à G
E à F }

There are no duplicates on the left side of the FDs, therefore we start eliminating extraneous attributes.

Eliminating B in ABE à CDGH

F1 = {
A à BC
AE à CDGH
C à GD
D à G
E à F } ABE+(wrt F) = {A, B, E, C, D, G, H, F}; ABE+(wrt F1) = {A, E, C, D, G, H, F, B} , therefore B is Extraneous on the left.

There are no more extraneous attributes on the left.

Eliminating C in A à BC

F2 = {
A à B
AE à CDGH
C à GD
D à G
E à F } A+(wrt F) = {A, B, C, G, D}; A+(wrt F2) = {A, B} , therefore C is not extraneous on the right.

Eliminating B in A à BC

F3 = {
A à C
AE à CDGH
C à GD
D à G
E à F } A+(wrt F) = {A, B, C, G, D}; A+(wrt F3) = {A, C, G, D} , therefore B is not extraneous on the right.

Eliminating C in AE à CDGH

F4 = {
A à BC
AE à DGH
C à GD
D à G
E à F } AE+(wrt F) = {A, B, E, C, D, G, H, F}; AE+(wrt F4) = {A, E, D, G, H, F, B, C} , therefore C is extraneous on the right.

Eliminating D in AE à DGH

F5 = {
A à BC
AE à GH
C à GD
D à G
E à F } AE+(wrt F) = {A, B, E, C, D, G, H, F}; AE+(wrt F5) = {A, E, G, H, F, B, C, D} , therefore D is extraneous on the right.

Eliminating G in AE à GH

F6 = {
A à BC
AE à H
C à GD
D à G
E à F } AE+(wrt F) = {A, B, E, C, D, G, H, F}; ABE+(wrt F6) = {A, B, E, H, F,C, G, D} , therefore G is extraneous on the right.

Eliminating G in C à GD

F7 = {
A à BC
AE à H
C à D
D à G
E à F } C+(wrt F) = {C, G, D}; C+(wrt F7) = {C,D,G} , therefore C is extraneous on the right.

Fc = F7 = {
A à BC
AE à H
C à D
D à G
E à F }

(b) (5%) find all candidate keys of R. Show your work.

Looking at the FDs in Fc we see that the following attributes are missing from the right:

{A, E }
Testing this for a candidate key we find that {A, E }+ = {A, E, B, C, H, D, G, F } therefore {A,E } is a candidate key and is a unique one as proven in the text.

(c) (5%) Give a lossless and dependency preserving decomposition of R into 3NF relations. Show your work.

Using the 3NF algorithm, start by taking the attributes of the Functional dependencies in Fc , we get the following relations.

R1 = {A, B, C }
R2 = {A, E, H }
R3 = {C, D }
R4 = {D, G }
R5 = {E, F }
These are all of the relations since the candidate key is contained within one of the relations.

Question 3. (20%)

(a) Consider the following relation instance r. For each of the FDs f listed below, determine if r satisfies f. Justify your answers.

A

B

C

D

a1
a2
a1
a2

b1
b2
b2
b1

c1
c2
c2
c2

d1
d1
d2
d1

(a1) (5%) A à D

r violates A à D, the first and third tuples {a1, b1, c1, d1 } and {a1, b2, c2, d2 } have a different d attribute for the same a attribute. NOT OK

(a2) (5%) AB à D

r satisfies f since all the {a, b} attribute pairs are different. OK

(a3) (5%) AC à D

r, satisfies f since the only {a, c} pairs that are equal have the same {d} attribute,
{a2, b2 c2, d1} and {a2, b1, c2, d1} OK

(b) (5%) Write a relation instance with two tuples on the scheme R = {E, F, G, H } that satisfies EF à H and FG à H but violates F à H. Justify that your relation instance satisfies the first two FDs and violates the third.

E

F

G

H

E1
E2

F1
F1

G1
G2

H1
H2

 

{ E1, F1 à H1; E2, F1 à H2 } satisfies the first FD
{ F1, G1 à H1; F1, G2 à H2 } satisfies the second FD
{ F1 à H1; F1 à H2 } violates the third FD

Question 4. (30%)

(a) (6%) List the 3 conditions that a "good decomposition" should have.

  1. Each relation scheme is "good".
  2. the decomposition is lossless.
  3. the decomposition is dependency preserving.

(b) (24%)  Given R = {A, B, C, D }, and the set of FDs A à BC, B à D evaluate each of the following decomposition's with respect to its "goodness" (i.e. with respect to the 3 conditions)

(b1) R1 = {A, B, C }, R2 = {A, D }.

Relations are "good" (i.e. no redundancy of data since R1 has all the attributes of the first FD and the second relation has only trivial dependencies)
The decomposition has all of the attributes and is lossless.
The decomposition is NOT dependency preserving, since the B à D dependency is not used.

(b2) R1 = {A, B, C }, R2 = {B, D }.

Relations are "good"
The decomposition has all of the attributes and is lossless.
The decomposition is dependency preserving, since the A à BC, B à D dependencies are there.

(b3) R1 = {A, B, C }, R2 = {C, D }.

Relations are NOT "good" since C à D is not implied by the FDs.
The decomposition has all of the attributes and is lossless.
The decomposition is NOT dependency preserving, since the B à D dependency is not used.

(b4) R1 = {A, B, D }, R2 = {A, C }.

Relations are NOT "good", since AB à D is not implied by the FDs.
The decomposition has all of the attributes and is lossless.
The decomposition is NOT dependency preserving, since the AB à C and B à D dependencies are not used.

http://www.uncg.edu/~akdippel/csc671/assignment5.htm