The recent years have seen an explosive growth in web and mobile application development. Such applications typically have rapid development cycles, and their developers expect mobile-friendly features and serverless characteristics such as rapid deployment capabilities (with minimal initialization), scalability to handle workload spikes, and flexible pay-as-you-go billing. Google’s Firestore is a NoSQL serverless database with real-time notification capability, and together with the Firebase ecosystem greatly simplifies common app development challenges by letting application developers focus primarily on their business logic and user experience. This paper presents the Firestore architecture, how it satisfies the aforementioned requirements, and how its real-time notification system works in tandem with Firebase client libraries to allow mobile applications to provide a smooth user experience even in the presence of network connectivity issues.

This in-person panel, which I will be moderating, will focus on startups founded by worldwide database researchers. The panelists are a set of people with different backgrounds in terms of their geographic locations, research careers, startup experiences, maturity of their past and present startups, etc. This panel is modeled after such a panel that I organized and moderated at the ACM SIGMOD International Conference on Management of Data in June 2020. This VLDB 2022 panel will be the second time such a panel will be hosted in a research-oriented database conference.

In a classic transactional distributed database management system (DBMS), write transactions invariably synchronize with a coordinator before final commitment. While enforcing serializability, this model has long been criticized for not satisfying the applications' availability requirements. When entering the era of Internet of Things (IoT), this problem has become more severe, as an increasing number of applications call for the capability of hybrid transactional and analytical processing (HTAP), where aggregation constraints need to be enforced as part of transactions. Current systems work around this by creating escrows, allowing occasional overshoots of constraints, which are handled via compensating application logic.The WiSer DBMS targets consistency with availability, by splitting the database commit into two steps. First, a PROMISE step that corresponds to what humans are used to as commitment, and runs without talking to a coordinator. Second, a SERIALIZE step, that fixes transactions' positions in the serializable order, via a consensus procedure. We achieve this split via a novel data representation that embeds read-sets into transaction deltas, and serialization sequence numbers into table rows. WiSer does no sharding (all nodes can run transactions that modify the entire database), and yet enforces aggregation constraints. Both read-write conflicts and aggregation constraint violations are resolved lazily in the serialized data. WiSer also covers node joins and departures as database tables, thus simplifying correctness and failure handling. We present the design of WiSer as well as experiments suggesting this approach has promise.

It has been a decade since the concept of blockchain was invented as the underlying core data structure of the permissionless or public Bitcoin cryptocurrency network. Since then, several cryptocurrencies, tokens and ICOs have emerged. After much speculation and hype, significant number of them have become problematic or worthless! The public blockchain system Ethereum emerged by generalizing the use of blockchains to manage any kind of asset, be it physical or purely digital, with the introduction of Smart Contracts. Over the years, numerous myths have developed with respect to the purported utility and the need for public blockchains. The adoption and further adaptation of blockchains and smart contracts for use in the permissioned or private environments is what I consider to be useful and of practical consequence. Hence, the technical aspects of only private blockchain systems will be the focus of my SIGMOD 2019 keynote. Along the way, I will bust many myths associated with public blockchains. I will also compare traditional database technologies with blockchain systems' features and identify desirable future research topics.

In this tutorial, I survey some of the private blockchain systems with respect to their architectures in general and their approaches to some specific technical areas. Specifically, I focus on how the functionality of traditional and modern data stores are being utilized or not utilized in the different blockchain systems.

Provides an abstract of the keynote presentation and may include a brief professional biography of the presenter. The complete presentation was not made available for publication as part of the conference proceedings.

In the last few years, blockchain (also known as distributed ledger), the underlying technology of the permissionless or public Bitcoin network, has become very popular for use in private or permissioned environments. Computer companies like IBM and Microsoft, and many key players in different vertical industry segments have recognized the utility of blockchains for securely managing assets (physical/digital) other than cryptocurrencies. IBM did some pioneering work by architecting and implementing a private blockchain system, and then open sourcing it. That system, which has since then been named Fabric, is being enhanced via the Hyperledger Consortium set up under the auspices of the Linux Foundation. Other efforts in the industry include Enterprise Ethereum, R3 Corda and BigchainDB.

We demonstrate Hybrid Transactional and Analytics Processing (HTAP) on the Spark platform by the Wildfire prototype, which can ingest up to ~6 million inserts per second per node and simultaneously perform complex SQL analytics queries. Here, a simplified mobile application uses Wildfire to recommend advertising to mobile customers based upon their distance from stores and their interest in products sold by these stores, while continuously graphing analytics results as those customers move and respond to the ads with purchases.

