Databases Reference

In-Depth Information

Now, it's obvious that a relvar that's not in BCNF (or indeed 4NF) isn't in Vincent's RFNF either by the

foregoing definition (once again, see relvar S for an example). But what about a relvar that's in “our” RFNF?
3

Well, recall the following example from Chapter 13. We're given a relvar SPJ′, with attributes SNO (supplier

number), PNO (part number), and JNO (project number), and predicate
Supplier SNO supplies part PNO to project

JNO
. Also, the following dependencies hold:

{ SNO , PNO }
→
{ JNO }

{ { SNO , PNO } , { PNO , JNO } , { JNO , SNO } }

Now, we saw in Chapter 13 that if the relvar contains the following three tuples─

t1 = s1 p1 j2

t2 = s1 p2 j1

t3 = s2 p1 j1

─then the following tuple has to appear as well:

t4 = s1 p1 j1

But {SNO,PNO} is a key; it follows that tuples
t1
and
t4
, since they have the same key value, are in fact one and the

same (and hence that
j1
=
j2
). As a consequence, SPJ′ suffers from neither FD redundancy nor JD redundancy (as I

defined those terms in Chapter 13), and the relvar is therefore in “our” RFNF.

Observe now, however, that the very fact that
j2
, in tuple
t1
, must be equal to
j1
means the relvar is subject to

redundancy by Vincent's definition! It follows that the two RFNFs, ours and Vincent's, are logically different; in

fact, Vincent's definition is strictly stronger than ours, in the sense that a relvar can be in RFNF by our definition

without being in RFNF by Vincent's, while the converse isn't so. (It further follows that the two RFNFs really need

different names, of course.) In fact, we can make the following stronger statement:

Theorem:
5NF implies SKNF; SKNF implies Vincent's RFNF; Vincent's RFNF implies our RFNF; and our

RFNF implies 4NF. The reverse implications do
not
hold.

Vincent also proves the following useful result:

Theorem:
Relvar
R
is in Vincent's RFNF if and only if it's in BCNF and, for every JD
J
that holds in
R
, the

union of those components of
J
that are superkeys for
R
is equal to the heading of
R
.
4

By way of example, consider relvar SPJ′ once again. As we know, the following JD holds in that relvar:

{ { SNO , PNO } , { PNO , JNO } , { JNO , SNO } }

3
As noted in Chapter 13, “our” RFNF has since been renamed
ETNF
(“essential tuple normal form”). For further discussion, see the section

“Stop Press” in Appendix C.

4
What Vincent actually does is this: He defines relvar
R
to be in yet another normal form that he calls KCNF (key complete normal form) if and

only if it satisfies the stated conditions (i.e., if and only if it's in BCNF and, for every JD
J
that holds in
R
, the union of those components of
J

that are superkeys for
R
is equal to the heading of
R
). Then he goes on to prove that KCNF and his RFNF are logically equivalent.