Databases Reference
In-Depth Information
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:
1.
Singleton dependant:
Every FD in
C
has just one attribute on the right side.
2.
Irreducible determinant:
No attribute can be discarded from the left side without losing the property that
C
is a cover for
F
.
3.
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
?)
