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} →
