Transaction chopping
- 1 September 1995
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 20 (3), 325-363
- https://doi.org/10.1145/211414.211427
Abstract
Chopping transactions into pieces is good for performance but may lead to nonserializable executions. Many researchers have reacted to this fact by either inventing new concurrency-control mechanisms, weakening serializability, or both. We adopt a different approach. We assume a user who —has access only to user-level tools such as (1) choosing isolation degrees 1ndash;4, (2) the ability to execute a portion of a transaction using multiversion read consistency, and (3) the ability to reorder the instructions in transaction programs; and —knows the set of transactions that may run during a certain interval (users are likely to have such knowledge for on-line or real-time transactional applications). Given this information, our algorithm finds the finest chopping of a set of transactions TranSet with the following property: If the pieces of the chopping execute serializably, then TranSet executes serializably . This permits users to obtain more concurrency while preserving correctness. Besides obtaining more intertransaction concurrency, chopping transactions in this way can enhance intratransaction parallelism. The algorithm is inexpensive, running in O(n×(e+m)) time, once conflicts are identified, using a naive implementation, where n is the number of concurrent transactions in the interval, e is the number of edges in the conflict graph among the transactions, and m is the maximum number of accesses of any transaction. This makes it feasible to add as a tuning knob to real systems.Keywords
This publication has 21 references indexed in Scilit:
- Analysis of database performance with dynamic lockingJournal of the ACM, 1990
- The virtues of locking by symbolic namesJournal of Algorithms, 1987
- Concurrency control performance modeling: alternatives and implicationsACM Transactions on Database Systems, 1987
- Partitioned two-phase lockingACM Transactions on Database Systems, 1986
- Consistency of transactions and random batchACM Transactions on Database Systems, 1986
- Multilevel atomicity—a new correctness criterion for database concurrency controlACM Transactions on Database Systems, 1983
- Using semantic knowledge for transaction processing in a distributed databaseACM Transactions on Database Systems, 1983
- A Theory of Safe Locking Policies in Database SystemsJournal of the ACM, 1982
- Concurrency control in a system for distributed databases (SDD-1)ACM Transactions on Database Systems, 1980
- Interval hierarchies and their application to predicate filesACM Transactions on Database Systems, 1977