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

A Serialization Graph Construction for Nested Transactions.

Alan Fekete, Nancy A. Lynch, William E. Weihl: A Serialization Graph Construction for Nested Transactions. PODS 1990: 94-108
@inproceedings{DBLP:conf/pods/FeketeLW90,
  author    = {Alan Fekete and
               Nancy A. Lynch and
               William E. Weihl},
  title     = {A Serialization Graph Construction for Nested Transactions},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {94-108},
  ee        = {http://doi.acm.org/10.1145/298514.298547, db/conf/pods/FeketeLW90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper makes three contributions. First, we present a proof technique that offers system designers the same ease of reasoning about nested transaction systems as is given by the classical theory for systems without nesting, and yet can be used to verify that a system satisfies the robust "user view" definition of correctness of [10]. Second, as applications of the technique, we verify the correctness of Moss' read/write locking algorithm for nested transactions, and of an undo logging algorithm that has not previously been presented or proved for nested transaction systems. Third, we make explicit the assumptions used for this proof technique, assumptions that are usually made implicitly in the classical theory, and therefore we clarify the type of system for which the classical theory itself can reliably be used.

Copyright © 1990 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 Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee. ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
James Aspnes, Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl: A Theory of Timestamp-Based Concurrency Control for Nested Transactions. VLDB 1988: 431-444 BibTeX
[2]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) BibTeX
[3]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[4]
Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl: Nested Transactions and Read/Write Locking. PODS 1987: 97-111 BibTeX
[5]
Alan Fekete, Nancy A. Lynch, Michael Merritt, William E. Weihl: Commutativity-Based Locking for Nested Transactions. J. Comput. Syst. Sci. 41(1): 65-156(1990) BibTeX
[6]
Kenneth J. Goldman, Nancy A. Lynch: Quorum Consensus in Nested Transaction Systems. PODC 1987: 27-41 BibTeX
[7]
Thanasis Hadzilacos, Vassos Hadzilacos: Transaction Synchronisation in Object Bases. PODS 1988: 193-200 BibTeX
[8]
Maurice Herlihy, Nancy A. Lynch, Michael Merritt, William E. Weihl: On the Correctness of Orphan Management Algorithms. J. ACM 39(4): 881-930(1992) BibTeX
[9]
Barbara Liskov: Distributed Programming in Argus. Commun. ACM 31(3): 300-312(1988) BibTeX
[10]
Nancy A. Lynch, Michael Merritt: Introduction to the Theory of Nested Transactions. Theor. Comput. Sci. 62(1-2): 123-185(1988) BibTeX
[11]
Nancy A. Lynch, Michael Merritt, William E. Weihl, Alan Fekete: A Theory of Atomic Transactions. ICDT 1988: 41-71 BibTeX
[12]
Nancy A. Lynch, Mark R. Tuttle: Hierarchical Correctness Proofs for Distributed Algorithms. PODC 1987: 137-151 BibTeX
[13]
...
[14]
...
[15]
...
[16]
William E. Weihl: The Impact of Recovery on Concurrency Control. PODS 1989: 259-269 BibTeX
[17]
William E. Weihl: Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM Trans. Program. Lang. Syst. 11(2): 249-283(1989) BibTeX
[18]
...

Referenced by

  1. Krithi Ramamritham, Panos K. Chrysanthis: A Taxonomy of Correctness Criteria in Database Applications. VLDB J. 5(1): 85-97(1996)
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:33:59 2009