Databases Reference
In-Depth Information
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:
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 ?)
Search WWH ::

Custom Search