University of Toronto CSC343 Winter 2021
In-class Exercises: Projection and Minimal Basis
1.SupposewehavetheseFDs::S={ABE→CF, DF→BD, C→DF, E→A, AF→B} Project the FDs onto: L = CDEF
Attributes to take all subsets X of: Closure of the subset
C D
Solution:
E F X+
Functional dependencies inferred
C
D
E
F
closure
FDs
C+ =CDFB
D+ = D
C → DF
E+ = EA
nothing
nothing
F+ =F
CD+ =CDFB
nothing
CE+ =CEDFAB
nothing, since CD → DF is weaker than C → DF which we have already
nothing, since CE → DF is weaker than C → DF which we have already
CF+ =CFDB
nothing, since CF → D is weaker than C → DF which we have already
DE+ = DEA
DF+ =DFB
nothing
nothing
EF+ =EFABCD
EF → CD
CDE+ = CDEF
CDF+ =CDFB
nothing, since CDE → F is weaker than C → DF which we have already
nothing
since EF is a key, supersets of EF can only yield FDs that are weaker than ones we have.
since EF is a key, supersets of EF can only yield FDs that are weaker than ones we have.
Final answer: The projection of S onto L is C → DF, EF → CD.
2.FindaminimalbasisforthissetofFDs:S={ABF→G, BC→H, BCH→EG, BE→GH}. Solution:
Step 1: Split the RHSs to get our initial set of FDs, S1:
(a) ABF → G (b) BC → H
(c) BCH → E (d) BCH → G
(e) BE → G (f) BE → H.
Step 2: For each FD, try to reduce the LHS:
(a) A+ = A,B+ = B,F+ = F. In fact, no singleton LHS yields anything. AB+ = AB,AF+ = AF, and BF+ = BF,
so none of them yields G either. We cannot reduce the LHS of this FD.
(b) Since this FD has only two attributes on the LHS, and no singleton LHS yields anything, we cannot reduce the
LHS of this FD.
(c) Since no singleton LHS yields anything, we need only consider LHSs with two or more attributes. We only have three to begin with, so that leaves LHSs with two attributes. BC+ = BCHEG. So we can reduce the LHS of this FD, yielding the new FD: BC → E.
(d) By the same argument, we can reduce this FD to: BC → G.
(e) Since no singleton LHS yields anything, we cannot reduce the LHS of this FD.
(f) Since no singleton LHS yields anything, we cannot reduce the LHS of this FD.
Our new set of FDs, let’s call it S2, is
(a) ABF → G (b) BC → H (c) BC → E (d) BC → G (e) BE → G
(f) BE → H.
Step 3: Try to eliminate each FD.
(a) ABF+ = ABF. We need this FD. S2−(a)
(b) BC+ = BCEGH. We can remove this FD. S2−(b)
(c) BC+ S2−{(b),(c)}
(d) BC+ S2−{(b),(d)}
= BCG. We need this FD.
= BCEGH. We can remove this FD.
(e) BE+ S2−{(b),(d),(e)}
= BEH. We need this FD. (f) BE+ = BEG. We need this FD.
(a) ABF → G (b) BC → E (c) BE → G
(d) BE → H.
S2−{(b),(d),(f)} Our final set of FDs is: