Search

The execution of a client/server application involving database access requires a sequence of database transaction events (or, T-events), called a transaction sequence (or, T-sequence). A client/server database application may have nondeterministic behavior in that multiple executions thereof with the same input may produce different T-sequences. We present a framework for testing all possible T-sequences of a client/server database application. We first show how to define a T-sequence in order to provide sufficient information to detect race conditions between T-events. Second, we design algorithms to change the outcomes of race conditions in order to derive race variants, which are prefixes of other T-sequences. Third, we develop a prefix-based replay technique for race variants derived from T-sequences. We prove that our framework can derive all the possible T-sequences in cases where every execution of the application terminates. A formal proof and an analysis of the proposed framework are given. We describe a prototype implementation of the framework and present experimental results obtained from it.

Given N request streams and L/spl les/N LRU caches, the cache assignment problem asks to which cache each stream should be assigned in order to minimize the overall miss rate. An efficient solution to this problem is provided, based on characterizing each stream using the stack reference model and characterizing the interaction of the streams using a bursty stream model. It is shown that for Bernoulli (purely random) mixing of streams, the optimal cache assignment is to have one cache per stream. In practice streams are mixed in a way that is much "burstier" than can be represented by the Bernoulli model. Therefore a method is presented for superposition of bursty streams. The performance of the methods developed for bursty stream superposition and cache assignment are tested using trace data obtained from the database system DB2. The resulting cache assignment recommendations are then applied to the DB2 system, and considerable performance improvement is found to result.

Database query languages and their use for programming nontraditional applications, such as engineering and artificial intelligence applications, are discussed. In such environments, database programs are used to code applications that work over large data sets residing in databases. Optimizing such programs then becomes a necessity. An examination is made of various optimization techniques, and transformations are suggested for improving the performance of database programs. These transformations result in new equivalent database programs with better space and time performance. Several of these techniques apply to classical query languages, although extended query languages which include an iteration operator are specifically discussed. >

We present a methodology for structured database decomposition based on the relational data model. It is argued that in the distributed database environment, structured database decomposition is attractive both for efficiency and for database security considerations. Techniques for parallel processing and hashed access of structurally decomposed database are presented. Techniques for structured database decomposition to support multiple user views are also described. Structured database decomposition is most advantageous in a query only database environment with stable user views, although dynamic updates can also be handled using techniques described in this paper.

Concurrency control algorithms for database systems are usually regarded as methods for synchronizing Read and Write operations. Such methods are judged to be correct if they only produce serializable executions. However, Reads and Writes are sometimes inaccurate models of the operations executed by a database system. In such cases, serializability does not capture all aspects of concurrency control executions. To capture these aspects, we describe a proof schema for analyzing concurrency control correctness. We illustrate the proof schema by presenting two new concurrency algorithms for distributed database systems.

Database machine architectures have been proposed as a promising alternative to improve database system performance, control, and flexibility. While many claims have been made for the database machine concept, few studies have been made to test the performance advantages and disadvantages of a database machine in an application environment. A comprehensive benchmark study comparing the performance of database systems on a conventional computer system and a database machine is reported in this paper. The results show the database machine architecture to have superior performance in most cases. The performance advantage is sensitive to the communication line speed between the host computer and the database machine. The effects of line speed are studied and displayed in the benchmark results. A summary of the similarities and differences between the architectures based upon our benchmark results completes the paper.

Conventional database design techniques rely heavily on the designer's skill and experience, which are neither efficient nor effective for large, realistic design problems. A computer design aid can help by storing many design parameters and performing simple preprocessing before design decisions are made. In this paper, we report on the development of such a system.

Localized information referencing is a long-known and much-exploited facet of program behavior. The existence of such behavior in the data accessing patterns produced by database management systems is not currently supported by empirical results. We present experimental results which demonstrate that in certain environments and under certain important applications, locality of reference is an undeniable characteristic of the information accessing behavior of a hierarchical database management system. Furthermore, database locality of reference is in a sense more regular, predictable, and hence, more exploitable than the localized reference activity found in programs in general. The implications of these results for the performance enhancement and workload characterization of database management systems are discussed.

This paper describes a simulation study of the effect of runtime schema interpretation in a network data model database management system. To perform database operations, programmers use a data manipulation language which supports calls to the data manipulation routines. The data manipulation routines utilize database descriptors from the schema to determine which operations on the database are to be performed for a given actual parameter to the procedure. Current database systems perform the binding of schema descriptors in the data manipulation routines at run-time by interpretation. A niumber of researchers are studying methods to precompute the information required to determine the correct function to execute rather than using run-time interpretation.

This paper presents the concept of a model of database skeleton which is used to represent user's knowledge on the meaning of the data. The logical database synthesis pfoblem is then formulated as a problem of convetting a partially specified database skeleton to a completely specified-one, which corresponds to one of several data models. Approaches to optimal logical database synthesis for the relational database are then considered.

The optimal selection of secondary indexes asks for the quantitative evaluation of the performance of a number of candidate secondary indexes in order to determine the particular combination of indexes which satisfies the anticipated user transactions at a minimal cost. Previous studies determine the optimal selection by assuming that the cost of satisfying a query using a secondary index is not affected by the existence of other indexes in the database. This assumption is realistic when the inverted file organization is used to organize secondary indexes. The main reason is that inverted files do not alter the size of the file. However, the assumption is not valid when the next most popular method for structuring secondary indexes is used, namely, the multilist database structures. This is so, because each multilist increases the size of the file. This paper studies the secondary index selection problem by making the assumption that the multilist organization is utilized to structure secondary indexes and develops a dynamic programming algorithm to solve it. The practical significance of the study lies in the fact that multilists can be easily implemented on network databases.

