Databases Reference
In-Depth Information
( c , t1 , x1 ) appear, then ( c , t2 , x1 ) must appear as well. But the four-line version of the constraint is more symmetric
and aesthetically satisfying, as well as perhaps being easier to understand.
By the way, you might be thinking the redundancies in CTX are unnecessary; more specifically, you might
be thinking the relvar doesn't need to show all possible TNO / XNO combinations for a given CNO. For example,
two tuples would clearly be enough to represent the information that course C1 has two teachers and two textbooks.
The problem is, which two tuples? Any specific choice leads to a relvar having a very unobvious interpretation and
very strange update behavior. (Try stating the predicate for such a relvar!─i.e., try stating the criteria for deciding
whether or not some given update is logically acceptable on that relvar. If you try this exercise, I think you'll see
why the redundancies in CTX are necessary after all.)
The existence of “problem” BCNF relvars like CTX was recognized very early on, and the way to deal with them
was also recognized at that time, at least intuitively (see Exercise 12.8). However, it wasn't until 1977 that these
intuitive ideas were put on a sound theoretical footing by Fagin's introduction of the notion of MVDs. 2 Let me
Relvar CTX is subject to the JD {{CNO,TNO},{CNO,XNO}}. However, we can equally well say it's
subject to the following pair of MVDs:
{ CNO } →→ { TNO }
{ CNO } →→ { XNO }
Note: The MVD X →→ Y can be read as “ X multidetermines Y ” or “ Y is multidependent on X ,” or more simply just
as “ X double arrow Y .”
Taken together, what the foregoing MVDs mean, intuitively, is this: Courses don't have just one teacher or
just one textbook (i.e., the FDs {CNO} → {TNO} and {CNO} → {XNO} don't hold)─but they do have a set of
teachers and a set of textbooks. What's more, for a given course, the set of teachers and the set of textbooks are
completely independent of each other. (As I put it earlier, it doesn't matter who actually teaches some particular
offering of some course, the same textbooks are used. Likewise, it doesn't matter, with respect to some course,
which textbooks are actually used─the same teachers can teach it.) So we can say the following:
For a given course c and a given textbook x , the set of teachers t associated with that ( c , x ) pair depends on c
alone─it makes no difference which particular x we choose.
Likewise, for a given course c and a given teacher t , the set of textbooks x associated with that ( c , t ) pair also
depends on c alone─it makes no difference which particular t we choose.
Note that the sample value of relvar CTX shown in Fig. 12.1 does indeed abide by these rules.
To repeat, relvar CTX is subject to a pair of MVDs. In general, in fact, it's easy to show (see the next
section) that, given relvar R with heading H and subsets X , Y , and Z of H such that the union of X , Y , and Z is equal
to H , the MVD X →→ Y holds in R if and only if the MVD X →→ Z also holds in R . MVDs always go together in
pairs in this way. For that reason it's usual to write them as a “one liner,” thus:
X →→ Y | Z
2 Fagin's work on MVDs predated the widespread adoption of the concept of JDs in general, which is why MVDs were initially treated as a
separate phenomenon in their own right.
Search WWH ::

Custom Search