This tutorial on Modern Database Systems (MDS) is targeted at a broad set of database systems and applications people. It is intended to let the attendees better appreciate what is really behind the covers of many of the modern database systems (e.g., NoSQL and NewSQL systems), going beyond the hype associated with these open source, commercial and/or research systems. The capabilities and limitations of such systems will be addressed. Modern extensions to decades old relational DBMSs like DB2 and SQL Server will also be described. Some application case studies will also be presented.

No abstract available.

In this paper, I describe some of the recent developments in the database management area, in particular the NoSQL phenomenon and the hoopla associated with it. The goal of the paper is not to do an exhaustive survey of NoSQL systems. The aim is to do a broad brush analysis of what these developments mean - the good and the bad aspects! Based on my more than three decades of database systems work in the research and product arenas, I will outline what are many of the pitfalls to avoid since there is currently a mad rush to develop and adopt a plethora of NoSQL systems in a segment of the IT population, including the research community. In rushing to develop these systems to overcome some of the shortcomings of the relational systems, many good principles of the latter, which go beyond the relational model and the SQL language, have been left by the wayside. Now many of the features that were initially discarded as unnecessary in the NoSQL systems are being brought in, but unfortunately in ad hoc ways. Hopefully, the lessons learnt over three decades with relational and other systems would not go to waste and we wouldn't let history repeat itself with respect to simple minded approaches leading to enormous pain later on for developers as well as users of the NoSQL systems!

Storage class memory (SCM), a new generation of memory technology, offers non-volatility, high-speed, and byte-addressability, which combines the best properties of current hard disk drives (HDD) and main memory. With these extraordinary features, current systems and software stacks need to be redesigned to get significantly improved performance by eliminating disk input/output (I/O) barriers; and simpler system designs by avoiding complicated data format transformations. In current DBMSs, logging and recovery are the most important components to enforce the atomicity and durability of a database. Traditionally, database systems rely on disks for logging transaction actions and log records are forced to disks when a transaction commits. Because of the slow disk I/O speed, logging becomes one of the major bottlenecks for a DBMS. Exploiting SCM as a persistent memory for transaction logging can significantly reduce logging overhead. In this paper, we present the detailed design of an SCM-based approach for DBMSs logging, which achieves high performance by simplified system design and better concurrency support. We also discuss solutions to tackle several major issues arising during system recovery, including hole detection, partial write detection, and any-point failure recovery. This new logging approach is used to replace the traditional disk based logging approach in DBMSs. To analyze the performance characteristics of our SCM-based logging approach, we implement the prototype on IBM SolidDB. In common circumstances, our experimental results show that the new SCM-based logging approach provides as much as 7 times throughput improvement over disk-based logging in the Telecommunication Application Transaction Processing (TATP) benchmark.

A conventional query execution engine in a database system essentially uses a SQL virtual machine (SVM) to interpret a dataflow tree in which each node is associated with a relational operator. During query evaluation, a single tuple at a time is processed and passed among the operators. Such a model is popular because of its efficiency for pipelined processing. However, since each operator is implemented statically, it has to be very generic in order to deal with all possible queries. Such generality tends to introduce significant runtime inefficiency, especially in the context of memory-resident systems, because the granularity of data commercial system, using SVM. processing (a tuple) is too small compared with the associated overhead. Another disadvantage in such an engine is that each operator code is compiled statically, so query-specific optimization cannot be applied. To improve runtime efficiency, we propose a compiled execution engine, which, for a given query, generates new query-specific code on the fly, and then dynamically compiles and executes the code. The Java platform makes our approach particularly interesting for several reasons: (1) modern Java Virtual Machines (JVM) have Just- In-Time (JIT) compilers that optimize code at runtime based on the execution pattern, a key feature that SVMs lack; (2) because of Java’s continued popularity, JVMs keep improving at a faster pace than SVMs, allowing us to exploit new advances in the Java runtime in the future; (3) Java is a dynamic language, which makes it convenient to load a piece of new code on the fly. In this paper, we develop both an interpreted and a compiled query execution engine in a relational, Java-based, in-memory database prototype, and perform an experimental study. Our experimental results on the TPC-H data set show that, despite both engines benefiting from JIT, the compiled engine runs on average about twice as fast as the interpreted one, and significantly faster than an in-memory

