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

[2]

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

[3]

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

[4]

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

[5]

...

[6]

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

[7]

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

[8]

...

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

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

[18]

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

[19]

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

[20]

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

[21]

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

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

[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

[24]

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

[25]

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

[26]

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

[27]

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

[28]

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

[29]

...

[30]

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

[31]

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

[32]

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

[33]

...

[34]

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

[35]

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

[36]

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

[37]

...

[38]

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

[39]

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

[40]

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

[41]

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

[42]

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

[43]

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

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

[45]

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

[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

[48]

...

[49]

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

[50]

...

[51]

...

[52]

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

[53]

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

[54]

Mihalis Yannakakis: Serializability by Locking. J. ACM 31(2): 227-244(1984)

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