COMPUTING PRACTICES A History and Evaluation of System R Donald D. Chamberlin Morton M. Astrahan Michael W. Blasgen James N. Gray W. Frank King Bruce G. Lindsay Raymond Lorie James W. Mehl Thomas G. Price Franco Putzolu Patricia Griffiths Selinger Mario Schkolnick Donald R. Slutz Irving L. Traiger Bradford W. Wade Robert A. Yost IBM Research Laboratory San Jose, California 1. Introduction Throughout the history of infor- mation storage in computers, one of the most readily observable trends has been the focus on data indepen- dence. C.J. Date [27] defined data independence as "immunity of ap- plications to change in storage struc- ture and access strategy." Modern database systems offer data indepen- dence by providing a high-level user interface through which users deal with the information content of their data, rather than the various bits, pointers, arrays, lists, etc. which are used to represent that information. The system assumes responsibility for choosing an appropriate internal Permission to copy without fee all or part of this material is granted provided that the cop- ies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Com- puting Machinery. To copy otherwise, or to republish, requires a fee and/or specific per- mission. Key words and phrases: database manage- ment systems, relational model, compilation, locking, recovery, access path selection, au- thorization CR Categories: 3.50, 3.70, 3.72, 4.33, 4.6 Authors' address: D. D. Chamberlin et al., IBM Research Laboratory, 5600 Cottle Road, San Jose, California 95193. © 1981 ACM 0001-0782/81/1000-0632 75¢. 632 SUMMARY: System R, an experimental database system, was constructed to demonstrate that the usability advantages of the relational data model can be realized in a system with the complete function and high performance required for everyday production use. This paper describes the three principal phases of the System R project and discusses some of the lessons learned from System R about the design of relational systems and database systems in general. representation for the information; indeed, the representation of a given fact may change over time without users being aware of the change. The relational data model was proposed by E.F. Codd [22] in 1970 as the next logical step in the trend toward data independence. Codd ob- served that conventional database systems store information in two ways: (1) by the contents of records stored in the database, and (2) by the ways in which these records are con- nected together. Different systems use various names for the connec- tions among records, such as links, sets, chains, parents, etc. For exam- ple, in Figure l(a), the fact that sup- plier Acme supplies bolts is repre- Communications of the ACM sented by connections between the relevant part and supplier records. In such a system, a user frames a ques- tion, such as "What is the lowest price for bolts?", by writing a pro- gram which "navigates" through the maze of connections until it arrives at the answer to the question. The user of a "navigational" system has the burden (or opportunity) to spec- ify exactly how the query is to be processed; the user's algorithm is then embodied in a program which is dependent on the data structure that existed at the time the program was written. Relational database systems, as proposed by Codd, have two impor- tant properties: (1) all information is October 1981 Volume 24 Number 10represented by data values, never by any sort of "connections" which are visible to the user; (2) the system supports a very high-level language in which users can frame requests for data without specifying algorithms for processing the requests. The re- lational representation of the data in Figure l(a) is shown in Figure l(b). Information about parts is kept in a PARTS relation in which each record has a "key" (unique identifier) called PARTNO. Information about suppliers is kept in a SUPPLIERS relation keyed by SUPPNO. The information which was formerly represented by connec- tions between records is now con- tained in a third relation, PRICES, in which parts and suppliers are repre- sented by their respective keys. The question "What is the lowest price for bolts?" can be framed in a high- level language like SQL [16] as fol- lows: SELECT MIN(PRICE) FROM PRICES WHERE PARTNO IN (SELECT PARTNO FROM PARTS. WHERE NAME = 'BOLT'); A relational system can maintain whatever pointers, indices, or other access aids it finds appropriate for processing user requests, but the user's request is not framed in terms of these access aids and is therefore not dependent on them. Therefore, the system may change its data rep- resentation and access aids periodi- cally to adapt to changing require- ments without disturbing users' ex- isting applications. Since Codd's original paper, the advantages of the relational data model in terms of user productivity and data independence have become widely recognized. However, as in the early days of high-level program- ming languages, questions are some- times raised about whether or not an automatic system can choose as ef- ficient an algorithm for processing a complex query as a trained program- mer would. System R is an experi- mental system constructed at the San Jose IBM Research Laboratory to demonstrate that a relational data- base system can incorporate the high performance and complete function 633 SUPPLIERS Fig. l(a). A "Navigational" Database. FF p cF required for everyday production use. The key goals established for Sys- tem R were: (1) To provide a high-level, nonnavigational user interface for maximum user productivity and data independence. (2) To support different types of database use including pro- grammed transactions, ad hoc que- ries, and report generation. (3) To support a rapidly chang- ing database environment, in which tables, indexes, views, transactions, and other objects could easily be added to and removed from the data- base without stopping the system. (4) To