University of Toronto CSC343 Winter 2021
In-class Exercises: Functional Dependencies
Suppose we have a relation R with attributes ABCD
1. What an FD means. Suppose the functional dependency BC → D holds in R. Create an instance of R that violates
this FD.
Solution:
In order to violate this FD, we need two tuples with the same value for B and the same value for C (both!), yet different values for D.
ABCD 1364 2365
2. Equivalent sets of FDs.
(a) Are the sets A → BC and A → B, A → C equivalent? If yes, explain why. If no, construct an instance of R that
satisfies one set of FDs but not the other.
Solution:
These are equivalent — there is no instance of the relation that satisfies one but not the other. This can be proven, and now that you know the closure test, the proof is very concise:
• Assume that A → BC.
– Under this assumption, A+ = ABC. – ThereforeA→B,andA→C.
• AssumethatA→B,andA→C.
– Under this assumption, A+ = ABC. – Therefore A → BC.
• Therefore each set of FDs follows from the other. They are equivalent.
In fact we can always “split the RHS” of an FD. Review the definition of an FD to see why this makes sense.
(b) Are the sets P Q → R and P → R, Q → R equivalent? If yes, explain why. If no, construct an instance of R that satisfies one set of FDs but not the other.
Solution:
These are not equivalent, as demonstrated by the same instance. It satisfies P Q → R but not P → R, Q → R:
PQR 124 325
We can never split the LHS of an FD. Again, the definition of FD makes clear why.
(c) Are the sets P Q → R and P → Q, P → R equivalent? If yes, explain why. If no, construct an instance of R that satisfies one set of FDs but not the other.
Solution:
These are not equivalent, as demonstrated by this instance that satisfies P Q → R but not P → Q, P → R:
PQR 124 189
3. Keys and FDs.
(a) We claimed that if a set of attributes K functionally determines all attributes, K must be a superkey (i.e., no two tuples can agree on all attributes in K). Do you believe this? Suppose these FDs hold in R: A → BC, C → D.
Does A functionally determine all attributes of R? Can two tuples agree on A? Solution:
This is left as an exercise to explore on your own, in order to build your intuition.
(b) We also said that if K is a superkey (i.e., no two tuples can agree on all attributes in K) K must functionally determine all attributes. Do you believe this? Suppose A is a superkey of R Does A functionally determine all attributes of R?
Solution:
Again, this is left as an intuition-building exercise.
4. Does an FD follow from a set of FDs? Suppose we have a relation on attributes ABCDEF with these FDs: AC →F,CEF →B,C →D,DC →A
(a) Does it follow that C → F?
(b) Does it follow that ACD → B?
Solution:
We use the closure test to check whether an FD follow from a set of FDs. C+ = CDAF . Therefore, C → F does follow.
ACD+ = ACDF. Therefore, ACD → B does not follow.
5. Projecting a set of FDs onto a subset of the attributes. Suppose we have a relation on attributes ABCDE with these FDs:
(a) Project the FDs onto attributes ABC.
Solution:
A→C, C→E, E→BD
To project onto a set of attributes, we systematically consider every possible LHS of an FD that might hold on those attributes.
• A+ = ACEBD, therefore A → BC. (It also functionally determines DE, but these are not in our set of attributes. And it functionally determines itself, but we don’t need to write down dependencies that are tautologies.)
• B+ = B. This yields no FDs for our set of attributes.
• C+ = CEBD, therfore C → B.
• We don’t need to consider any supersets of A. A already determines all of our attributes ABC, so supersets
of A will be only yield FDs that already follow from A → BC.
• The only remaining subset of the attributes ABC to consider is BC. BC+ = BCED. This yields no FDs for
our set of attributes. •SotheprojectionoftheFDsontoABCis:{A→BC, C→B}.
(b) Project the FDs onto attributes ADE.
Solution:
• A+ = ACEBD, therefore A → DE.
• D+ = D. This yields no non-trivial FDs..
• E+ = EBD, therfore E → D.
• Again, we don’t need to consider any supersets of A, since A determines all the attributes ADE also.
• The only remaining subset of the attributes ABC to consider is DE. DE+ = DEB. This yields no FDs for
our set of attributes. •SotheprojectionoftheFDsontoADEis:{A→DE, E→D}.