Application Servers (ASs), which have become very popular in the last few years, provide the platforms for the execution of transactional, server-side applications in the online world. While transaction processing monitors (TPMs) have been providing similar functionality for over 3 decades, ASs are their modern equivalents. ASs play a central role in enabling electronic commerce in the web context. The objective of this seminar is to provide an introduction to different ASs and their underlying technologies for the novice as well as the experienced person. The intent is to broaden the background of database people for them to be able to better appreciate application requirements and scenarios. C. Mohan (Ph.D. 1981, UT-Austin) was named an IBM Fellow in 1997 for being recognized worldwide as a leading innovator in transaction management. He is the primary inventor of the ARIES family of recovery and locking methods, and the industry-standard Presumed Abort commit protocol. He received the 1996 ACM SIGMOD Innovations Award. At the 1999 VLDB Conference, he was honored with the 10 Year Best Paper Award for the widespread commercial and research impact of his work on ARIES. Mohan, who is an inventor of 33 patents, works very closely with numerous IBM product groups. His research results are implemented in numerous IBM and non-IBM prototypes and products like DB2, MQSeries, Lotus Domino, S/390 Parallel Sysplex and SQLServer. Currently,Mohan is a member of IBM’s Application Integration Middleware Architecture Board and is working on next generation messaging technologies and database caching in the context of WebSphere and DB2.

No abstract available.

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.

Managing a combined store consisting of database data and file data in a robust and consistent manner is a challenge for database systems and content management systems. In such a hybrid system, images, videos, engineering drawings, etc. are stored as files on a file server while meta-data referencing/indexing such files is created and stored in a relational database to take advantage of efficient search. In this paper we describe solutions for two potentially problematic aspects of such a data management system: backup/recovery and data consistency. We present algorithms for performing backup and recovery of the DBMS data in a coordinated fashion with the files on the file servers. Our algorithms for coordinated backup and recovery have been implemented in the IBM DB2/DataLinks product [1]. We also propose an efficient solution to the problem of maintaining consistency between the content of a file and the associated meta-data stored in the DBMS from a reader's point of view without holding long duration locks on meta-data tables. In the model, an object is directly accessed and edited in-place through normal file system APIs using a reference obtained via an SQL Query on the database. To relate file modifications to meta-data updates, the user issues an update through the DBMS, and commits both file and meta-data updates together.

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.

Application Servers (ASs), which have become very popular in the last few years, provide the platforms for the execution of transactional, server-side applications in the online world. ASs are the modern cousins of traditional transaction processing monitors (TPMs) like CICS. In this tutorial, I will provide an introduction to different ASs and their technologies. ASs play a central role in enabling electronic commerce in the web context. They are built on the basis of more standardized protocols and APIs than were the traditional TPMs. The emergence of Java, XML and OMG standards has played a significant role in this regard. Consequently, I will also briefly introduce the related XML, Java and OMG technologies like SOAP, J2EE and CORBA. One of the most important features of ASs is their ability to integrate the modern application environments with legacy data sources like IMS, CICS, VSAM, etc. They provide a number of connectors for this purpose, typically using asynchronous transactional messaging technologies like MQSeries and JMS. Traditional TPM-style requirements for industrial strength features like scalability, availability, reliability and high performance are equally important for ASs also. Security and authentication issues are additional important requirements in the web context. ASs support DBMSs not only as storage engines for user data but also as repositories for tracking their own state. Recently, the ECPerf benchmark has been developed via the Java Community Process to evaluate in a standardized way the cost performance of J2EE-compliant ASs. Several caching technologies have been developed to improve performance of ASs.Soon after this conference is over, the slides of this tutorial will be available on the web at the following URL: http://www.almaden.ibm.com/u/mohan/AppServersTutorial_SIGMOD2002_Slides.pdf

No abstract available.

Execution plans produced by traditional query optimizers for data integration queries may yield poor performance for several reasons. The cost estimates may be inaccurate, the memory available at run-time may be insufficient, or data delivery rate can be unpredictable. We address the problem of unpredictable data arrival rate. We propose to dynamically schedule queries in order to deal with irregular data delivery rate and gracefully adapt to the available memory. Our approach performs careful step-by-step scheduling of several query fragments and processes these fragments based on data arrivals. We describe a performance evaluation that shows important performance gains in several configurations.

In this one-page summary, I introduce the database aspects of Lotus Domino/Notes. These database features are covered in detail in the corresponding SIGMOD99 tutorial available at www.almaden.ibm.com/u/mohan/domino_sigmod99.ps.

