The concept of a differential file has previously been proposed as an efficient means of collecting database updates for on-line systems. This paper studies the problem of database backup and recovery for such systems, and presents an analytic model of their operation. Five key design decisions are identified and an optimization procedure for each is developed. A design algorithm that quickly provides parameters for a near-optimal differential file architecture is provided.

Frame memory is a virtual view of secondary storage that can be implemented with reasonable overhead to support database record storage and accessing requirements. Frame memory is designed so that its operating characteristics can be easily manipulated by either designers or design algorithms, while performance effects of such changes can be accurately predicted. Automated design procedures exist to generate and evaluate alternative database designs built upon frame memory, and the existence of these procedures establishes frames as an attractive memory management architecture for future database management systems.

This paper provides an overview of a methodology developed to support systems analysts in the process of database design. The design approach is built upon an analytic model composed of (1) parametric descriptions for components of a generalized database organization, (2) costing equations which can evaluate a proposed modular database design, (3) an analyst interface which accepts an arbitrary database organization for evaluation, and (4) search procedures which automatically generate and compare thousands of alternative designs. Performance is measured as the sum of storage, retrieval, and maintenance costs and is estimated from parameters of the proposed design, the problem description and the storage environment. A virtual, record-frame view of secondary storage has been developed in which data records are added, deleted and modified with minimal effect on existing data structures. Application of the modeling approach to a realistic design problem is described, and modeling accuracy to within four percent is claimed.

It is generally believed that 80 percent of all retrieval from a commercial database is directed at only 20 percent of the stored data items. By partitioning data items into primary and secondary record segments, storing them in physically separate files, and judiciously allocating available buffer space to the two files, it is possible to significantly reduce the average cost of information retrieval from a shared database. An analytic model, based upon knowledge of data item lengths, data access costs, and user retrieval patterns, is developed to assist an analyst with this assignment problem. A computationally tractable design algorithm is presented and results of its application are described.

The representation of a collection of data in terms of its differences from some pre-established point of reference is a basic compaction technique which finds wide applicability. This paper describes a differential database representation which is shown to be an efficient method for storing large and volatile databases. The technique confines database modifications to a relatively small area of physical storage and as a result offers two significant operational advantages. First, because the "reference point" for the database is inherently static, it can be simply and efficiently stored. Moreover, since all modifications to the database are physically localized, the process of backup and the process of recovery are relatively fast and inexpensive.

It is possible to significantly reduce the average cost of information retrieval from a large shared database by partitioning data items stored within each record into a primary and a secondary record segment. An analytic model, based upon knowledge of data item lengths, transportation costs, and retrieval patterns, is developed to assist an analyst with this assignment problem. The model is generally applicable to environments in which a database resides in secondary storage, and is useful for both uniprogramming and multiprogramming systems. A computationally tractable record design algorithm has been implemented as a Fortran program and applied to numerous problems. Realistic examples are presented which demonstrate a potential for reducing total system cost by more than 65 percent.

The representation of a collection of data in terms of its differences from some preestablished point of reference is a basic storage compaction technique which finds wide applicability. This paper describes a differential database representation which is shown to be an efficient method for storing large and volatile databases. The technique confines database modifications to a relatively small area of physical storage and as a result offers two significant operational advantages. First, because the “reference point” for the database is inherently static, it can be simply and efficiently stored. Second, since all modifications to the database are physically localized, the process of backup and the process of recovery are relatively fast and inexpensive.

The physical structure and relative placement of information elements within a data base is critical for the efficient design of a computerized information system which is shared by a community of users. Traditionally the selection among alternative structural designs has been handled largely via heuristics. Recent research has shown that a number of significant design problems can be stated mathematically as nonlinear, integer, zero-one programming problems. In concept, therefore, mathematical programming algorithms can be used to determine "optimal" data base designs. In practice, one finds that realistic problems of even modest size are computationally infeasible. This paper presents a means for overcoming this difficulty in the design of data base records. A metric with which to measure the similarity of usage among data items is developed and used by a clustering algorithm to reduce the space of alternative designs to a point where solution is economically feasible.