Consistency and Orderability: Semantics-Based Correctness Criteria for Databases.
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)@article{DBLP:journals/tods/AgrawalAS93,
author = {Divyakant Agrawal and
Amr El Abbadi and
Ambuj K. Singh},
title = {Consistency and Orderability: Semantics-Based Correctness Criteria
for Databases},
journal = {ACM Trans. Database Syst.},
volume = {18},
number = {3},
year = {1993},
pages = {460-486},
ee = {http://doi.acm.org/10.1145/155271.155276, db/journals/tods/AgrawalAS93.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
The semantics of objects and transactions in database systems are investigated. User-defined predicates called consistency assertions are used to specify user programs. Three new correctness criteria are proposed. The first correctness criterion consistency is based solely on the users' specifications and admit nonserializable executions that are acceptable to the users. Integrity constraints of the database are maintained through consistency assertions. The second correctness criterion orderability is a generalization of view serializability and represents a weak notion of equivalence to a serial schedule. Finally, the third correctness criterion strong order-ability is introduced as a generalization of conflict serializability. Unlike consistency, the notions of orderability allow users to operate an isolation as maintenance of the integrity constrainst now becomes the responsibility of the database system.
Copyright © 1993 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.
CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
[Abstract and Index Terms]
[Full Text in PDF Format, 1876 KB]
References
- [1]
- Serge Abiteboul, Victor Vianu:
Transactions and Integrity Constraints.
PODS 1985: 193-204 BibTeX
- [2]
- B. R. Badrinath, Krithi Ramamritham:
Semantics-Based Concurrency Control: Beyond Commutativity.
ICDE 1987: 304-311 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, 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]
- Stefan Böttcher, Matthias Jarke, Joachim W. Schmidt:
Adaptive Predicate Managers in Database Systems.
VLDB 1986: 21-29 BibTeX
- [6]
- Edsger W. Dijkstra:
A Discipline of Programming.
Prentice-Hall 1976
BibTeX
- [7]
- 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
- [8]
- Abdel Aziz Farrag, M. Tamer Özsu:
Using Semantic Knowledge of Transactions to Increase Concurrency.
ACM Trans. Database Syst. 14(4): 503-525(1989) BibTeX
- [9]
- Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl:
Commutativity-Based Locking for Nested Transactions.
POS 1989: 319-340 BibTeX
- [10]
- Hector Garcia-Molina:
Using Semantic Knowledge for Transaction Processing in Distributed Database.
ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX
- [11]
- Dieter Gawlick, David Kinkade:
Varieties of Concurrency Control in IMS/VS Fast Path.
IEEE Database Eng. Bull. 8(2): 3-10(1985) BibTeX
- [12]
- Jim Gray:
The Transaction Concept: Virtues and Limitations (Invited Paper).
VLDB 1981: 144-154 BibTeX
- [13]
- John V. Guttag, James J. Horning:
Report on the Larch Shared Language.
Sci. Comput. Program. 6(2): 103-134(1986) BibTeX
- [14]
- Thanasis Hadzilacos, Vassos Hadzilacos:
Transaction Synchronisation in Object Bases.
PODS 1988: 193-200 BibTeX
- [15]
- Theo Härder:
Handling hot spot in DB-sharing systems.
Inf. Syst. 13(2): 155-166(1988) BibTeX
- [16]
- Maurice Herlihy:
A Quorum-Consensus Replication Method for Abstract Data Types.
ACM Trans. Comput. Syst. 4(1): 32-53(1986) BibTeX
- [17]
- Maurice Herlihy, William E. Weihl:
Hybrid Concurrency Control for Abstract Data Types.
J. Comput. Syst. Sci. 43(1): 25-61(1991) BibTeX
- [18]
- C. A. R. Hoare:
An Axiomatic Basis for Computer Programming.
Commun. ACM 12(10): 576-580(1969) BibTeX
- [19]
- C. A. R. Hoare:
Proof of Correctness of Data Representations.
Acta Inf. 1: 271-281(1972) BibTeX
- [20]
- Harry B. Hunt III, Daniel J. Rosenkrantz:
The Complexity of Testing Predicate Locks.
SIGMOD Conference 1979: 127-133 BibTeX
- [21]
- Edgar Knapp:
Deadlock Detection in Distributed Databases.
ACM Comput. Surv. 19(4): 303-328(1987) BibTeX
- [22]
- Henry F. Korth:
Locking Primitives in a Database System.
J. ACM 30(1): 55-79(1983) BibTeX
- [23]
- Henry F. Korth, Gregory D. Speegle:
Formal Model of Correctness Without Serializability.
SIGMOD Conference 1988: 379-386 BibTeX
- [24]
- Henry F. Korth, Eliezer Levy, Abraham Silberschatz:
A Formal Approach to Recovery by Compensating Transactions.
VLDB 1990: 95-106 BibTeX
- [25]
- ...
- [26]
- Nancy A. Lynch:
Multilevel Atomicity - A New Correctness Criterion for Database Concurrency Control.
ACM Trans. Database Syst. 8(4): 484-502(1983) BibTeX
- [27]
- C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz:
ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging.
ACM Trans. Database Syst. 17(1): 94-162(1992) BibTeX
- [28]
- Patrick E. O'Neil:
The Escrow Transactional Method.
ACM Trans. Database Syst. 11(4): 405-430(1986) BibTeX
- [29]
- Christos H. Papadimitriou:
The serializability of concurrent database updates.
J. ACM 26(4): 631-653(1979) BibTeX
- [30]
- Andreas Reuter:
Concurrency on High-trafic Data Elements.
PODS 1982: 83-92 BibTeX
- [31]
- Helmut Wächter, Andreas Reuter:
The ConTract Model.
Database Transaction Models for Advanced Applications 1992: 219-263 BibTeX
- [32]
- Peter M. Schwarz, Alfred Z. Spector:
Synchronizing Shared Abstract Types.
ACM Trans. Comput. Syst. 2(3): 223-250(1984) BibTeX
- [33]
- ...
- [34]
- Victor Vianu, Gottfried Vossen:
Conceptual Level Concurrency Control of Relational Update Transactions.
ICDT 1988: 353-367 BibTeX
- [35]
- William E. Weihl:
Commutativity-Based Concurrency Control for Abstract Data Types.
IEEE Trans. Computers 37(12): 1488-1505(1988) BibTeX
- [36]
- William E. Weihl:
Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types.
ACM Trans. Program. Lang. Syst. 11(2): 249-283(1989) BibTeX
- [37]
- William E. Weihl:
The Impact of Recovery on Concurrency Control.
PODS 1989: 259-269 BibTeX
- [38]
- William E. Weihl, Barbara Liskov:
Implementation of Resilient, Atomic Data Types.
ACM Trans. Program. Lang. Syst. 7(2): 244-269(1985) BibTeX
- [39]
- Gerhard Weikum:
A Theoretical Foundation of Multi-Level Concurrency Control.
PODS 1986: 31-43 BibTeX
- [40]
- Gerhard Weikum:
Principles and Realization Strategies of Multilevel Transaction Management.
ACM Trans. Database Syst. 16(1): 132-180(1991) BibTeX
- [41]
- Gerhard Weikum, Christof Hasse, Peter Brössler, Peter Muth:
Multi-Level Recovery.
PODS 1990: 109-123 BibTeX
Referenced by
- Arthur J. Bernstein, David Scott Gerstl, Wai-Hong Leung, Philip M. Lewis:
Design and Performance of an Assertional Concurrency Control System.
ICDE 1998: 436-445
- Tetsuya Furukawa, Haiyan Xu, Yihua Shi:
Supporting Collaborative Work by Process-Based Transaction Model.
ER Workshops 1998: 421-433
- Paul Ammann, Sushil Jajodia, Indrakshi Ray:
Applying Formal Methods to Semantic-Based Decomposition of Transactions.
ACM Trans. Database Syst. 22(2): 215-254(1997)
- Paul Ammann, Sushil Jajodia, Indrakshi Ray:
Using Formal Methods to Reason about Semantics-Based Decompositions of Transactions.
VLDB 1995: 218-227
- Munindar P. Singh:
Semantical Considerations on Workflows: An Algebra for Intertask Dependencies.
DBPL 1995: 5
- Man Hon Wong, Divyakant Agrawal:
Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems.
PODS 1992: 236-245
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:15 2008