A Taxonomy of Correctness Criteria in Database Applications.

@article{DBLP:journals/vldb/RamamrithamC96,
  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, http://dblp.uni-trier.de}
}

Abstract

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

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)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An4-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

B. R. Badrinath, Krithi Ramamritham: Performance Evaluation of Semantics-based Multilevel Concurrency Control Protocols. SIGMOD Conference 1990: 163-172 BibTeX

[2]

Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991) BibTeX

[3]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) BibTeX

[4]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX

[5]

...

[6]

Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz: On Rigorous Transaction Scheduling. IEEE Trans. Software Eng. 17(9): 954-960(1991) BibTeX

[7]

Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz: Overview of Multidatabase Transaction Management. VLDB J. 1(2): 181-239(1992) BibTeX

[8]

...

[9]

Panos K. Chrysanthis, Krithi Ramamritham: ACTA: A Framework for Specifying and Reasoning about Transaction Structure and Behavior. SIGMOD Conference 1990: 194-203 BibTeX

[10]

Panos K. Chrysanthis, Krithi Ramamritham: A Formalism for Extended Transaction Model. VLDB 1991: 103-112 BibTeX

[11]

Panos K. Chrysanthis, Krithi Ramamritham: ACTA: The SAGA Continues. Database Transaction Models for Advanced Applications 1992: 349-397 BibTeX

[12]

Panos K. Chrysanthis, S. Raghuram, Krithi Ramamritham: Extracting Concurrency from Objects: A Methodology. SIGMOD Conference 1991: 108-117 BibTeX

[13]

Umeshwar Dayal, Meichun Hsu, Rivka Ladin: Organizing Long-Running Activities with Triggers and Transactions. SIGMOD Conference 1990: 204-214 BibTeX

[14]

Umeshwar Dayal, Klaus R. Dittrich: Active Database Systems (Abstract). VLDB 1991: 209 BibTeX

[15]

Weimin Du, Ahmed K. Elmagarmid: Quasi Serializability: a Correctness Criterion for Global Concurrency Control in InterBase. VLDB 1989: 347-355 BibTeX

[16]

Ahmed K. Elmagarmid (Ed.): Database Transaction Models for Advanced Applications. Morgan Kaufmann 1992, ISBN 1-55860-214-3
Contents BibTeX

[17]

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

[18]

Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989) BibTeX

[19]

Alan Fekete, Nancy A. Lynch, William E. Weihl: A Serialization Graph Construction for Nested Transactions. PODS 1990: 94-108 BibTeX

[20]

Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX

[21]

Hector Garcia-Molina, Kenneth Salem: Sagas. SIGMOD Conference 1987: 249-259 BibTeX

[22]

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

[23]

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

[24]

Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210 BibTeX

[25]

Maurice Herlihy, Jeannette M. Wing: Axioms for Concurrent Objects. POPL 1987: 13-26 BibTeX

[26]

Wen-Chi Hou, Gultekin Özsoyoglu, Baldeo K. Taneja: Processing Aggregate Relational Queries with Hard Time Constraints. SIGMOD Conference 1989: 68-77 BibTeX

[27]

Henry F. Korth, Gregory D. Speegle: Formal Model of Correctness Without Serializability. SIGMOD Conference 1988: 379-386 BibTeX

[28]

Henry F. Korth, Won Kim, François Bancilhon: On Long-Duration CAD Transactions. Inf. Sci. 46(1-2): 73-107(1988) BibTeX

[29]

...

[30]

Henry F. Korth, Eliezer Levy, Abraham Silberschatz: A Formal Approach to Recovery by Compensating Transactions. VLDB 1990: 95-106 BibTeX

[31]

Henry F. Korth, Nandit Soparkar, Abraham Silberschatz: Triggered Real-Time Databases with Consistency Constraints. VLDB 1990: 71-82 BibTeX

[32]

Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX

[33]

...

[34]

Bruce E. Martin, Claus H. Pedersen: Long-Lived Concurrency Activities. IWDOM 1992: 188-206 BibTeX

[35]

Sharad Mehrotra, Rajeev Rastogi, Henry F. Korth, Abraham Silberschatz: Non-Serializable Executions in Heterogeneous Distributed Database Systems. PDIS 1991: 245-252 BibTeX

[36]

Sharad Mehrotra, Rajeev Rastogi, Yuri Breitbart, Henry F. Korth, Abraham Silberschatz: Ensuring Transaction Atomicity in Multidatabase Systems. PODS 1992: 164-175 BibTeX

[37]

...

[38]

J. Eliot B. Moss, Nancy D. Griffeth, Marc H. Graham: Abstraction in Recovery Management. SIGMOD Conference 1986: 72-83 BibTeX

[39]

Patrick E. O'Neil: The Escrow Transactional Method. ACM Trans. Database Syst. 11(4): 405-430(1986) BibTeX

[40]

Calton Pu, Avraham Leff: Replica Control in Distributed Systems: An Asynchronous Approach. SIGMOD Conference 1991: 377-386 BibTeX

[41]

Calton Pu, Gail E. Kaiser, Norman C. Hutchinson: Split-Transactions for Open-Ended Activities. VLDB 1988: 26-37 BibTeX

[42]

Krithi Ramamritham: Real-Time Databases. Distributed and Parallel Databases 1(2): 199-226(1993) BibTeX

[43]

Krithi Ramamritham, Calton Pu: A Formal Characterization of Epsilon Serializability. IEEE Trans. Knowl. Data Eng. 7(6): 997-1007(1995) BibTeX

[44]

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

[45]

Marek Rusinkiewicz, Amit P. Sheth, George Karabatis: Specifying Interdatabase Dependencies in a Multidatabase Environment. IEEE Computer 24(12): 46-53(1991) BibTeX

[46]

...

[47]

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

[48]

...

[49]

Amit P. Sheth, Marek Rusinkiewicz, George Karabatis: Using Polytransactions to Manage Interdependent Data. Database Transaction Models for Advanced Applications 1992: 555-581 BibTeX

[50]

...

[51]

...

[52]

Andreas Reuter, Helmut Wächter: The ConTract Model. IEEE Data Eng. Bull. 14(1): 39-43(1991) BibTeX

[53]

Gerhard Weikum, Hans-Jörg Schek: Architectural Issues of Transaction Management in Multi-Layered Systems. VLDB 1984: 454-465 BibTeX

[54]

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