Databases Reference
In-Depth Information
┌─────┬─────┬─────┬──────┐
CTXD │ CNO │ TNO │ XNO │ DAYS │
├═════┼═════┼═════┼──────┤
│ C1 │ T1 │ X1 │ 7 │
│ C1 │ T1 │ X2 │ 8 │
│ C1 │ T2 │ X1 │ 9 │
│ C1 │ T2 │ X2 │ 6 │
└─────┴─────┴─────┴──────┘
Fig. 12.2: The 5NF relvar CTXD─sample value
do
not
hold
6
─but they do hold in the projection of CTXD on {CNO,TNO,XNO}. For that reason, those MVDs are
said to be
embedded
in the original relvar CTXD. In general, given some relvar
R
with heading
H
, an embedded
dependency with respect to
R
is a dependency that doesn't hold in
R
itself but does hold in the projection of
R
on
some proper subset of
H
. As the example illustrates, therefore (and as was noted in Chapter 9, albeit in different
words), embedded dependencies cause redundancy, but that redundancy can't be eliminated by taking projections.
Such redundancies thus correspond to constraints that must be separately stated and enforced (see Exercise 12.2).
Observe, incidentally, that the foregoing notion of embedding applies to JDs (and therefore to MVDs)
7
but
not to FDs. That is, given some relvar
R
and a projection of
R
whose heading includes both
X
and
Y
, the FD
X
→
Y
holds in that projection if and only if it holds in
R
itself. For example, the FD {CITY} → {STATUS} holds in
relvar S as such and also in every projection of that relvar that retains both of those attributes.
EXERCISES
12.1 Give (a) an example of a relvar of degree at least three that's in BCNF but not 4NF and (b) an example of a
binary
relvar that's in BCNF but not 4NF.
12.2 Write
Tutorial D
CONSTRAINT statements to express (a) the MVDs that hold in relvar CTX and (b) the
embedded MVDs that hold in relvar CTXD, where relvars CTX and CTXD are as in the body of the chapter.
12.3 Consider relvar CTX from the body of the chapter. What kinds of update anomalies can occur with that
relvar?
12.4
Give an example of a relvar that's in 4NF but not 5NF.
12.5 Prove that, given some relvar
R
and a projection of
R
whose heading includes both
X
and
Y
, the FD
X
→
Y
holds in that projection if and only if it holds in
R
itself.
12.6
Show that if relvar
R
is subject to the FD
X
→
Y
, it's also subject to the MVD
X
→→
Y
.
12.7 Let
X
→→
Y
be an MVD,
M
say, with respect to heading
H
. Prove that
M
is trivial if and only if either (a)
Y
is a subset of
X
or (b) the union of
X
and
Y
is equal to
H
. Incidentally, note that it follows from this result that, given
6
I'm being a little sloppy here; by the definitions given earlier in the chapter, the MVDs {CNO} →→ {TNO}|{XNO} can't possibly hold in
relvar CTXD, since they fail to mention the DAYS attribute. But I think you see what I mean.
7
For an example of an embedded JD that's not an embedded MVD, suppose relvar SPJ from Chapter 9 is extended to include a quantity
attribute, QTY, thereby forming a new relvar SPJQ. Suppose the FD {SNO,PNO,JNO} → {QTY} holds in SPJQ (i.e., {SNO,PNO,JNO} is a
key). Then
{{SNO,PNO},{PNO,JNO},{JNO,SNO}} is a JD that holds in the projection of SPJQ on {SNO,PNO,JNO} but not in SPJQ itself.
