Databases Reference

In-Depth Information

┌─────┬─────┐ ┌─────┬─────┐ ┌─────┬─────┐

│ SNO │ PNO │ │ PNO │ JNO │ │ JNO │ SNO │

├═════┼═════┤ ├═════┼═════┤ ├═════┼═════┤

│ S1 │ P1 │ │ P1 │ J2 │ │ J2 │ S1 │

│ S1 │ P2 │ │ P2 │ J1 │ │ J1 │ S1 │

│ S2 │ P1 │ │ P1 │ J1 │ │ J1 │ S2 │

└─────┴─────┘ └─────┴─────┘ └─────┴─────┘

│ │ │

└─► join on {PNO} ◄─┘ │

│ │

▼ │

┌─────┬─────┬─────┐ │

│ SNO │ PNO │ JNO │────► join on ◄─────┘

├═════┼═════┼═════┤ {JNO,SNO}

│ S1 │ P1 │ J2 │ │

│ S1 │ P2 │ J1 │ └───►
original value of SPJ

│ S2 │ P1 │ J1 │

│
S2
│
P1
│
J2
│◄───
spurious

│ S2 │ P1 │ J1 │

└─────┴─────┴─────┘

Fig. 9.2: SPJ = the join of all three of its binary projections but not of any two

both explicitly, by means of the tuple (S1,P1,J1), and implicitly as a logical consequence of the JD and the

propositions represented by the other three tuples.

More terminology:
We say a JD like the one that applies in the SPJ example is
tuple forcing
, because if

certain tuples appear, it forces certain additional tuples to appear as well. In Fig. 9.1, for example, the appearance of

the three tuples (S1,P1,J2), (S1,P2,J1), and (S2,P1,J1) forces the appearance of the tuple (S1,P1,J1). Note carefully

that not all JDs are tuple forcing; for example, the join dependency
{{SNO,SNAME,CITY},{CITY,STATUS}}

holds in relvar S, but there's no question of it forcing additional tuples to appear.
Note:
To jump ahead of ourselves

for a moment, it'll turn out later that a relvar that's subject to a tuple forcing JD can't be in 5NF (though as the SPJ

example shows, it can be in BCNF).

CYCLIC RULES

Observe now the cyclic nature of the business rule in the SPJ example (“if
s
is connected to
p
and
p
is connected to
j

and
j
is connected back to
s
again, then
s
and
p
and
j
must all be
directly
connected, in the sense that they must all

appear together in the same tuple”). Let's agree to say this rule is “3-way cyclic.” Then we can say in general that

it's if an
n-
way cyclic rule exists for some
n
> 2 that we might be faced with a relvar that's (a) in BCNF and not in

5NF and therefore (b) can be nonloss decomposed into
n
projections and not into fewer.
10

That said, I have to say too that in my experience such cyclic rules are rare in practice─which means that, in

practice, most relvars, if they're in at least BCNF, are probably in 5NF as well. Indeed, it's quite unusual in practice

to find a relvar that's in BCNF and not in 5NF. Unusual, but not unknown!─I've encountered a few real world

examples myself from time to time. In other words, the fact that such relvars are unusual doesn't mean you don't

need to worry about them, or about JDs and 5NF.
Au contraire:
JDs and 5NF are tools in your designer's toolkit, as

10
If the rule takes the slightly simpler form “if
s
is connected to
p
and
s
is connected to
j
, then
s
and
p
and
j
must all be directly connected,” then

we might have a relvar that's in BCNF but not in
4NF
(and hence not in 5NF either, a fortiori). See Chapter 12.