A → BC
B → E
CD → EF
I'll now show the FD AD → F also holds in R (a fact that, I think you'll agree, isn't immediately obvious). 3
Here's the proof:
1 . A → BC (given)
2. A → C (1, decomposition)
3. AD → CD (2, augmentation)
4. CD → EF (given)
5. AD → EF (3 and 4, transitivity)
6. AD → F (5, decomposition)
For a second example, recall from Chapter 6 the notion of an irreducible cover . Just to remind you, (a) a
cover for a given set F of FDs is a set C of FDs such that every FD in F is implied by those in C , and (b) that cover
C is irreducible if and only if it possesses all of the following properties:
Singleton dependant: Every FD in C has just one attribute on the right side.
Irreducible determinant: No attribute can be discarded from the left side without losing the property that C
is a cover for F .
No redundant FDs: No FD can be discarded from C without losing the property that C is a cover for F .
Now, I assumed in the previous chapter (tacitly) that every set F of FDs had an irreducible cover. In fact,
this is easy to see:
Thanks to the decomposition rule, we can assume without loss of generality that every FD in F has a
singleton right side.
Next, for each FD in F , examine each attribute A on the left side; if deleting A from that left side has no effect
on the closure F + , delete A from that left side.
For each FD remaining in F , if deleting that FD from F has no effect on the closure F + , delete that FD
from F .
The final version of F is irreducible and is a cover for the original version.
Here then is a concrete example to illustrate the process of actually finding an irreducible cover. Let the
given set of FDs (which all presumably hold in some relvar R with attributes A , B , C , D ) be as follows:
A → BC
B → C
A → B
AB → C
AC → D
3 If you'd prefer a more concrete example, take A as employee number, B as department number, C as manager's employee number, D as project
number for a project directed by that manager (unique within manager), E as department name, and F as percentage of time spent by the specified
manager on the specified project. The FDs A → BC , B → E , and CD → EF are then all intuitively reasonable. (And what about AD → F ?)