The semijoin provides a means of reducing the amount of data transmission among sites in a distributed database system. Previously the semijoin has been studied mainly for reducing communication cost in an environment with global public communication networks. In a local area system, however, wide bandwidth is usually available and the communication cost is virtually negligible. In view of this, we adopt a simplified model of a local area network, imposing no constraint on the transmission line capacity and the communication processing capability at each site. For this model, an efficient algorithm for obtaining the shortest semijoin schedule, in the sense of minimizing the total number of semijoin transmissions, is developed. It is based on a schedule diagram newly introduced to represent the semijoin schedule.

When a crash occurs in a transaction processing system, the database can enter an unacceptable state. To continue the processing, the recovery system has three tasks: 1) verification of the database state for acceptability, 2) restoration of an acceptable database state, and 3) restoration of an acceptable history of transaction processing. Unfortunately these tasks are not trivial and the computational complexity of the algorithms for most of them is either NP-complete or NP-hard. In this paper we discuss the concepts and design issues of a construct called database integrity block (DIB). The implementation of this construct allows for efficient verification of the database state by employing a set of integrity assertions and restoration of transaction history by utilizing any database restoration technique such as audit trail or differential file. This paper presents approximation algorithms for minimizing the costs of evaluation of integrity assertions by modeling the problem as the directed traveling salesman problem, and presents a methodology to compare the costs of audit trail and differential file techniques for database restoration. The applicability of integrity verification research to the problem of multiple-query optimization is also included.

This paper treats the problem of fuzzy query translation using the concept of database skeleton. An imprecise, or fuzzy, query is represented by a query graph, which can be analyzed for translatability with respect to a given database skeleton. The fuzzy query translation problem is formulated as a problem of converting a partially specified query graph into a completely specified query graph. This graph is then translated into a sequence of data manipulation commands, such as commands in relational algebra. Approaches to optimal fuzzy query translation are also described.

In designing the interface between a relational database and a Prolog interpreter, efficiency is a major issue. The authors present a method for loading into the memory-resident database of Prolog facts permanently stored in secondary storage. The rationale of the method is to save access to the database by never repeating the same query and by storing in main memory, in a compact and efficient way, information about the past interaction with the database. The authors discuss how to reduce subsumption rests required by the method to pattern matching in many relevant cases. They also describe a simulator of the method, which validates their approach, and they discuss the results of the simulation. >

The rapid advances in the development of low-cost computer hardware have led to many proposals for the use of this hardware to improve the performance of database management systems. Usually the design proposals are quite vague about the performance of the system with respect to a given data management application. In this paper we predict the performance of several of the proposed database management machines with respect to several representative INGRES queries. The systems analyzed in this paper include associative disks, RAP, CASSM, DBC, DIRECT, and CAFS. We demonstrate that no one database machine is best for executing all types of queries. We will also show that for one class of queries the degree of performance improvement achieved does not warrant use of a database machine.

The authors investigate dynamic transaction routing strategies for locally distributed database systems in which the database is partitioned and distributed among multiple transaction-processing systems, and the incoming transactions are routed by a common front-end processor. If a transaction issues a database request referencing a nonlocal database partition, the request has to be shipped to the system owing the referenced partition for processing. Various dynamic strategies are studied. Their performance is compared with that of the optimal static strategy. A class of dynamic transaction routing strategies which take into account routing history and minimize the estimated response time of incoming transactions is proposed; they are found to provide a substantial improvement over the optimal static strategy. The robustness of the strategies is further studied through sensitivity analysis over various transaction loads, communication overheads, and database reference distributions. >

This paper is concerned with the problem of ensuring the integrity of database systems that are accessed concurrently by a number of independent asychronously running transactions. It is assumed that the database system is partitioned into small units that are referred to as the database entities. The relation between the entities is represented by a directed acyclic graph in which the vertices correspond to the database entities and the arcs correspond to certain access rights. We develop a family of non-two-phase locking protocols for such systems that will be shown to ensure serializability and deadlock-freedom. This family is sufficientdy general to encompass all the previously developed non-two-phase lose locking protocols as well as a number of new protocols. One of these new protocols that seems to be particularly useful is also presented in this paper.

Database computers are special-purpose storage and processing devices which are intended to relieve the database management (software) systems running on the general-purpose computers and provide improved storage and processing capabilities (via hardware) for the existing and new database application. However, to support existing database applications, two steps must be followed. First, the existing database must be transformed into the storage format of the new database computer. This one-time tranformation, known as database transformation, is required to preserve the semantics of the database and to take advantage of the advanced hardware features of the new computer. Second, the database sublanguage used in the existing application programs must be supported in real time by the new database computer so that application programs may be executed in the new environment without the need of program conversion. Such real-time translation of sublanguage calls to the instructions of the new database computer, known as query translation, must be straightforward with minimal software support.

The performance of a hypothetical multiprocessor back-end database machine is compared to that of a mainframe database system. The hypothetical database machine uses standard microprocessors and disks as well as processors and disks projected to be available in the future. The class of workloads considered is high-volume transaction processing. Analytic queueing models of the two architectures are constructed and used in parametric performance studies. The performance sensitivities with respect to transactions complexity, the amount of overhead required to implement the distributed database function, the amount of skew in the data access pattern, and the buffer miss ratio are determined. >

Databases that are mainly used for statistical analysis are called statistical databases (SDB). A statistical database management system (SDBMS) may be defined as a database management system that provides capabilities 1) to model, store, and manipulate data in a manner suitable for the needs of SDB users, and 2) to apply statistical data analysis techniques that range from simple summary statistics to advanced procedures. This paper surveys the existing and proposed SDB data definition and data manipulation (i.e., query) languages.