Databases Reference

In-Depth Information

in particular, when we're trying to develop a
theory
of design—then we need to take all FDs into account, trivial

ones as well as nontrivial.

KEYS REVISITED

I discussed the concept of keys in general terms in Chapter 1, but it's time to get a little more precise about the

matter and to introduce some more terminology. First, here for the record is a precise definition of the term

candidate key:

Definition:
Let
K
be a subset of the heading of relvar
R
. Then
K
is a
candidate key
(or just
key
for short)

for
R
if and only if it possesses both of the following properties:

1.

Uniqueness:
No valid value for
R
contains two distinct tuples with the same value for
K
.

2.

Irreducibility:
No proper subset of
K
has the uniqueness property.

Aside:
This is the first definition we've encountered that involves some kind of irreducibility, but we'll meet

several more in the pages ahead—irreducibility of one kind or another is ubiquitous, and important,

throughout the field of design theory in general, as we'll see. Regarding key irreducibility in particular, one

reason (not the only one) why it's important is that if we were to specify a “key” that wasn't irreducible, the

DBMS wouldn't be able to enforce the proper uniqueness constraint. For example, suppose we told the

DBMS (lying!) that {SNO,CITY} was a key, and in fact the only key, for relvar S. Then the DBMS couldn't

enforce the constraint that supplier numbers are “globally” unique; instead, it could enforce only the weaker

constraint that supplier numbers are “locally” unique, in the sense that they're unique within the pertinent

city.
End of aside.

I'm not going to discuss the foregoing definition any further here, since the concept is so familiar
6
—but

observe how the next few definitions depend on it:

Definition:
A
key attribute
for relvar
R
is an attribute of
R
that's part of at least one key of
R
.

Definition:
A
nonkey attribute
for relvar
R
is an attribute of
R
that's not part of any key of
R
.
7

For example, in relvar SP, SNO and PNO are key attributes and QTY is a nonkey attribute.

Definition:
A relvar is
“all key”
if and only if the entire heading is a key (in which case it's the only key,

necessarily)—equivalently, if and only if no proper subset of the entire is a key.
Note:
If a relvar is “all

key,” then it certainly has no nonkey attributes, but the converse is false—a relvar can be such that all of its

attributes are key attributes and yet not be “all key” (right?).

6
Do note, however, that there's no suggestion that relvars have just one key.
Au contraire
, in fact: A relvar can have any number of distinct

keys, subject only to a limit that's a logical consequence of the degree of the relvar in question. See Exercise 4.9.

7
As a historical note, I remark that key and nonkey attributes were called prime and nonprime attributes, respectively, in Codd's original

normalization papers (see Appendix C).