NonStop SQL [TM] achieves high performance through an implementation which integrates SQL record access with the pre-existing disk I/O and transaction management subsystems, and moves SQL function downward from the client to the server level of these subsystems. System integration and movement of function to the server reduce message traffic and CPU consumption by putting SQL optimizations at the lower levels of the system. Examples of such optimizations are message traffic savings by filtering data and applying updates at the data source, I/O savings by SQL-optimized buffer pool management, and locking and transaction journaling techniques which take advantage of SQL semantics. Achieving message traffic reduction is particularly important in a distributed, non shared-memory architecture such as the Tandem NonStop System. The result of this implementation is an SQL system which matches the performance of the pre-existing DBMS, while inheriting such pre-existing architecturally-derived features as high availability, transaction-based data integrity, and distribution of both data and execution.

ABSTRACT: If an item is accessed frequently enough, it should be main memory resident. For current technology, "frequently enough " means about every five minutes. Along a similar vein, one can frequently trade memory space for cpu trme. For example, bits can be packed in a byte at the expense of extra instructions to extract the bits. It makes economic sense to spend ten bytes of main memory to save one lnstructlon per second. These results depend on current price ratios of processors, memory and disc accesses These ratios are changing and

System R is a database management system which provides a high level relational data interface. The systems provides a high level of data independence by isolating the end user as much as possible from underlying storage structures. The system permits definition of a variety of relational views on common underlying data. Data control features are provided, including authorization, integrity assertions, triggered transactions, a logging and recovery subsystem, and facilities for maintaining data consistency in a shared-update environment. This paper contains a description of the overall architecture and design of the system. At the present time the system is being implemented and the design evaluated. We emphasize that System R is a vehicle for research in database architecture, and is not planned as a product.

This paper proposes a locking protocol which associates locks with sets of resources. This protocol allows simultaneous locking at various granularities by different transactions. It is based on the introduction of additional lock modes besides the conventional share mode and exclusive mode. The protocol is generalized from simple hierarchies of locks to directed acyclic graphs of locks and to dynamic graphs of locks. The issues of scheduling and granting conflicting requests for the same resource are then discussed. Lastly, these ideas are compared with the lock mechanisms provided by existing data management systems.

Programmed algorithms for test generation and test evaluation are described. The D-notation is introduced and a test generator (DALG) for combinational logic is presented. The sequential case is then examined. "Real life" constraints related to LSI testing are discussed. Two heuristic test generators satisfying these constraints are introduced. The iterative test generator (ITG) generates tests by transforming the given sequential circuit into an iterative combinational circuit. The macroblock test generator (MTG) uses the same approach but makes use of complex primitives (latches, triggers, etc.) to represent the circuit to be tested. Both the ITG and the MTG are not always guaranteed to generate good tests for each examined failure, and are used in connection with a test evaluator (simulator). Basic features of this evaluator are discussed.

This paper describes an algorithm for the computation of tests to detect failures in asynchronous sequential logic circuits. It is based upon an extension of the D-algorithm [1]. Discussion of experience with a program of the procedure is given.

No abstract available.

The first problem in a two level Boolean minimization is the determination of the prime k -cubes. This paper is concerned with the estimation of the statistical complexity of some well-known algorithms which solve this problem. Formulas are given for the average number of comparison operations among k -cubes occurring in Quine's method and in Mc-Cluskey's method; these quantities provide indications of the average execution time of computer programs based on the corresponding algorithms. Numerical values are given and commented on. Formulas are also obtained for the variance of the number of k -cubes and the variance of the number of cubes of a Boolean function; in fact the calculation of these quantities is strictly related to that of the average number of comparison operations among k -cubes. These variances give an idea of the probable error made by using the corresponding average values (obtained in a previous paper by the authors) to make forecasts. It turns out that this error is quite small.

In connection with the problem of two-level minimization of systems of Boolean functions, formulas are obtained for the following statistical quantities: average number of k cubes, prime k cubes, and essential k cubes of a system of Boolean functions. The parameters appearing in the formulas are the number of variables, the number of functions of the system, and the number of ``one'' vertices of each function. Numerical evaluations are given. Increasing by one the number of variables n of a system of m functions roughly results in multiplying the average numbers of cubes and prime cubes by a factor of about 2.2 to 2.3. The ratio of the average numbers of essential cubes and prime cubes rapidly decreases increasing n or m, so that the minimization algorithms, which obtain the essential cubes before the prime cubes, seem statistically unsuitable to solve ``large'' minimization problems. The average occupation memory occurring in Quine, McCluskey, and Bartee algorithms is also evaluated. Its rate of increase with the number of variables is about 2.5.

In connection with the problem of two-level minimization of Boolean functions, we have obtained in a combinatorial way the formulas which give the following quantities of statistical interest: average numbers of k cubes, prime k cubes and essential k cubes of a Boolean function. The parameters which appear in our formulas are: number of variables, number of ``one'' vertices and number of ``don't care'' vertices.