Bubba is a highly parallel computer system for data-intensive applications. The basis of the Bubba design is a scalable shared-nothing architecture which can scale up to thousands of nodes. Data are declustered across the nodes (i.e. horizontally partitioned via hashing or range partitioning) and operations are executed at those nodes containing relevant data. In this way, parallelism can be exploited within individual transactions as well as among multiple concurrent transactions to improve throughput and response times for data-intensive applications. The current Bubba prototype runs on a commercial 40-node multicomputer and includes a parallelizing compiler, distributed transaction management, object management, and a customized version of Unix. The current prototype is described and the major design decisions that went into its construction are discussed. The lessons learned from this prototype and its predecessors are presented.>

We compare two high-availability techniques for recovery from media failures in database systems. Both techniques achieve high availability by having two copies of all data and indexes, so that recovery is immediate. “Mirrored declustering” spreads two copies of each relation across two identical sets of disks. “Interleaved declustering” spreads two copies of each relation across one set of disks while keeping both copies of each tuple on separate disks. Both techniques pay the same costs of doubling storage requirements and requiring updates to be applied to both copies.

The authors investigate a direct storage scheme for complex objects called FIHSM (Fully Inverted Hierarchical Storage Model) and propose a novel parallel-query-processing strategy (QPS) for it. The QPS has four phases (select, pivot, value materialize and compose). With a declustered placement strategy, each of these phases provides for both inter and intra-operation parallelism. Furthermore, partial results of one phase could be pipelined to the subsequent phase. The proposed four-phase structured algorithm is based on heuristics and thus avoids the prohibitive exhaustive searches which are needed for optimizing query executions in parallel environments.>

In dataflow architectures, each dataflow node (i.e., operation) is typically executed on a single physical node. We are concerned with distributed data-intensive systems, in which each base (i.e., persistent) set of data has been declustered over many physical nodes to achieve load balancing. Because of large base set size, each operation is executed where the base set resides, and intermediate results are transferred between physical nodes. In such systems, each dataflow node is typically executed on many physical nodes. Furthermore, because computations are data-dependent, we cannot know until run time which subset of the physical nodes containing a particular base set will be involved in a given dataflow node. This uncertainty affects program loading, task activation and termination, and data transfer among the nodes.

In dataflow architectures, each dataflow operation is typically executed on a single physical node. We are concerned with distributed data-intensive systems, in which each base (i.e., persistent) set of data has been declustered over many physical nodes to achieve load balancing. Because of large base set size, each operation is executed where the base set resides, and intermediate results are transferred between physical nodes. In such systems, each dataflow operation is typically executed on many physical nodes. Furthermore, because computations are data-dependent, we cannot know until run time which subset of the physical nodes containing a particular base set will be involved in a given dataflow operation. This uncertainty creates several problems.

This paper examines the problem of data placement in Bubba, a highly-parallel system for data-intensive applications being developed at MCC. “Highly-parallel” implies that load balancing is a critical performance issue. “Data-intensive” means data is so large that operations should be executed where the data resides. As a result, data placement becomes a critical performance issue.

Handling parallelism in database systems involves the specification of a storage model, a placement strategy, and a query processing strategy. An important goal is to determine the appropriate combination of these three strategies in order to obtain the best performance advantages. In this paper we present a novel and promising query processing strategy for a decomposed storage model. We discuss some of the qualitative advantages of the scheme. We also compare the performance of the proposed “pivot” strategy with conventional query processing for the n-ary storage model. The comparison is performed using the Wisconsin Benchmarks.

The availability of larger RAM spaces for DBMSs provides interesting opportunities for performance enhancements, especially in buffer management. In this paper we propose and compare two alternative strategies for the buffer management of permanent data (i.e., the data committed by transactions) called block buffering and attribute buffering. These strategies use statistics to capture the changing locality of a reference string. We model and demonstrate the impact of locality on the performance of buffering. We also analyze and compare the effect of both the attribute and predicate dimensions of locality on buffering, varying a number of parameters including the degree of locality, RAM size, and RAM utilization.

Identity is that property of an object which distinguishes each object from all others. Identity has been investigated almost independently in general-purpose programming languages and database languages. Its importance is growing as these two environments evolve and merge.

This report examines the relative advantages of a storage model based on decomposition (of community view relations into binary relations containing a surrogate and one attribute) over conventional n-ary storage models

To overcome limitations in the modeling power of existing database systems and provide a better tool for database application programming, Servio Logic Corporation is developing a computer system to support a set-theoretic data model in an object-oriented programming environment We recount the problems with existing models and database systems We then show how features of Smalltalk, such such as operational semantics, its type hierarchy, entity identity and the merging of programming and data language, solve many of those problems Nest we consider what Smalltalk lacks as a database system secondary storage management, a declarative semantics, concurrency, past states To address these shortcomings, we needed a formal data model We introduce the GemStone data model, and show how it helps to define path expressions, a declarative semantics and object history in the OPAL language We summarize similar approaches, and give a brief overview of the GemStone system implementation

This paper presents the architecture of a context-addressed cellular system for non-numeric information processing, using an inexpensive, large-capacity circulating memory device. The system allows data to be represented in a structure very close to the form as the user perceives it (information structure) and allows the search operations of high level queries to be implemented directly. The information structures currently used in existing information systems are described. Then the architecture of the system as a whole is presented, as well as the implementation of these information structures as basic data types and hardware management of storage allocation and garbage collection.

A methodology is developed for determining how much parallelism is optimal if a given job stream is to be executed without multiprogramming. Qualitative design tradeoffs are inferred from the cost-performance effect of parallelism on different hardware subsystems. Measures of software parallelism are analytically related to measures of hardware performance. It is shown that an increase in hardware parallelism may be desirable even though it causes an increase in job processing cost and/or a decrease in hardware efficiency.