Databases Reference

In-Depth Information

Consider Fig. 12.1, which
s
hows a sample value for a relvar called CTX.
1
The predicate is as follows:
Course

CNO can be taught by teacher TNO and uses textbook XNO
.

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

CTX │ CNO │ TNO │ XNO │

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

│ C1 │ T1 │ X1 │

│ C1 │ T1 │ X2 │

│ C1 │ T2 │ X1 │

│ C1 │ T2 │ X2 │

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

Fig. 12.1: Relvar CTX─sample value

Now, relvar CTX is “all key” and is therefore certainly in BCNF. Yet it suffers from redundancy, as you can

see; for example, the fact that teacher T1 can teach course C1 appears twice, and so does the fact that course C1 uses

textbook X1. (It therefore suffers from certain update anomalies also. See Exercise 12.3.) And the reason for these

redundancies is that I'm assuming─perhaps not very realistically─that teachers and textbooks are quite independent

of one another; that is, no matter who actually teaches any particular offering of some particular course, the same

textbooks are used. I also assume a given teacher or given textbook can be associated with any number of courses.

Thus:

Each course
c
has a set
T
of teachers who can teach it and a set
X
of textbooks that it uses.

And, for each such course
c
, there's a tuple in CTX for every possible combination of a teacher
t
from
T
and

a textbook
x
from
X
. (Loosely speaking, in other words, each CNO value appears together with the
cartesian

product
of all of the TNO and XNO values that correspond to that CNO value.)

To state the matter more precisely, the following constraint holds in relvar CTX (recall that from Chapter 9

that the symbol “∈” means “appears in”):

IF (
c
,
t1
,
x1
)
∈
CTX

AND (
c
,
t2
,
x2
)
∈
CTX

THEN (
c
,
t1
,
x2
)
∈
CTX

AND (
c
,
t2
,
x1
)
∈
CTX

But to say this constraint holds is equivalent to saying the following JD holds:

{ { CNO , TNO } , { CNO , XNO } }

It follows that CTX is subject to this JD, and it further follows that the relvar can, and probably should, be

decomposed into its projections on {CNO,TNO} and {CNO,XNO}.
Exercise:
Show the values of these projections

corresponding to the sample value of relvar CTX in Fig. 12.1, and check that the redundancies disappear. (But what

multirelvar constraint now needs to be enforced?)

As an aside, I remark that the constraint shown above could be reduced from four lines to three without loss,

by simply dropping the last line. What I mean is, if tuples (
c
,
t1
,
x1
) and (
c
,
t2
,
x2
) both appear, then the tuple (
c
,
t1
,
x2
)

must appear (that's what the third line says); so, switching the first two tuples around, it follows that if (
c
,
t2
,
x2
) and

1
The example is a modified version of the CTXD example from Chapter 9.