A Taxonomy of Correctness Criteria in Database Applications.

Krithi Ramamritham, Panos K. Chrysanthis: A Taxonomy of Correctness Criteria in Database Applications. VLDB J. 5(1): 85-97(1996)
  author    = {Krithi Ramamritham and
               Panos K. Chrysanthis},
  title     = {A Taxonomy of Correctness Criteria in Database Applications},
  journal   = {VLDB J.},
  volume    = {5},
  number    = {1},
  year      = {1996},
  pages     = {85-97},
  ee        = {db/journals/vldb/RamamrithamC96.html},
  bibsource = {DBLP,}


Whereas serializability captures database consistency requirements and transaction correctness properties via a single notion, recent research has attempted to come up with correctness criteria that view these two types of requirements independently. The search for more flexible correctness criteria is partily motivated by the introduction of new transaction models that extend the traditional atomic transaction model. These extensions came about because the atomic transaction model in conjunction with serializability is found to be very constraining when used in advanced applications (e.g., design databases) that function in distributed, cooperative, and heterogeneous environments.

In this article we develop a taxonomy of various correctness criteria that focus on database consistency requirements and transaction correctness properties from the viewpoint of what the different dimensions of these two are. This taxonomy allows us to categorize correctness criteria that have been proposed in the literature. To help in this categorization, we have applied a uniform specification technique, based on ACTA, to express the various criteria. Such a categorization helps shed light on the similarities and differences between different criteria and places them in perspective.

Key Words

Transaction Processing, concurrency control, database correctness criteria, formal specifications.

Copyright © 1996 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


