The Design and Implementation of INGRES MICHAEL STONEBRAKER, EUGENE WONG, AND PETER KREPS University of California, Berkeley and GERALD HELD Tandem Computers, Inc. The currently operational (March 1976) version of the INGRES database management system is described. This multiuser system gives a relational view of data, supports two high level nonprocedural data sublanguages, and runs as a collection of user processes on top of the UNIX operating system for Digital Equipment Corporation PDP 11/40, 11/45, and 11/70 computers. Emphasis is on the design decisions and tradeoffs related to (1) structuring the system into processes, (2) embedding one command language in a general purpose programming language, (3) the algorithms implemented to process interactions, (4) the access methods implemented, (5) the concurrency and recovery control currently provided, and (6) the data structures used for system catalogs and the role of the database administrator. Also discussed are (1) support for integrity constraints (which is only partly operational), (2) the not yet supported features concerning views and protection, and (3) future plans con- cerning the system. Key Words and Phrases: relational database, nonprocedural language, query language, data sublanguage, data organization, query decomposition, database optimization, data integrity, protection, concurrency CR Categories: 3.50, 3.70, 4.22, 4.33, 4.34 1. INTRODUCTION INGRES (Interactive Graphics and Retrieval System) is a relational database system which is implemented on top of the UNIX operating system developed at Bell Telephone Laboratories [22] for Digital Equipment Corporation PDP 11/40, 11/45, and 11/70 computer systems. The implementation of INGRES is primarily programmed in C, a high level language in which UNIX itself is written. Parsing is done with the assistance of YACC, a compiler-compiler available on UNIX [19]. Copyright @ 1976, Association for Computing Machinery, Inc. General permission to repub-1 lish, but not for profit, all or part of this material is granted provided that ACM’s copyright notice is given and that reference is made to the publication,.to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. This research was sponsored by Army Research Office Grant DAHC04-74-GO087, the Naval Electronic Systems Command Contract NOOO39-76-C-0922, the Joint Services Electronics Program Contract F44620-71-C-0087, National Science Foundation Grants DCR75-03839 and ENG74-06651-AOl, and a grant from the Sloan Foundation. Authors’ addresses: M. Stonebraker and E. Wong, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA94720; P. Kreps, Depart- ment of Computer Science and Applied Mathematics, Building SOB, Lawrence Berkeley Lab- oratories, University of California, Berkeley, Berkeley, CA 94720; G. Held, Tandem Compu- ters, Inc., Cupertino, CA 95014. ACM Transactions on Database Systems, Vol. 1, No. 3, September 1976, Pages 189-222.190 l M. Stonebraker, E. Wong, P. Kreps, and G. Held The advantages of a relational model for database management systems have been extensively discussed in the literature [7, 10, 111 and hardly require further elaboration, In choosing the relational model, we were particularly motivated by (a) the high degree of data independence that such a model affords, and (b) the possibility of providing a high level and entirely procedure free facility for data definition, retrieval, update, access control, support of views, and integrity verifica- tion . 1 .l Aspects Described in This Paper In this paper we describe the design decisions made in INGRES. In particular we stress the design and implementation of: (a) the system process structure (see Sec- tion 2 for a discussion of this UNIX notion) ; (b) the embedding of all INGRES commands in the general purpose programming language C; (c) the access methods implemented; (d) the catalog structure and the role of the database administrator; (e) support for views, protection, and integrity constraints; (f) the decomposition procedure implemented; (g) implementation of updates and consistency of second- ary indices; (h) recovery and concurrency control. In Section 1.2 we briefly describe the primary query language supported, QUEL, and the utility commands accepted by the current system. The second user inter- face, CUPID, is a graphics oriented, casual user language which is also operational [20, 211 but not discussed in this paper. In Section 1.3 we describe the EQUEL (Em- bedded QUEL) precompiler, which allows the substitution of a user supplied C pro- gram for the “front end” process. This precompiler has the effect of embedding all of INGRES in the general purpose programming language C. In Section 1.4 a few comments on QUEL and EQUEL are given. In Section 2 we describe the relevant factors in the UNIX environment which have affected our design decisions. Moreover, we indicate the structure of the four processes into which INGRES is divided and the reasoning behind the choices im- plemented. In Section 3 we indicate the catalog (system) relations which exist and the role of the database administrator with respect to all relations in a database. The im- plemented access methods, their calling conventions, and, where appropriate, the actual layout of data pages in secondary storage are also presented. Sections 4, 5, and 6 discuss respectively the various functions of each of the three “core” processes in the system. Also discussed are the design and implementation strategy of each process. Finally, Section 7 draws conclusions, suggests future ex- tensions, and indicates the nature of the current applications run on INGRES. Except where noted to the contrary,