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
?)