B. R. Badrinath, Krithi Ramamritham: Performance Evaluation of Semantics-based Multilevel Concurrency Control Protocols. SIGMOD Conference 1990: 163-172 BibTeX
Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991) BibTeX
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) BibTeX
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz: On Rigorous Transaction Scheduling. IEEE Trans. Software Eng. 17(9): 954-960(1991) BibTeX
Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz: Overview of Multidatabase Transaction Management. VLDB J. 1(2): 181-239(1992) BibTeX
Panos K. Chrysanthis, Krithi Ramamritham: ACTA: A Framework for Specifying and Reasoning about Transaction Structure and Behavior. SIGMOD Conference 1990: 194-203 BibTeX
Panos K. Chrysanthis, Krithi Ramamritham: A Formalism for Extended Transaction Model. VLDB 1991: 103-112 BibTeX
Panos K. Chrysanthis, Krithi Ramamritham: ACTA: The SAGA Continues. Database Transaction Models for Advanced Applications 1992: 349-397 BibTeX
Panos K. Chrysanthis, S. Raghuram, Krithi Ramamritham: Extracting Concurrency from Objects: A Methodology. SIGMOD Conference 1991: 108-117 BibTeX
Umeshwar Dayal, Meichun Hsu, Rivka Ladin: Organizing Long-Running Activities with Triggers and Transactions. SIGMOD Conference 1990: 204-214 BibTeX
Umeshwar Dayal, Klaus R. Dittrich: Active Database Systems (Abstract). VLDB 1991: 209 BibTeX
Weimin Du, Ahmed K. Elmagarmid: Quasi Serializability: a Correctness Criterion for Global Concurrency Control in InterBase. VLDB 1989: 347-355 BibTeX
Ahmed K. Elmagarmid (Ed.): Database Transaction Models for Advanced Applications. Morgan Kaufmann 1992, ISBN 1-55860-214-3
Contents BibTeX
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
Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989) BibTeX
Alan Fekete, Nancy A. Lynch, William E. Weihl: A Serialization Graph Construction for Nested Transactions. PODS 1990: 94-108 BibTeX
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
Hector Garcia-Molina, Kenneth Salem: Sagas. SIGMOD Conference 1987: 249-259 BibTeX
Hector Garcia-Molina, Dieter Gawlick, Johannes Klein, Karl Kleissner, Kenneth Salem: Modeling Long-Running Activities as Nested Sagas. IEEE Data Eng. Bull. 14(1): 14-18(1991) BibTeX
Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, Irving L. Traiger: Granularity of Locks in a Large Shared Data Base. VLDB 1975: 428-451 BibTeX
Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210 BibTeX
Maurice Herlihy, Jeannette M. Wing: Axioms for Concurrent Objects. POPL 1987: 13-26 BibTeX
Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Processing Aggregate Relational Queries with Hard Time Constraints. SIGMOD Conference 1989: 68-77 BibTeX
Henry F. Korth, Gregory D. Speegle: Formal Model of Correctness Without Serializability. SIGMOD Conference 1988: 379-386 BibTeX
Henry F. Korth, Won Kim, François Bancilhon: On Long-Duration CAD Transactions. Inf. Sci. 46(1-2): 73-107(1988) BibTeX
Henry F. Korth, Eliezer Levy, Abraham Silberschatz: A Formal Approach to Recovery by Compensating Transactions. VLDB 1990: 95-106 BibTeX
Henry F. Korth, Nandit Soparkar, Abraham Silberschatz: Triggered Real-Time Databases with Consistency Constraints. VLDB 1990: 71-82 BibTeX
Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX
Bruce E. Martin, Claus H. Pedersen: Long-Lived Concurrency Activities. IWDOM 1992: 188-206 BibTeX
Sharad Mehrotra, Rajeev Rastogi, Henry F. Korth, Abraham Silberschatz: Non-Serializable Executions in Heterogeneous Distributed Database Systems. PDIS 1991: 245-252 BibTeX
Sharad Mehrotra, Rajeev Rastogi, Yuri Breitbart, Henry F. Korth, Abraham Silberschatz: Ensuring Transaction Atomicity in Multidatabase Systems. PODS 1992: 164-175 BibTeX
J. Eliot B. Moss, Nancy D. Griffeth, Marc H. Graham: Abstraction in Recovery Management. SIGMOD Conference 1986: 72-83 BibTeX
Patrick E. O'Neil: The Escrow Transactional Method. ACM Trans. Database Syst. 11(4): 405-430(1986) BibTeX
Calton Pu, Avraham Leff: Replica Control in Distributed Systems: An Asynchronous Approach. SIGMOD Conference 1991: 377-386 BibTeX
Calton Pu, Gail E. Kaiser, Norman C. Hutchinson: Split-Transactions for Open-Ended Activities. VLDB 1988: 26-37 BibTeX
Krithi Ramamritham: Real-Time Databases. Distributed and Parallel Databases 1(2): 199-226(1993) BibTeX
Krithi Ramamritham, Calton Pu: A Formal Characterization of Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 7(6): 997-1007(1995) BibTeX
Marek Rusinkiewicz, Ahmed K. Elmagarmid, Yungho Leu, Witold Litwin: Extending the Transaction Model to Capture more Meaning. SIGMOD Record 19(1): 3-7(1990) BibTeX
Marek Rusinkiewicz, Amit P. Sheth, George Karabatis: Specifying Interdatabase Dependencies in a Multidatabase Environment. IEEE Computer 24(12): 46-53(1991) BibTeX
Amit P. Sheth, Marek Rusinkiewicz: Management of Interdependent Data: Specifying Dependency and Consistency Requirements. Workshop on the Management of Replicated Data 1990: 133-136 BibTeX
Amit P. Sheth, Marek Rusinkiewicz, George Karabatis: Using Polytransactions to Manage Interdependent Data. Database Transaction Models for Advanced Applications 1992: 555-581 BibTeX
Andreas Reuter, Helmut Wächter: The ConTract Model. IEEE Data Eng. Bull. 14(1): 39-43(1991) BibTeX
Gerhard Weikum, Hans-Jörg Schek: Architectural Issues of Transaction Management in Multi-Layered Systems. VLDB 1984: 454-465 BibTeX
Mihalis Yannakakis: Serializability by Locking. J. ACM 31(2): 227-244(1984) BibTeX

Referenced by

  1. Jayavel Shanmugasundaram, Arvind Nithrakashyap, Rajendran M. Sivasankaran, Krithi Ramamritham: Efficient Concurrency Control for Broadcast Environments. SIGMOD Conference 1999: 85-96
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:31:27 2009