System R supports a high-level relational user language called SQL which may be used by ad hoc users at terminals or as an embedded data sublanguage in PL/I or COBOL. Host-language programs with embedded SQL statements are processed by the System R precompiler which replaces the SQL statements by calls to a machine-language access module. The precompilation approach removes much of the work of parsing, name binding, and access path selection from the path of a running program, enabling highly efficient support for repetitive transactions. Ad hoc queries are processed by a similar approach of name binding and access path selection which takes place on-line when the query is specified. By providing a flexible spectrum of binding times, System R permits transaction-oriented programs and ad hoc query users to share a database without loss of efficiency. System R is an experimental database management system designed and built by members of the IBM San Jose Research Laboratory as part of a research program on the relational model of data. This paper describes the architecture of System R, and gives some preliminary measurements of system performance in both the ad hoc query and the “canned program” environments.

In a high level query and data manipulation language such as SQL, requests are stated non-procedurally, without reference to access paths. This paper describes how System R chooses access paths for both simple (single relation) and complex queries (such as joins), given a user specification of desired data as a boolean expression of predicates. System R is an experimental database management system developed to carry out research on the relational model of data. System R was designed and built by members of the IBM San Jose Research Laboratory.

In the independent reference model of program behavior, King’s formulas for the expected FIFO (“first-in-first-out”) and expected LRU (“least-recently-used”) miss ratios each contain an exponential number of terms (very roughly $n^{{\text{CAP}}} $, where n is the number of pages and CAP is the capacity of main memory). Hence, under the straightforward algorithms, these formulas are computationally intractable. We present an algorithm which is both efficient (there are $O(n \cdot {\text{CAP}})$ additions, multiplications, and divisions) and provably numerically stable, for calculating the expected FIFO miss ratio. In the case of LRU, we present an efficient method, based on an urn model, for obtaining an unbiased estimate of the expected LRU miss ratio (the method requires $O(n \cdot {\text{CAP}})$ additions and comparisons, and $O({\text{CAP}})$ divisions and random number generations).

Upper and lower bounds on processor utilization for the queueing model M/G/1/N are derived. The upper bound is equal to the utilization for constant service times and the lower bound is approached when the average number of operations per busy period approaches one. These bounds show that the form of the processing time distribution can have a substantial effect on processor utilization. We show that the utilization will be near the lower bound if there are a large number of short processing times. The variance does not always give an accurate indication of the effect of the distribution on utilization.