This paper presents general algorithms for concurrency control in tree-based access methods as well as a recovery protocol and a mechanism for ensuring repeatable read. The algorithms are developed in the context of the Generalized Search Tree (GiST) data structure, an index structure supporting an extensible set of queries and data types. Although developed in a GiST context, the algorithms are generally applicable to many tree-based access methods. The concurrency control protocol is based on an extension of the link technique originally developed for B-trees, and completely avoids holding node locks during I/Os. Repeatable read isolation is achieved with a novel combination of predicate locks and two-phase locking of data records. To our knowledge, this is the first time that isolation issues have been addressed outside the context of B-trees. A discussion of the fundamental structural differences between B-trees and more general tree structures like GiSTs explains why the algorithms developed here deviate from their B-tree counterparts. An implementation of GiSTs emulating B-trees in DB2/Common Server is underway.

In recent years, numerous transaction models have been proposed to address the problems posed by advanced database applications, but only a few of these models are being used in commercial products. In this paper, we make the case that such models may be too centered around databases to be useful in real environments. Advanced applications raise a variety of issues that are not addressed at all by transaction models. These same issues, however, are the basis for existing workflow systems, which are having considerable success as commercial products in spite of not having a solid theoretical foundation. We explore some of these issues and show that, in many aspects, workflow models are a superset of transaction models and have the added advantage of incorporating a variety of ideas that have so far remained outside the scope of traditional transaction processing.

In the last few years, workflow management has become a hot topic in the research community and, especially, in the commercial arena. Workflow management is multidisciplinary in nature encompassing many aspects of computing: database management, distributed client-server systems, transaction management, mobile computing, business process reengineering, integration of legacy and new applications, and heterogeneity of hardware and software. Many academic and industrial research projects are underway. Numerous successful products have been released. Standardization efforts are in progress under the auspices of the Workflow Management Coalition. As has happened in the RDBMS area with respect to some topics, in the workflow area also, some of the important real-life problems faced by customers and product developers are not being tackled by researchers. This tutorial will survey the state of the art in workflow management research and products.

We discuss several disk read-write optimizations that are implemented in different transaction systems and disk hardware to improve performance. These include: (1) when multiple sectors are written to disk, the sectors may be written out of sequence (SCSI disk interfaces do this). (2) Avoiding initializing pages on disk when a file is extended. (3) Not accessing individual pages during a mass delete operation (e.g., dropping an index from a file which contains multiple indexes). (4) Permitting a previously deallocated page to be reallocated without the need to read the deallocated version of the page from disk during its reallocation. (5) Purging of file pages from the buffer pool during a file erase operation (e.g., a table drop). (6) Avoiding logging for bulk operations like index create. We consider a system which implements the above optimizations and in which a page consists of multiple disk sectors and recovery is based on write-ahead logging using a log sequence number on every page. For such a system, we present a simple method for guaranteeing the detection of the partial disk write of a page. Detecting partial writes is very important not only to ensure data integrity from the users' viewpoint but also to make the transaction system software work correctly. Once a partial write is detected, it is easy to recover such a page using media recovery techniques. Our method imposes minimal CPU and space overheads. It has been implemented in DB2/6000 and ADSM.>

No abstract available.

This paper presents an algorithm, called ARIES/CSA (Algorithm for Recovery and Isolation Exploiting Semantics for Client-Server Architectures), for performing recovery correctly in client-server (CS) architectures. In CS, the server manages the disk version of the database. The clients, after obtaining database pages from the server, cache them in their buffer pools. Clients perform their updates on the cached pages and produce log records. The log records are buffered locally in virtual storage and later sent to the single log at the server. ARIES/CSA supports a write-ahead logging (WAL), fine-granularity (e.g., record) locking, partial rollbacks and flexible buffer management policies like steal and no-force. It does not require that the clocks on the clients and the server be synchronized. Checkpointing by the server and the clients allows for flexible and easier recovery.

The algorithm for recovery and isolation exploitation semantics for linear hashing with separators (ARIES/LHS) that controls concurrent operations on storage structures by different users is presented. The algorithm uses fine granularity locking, guarantees serializability, and prevents rolling back transactions from getting involved in deadlocks.>

A method for managing a remote backup database to provide protection from disasters that destroy the primary database is presented. The method is general enough to accommodate the ARIES-type recovery and concurrency control methods as well as the methods used by other systems such as DB2, DL/I and IMS Fast Path. It provides high performance by exploiting parallelism and by reducing inputs and outputs using different means, like log analysis and choosing a different buffer management policy from the primary one. Techniques are proposed for checkpointing the state of the backup system so that recovery can be performed quickly in case the backup system fails, and for allowing new transaction activity to begin even as the backup is taking over a primary failure. Some performance measurements taken from a prototype are also presented.>

