Databases Reference
In-Depth Information
Chapter 5
F D s a n d B C N F
( F o r m a l )
What's formal is normal
What's not so is not
And if normal is formal,
Informal is what?
—Anon:
Where Bugs Go
Now I want to step back, take a deep breath as it were, and consider FDs and BCNF all over again—but this time I
want to do it properly (with apologies for the small amount of repetition involved). As you'll quickly see, the
treatment in this chapter is rather more abstract than that in the previous one; it shouldn't be difficult to follow, if
you're fully comfortable with the material of that previous chapter, but it'll certainly be more formal. For that
reason,
I don't want you to look at this chapter at all until you've absorbed everything in the previous one.
(Of
course, that shouldn't be hard to do, since most of what was in that chapter was surely familiar to you anyway.)
One general point up front: Since BCNF is
the
normal form with respect to FDs, I won't have anything to
say in this chapter regarding 2NF or 3NF (or indeed 1NF). As I've more or less said already, 2NF and 3NF just
aren't all that interesting in themselves.
PRELIMINARY DEFINITIONS
In this section I simply give definitions, with little by way of further elaboration, of a few familiar but absolutely
fundamental concepts—definitions that are rather more precise than the ones typically found in the literature (as
well as being more precise, in some cases, than ones given earlier in this topic). Production of examples to illustrate
the definitions is left as an exercise.
Definition:
A
heading
H
is a set of attribute names.
Note:
I remind you that this definition is deliberately
not quite the same as the one I gave in Chapter 2, q.v. Also, for reasons that aren't important here,
The Third
Manifesto
uses {
H
}, not
H
, to denote a heading; however, the simpler form
H
is more convenient for the
purposes of this topic.
Definition:
A
tuple with heading
H
is a set of ordered pairs <
A
,
v
> (one such pair for each attribute name
A
appearing in
H
), where
v
is a value.
Note:
The phrase
tuple with heading H
can be abbreviated to just
tuple
,
if
H
is either understood or irrelevant for the purpose at hand.
Definition:
Let
t
be a tuple with heading
H
and let
X
be a subset of
H
. Then the (tuple)
projection
t
{
X
} of
t
on the attributes of
X
is a tuple with heading
X
—namely, that subset of
t
containing just those <
A
,
v
> pairs
