dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

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)
@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

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 ...

References

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

Last update Fri Sep 14 18:29:10 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page