Eleven two-phase commit (2PC) protocol variations that optimize towards the normal case are described and compared with a baseline 2PC protocol. Environments in which they are most effective are discussed. The variations are compared and contrasted in terms of number of message flows, number of log writes (both forced and non-forced), probability of heuristic damage, how damage is reported, and other tradeoffs.>

This paper very briefly summarizes the features and technologies implemented in the IBM relational DBMS products. The topics covered include record and index management, concurrency control and recovery methods, commit protocols, query optimization and execution techniques, high availability and support for parallelism and distributed data. Some indications of likely future product directions are also given.

We describe an efficient method for supporting incremental and full archiving of data bases (e.g., individual files). Customers archive their data bases quite frequently to minimize the duration of data outage. Because of the growing sizes of data bases and the ever increasing need for high availability of data, the efficiency of the archive copy utility is very important. The method presented here minimizes interferences with concurrent transactions by not acquiring any locks on the data being copied. It significantly reduces disk I/Os by not keeping on data pages any extra tracking information in connection with archiving. These features make the archive copy operation be more efficient in terms of resource consumption compared to other methods. The method is also flexible in that it optionally supports direct copying of data from disks, bypassing the DBMS's buffer pool. This reduces buffer pool pollution and processing overheads, and allows the utility to take advantage of device geometries for efficiently retrieving data. We also describe extensions to the method to accommodate the multisystem shared disks transaction environment. The method tolerates gracefully system failures during the archive copy operation.

Solutions to the problem of performing recovery correctly in shared-disks (SD) and client-server (CS) architectures are presented. In SD, all the disks containing the data bases are shared among multiple instances of the database management system (DBMS). In CS, the server manages the disk version of the data base. The clients, after obtaining database pages from the server, cache them in their buffer pools. Clients perform their updates on the cached pages and produce log records. In write-ahead logging (WAL) systems, a monotonically increasing value called the log sequence number (LSN) is associated with each log record. Every database page contains the LSN of the log record describing the most recent update to that page. This is required for proper recovery after a system failure. A technique for generating monotonically increasing LSNs in SD and CS architectures without using synchronized clocks is presented.>

This paper provides a comprehensive treatment of index management in transaction systems. We present a method, called ARIESIIM (Algorithm for Recovery and Isolation Exploiting Semantics for Index Management), for concurrency control and recovery of B+-trees. ARIES/IM guarantees serializability and uses write-ahead logging for recovery. It supports very high concurrency and good performance by (1) treating as the lock of a key the same lock as the one on the corresponding record data in a data page (e.g., at the record level), (2) not acquiring, in the interest of permitting very high concurrency, commit duration locks on index pages even during index structure modification operations (SMOs) like page splits and page deletions, and (3) allowing retrievals, inserts, and deletes to go on concurrently with SMOs. During restart recovery, any necessary redos of index changes are always performed in a page-oriented fashion (i.e., without traversing the index tree) and, during normal processing and restart recovery, whenever possible undos are performed in a page-oriented fashion. ARIES/IM permits different granularities of locking to be supported in a flexible manner. A subset of ARIES/IM has been implemented in the OS/2 Extended Edition Database Manager. Since the locking ideas of ARIES/IM have general applicability, some of them have also been implemented in SQL/DS and the VM Shared File System, even though those systems use the shadow-page technique for recovery.

As relational DBMSs become more and more popular and as organizations grow, the sizes of individual tables are increasing dramatically. Unfortunately, current DBMSs do not allow updates to be performed on a table while an index (e.g., a B+-tree) is being built for that table, thereby decreasing the systems' availability. This paper describes two algorithms in order to relax this restriction. Our emphasis has been to maximize concurrency, minimize overheads and cover all aspects of the problem. Builds of both unique and nonunique indexes are handled correctly. We also describe techniques for making the index-build operations restartable, without loss of all work, in case a system failure were to interrupt the completion of the creation of the index. In this connection, we also present algorithms for making a long sort of operation restartable. These include algorithms for the sort and merge phases of sorting.

