Databases Reference

In-Depth Information

essentially the same reasons).
9
Note:
Just as an aside, I remark that the example thus gives the lie to two popular

misconceptions (see Exercise 10.1): first, that a relvar with just one key and just one nonkey attribute must be in

5NF; second, that a BCNF relvar that's not in 5NF must be all key.

Now suppose the relvar contains the following three tuples:

t1 = s1 p1 j2

t2 = s1 p2 j1

t3 = s2 p1 j1

(The symbols
s1
and
s2
denote supplier numbers;
p1
and
p2
denote part numbers;
j1
and
j2
denote project numbers;

and
t1
,
t2
, and
t3
are reference labels for the three tuples.) Thanks to the JD, then, the following tuple must 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
). Hence, the kind of redundancy we observed in Chapter 9 with SPJ doesn't occur

with SPJ′. (To be more specific, tuple
t4
in this case isn't an “additional” tuple. See the discussion of tuple forcing

JDs in the paragraph immediately following.) In other words, SPJ′, even though it's not in 5NF, doesn't
and in fact

can't
suffer from the kind of redundancy that 5NF is intended to address. Thus, it looks as if 5NF might be, in a

certain sense, too strong for the purpose.

Let me now remind you of the notion of
tuple forcing JDs
. Basically, a JD is tuple forcing if it's such that, if

certain tuples appear, certain additional tuples are forced to appear as well. I've appealed to this notion several

times in previous chapters, but I've never really defined it properly─so here now is such a definition:

Definition:
Let
J
be a JD with respect to heading
H
, and let
J
hold in relvar
R
. Then
J
might or might not

have the consequence that if certain tuples
t1
, ...,
tn
appear in
R
, a certain additional tuple
t
is forced to appear

in
R
as well (where
additional
means
t
is distinct from each of
t1
, ...,
tn
). If it does have that consequence,

then
J
is
tuple forcing with respect to
R
.
Note:
It's easy to see that any such
J
must be (a) nontrivial, (b)

not implied by any FD of
R
, and (c) not implied by the keys of
R
.
10

Relvar SPJ in Chapter 9 was subject to a tuple forcing JD (indeed, that was precisely what was wrong with

the design of that relvar).
But the same criticism doesn't apply to the SPJ′ example:
The JD that holds in SPJ′ does

not
force any additional tuples to appear, thanks to the FD that also holds in that relvar. That's why SPJ′ doesn't

suffer from the same kind of redundancy as SPJ does, even though─like SPJ─it's not in 5NF.

With the foregoing example by way of motivation, then, I can define another new normal form. However, I

need to do it a step at a time. First we need a precise definition of the kind of redundancy we're talking about:

Definition:
Relvar
R
is
FD redundant
if and only if it's not in BCNF.

Definition:
Relvar
R
is
JD redundant
if and only if some tuple forcing JD holds in
R
.

9
In fact it's not just in BCNF, it's actually in 4NF. Equally, it's not just not in 5NF, it's not even in SKNF (please excuse the deliberately clumsy

wording here).

10
You might be thinking the third of these conditions is a logical consequence of the other two, but such is not the case. For example, consider a

relvar
R
with attributes
A
,
B
,
C
, and
D
and keys
A
and
B
; let no FDs hold in
R
except ones implied by those keys. Then it's easy to see the

nontrivial JD
{
AB
,
AD
,
BC
} holds in
R
, because that JD is implied by those keys taken together. However, it isn't implied by either key taken

individually; in other words, it isn't implied by any individual FD, as such, that holds in
R
.