Graded Homework1 COSC 6340 (Spring 2004)
Normalization and Theory of the Relational Data Model


Due date: Th., March 25, in class
last updated: Th, March 4, 8a
Look at 6340-homepage for further instructions or clarifications

Problem1 (taken from the Stanford Website) [8]
Consider a relation R(a,b,c,d,e) with FD's:
ab->c, bc->d, e->bd, d->b, and cd->e

(a)
Find all the candidate keys for R.

(b)
How many superkeys are there (including the keys)? Explain your reasoning for partial credit.

(c)
Which of the given FD's violates BCNF?

Problem 2 [18]
Assume we have a relation R(A,B,C,D,E, F) with the following dependencies:

(1)	AB -> CDEF 
(2)	C -> ABDEF
(3)	E ->->  BC 

Answer the following questions giving reasons for your answers:


a)	Is R in 4th normal form? [1]

b)	Is it possible to decompose R into R1 (A, B, D, E) and R2 (C, E, F) 
without loss of information? [3]

c)	Does C ->->  BDEF hold for R? [1]

d)	Does E ->->  D hold for R? [5]

e)	Does E -> A hold for R? [5] 

f)	Is R in BCNF? [3]
In the case that a dependency does not hold, give a counter example that satisfies (1), (2), (3) but violates the dependency in question.

Problem 3 [9]

R(A,B,C,D,E) is given with (1) A->->B and (2) A->->C.
a) Does A->->BC hold for R(prove it using the inference rules or give
a counter example!)? [6]
b) Assume that R contains (a,b1,c1,d1,e1), (a,b1,c2,d2,e2) and (a,b3,c2,d3,e3). What other tuples must R contain (due to the two MVD's)? [3]

Problem 4 [7]

R(A,B,C,D,E,F) is given with: (1) AB->C (2)C->AB (3)EF->C.
Transform R into a relational schema that is in BCNF and does not have any lost functional dependencies!