We present efficient and flexible methods which permit read-only transactions that do not mind reading a possibly slightly old, but still consistent, version of the data base to execute without acquiring locks. This approach avoids the undesirable interferences between such queries and the typically shorter update transactions that cause unnecessary and costly delays. Indexed access by such queries is also supported, unlike by the earlier methods. Old versions of records are maintained only in a transient fashion. Our methods are characterized by their flexibility (number of versions maintained and the timing of version switches, supporting partial rollbacks, and different recovery and buffering methods) and their efficiency (logging, garbage collection, version selection, and incremental, record-level versioning). Distributed data base environments are also supported, including commit protocols with the read-only optimization. We also describe efficient methods for garbage collecting unneeded older versions.

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.

A new join method, called hybrid join, is proposed which uses the join-index filtering and the skip sequential prefetch mechanism for efficient data access. With this method, the outer table is sorted on the join column. Then, the outer is joined with the index on the join column of the inner. The inner tuple is represented by its surrogate, equivalent of its physical disk address, which is carried in the index. The partial join result is sorted on the surrogate and then the inner table is accessed sequentially to complete the join result. Local predicate filtering can also be applied before the access of the inner relation through the index AND/ORing. Efficient methods for skip sequential access and prefetching of logically discontiguous leaf pages of B/sup +/-tree indexes are also presented.>

A method called ARIES-RRH (algorithm for recovery and isolation exploiting semantics with restricted repeating of history) is presented which is a modified version of the ARIES transaction recovery and concurrency control method implemented to varying degrees in Starburst, QuickSilver, the OS/2 Extended Edition Database Manager, DB2 V2, Workstation Data Save Facility/VM and the Gamma database machine. The repeating history paradigm of ARIES is analyzed to propose a more efficient handling of redos, especially when the smallest granularity of locking is not less than a page, by combining the paradigm of selective redo from DB2 V1. Even with fine-granularity locking, it is not always the case that all the unapplied but logged changes needed to be redone. ARIES-RRH, which incorporates these changes, still retains all the good properties of ARIES-avoiding undo of undos, single-pass media recovery, nested top actions, etc. The fundamentals behind why DB2 V1's selective redo works, in spite of failures during restart recovery, are also explained.>

No abstract available.

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.

A locking protocol is a set of rules governing the manner in which the database entities may be accessed. Such a protocol usually employs several kinds of locks. Most of the previous work in this area has assumed that once a transaction acquires a particular kind of lock on a data item it is not allowed to convert this lock to another kind. In this paper we perform a systematic study of the consequences of allowing lock conversions in non-two-phase locking protocols, and show how this leads to increased concurrency and affects deadlock-freedom. The non-two-phase protocols that we study are the very general guard protocols defined for databases in which a directed acyclic graph structure can be superimposed on the data items. We present very natural generalizations of these protocols, including correctness proofs, and develop deadlock removal methods.

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.

This paper describes an application of Byzantine Agreement [DoSt82a, DoSt82c, LyFF82] to distributed transaction commit. We replace the second phase of one of the commit algorithms of [MoLi83] with Byzantine Agreement, providing certain trade-offs and advantages at the time of commit and providing speed advantages at the time of recovery from failure. The present work differs from that presented in [DoSt82b] by increasing the scope (handling a general tree of processes, and multi-cluster transactions) and by providing an explicit set of recovery algorithms. We also provide a model for classifying failures that allows comparisons to be made among various proposed distributed commit algorithms. The context for our work is the Highly Available Systems project at the IBM San Jose Research Laboratory [AAFKM83].

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.

Research on concurrency control mechanisms for database systems has had as a primary goal the discovery of techniques for allowing increased levels of concurrent execution of transactions. In this paper, we study this problem in the context of non-two-phase locking protocols which are defined for data bases in which a directed acyclic graph structure is superimposed on the data items. We introduce a new lock mode, called INV, with properties fundamentally different from locking modes previously studied and show how this allows increased concurrency. Through the introduction of the INV mode of locking we have enunciated a new principle of the theory of data base concurrency control. This principle involves the separation of the effects of the commutativity and compatibility of data manipulation operations. We then examine how the introduction of such a lock mode affects the occurrence of deadlocks in a system. Certain conditions under which deadlock-freedom is maintained are identified, and simple methods for removing deadlocks in other situations are presented.

A data base design methodology which utilizes multiple levels of design abstraction is outlined. An example of the design of conceptual, logical and physical data base structures utilizing this methodology is presented. The importance of a good conceptual schema model is emphasized and a two-step conceptual schema design process is proposed. The design of logical and physical schemas is illustrated for a CODASYL model environment, taking into consideration the 1978 CODASYL DDL and DSDL specifications.