Simple rational guidance for chopping up transactions

Dennis Shasha, Eric Simon, Patrick Valcluriez

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Chopping transactions into pieces is good for performance but may lead to non-serializable executions. Many research ers 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 l has only the degree 2 and degree 3 consistency options offered by the vast majority of conventions] database systems; and knows the set of transactions that may run during a certain interval (users are likely to Jrave such knowledge for online or real-time transactional applications). Given this information, our algorifhm finds the finest parfifioning of a set of transactions TranSet with the following property: if the partitioned transactions execute serializable, then TranSet executes serializable. This permits users to obtain more concurrency while preserving correctness. Besides obtaining more inter-transaction concurrency, chopping transactions in this way can enhance intra-transaction parallelism. The algorithm is inexpensive, running in O(n x (e + m)) time using a naive implementation where n is the number of concurrent transactions in fhe 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 pracfical Systems.

Original languageEnglish (US)
Title of host publicationProceedings of the 1992 ACM SIGMOD International Conference on Management of Data, SIGMOD 1992
EditorsMichael Stonebraker
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)0897915216
StatePublished - Jun 2 1992
Event1992 ACM SIGMOD International Conference on Management of Data, SIGMOD 1992 - San Diego, United States
Duration: Jun 2 1992Jun 5 1992

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
VolumePart F129624
ISSN (Print)0730-8078


Other1992 ACM SIGMOD International Conference on Management of Data, SIGMOD 1992
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Software
  • Information Systems


Dive into the research topics of 'Simple rational guidance for chopping up transactions'. Together they form a unique fingerprint.

Cite this