ACM SIGMOD Anthology TODS dblp.uni-trier.de

Formal Aspects of Concurrency Control in Long-Duration Transaction Systems Using the NT/PV Model.

Henry F. Korth, Gregory D. Speegle: Formal Aspects of Concurrency Control in Long-Duration Transaction Systems Using the NT/PV Model. ACM Trans. Database Syst. 19(3): 492-535(1994)
@article{DBLP:journals/tods/KorthS94,
  author    = {Henry F. Korth and
               Gregory D. Speegle},
  title     = {Formal Aspects of Concurrency Control in Long-Duration Transaction
               Systems Using the NT/PV Model},
  journal   = {ACM Trans. Database Syst.},
  volume    = {19},
  number    = {3},
  year      = {1994},
  pages     = {492-535},
  ee        = {http://doi.acm.org/10.1145/185827.185854, db/journals/tods/KorthS94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In the typical database system, an execution is correct if it is equivalent to some serial execution. This criterion, called serializability, is unacceptable for new database applications which require long-duration transactions. We present a new transaction model which allows correctness criteria more suitable for these applications. This model combines three enhancements to the standard model: nested transactions, explicit predicates, and multiple versions. These features yield the name of the new model, nested transactions with predicates and versions, or NT/PV.

The modular nature of the NT/PV model allows a straightforward representation of simple systems. It also provides a formal framework for describing complex interactions. The most complex interactions the model allows can be captured by a protocol which exploits all of the semantics available to the NT/PV model. An example of these interactions is shown in a CASE application. The example shows how a system based on the NT/PV model is superior to both standard database techniques and unrestricted systems in both correctness and performance.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 3154 KB]

References

[Agrawal and Sengupta 1989]
Divyakant Agrawal, Soumitra Sengupta: Modular Synchronization in Multiversion Databases: versionControl and Concurrency Control. SIGMOD Conference 1989: 408-417 BibTeX
[Bancilhon et al. 1985]
François Bancilhon, Won Kim, Henry F. Korth: A Model of CAD Transactions. VLDB 1985: 25-33 BibTeX
[Barghouti and Kaiser 1991]
Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991) BibTeX
[Beeri et al. 1989]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) BibTeX
[Bernstein et al. 1987]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[Chrysanthis and Ramamritham 1992]
Panos K. Chrysanthis, Krithi Ramamritham: ACTA: The SAGA Continues. Database Transaction Models for Advanced Applications 1992: 349-397 BibTeX
[Chrysanthis and Ramamritham 1990]
Panos K. Chrysanthis, Krithi Ramamritham: ACTA: A Framework for Specifying and Reasoning about Transaction Structure and Behavior. SIGMOD Conference 1990: 194-203 BibTeX
[Conklin and Begeman 1988a]
Jeff Conklin, Michael L. Begeman: gIBIS: A Hypertext Tool for Exploratory Policy Discussion. ACM Trans. Inf. Syst. 6(4): 303-331(1988) BibTeX
[Conklin and Begeman 1988b]
...
[Dayal et al. 1990]
Umeshwar Dayal, Meichun Hsu, Rivka Ladin: Organizing Long-Running Activities with Triggers and Transactions. SIGMOD Conference 1990: 204-214 BibTeX
[Du and Ghanta 1987]
David Hung-Chang Du, Subbarao Ghanta: A Framework for Efficient IC/VLSI CAD Databases. ICDE 1987: 619-625 BibTeX
[Elmagarmid et al. 1990]
Ahmed K. Elmagarmid, Yungho Leu, Witold Litwin, Marek Rusinkiewicz: A Multidatabase Transaction Model for InterBase. VLDB 1990: 507-518 BibTeX
[Eswaran et al. 1976]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[Farrag and Özsu 1989]
Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989) BibTeX
[Garcia-Molina 1983]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
[Gray et al. 1975]
...
[Guindon and Curtis 1988]
...
[Guindon et al. 1988]
...
[Guindon et al. 1987]
...
[Haskin and Lorie 1982]
Roger L. Haskin, Raymond A. Lorie: On Extending the Functions of a Relational Database System. SIGMOD Conference 1982: 207-212 BibTeX
[Katz 1982]
...
[Kim 1990]
...
[Kim et al. 1984]
Won Kim, Raymond A. Lorie, Dan McNabb, Wil Plouffe: A Transaction Mechanism for Engineering Design Databases. VLDB 1984: 355-362 BibTeX
[Korth 1983]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX
[Korth and Speegle 1990a]
...
[Korth and Speegle 1990b]
...
[Korth and Speegle 1990c]
Henry F. Korth, Gregory D. Speegle: Long-Duration Transactions in Software Design Projects. ICDE 1990: 568-574 BibTeX
[Korth and Speegle 1988]
Henry F. Korth, Gregory D. Speegle: Formal Model of Correctness Without Serializability. SIGMOD Conference 1988: 379-386 BibTeX
[Korth et al. 1989]
...
[Korth et al. 1988]
...
[Korth et al. 1990]
Henry F. Korth, Eliezer Levy, Abraham Silberschatz: A Formal Approach to Recovery by Compensating Transactions. VLDB 1990: 95-106 BibTeX
[Lorie and Plouffe 1983]
...
[Lynch 1983]
Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX
[Lynch 1986]
Nancy A. Lynch: Concurrency Control for Resilient Nested Transactions. Advances in Computing Research 3: 335-373(1986) BibTeX
[McCune and Henschen 1989]
William McCune, Lawrence J. Henschen: Maintaining state constraints in relational databases: a proof theoretic basis. J. ACM 36(1): 46-68(1989) BibTeX
[Moss 1985]
...
[Papadimitriou 1986]
...
[Reddy et al. 1993]
Y. V. Ramana Reddy, Kankanahalli Srinivas, Vasudevan Jagannathan, Raghu Karinthi: Computer Support for Concurrent Engineering - Guest Editors' Introduction. IEEE Computer 26(1): 12-16(1993) BibTeX
[Reed 1983]
David P. Reed: Implementing Atomic Actions on Decentralized Data. ACM Trans. Comput. Syst. 1(1): 3-23(1983) BibTeX
[Speegle 1990]
...
[Speegle and Gordon 1992]
...
[Weikum 1991]
Gerhard Weikum: Principles and Realization Strategies of Multilevel Transaction Management. ACM Trans. Database Syst. 16(1): 132-180(1991) BibTeX

Referenced by

  1. Alexander Thomasian: Concurrency Control: Methods, Performance, and Analysis. ACM Comput. Surv. 30(1): 70-119(1998)
  2. Paul Ammann, Sushil Jajodia, Indrakshi Ray: Applying Formal Methods to Semantic-Based Decomposition of Transactions. ACM Trans. Database Syst. 22(2): 215-254(1997)
  3. Sanjay Kumar Madria, Bharat K. Bhargava: System Defined Prewrites for Increasing Concurrency in Databases. ADBIS 1997: 18-22
  4. Nandit Soparkar, Henry F. Korth, Abraham Silberschatz: Databases with Deadline and Contingency Constraints. IEEE Trans. Knowl. Data Eng. 7(4): 552-565(1995)
  5. Henry F. Korth: The Double Life of the Transaction Abstraction: Fundamental Principle and Evolving System Concept. VLDB 1995: 2-6
  6. Paul Ammann, Sushil Jajodia, Indrakshi Ray: Using Formal Methods to Reason about Semantics-Based Decompositions of Transactions. VLDB 1995: 218-227
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:17 2008