This example is due to Hugh Darwen. It’s based on a real life situation that arises in connection with the Open University in the U.K. We’re given a relvar that looks like this:
SCT { SNO , CNO , TNO }
KEY { SNO , CNO , TNO }The predicate is: Tutor TNO tutors student SNO on course CNO. Figure 15-7 shows a sample value for this relvar. The redundancies are obvious: For example, the fact that student S1 is enrolled in course C1, the fact that course C1 is tutored by tutor T1, and the fact that tutor T1 tutors student S1 are all represented more than once in the sample value shown in the figure.[163] (Note that the JD 
{{SNO,CNO},{CNO,TNO},{TNO,SNO}} does not hold in relvar SCT.)
Now, one tactic we might consider for reducing redundancy in examples like this one is to make use of surrogate keys (surrogates for short).[164] For example, we might introduce an attribute X, say, whose values serve as surrogates for (SNO,CNO) pairs, as illustrated in Figure 15-8. (Observe from that figure that I’ve made {X} the primary key for relvar XSC. However, the combination {SNO,CNO} is still a key too, of course.)
One difficulty with this approach is as follows: On what basis do we decide to use surrogates for (SNO,CNO) combinations and not for (CNO,TNO) combinations or (TNO,SNO) combinations? Whichever choice we make is asymmetric. Moreover, surrogates are not without problems of their own. Here are some of them:[165]
Surrogates can make updating more complicated (in essence, users have to do their own foreign key checking).
To add insult to injury, the system’s foreign key checking—which still has to be done!—(a) will never fail and (b) will therefore be pure overhead.
Queries and updates become longer, more tedious to write, more error prone, harder to debug, and harder to maintain.
More integrity constraints become necessary.
For present purposes, however, the real question is this: Does introducing surrogates really serve to reduce redundancy? I don’t want to try to address this question here; I’ll come back to it later, in the section MANAGING REDUNDANCY.
[163] You might not agree that those repetitions constitute redundancy. If you don’t, however, I ask you to hold your objections for now—I’ll be taking a much closer look at this example later in the chapter.
[164] As a matter of fact, Codd advocated the use of surrogates in his RM/T discipline in connection with all entity types. In this recommendation he was following the pioneering work of Patrick Hall, John Owlett, and Stephen Todd in their paper “Relations and Entities,” in G. M. Nijssen (ed.), Modelling in Data Base Management Systems (North-Holland/Elsevier Science, 1975).
[165] These problems are elaborated in my paper “Composite Keys” in Relational Database Writings 1989-1991 (Addison-Wesley, 1992).