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.
