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 information storage in computers one of the most readily observable trends has been the focus on data independence C J Date 27 defined data independence as immunity of applications to change in storage structure and access strategy Modern database systems offer data independence 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 copies are not made or distributed for direct commercial advantage the ACM copyright notice and the title o f the publication and its date appear and notice is given that copying is by permission of the Association for Computing Machinery To copy otherwise or to republish requires a fee and or specific permission Key words and phrases database management systems relational model compilation locking recovery access path selection authorization 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 observed 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 connected together Different systems use various names for the connections among records such as links sets chains parents etc For example in Figure l a the fact that supplier Acme supplies bolts is repre sented by connections between the relevant part and supplier records In such a system a user frames a question such as What is the lowest price for bolts by writing a program 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 specify 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 important properties 1 all information is Communications of the ACM October 1981 Volume 24 Number 10 represented 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 relational 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 SUPPLIERSrelation keyed by SUPPNO The information which was formerly represented by connections between records is now contained in a third relation PRICES in which parts and suppliers are represented by their respective keys The question What is the lowest price for bolts can be framed in a highlevel language like SQL 16 as follows SELECT MIN PRICE FROM PRICES W H E R E PARTNO IN SELECT P A R T N O FROM PARTS W H E R E 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 representation and access aids periodically to adapt to changing requirements without disturbing users existing 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 programming languages questions are sometimes raised about whether or not an automatic system can choose as efficient an algorithm for processing a complex query as a trained programmer would System R is an experimental system constructed at the San Jose IBM Research Laboratory to demonstrate that a relational database system can incorporate the high performance and complete function 633 FF SUPPLIERS pcF Fig l a A Navigational Database required for everyday production use The key goals established for System 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 programmed transactions ad hoc queries and report generation 3 To support a rapidly changing database environment in which tables indexes views transactions and other objects could easily be added to and removed from the database without stopping the system 4 To support a population of many concurrent users with mecha PARTS PARTNO P107 P113 P125 P132 nisms to protect the integrity of the database in a concurrent update environment 5 To provide a means of recovering the contents of the database to a consistent state after a failure of hardware or software 6 To provide a flexible mechanism whereby different views of stored data can be defined and various users can be authorized to query and update these views 7 To support all of the above functions with a level of performance comparable to existing lower function database systems