Databases Reference

In-Depth Information

Definition:
Relvar
R
is in
fifth normal form
(5NF), also known as
projection-join normal form
(PJ/NF),

if and only if every JD of
R
is implied by the keys of
R
.

It should be clear that if a JD is implied by the keys of
R
, it certainly holds in
R
(i.e., it's certainly “a JD of

R
”).
But the converse is false:
A JD can hold in
R
without being implied by the keys of
R
. In other words, the

whole point about the 5NF definition is that the only JDs that hold in a 5NF relvar are ones we can't get rid of—

which means ones implied by keys (including trivial ones as a special case).
2

I'd like to close this section by pointing out an intuitively attractive parallelism between the BCNF and 5NF

definitions:

R
is in BCNF if and only if every FD that holds in
R
is implied by the keys of
R
.

R
is in 5NF if and only if every JD that holds in
R
is implied by the keys of
R
.

However, there's a significant difference also. In the BCNF definition, we can simplify the phrase “implied

by the keys” to “implied by
some
key,” meaning, loosely, that each FD that holds is an arrow out of some specific

key considered in isolation (not necessarily the same key for every such FD, of course). By contrast, no such

simplification applies to 5NF─the JDs that hold are JDs that are implied by the keys taken in combination,
not

necessarily just by some key considered in isolation. For example, suppose for the moment that relvar S had two

keys, {SNO} and {SNAME}. Then the following JD (a repeat of one we've seen several times already)─

{ { SNO , SNAME } , { SNO , STATUS } , { SNAME , CITY } }

─would hold in that relvar. As it is, however, it doesn't hold, because {SNAME} isn't in fact a key.
Exercise:

Invent some sample data to demonstrate the truth of these claims.

JDs IMPLIED BY KEYS

So how do we determine whether a given nontrivial JD is implied by keys? It turns out there's an algorithm, the

membership
algorithm (due to Fagin), that does the job. It works like this. Let relvar
R
have heading
H
, and let

{
X1
,...,
Xn
} be a JD,
J
say, with respect to
H
. Then:

1.

If two distinct components of
J
both include the same key
K
of
R
, replace them in
J
by their union.

2.

Repeat the previous step until no further replacements are possible.

Then the original JD is implied by the keys of
R
if and only if
J
is now trivial─i.e., if and only if the final version of

J
contains
H
as a component.
3
(Notice, incidentally, that trivial JDs in particular cause the algorithm to succeed,

trivially.)

Let's look at a few examples. First of all, consider our usual suppliers relvar S. Here's another JD─let's call

it J1─that holds in that relvar:

2
As usual, “getting rid of” a dependency (of any kind) really means replacing it by some multirelvar constraint.

3
In practice, of course, we might not need to go all the way to the bitter end and compute that final version of
J
—we can quit as soon as a

component is produced that's equal to
H
.