Equivalent functional dependencies

dependenciesnormalizationrelations

I cannot understand why F1 is not equivalent to the other sets of dependencies below given the relation R(A,B,C):

  • F1 = {A → B, B → C}

  • F2 = {A → B, A → C}

  • F3 = {A → B, AB → C}

This is question no. 6 in this open exercise from stanford.edu, and the answer provided at the bottom of that page states that F1 is not equivalent. But I do not understand why because I was thinking that it is equivalent to the other sets by virtue of transitivity. I thought B → C in F1 and A → C in F2 are the same since A → B.

Best Answer

the answer provided at the bottom of that page states that F1 is not equivalent.

That is correct. F2 and F3 are equivalent but F1 is not.

F2 is equivalent to F3 because from A → C we can infer that AB → C (therefore F2 => F3) and from A → B, AB → C we can infer: A → AB and then A → C (therefore F3 => F2).

You could also prove that F1 => F2 (and F1 => F3) but not F2 => F1.

A counterexample should convince that there are cases where F2 (A → B, A → C) holds but not F1 (B → C):

 A   B        C
----------------------
 1   Bill     Clinton
 2   Hilary   Clinton
 3   Bill     Murray
Related Question