Optimizing the Performance of a Relational Algebra Database Interface An approach for implementing a "smart" interface to support a relational view of data is proposed. The basic idea is to employ automatic programming techniques so that the interface analyzes and efficiently refines the high level query specification supplied by the user. A relational algebra interface, called SQUIRAL, which was designed using this approach, is described in detail. SQUIRAL seeks to minimize query response time and space utilization by: (1) performing global query optimization, (2) exploiting disjoint and pipelined concurrency, (3) coordinating sort orders in temporary relations, (4) employing directory analysis, and (5) maintaining locality in page references. Algorithms for implementing the operators of E. F. Codd's relational algebra are presented, and a methodology for composing them to optimize the performance of a particular user query is described. CACM October, 1975 Smith, J. M. Yen-Tang Chang, P. relational database, database optimization, inverted file, automatic programming, query language, data manipulation language, very high level language 3.70 4.13 4.33 CA751003 JB January 6, 1978 11:19 AM 2155 4 2716 2406 4 2716 2710 4 2716 2710 4 2716 2715 4 2716 2716 4 2716 2716 4 2716 2717 4 2716 2718 4 2716 2765 4 2716 2817 4 2716 2888 4 2716 2901 4 2716 2901 4 2716 2957 4 2716 2959 4 2716 2965 4 2716 3087 4 2716 3154 4 2716 2046 5 2716 2715 5 2716 2716 5 2716 2716 5 2716 2716 5 2716