Databases Reference

In-Depth Information

Elementary key normal form (EKNF)

Elementary key normal form was introduced by Zaniolo in 1982.
18
Here's the definition:

Definition:
Relvar
R
is in
elementary key normal form
(EKNF) if and only if, for every nontrivial FD
X

→
Y
that holds in
R
, either (a)
X
is a superkey or (b)
Y
is a subkey of some elementary key─where key
K
is

elementary
if and only if there exists some attribute
A
of
R
such that the FD
K
→ {
A
} is nontrivial and

irreducible.

EKNF falls strictly between 3NF and BCNF; that is, BCNF implies EKNF, EKNF implies 3NF, and the

reverse implications don't hold. The stated intent of EKNF is “to capture the salient qualities of both 3NF and

BCNF” while avoiding the problems of both (namely, that 3NF is “too forgiving” and BCNF is “prone to

computational complexity”). That said, I should say too that EKNF isn't much referenced in the literature.

Overstrong PJ/NF

Recall that 5NF was originally called PJ/NF, and PJ/NF means every JD is implied by keys (speaking rather

loosely). In fact, in the paper in which he introduced PJ/NF, Fagin also introduced what he called
overstrong
PJ/NF,

which meant (again rather loosely) that every JD is implied by some specific key considered in isolation. Note that

this latter is what one might intuitively have expected the definition of
regular
PJ/NF (i.e., 5NF) to have been─recall

the remarks in Chapters 10 and 12 concerning the parallelism between the definitions of BCNF, 4NF, and 5NF. Be

that as it may, here's the definition:

Definition:
Relvar
R
is in
overstrong PJ/NF
if and only if every JD of
R
is implied by some key of
R
.

Overstrong PJ/NF clearly implies 5NF (i.e., “regular” PJ/NF), but the reverse is not true. A single

counterexample suffices to demonstrate this latter fact:
19
Consider a relvar
R
with attributes
A
,
B
,
C
, and
D
(only)

and keys {
A
} and {
B
} only. Let the only dependencies to hold in
R
be ones that are implied by these keys (so
R
is

definitely in 5NF). Now consider the JD
{
AB
,
BC
,
AD
}. Applying the membership algorithm, we see that this JD

holds in
R
; but it's not a consequence of either of the keys considered in isolation, as can also be seen by checking

the membership algorithm. So
R
is in 5NF (or PJ/NF) but not in overstrong PJ/NF.

“Restriction-union” normal form

Consider the parts relvar P from the suppliers-and-parts database. Normalization theory as I've described it prior to

this point tells us relvar P is in a “good” normal form; indeed, it's in 5NF, and it's therefore guaranteed to be free of

anomalies that can be removed by taking projections. But why keep all parts in a single relvar? What about a

design in which red parts are kept in one relvar (RP, say), blue ones in another (BP, say), and so on? In other words,

what about the possibility of decomposing the original parts relvar via restriction instead of projection? Would the

resulting structure be a good design or a bad one? (In fact it would almost certainly be bad unless we were very

careful, as we'll see in Part IV of this topic; however, the point here is that classical normalization theory as such has

absolutely nothing to say about the matter.)

18
Carlo Zaniolo: “A New Normal Form for the Design of Relational Database Schemata,”
ACM TODS 7
, No. 3 (September 1982).

19
This same example was used in a footnote earlier in the chapter in connection with the definition of tuple forcing JDs.