ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems.

Man Hon Wong, Divyakant Agrawal: Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems. PODS 1992: 236-245
@inproceedings{DBLP:conf/pods/WongA92,
  author    = {Man Hon Wong and
               Divyakant Agrawal},
  title     = {Tolerating Bounded Inconsistency for Increasing Concurrency in
               Database Systems},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
               California},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {236-245},
  ee        = {http://doi.acm.org/10.1145/137097.137880, db/conf/pods/WongA92.html},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Recently, the scope of databases has been extended to many non-standard applications, and serializability is found to be too restrictive for such applications. In general, two approaches are adopted to address this problem. The first approach considers placing more structure on data objects to exploit type specific properties while keeping serializability as the correctness criterion. The other approach uses explicit semantics of transactions and databases to permit interleaved executions of transactions that are non-serializable. In this paper, we attempt to bridge the gap between the two approaches by using the notion of serializability with bounded inconsistency. Users are free to specifiy the maximum level of inconsistency that can be allowed in the executions of operations dynamically. In particular, if no inconsistency is allowed in the execution of any operation, the protocol will be reduced to a standard strict two phase locking protocol based on type-specific semantics of data objects. Bounded inconsistency can be applied to many areas which do not require exact values of the data such as for gathering information for statistical purpose, for making high level decisions and reasoning in expert systems which can tolerate uncertainty in input data.

Copyright © 1992 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition: ACM Digital Library

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

References

[1]
Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh: Consistency and Orderability: Semantics-Based Correctness Criteria for Databases. ACM Trans. Database Syst. 18(3): 460-486(1993) BibTeX
[2]
B. R. Badrinath, Krithi Ramamritham: Semantics-Based Concurrency Control: Beyond Commutativity. ACM Trans. Database Syst. 17(1): 163-199(1992) BibTeX
[3]
Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991) BibTeX
[4]
Philip A. Bernstein, David W. Shipman, Wing S. Wong: Formal Aspects of Serializability in Database Concurrency Control. IEEE Trans. Software Eng. 5(3): 203-216(1979) BibTeX
[5]
Panos K. Chrysanthis, S. Raghuram, Krithi Ramamritham: Extracting Concurrency from Objects: A Methodology. SIGMOD Conference 1991: 108-117 BibTeX
[6]
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
[7]
Abdel Aziz Farrag, M. Tamer Özsu: Using Semantic Knowledge of Transactions to Increase Concurrency. ACM Trans. Database Syst. 14(4): 503-525(1989) BibTeX
[8]
Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
[9]
Hector Garcia-Molina, Kenneth Salem: Non-Deterministic Queue Operations. PODS 1991: 53-62 BibTeX
[10]
Thanasis Hadzilacos, Vassos Hadzilacos: Transaction Synchronisation in Object Bases. J. Comput. Syst. Sci. 43(1): 2-24(1991) BibTeX
[11]
Maurice Herlihy: A Quorum-Consensus Replication Method for Abstract Data Types. ACM Trans. Comput. Syst. 4(1): 32-53(1986) BibTeX
[12]
Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210 BibTeX
[13]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX
[14]
Nancy A. Lynch: Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control. ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX
[15]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[16]
Calton Pu, Avraham Leff: Replica Control in Distributed Systems: An Asynchronous Approach. SIGMOD Conference 1991: 377-386 BibTeX
[17]
Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) BibTeX
[18]
...
[19]
William E. Weihl: Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM Trans. Program. Lang. Syst. 11(2): 249-283(1989) BibTeX
[20]
William E. Weihl: The Impact of Recovery on Concurrency Control. PODS 1989: 259-269 BibTeX

Referenced by

  1. Sharad Mehrotra, Rajeev Rastogi, Henry F. Korth, Abraham Silberschatz: Ensuring Consistency in Multidatabases by Preserving Two-Level Serializability. ACM Trans. Database Syst. 23(2): 199-230(1998)
  2. Lisa Cingiser DiPippo, Victor Fay Wolfe: Object-Based Semantic Real-Time Concurrency Control with Bounded Imprecision. IEEE Trans. Knowl. Data Eng. 9(1): 135-147(1997)
  3. Man Hon Wong: Recovery for Transaction Failures in Object-Based Databases. PODS 1996: 139-149
  4. Hang Kwong Mak, Man Hon Wong: Trading Operation Consistency for Concurrency. DASFAA 1995: 405-412
  5. Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance: A Technique for Increasing Concurrency in a Replicated System. ACM Trans. Database Syst. 19(4): 586-625(1994)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:06 2009