Several additional inference rules can be derived from the original three, the following among them. Such additional rules can be used to simplify the practical task of computing F+ from F. Here are some examples:
X → X (“self determination”).
If X → Y and X → Z, then X → YZ (“union”).
If X → Y and Z → W, then XZ → YW (“composition”).
If X → YZ, then X → Y and X → Z (“decomposition”).[67]
In the next section, I’ll show how these four rules can be derived from the original three. First, however, let me give a couple of examples to show how the rules (original and/or additional) can be used. By way of a first example, suppose we’re given a relvar R with attributes A, B, C, D, E, F, and we’re told the following FDs hold in that relvar:
A→BCB→ECD→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).[68] Here’s the proof:
A→BC(given)A→C(1, decomposition)AD→CD(2, augmentation)CD→EF(given)AD→EF(3 and 4, transitivity)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→BCB→CA→BAB→CAC→D
Then the following procedure will produce an irreducible cover for this given set.
First, rewrite the FDs such that each has a singleton right side:
A→BA→CB→CA→BAB→CAC→DObserve now that the FD A → B occurs twice, so one occurrence can be dropped.
Attribute C can be dropped from the left side of the FD AC → D, because we have A → C, so A → AC by augmentation, and we’re given AC → D, so A → D by transitivity; thus the C on the left side of AC → D is redundant.
The FD AB → C can be dropped, because again we have A → C, so AB → CB by augmentation, so AB → C by decomposition.
The FD A → C is implied by the FDs A → B and B → C, so it can be dropped.
We’re left with:
A→BB→CA→D
This set is irreducible.
[67] Two points: First, don’t confuse this kind of decomposition with nonloss decomposition as discussed at length elsewhere in this book. Second, observe that composition and decomposition as here defined aren’t quite inverses of each other; to be specific, the inverse of decomposition is that special case of composition in which Z is replaced by X and W is replaced by Z.
[68] 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?)