Many database systems support data processing transactions at multiple user sites. For example, a transaction operating at a particular user site may access a primary copy of a data item or record of a central database, while transactions at other user sites utilize replicated versions of the data item. A significant problem arises when the transactions at the different user sites attempt to update different replicated versions of the same data item, which may result in inconsistent replicated versions of a given data item. The problem of concurrent access to consistent replicated data has become increasingly challenging with the advent of large-scale distributed data warehouses and data marts, and the increasing use of distributed data in often-disconnected mobile computers. For example, data warehouses or data marts are now typically configured with storage capacities on the order of 0.5 to 3 terabytes, with approximately 10% to 25% of the stored data items being used in a replicated form, and about 10% of the data items being updated each day. These systems may require that all data item updates be reflected within a relatively short time period, such as 10 minutes or less. Other features of distributed database systems are described in, for example, A. A. Helal, A. A. Heddaya and B. B. Bhargava, "Replication Techniques in Distributed Systems," Kluwer Academic Publishers, 1996; C. Pu and A. Leff, "Replica Control in Distributed Systems: an Asynchronous Approach," Proceedings of ACM-SIGMOD 1991 International Conference on Management of Data, Denver, Colo., pp.377-386, May 1991; and J. Sidell, P. M. Aoki, S. Barr, A. Sah, C. Staelin, M. Stonebraker and A. Yu, "Data Replication in Mariposa," Proceedings of the Twelfth International Conference on Data Engineering, New Orleans, La., 1996, all of which are incorporated by reference herein.
In order to ensure that multiple concurrent transactions have access to consistent replicated data, it is important to determine whether a proposed schedule of transaction operations is globally serializable. A schedule of transaction operations is "serializable" if running the transactions concurrently in accordance with the schedule yields the same results as running the transactions in some sequential order. Global serializability refers to serializability as applied to execution of all transactions in a system regardless of the physical sites at which particular transactions operate. The serializability of a given schedule of transaction operations depends in large part on the techniques used to update replicated data items. A number of so-called "eager" update propagation techniques are described in E. Holler, "Multiple Copy Update," Lecture Notes in Computer Science, Distributed Systems-Architecture and Implementation: An Advanced Course, Springer-Verlag, Berlin, 1981, which is incorporated by reference herein. However, these techniques are often unsuitable for use with large-scale distributed systems. In a typical eager propagation technique, the number of deadlocks, in which two or more transactions simultaneously attempt to update a replica or primary copy of the same data item, increases as the cube of the number of user sites and as the fourth power of transaction size. This is particularly problematic with relatively long data-mining queries, which typically access many different data items, and with mobile transactions which effectively live for a long period of time if the portable computer or other mobile computing device is disconnected. Deadlocks are thus no longer rare events with a negligible impact on performance, but instead present a substantial barrier to the efficient operation of large-scale distributed database systems.
Other known update techniques, generally referred to as "lazy" propagation techniques, address the above-described update propagation problem. Under lazy propagation, only one replica of a particular data item is updated by a transaction utilizing that data item. A separate transaction runs on behalf of the original transaction at each site at which update propagation is required. Lazy propagation effectively reduces transaction size but creates the possibility of two or more transactions committing conflicting updates to a data item if the transactions operate on different replicas. For example, a transaction T.sub.1 could update a data item d using the replica at a site s.sub.1 while a transaction T.sub.2 updates the replica of d at another site s.sub.2. If both transactions T.sub.1 and T.sub.2 commit an update of their replicas of the data item, the distributed system discovers the conflict only when the updates are propagated. Such conflicts may require either update reconciliation or the use of compensating transactions, as described in H. F. Korth, E. Levy and A. Silberschatz, "A Formal Approach to Recovery by Compensating Transactions," Proceedings of the Sixteenth International Conference on Very Large Databases, Brisbane, Australia, pp. 95-106, August, 1990, which is incorporated by reference herein. Consistency can be ensured despite lazy propagation by directing all updates to a primary copy of the data item, and employing an appropriate concurrency-control protocol. The process of directing all updates to a primary copy of the data item is referred to as the lazy-master approach to update regulation in J. Gray, P. Helland, P. O'Neil and D. Shasha, "The Dangers of Replication and a Solution," Proceedings of ACM-SIGMOD 1996 International Conference on Management of Data, Montreal, Quebec, pp. 173-182, 1996, which is incorporated by reference herein. Unfortunately, previous techniques for managing transaction updates in accordance with the lazy-master approach either fail to guarantee consistency, or are subject to a prohibitive number of deadlocks, or both.
Conventional lazy propagation techniques may also cause an update transaction to read "old" replicas of some data items, resulting in an execution that generates an inconsistent database state. As an example, consider a bank database for checking and savings accounts that is distributed over two sites s.sub.1 and s.sub.2. Site s.sub.1 contains the primary copy of the checking-account relation and a replica of the savings-account relation, while site s.sub.2 contains the primary copy of the savings-account relation and a replica of the checking-account relation. The bank requires only that the sum of a customer's checking and savings accounts be positive. Suppose that a husband and wife have joint checking and savings accounts and the balances in these two accounts are $300 and $700, respectively. The husband withdraws $900 from the checking account using an ATM at s.sub.1 and, at approximately the same time, the wife withdraws $900 from the savings account using an ATM at s.sub.2. Due to the delay in update propagation resulting from use of a lazy propagation approach, both transactions may succeed. However, after the updates are propagated, both accounts have a negative balance, violating the bank's constraint that the sum of the balances must be positive. Conventional lazy propagation techniques generally have difficulty avoiding this type of inconsistency. The problem may be alleviated to some extent by augmenting the lazy-master approach with restrictions on how the primary copies of data items are selected, as described in P. Chundi, D. J. Rosenkrantz and S. S. Ravi, "Deferred Updates and Data Placement in Distributed Databases," Proceedings of the Twelfth International Conference on Data Engineering, New Orleans, La., 1996, which is incorporated by reference herein. However, the resulting update propagation remains unduly susceptible to deadlocks and therefore is unsuitable for use in applications such as large-scale distributed systems with mobile computers.
It is therefore apparent that a need exists for an improved technique for providing update propagation and other concurrency-control operations in a distributed database system in which replicated data items are processed at multiple sites, such that global serializability of a transaction schedule can be ensured, while the likelihood of deadlocks is substantially reduced and other problems associated with the conventional approaches are avoided.