Databases Reference

In-Depth Information

words, FDs as such are just a syntactic notion (an FD is just an expression that takes a certain syntactic form), while

FD irreducibility is a matter of semantics (it has to do with what the pertinent relvar means).
Note:
I won't assume

in what follows that the FDs we're talking about are irreducible ones only, though in practice we typically do.

Definition:
A
key
of relvar
R
is a subset
K
of the heading
H
of
R
such that the FD
K
→
H
is an irreducible

FD of
R
. That FD is a
key constraint
on
R
.

Note the appeal to FD irreducibility in the foregoing definition.

Definition:
Let relvar
R
have heading
H
and let
X
→
Y
be an FD,
F
say, with respect to
H
. Then
F
is

implied by the keys
of
R
if and only if every relation
r
that satisfies
R
's key constraints also satisfies
F
.

This definition requires some elaboration. First of all, to say some relation satisfies some key constraint is to

say it satisfies the applicable uniqueness requirement; and if it satisfies the uniqueness requirement for the set of

attributes that constitute some key, it certainly also satisfies the uniqueness requirement for every superset of that set

of attributes (just so long as that superset is a subset of the pertinent heading, of course)—in other words, for every

corresponding superkey. Thus, the phrase “satisfies
R
's key constraints” in the definition could be replaced by the

phrase “satisfies
R
's superkey constraints” without making any significant difference. Likewise, the concept

“implied by keys” could just as well be “implied by superkeys,” again without making any significant difference.

Second, what happens if the FD
F
mentioned in the definition is trivial? Well, in that case, by definition,
F
is

satisfied by every relation
r
with heading
H
, and so
F
is certainly satisfied by every relation
r
that satisfies
R
's key

constraints, a fortiori. So trivial FDs are always “implied by keys,” trivially.

Third, then, suppose
F
is nontrivial. Then it's easy to prove the following theorem:

Theorem:
Let
F
be an FD that holds in relvar
R
. Then
F
is
implied by the keys
of
R
if and only if it's a

superkey constraint on
R
.

In other words, it's like that business with trivial FDs: The formal definition as such isn't very helpful in

determining whether a given FD is implied by keys, but the theorem is. For that reason, we can regard the theorem

as an
operational
definition, since it does provide an effective test that can easily be applied in practice.

And now, at last, I can define BCNF:

Definition:
Relvar
R
is in
Boyce-Codd normal form
(BCNF) if and only if every FD of
R
is implied by the

keys of
R
.

However, given the various definitions and theorems already discussed in this section, we can see that the

following “operational” definition is valid too:

Definition:
Relvar
R
is in
Boyce-Codd normal form
(BCNF) if and only for every nontrivial FD
X
→
Y

that holds in
R
,
X
is a superkey for
R
.

As I put it in Chapter 4, it follows from this definition that the only FDs that hold in a BCNF relvar are either

trivial ones (we can't get rid of those, obviously) or arrows out of superkeys (we can't get rid of those, either).

Though now I'd like to add that when I talk about “getting rid of” some FD, I fear I'm being—I hope

uncharacteristically—a little sloppy ... For example, consider relvar S. That relvar is subject to the FD {CITY} →

{STATUS}, among others; as explained in Chapter 3, therefore, the recommendation is to decompose the relvar into

its projections SNC on {SNO,SNAME,CITY} and CT on {CITY,STATUS}. But if we do, then the FD {SNO} →