Many e-Business applications today are being developed and deployed on multi-tier environments involving browser-based clients, web application servers and backend databases. The dynamic nature of these applications necessitates generating web pages on-demand, making middle-tier database caching an effective approach to achieve high scalability and performance [3]. In the DBCache project, we are incorporating a database cache feature in DB2 UDB by modifying the engine code and leveraging existing federated database functionality. This allows us to take advantage of DB2's sophisticated distributed query processing power for database caching. As a result, the user queries can be executed at either the local database cache or the remote backend server, or more importantly, the query can be partitioned and then distributed to both databases for cost optimum execution.DBCache also includes a cache initialization component that takes a backend database schema and SQL queries in the workload, and generates a middle-tier database schema for the cache. We have implemented an initial prototype of the system that supports table level caching. As DB2's functionality is extended, we will be able to support subtable level caching, XML data caching and caching of execution results of web services.

While scaling up to the enormous and growing Internet population with unpredictable usage patterns, E-commerce applications face severe challenges in cost and manageability, especially for database servers that are deployed as those applications' backends in a multi-tier configuration. Middle-tier database caching is one solution to this problem. In this paper, we present a simple extension to the existing federated features in DB2 UDB, which enables a regular DB2 instance to become a DBCache without any application modification. On deployment of a DBCache at an application server, arbitrary SQL statements generated from the unchanged application that are intended for a backend database server, can be answered: at the cache, at the backend database server, or at both locations in a distributed manner. The factors that determine the distribution of workload include the SQL statement type, the cache content, the application requirement on data freshness, and cost-based optimization at the cache. We have developed a research prototype of DBCache, and conducted an extensive set of experiments with an E-Commerce benchmark to show the benefits of this approach and illustrate tradeoffs in caching considerations.

Outerjoins and antijoins are two important classes of joins in database systems. Reordering outerjoins and antijoins with innerjoins is challenging because not all the join orders preserve the semantics of the original query. Previous work did not consider antijoins and was restricted to a limited class of queries. We consider using a conventional bottom-up optimizer to reorder different types of joins. We propose extending each join predicate's eligibility list, which contains all the tables referenced in the predicate. An extended eligibility list (EEL) includes all the tables needed by a predicate to preserve the semantics of the original query. We describe an algorithm that can set up the EELs properly in a bottom-up traversal of the original operator tree. A conventional join optimizer is then modified to check the EELs when generating sub-plans. Our approach handles antijoin and can resolve many practical issues. It is now being implemented in an upcoming release of IBM's Universal Database Server for Unix, Windows and OS/2.

This panel will examine the implications of the XML revolution, which is currently raging on the web, for database systems research and development.

Incremental refresh of a materialized join view is often less expensive than a full, non-incremental refresh. However, it is still a potentially costly atomic operation. This paper presents an algorithm that performs incremental view maintenance as a series of small, asynchronous steps. The size of each step can be controlled to limit contention between the refresh process and concurrent operations that access the materialized view or the underlying relations. The algorithm supports point-in-time refresh, which allows a materialized view to be refreshed to any time between the last refresh and the present.

In a recent paper [MRL98], we had described a general framework for single pass approximate quantile finding algorithms. This framework included several known algorithms as special cases. We had identified a new algorithm, within the framework, which had a significantly smaller requirement for main memory than other known algorithms. In this paper, we address two issues left open in our earlier paper.

