The goal of on-line analytical processing (OLAP) is to quickly answer queries from large amounts of data residing in a data warehouse. Materialized view selection is an optimization problem encountered in OLAP systems. Published work on the problem of materialized view selection presents solutions scalable in the number of possible views. However, the number of possible views is exponential relative to the number of database dimensions. A truly scalable solution must be polynomial time relative to the number of dimensions. We present such a solution, our Polynomial Greedy Algorithm. Complexity analysis proves scalability, and a performance study verifies the result. Empirical evidence demonstrates benefits close to existing algorithms. We conclude the Polynomial Greedy Algorithm functions effectively where existing algorithms fail dramatically.

A data warehouse stores materialized views of aggregate data derived from a fact table in order to minimize the query response time. One of the most important decisions in designing the data warehouse is the selection of materialized views. This paper presents an algorithm which provides appropriate views to be materialized while the goal is to minimize the query response time and maintenance cost. We use a data cube lattice, frequency of queries and updates on views, and view size to select views to be materialized using greedy algorithms. In spite of the simplicity, our algorithm selects views which give us better performance than views that selected by existing algorithms.

We estimate the availability, reliability, and mean transaction time (response time) for repairable database configurations, centralized or distributed, in which each service component is continuously available for repair. Reliability, the probability that the entire transaction can execute properly without failure, is computed as a function of mean time to failure (MTTF) and mean time to repair (MTTR). Mean transaction time in the system is a function of the mean service delay time for the transaction over all components, plus restart delays due to component failures, plus queuing delays for contention. These estimates are potentially applicable to more generalized distributed systems.

The author study a M/G/1 queueing system with vacations, in which the sojourn time of the server at the queue is controlled by a timer. They consider three policies for setting the timer value: time-limited (TL), cycle-time-limited (CL) and cycle-time-limited with accumulated lateness (CLL). When the server arrives at the queue, the timer is set to a certain value depending on the policy employed. The server serves the waiting customers until either the system becomes empty, or the timer expires, whichever occurs first. In the latter case, the server completes the service on the customer being served, then takes a vacation. Customers are not served during the vacation. If the system is empty upon the server's return from a vacation, another vacation begins immediately. Such a queueing system finds applications in the performance analysis of local area network protocols such as the IEEE 802.4 (token bus) and the Fiber Distributed Data Interface (FDDI), in which the vacation would correspond to the time the token is away at other stations. Using the matrix-analytic approach, they compute the probability distribution of the number of customers in the system at an arbitrary point in time, and the distribution of the time the server spends at the queue before he takes a vacation.>

The volume of data required for decision making is growing fast.With technology

A network modeling tool, called NetMod, which uses simple analytical models to provide the designers of large interconnected local area networks with an in-depth analysis of the potential performance of these systems is presented. This tool can be used in either a university, industrial, or governmental campus networking environment consisting of thousands of computer sites. NetMod is implemented with a combination of the easy-to-use Macintosh software packages, HyperCard, and Excel. The objectives of NetMod, the analytical models, and the user interface are described in detail, along with its application to an actual campus-wide network.>

The File Design Analyzer is a software package which evaluates well-known database storage structures and access methods in terms of secondary storage processing time and storage overhead required to service a set of user applications. It implements a first-order analytical model to specifically evaluate sequential, indexed sequential, direct access, inverted, multilist, and network storage structures. Interaction with the package is available in conversational mode, enabling the experienced analyst to conduct on-line sensitivity analysis.The paper describes three extensions of a conceptual model and system into a practical tool for evaluation of existing or proposed database designs: batched transactions, multi-access interference due to shared secondary storage, and variable record size. Case studies of real systems illustrate the potential of the File Design Analyzer to provide insight regarding the optimal choice of physical parameters within a specified storage structure and to effectively compare alternative storage structures for a particular set of applications.

Reorganization is necessary in some databases for overcoming the performance deterioration caused by updates. The paper presents a dynamic reorganization algorithm which makes the reorganization decision by measuring the database search costs. Previously, the reorganization intervals could only be determined for linear deterioration and known database lifetime. It is shown that the dynamic reorganization algorithm is near optimum for constant reorganization cost and is superior for increasing reorganization cost. In addition, it can be applied to cases of unknown database lifetime and nonlinear performance deterioration. The simplicity, generality, and efficiency appear to make this good heuristic for database reorganization.

An important problem in accessing and updating large scale data bases is the determination of when to reorganize the data and eliminate records that have been flagged for deletion but have not as yet been physically deleted. Such records take up valuable storage space and cause a degradation of access times to the active records, mainly because of the necessity to maintain overflow areas. After a certain length of time it is usually desirable to merge the old data and its overflow areas into a new data base of the original format, thus reallocating the physical storage for maximum efficiency within the constraints imposed by the data base organization. The purpose of this study is to determine the effect of various system and user parameters on the choice of optimal reorganization points over a wide range of file organizations and user applications. The analysis of file reorganization is seen as a first step toward understanding large scale data base reorganization.

This paper appears in the March, 1972, issue of the Communications of the ACM. Its abstract is reproduced below.