We present new algorithms for computing approximate quantiles of large datasets in a single pass. The approximation guarantees are explicit, and apply without regard to the value distribution or the arrival distributions of the dataset. The main memory requirements are smaller than those reported earlier by an order of magnitude. We also discuss methods that couple the approximation algorithms with random sampling to further reduce memory requirements. With sampling, the approximation guarantees are explicit but probabilistic, i.e., they apply with respect to a (user controlled) confidence parameter. We present the algorithms, their theoretical analysis and simulation results. 1 Introduction This article studies the problem of computing order statistics of large sequences of online or disk-resident data using as little main memory as possible. We focus on computing quantiles, which are elements at specific positions in the sorted order of the input. The OE-quantile, for OE 2 [0; ...

Polyglot is an extensible relational-database-type system that supports inheritance, encapsulation, and dynamic method dispatch. It allows use from multiple application languages and permits objects to retain their behavior as they cross the boundary between database and application program. The authors describe the design of Polyglot, extensions to the structured query language (SQL) to support the use of Polyglot types and methods, and the implementation of Polyglot in the Starburst relational database system.>

An extension to SQL, called the SQL extended normal form (XNF), is discussed. It enhances relational technology by a composite object facility, which comprises not only extraction of composite objects from existing databases but also efficient navigation and manipulation facilities provided by an appropriate application programming interface. The language itself allows sharing of the database among normal form SQL applications and composite object applications. It provides proper subsetting of the database and subsequent structuring, exploiting subobject sharing and recursion, all based on its powerful composite object constructor concept, which is closed under the language operations. XNF is integrated into the relational framework, thus benefiting from the available technology such as relational engine and query optimization.>

DB2 TM , IMS, and Tandem TM systems. ARIES is applicable not only to database management systems but also to persistent object-oriented languages, recoverable file systems and transaction-based operating systems. ARIES has been implemented, to varying degrees, in IBM's OS/2 TM Extended Edition Database Manager, DB2, Workstation Data Save Facility/VM, Starburst and QuickSilver, and in the University of Wisconsin's EXODUS and Gamma database machine.

Multi-methods allow method selection to be based on the types of any number of arguments.Languages that currently support multi-methods do not support static type checking.We show how multi-methods can be statically type checked and how information collected at the time of program compilation can be used to make the run-time dispatch of multi-methods more efficient.The results presented can provide the basis for introducing multi-methods in languages with static type checking and for designing new object-oriented paradigms based on multi-methods. 'The exact syntax is different in C++;we have taken liberty with the syntax to clarify the point.

The purpose of the Starburst project is to improve the design of relational database management systems and enhance their performance, while building an extensible system to better support nontraditional applications and to serve as a testbed for future improvements in database technology. The design and implementation of the Starburst system to date are considered. Some key design decisions and how they affect the goal of improved structure and performance are examined. How well the goal of extensibility has been met is examined: what aspects of the system are extensible, how extensions can be done, and how easy it is to add extensions. Some actual extensions to the system, including the experiences of the first real customizers, are discussed.>

A database management system architecture is described that facilitates the implementation of data management extensions for relational database systems. The architecture defines two classes of data management extensions alternative ways of storing relations called relation “storage methods”, and access paths, integrity constraints, or triggers which are “attachments” to relations. Generic sets of operations are defined for storage methods and attachments, and these operations must be provided in order to add a new storage method or attachment type to the system. The data management extension architecture also provides common services for coordination of storage method and attachment execution. This article describes the data management extension architecture along with some implementation issues and techniques.

This paper discusses the experience gained during the implementation of a prototype distributed database management system. The R*prototype supports transparent distribution of a relational database which is accessed using the SQL language for data definition and manipulation. While supporting autonomy among the participating sites, R*also emphasizes good performance for both local and multi-site operations. During the implementation of the R*prototype, we were guided by a few key objectives and encountered several interesting problems. This paper will discuss the guiding objectives of the R*effort, as well as several areas of the implementation which presented special difficulties or were simplified by design decisions.

This article presents an algorithm to refresh the contents of database snapshots. A database snapshot is a read-only table whose contents are extracted from other tables in the database. The snapshot contents can be periodically refreshed to reflect the current state of the database. Snapshots are useful in many applications as a cost effective substitute for replicated data in a distributed database system.

This paper deals with the transaction management aspects of the R* distributed database system. It concentrates primarily on the description of the R * commit protocols, Presumed Abort (PA) and Presumed Commit (PC). PA and PC are extensions of the well-known, two-phase (2P) commit protocol. PA is optimized for read-only transactions and a class of multisite update transactions, and PC is optimized for other classes of multisite update transactions. The optimizations result in reduced intersite message traffic and log writes, and, consequently, a better response time. The paper also discusses R * 's approach toward distributed deadlock detection and resolution.

This article presents and discusses the computation and communication model used by R*, a prototype distributed database management system.An R* computation consists of a tree of processes connected by virtual circuit communication paths.The process management and communication protocols used by R* enable the system to provide reliable, distributed transactions while maintaining adequate levels of performance.Of particular interest is the use of processes in R* to retain user context from one transaction to another, in order to improve the system performance and recovery characteristics.

This paper describes two efficient distributed transaction commit protocols, the Presumed Abort (PA) and Presumed Commit (PC) protocols, which have been implemented in the distributed data base system R* [DSHLM82, LHMWY83]. PA and PC are extensions of the well-known two-phase (2P) commit protocol [Gray78, Lamp80, LSGGL80]. PA is optimized for read-only transactions and a class of multi-site update transactions, and PC is optimized for other classes of multi-site update transactions. The optimizations result in reduced inter-site message traffic and log writes, and, consequently, a better response time for such transactions. We derive the new protocols in a step-wise fashion by modifying the 2P protocol.

The design and implementation of R*, an experimental prototype of a distributed system for the management of interrelated, voluntarily cooperating, but also autonomous databases is based on several major objectives: site autonomy, transparency, ease of use and performance. This paper discusses the way data definition and control statements are executed in a distributed environment and shows how the general objectives are fulfilled. Specialized distributed execution facilities have been developed to facilitate the implementation of complex multi-site functions. This paper describes the facilities and methodology used to implement the distributed processing needed to perform multi-site data definition operations in R*.

R* is an experimental prototype distributed database management system. The computation needed to perform a sequence of multisite user transactions in R* is structured as a tree of processes communicating over virtual circuit communication links. Distributed computation can be supported by providing a server process per site which performs requests on behalf of remote users. Alternatively, a new process could be created to service each incoming request. Instead of using a shared server process or using the process per request approach, R* creates a process associated with the computation of the user on the first request to the remote site. This process is incorporated into the tree of processes serving a single user and is retained for the duration of the user computation. This approach allows R* to factor some of the request execution overhead into the process creation phase, and simplifies the retention of user and transaction context at the multiple sites of the distributed computation.

The concepts of transaction and of data consistency are defined for a distributed system. The cases of partitioned data, where fragments of a file are stored at multiple nodes, and replicated data, where a file is replicated at several nodes, are discussed. It is argued that the distribution and replication of data should be transparent to the programs which use the data. That is, the programming interface should provide location transparency, replica transparency, concurrency transparency, and failure transparency. Techniques for providing such transparencies are abstracted and discussed. By extending the notions of system schedule and system clock to handle multiple nodes, it is shown that a distributed system can be modeled as a single sequential execution sequence. This model is then used to discuss simple techniques for implementing the various forms of transparency.

When typed objects migrate in virtual memory, onto off-ine storage, or among the nodes of a network, the type managers must relinguish control over the object representation and state. In this paper we present a mechanism which allows a type manager to authenticate and reinstantiate migrated objects. This mechanism also solves some problems stemming from the hierarchical structure of the system itself. The mechanism is based on a combination of cryptographic techniques using (nondistributable) centralized, secret keys, and data redundancy which characterizes the object representation and state.