|
 ABSTRACT
Most current approaches to concurrency control in database systems rely on locking of data objects as a control mechanism. In this paper, two families of nonlocking concurrency controls are presented. The methods used are “optimistic” in the sense that they rely mainly on transaction backup as a control mechanism, “hoping” that conflicts between transactions will not occur. Applications for which these methods should be more efficient than locking are discussed.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Inf. 1, 3 (1972), 173-189.
|
| |
2
|
BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. Acta Inf. 9, 1 (1977), 1-21.
|
| |
3
|
ELLIS, C.S. Concurrency search and insertion in 2-3 trees. Acta Inf. 14, 1 (1980), 63-86.
|
 |
4
|
|
| |
5
|
|
| |
6
|
|
| |
7
|
|
| |
8
|
LAMPORT, L. Towards a theory of correctness for multi-user data base systems. Tech. Rep. CA- 7610-0712, Massachusetts Computer Associates, Inc., Wakefield, Mass., Oct. 1976.
|
| |
9
|
LEHMAN, P. L., AND YAO, S.B. Efficient locking for concurrent operations on B-trees. Submitted for publication.
|
| |
10
|
MILLER, R. E., AND SNYDER, L. Multiple access to B-trees. Presented at Proc. Conf. Information Sciences and Systems, Johns Hopkins Univ., Baltimore, Md., Max. 1978.
|
| |
11
|
PAPADIMITRIOU, C. H., BERNSTEIN, P. A., AND ROTHNIE, J.B. Computational problems related to database concurrency control. In Conf Theoretical Computer Science, Univ. Waterloo, 1977, pp. 275-282.
|
| |
12
|
|
| |
13
|
SAMADI, B. B-trees in a system with multiple users. Inf. Process. Lett. 5, 4 (Oct. 1976), I07-112.
|
| |
14
|
STEARNS, R. E., LEWIS, P. M., II, AND ROSENKRANTZ, D.J. Concurrency control for database systems. In Proc. 7th Syrup. Foundations of Computer Science, I976, pp. I9-32.
|
| |
15
|
YAo, A. On random 2-3 trees. Acta Inf. 2, 9 (1978), 159-170.
|
CITED BY 245
|
|
|
|
|
|
|
|
|
|
|
Kyu-Young Whang , Art Ammann , Anthony Bolmarcich , Maria Hanrahan , Guy Hochgesang , Kuan-Tsae Huang , Al Khorasani , Ravi Krishnamurthy , Gary Sockut , Paula Sweeney , Vance Waddle , Moshé Zloof, Office-by-example: an integrated office system and database manager, ACM Transactions on Information Systems (TOIS), v.5 n.4, p.393-427, Oct. 1987
|
|
|
|
|
|
|
|
|
|
|
|
J. Karszt , G. Lausen , W. Stucky, Datenbank-Pascal an extendable database management system for personal computer networks, Proceedings of the 1983 ACM SIGSMALL symposium on Personal and small computers, p.253-265, December 07-09, 1983, San Diego, California, United States
|
|
|
Andreas R. Diener , Richard P. Brägger , Andreas Dudler , Carl A. Zehnder, Replicating and allocating data in a distributed database system for workstations, Proceedings of the 1985 ACM SIGSMALL symposium on Small systems, p.5-9, May 1985, Danvers, Massachusetts, United States
|
|
|
|
|
|
D. Agrawal , A. El Abbadi , R. Jeffers, An approach to eliminate transaction blocking in locking protocols, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.223-235, June 02-05, 1992, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T. F. Bowen , G. Gopal , G. Herman , T. Hickey , K. C. Lee , W. H. Mansfield , J. Raitz , A. Weinrib, The Datacycle architecture, Communications of the ACM, v.35 n.12, p.71-81, Dec. 1992
|
|
|
William Weihl , Barbara Liskov, Specification and implementation of resilient, atomic data types, Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems, p.53-64, June 27-29, 1983, San Francisco, California, United States
|
|
|
|
|
|
San-Yih Hwang , Jiandong Huang , Jaideep Srivastava, Concurrency control in federated databases: a dynamic approach, Proceedings of the second international conference on Information and knowledge management, p.694-703, November 01-05, 1993, Washington, D.C., United States
|
|
|
John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishan Gummadi , Sean Rhea , Hakim Weatherspoon , Westley Weimer , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, ACM SIGPLAN Notices, v.35 n.11, p.190-201, Nov. 2000
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
SangKeun Lee , Chong-Sun Hwang , WonGye Lee, A uniform approach to global concurrency control and recovery in multidatabase environment, Proceedings of the sixth international conference on Information and knowledge management, p.51-58, November 10-14, 1997, Las Vegas, Nevada, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Abdelsalam Helal , Tung-Hui Ku , Jud Fortner, Quasi-dynamic two-phase locking, Proceedings of the third international conference on Information and knowledge management, p.211-218, November 29-December 02, 1994, Gaithersburg, Maryland, United States
|
|
|
SangKeun Lee , Chong-Sun Hwang , HeongChang Yu, Supporting transactional cache consistency in mobile database systems, Proceedings of the 1st ACM international workshop on Data engineering for wireless and mobile access, p.6-13, August 20-20, 1999, Seattle, Washington, United States
|
|
|
|
|
|
|
|
|
|
|
|
John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, ACM SIGARCH Computer Architecture News, v.28 n.5, p.190-201, Dec. 2000
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jayant R. Haritsa , Michael J. Carey , Miron Livny, On being optimistic about real-time constraints, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-343, April 02-04, 1990, Nashville, Tennessee, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Brian Bennett , Bill Hahm , Avrahm Leff , Thomas Mikalsen , Kevin Rasmus , James Rayfield , Isabelle Rouvellou, A distributed object oriented framework to offer transactional support for long running business processes, IFIP/ACM International Conference on Distributed systems platforms, p.331-348, April 03-07, 2000, New York, New York, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T. Bindhammer , R. Göckelmann , O. Marquardt , M. Schöttner , M. Wende , P. Schulthess, Device driver programming in a transactional DSM operating system, Australian Computer Science Communications, v.24 n.3, p.65-71, January-February 2002
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Anne-Marie Kermarrec , Antony Rowstron , Marc Shapiro , Peter Druschel, The IceCube approach to the reconciliation of divergent replicas, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.210-218, August 2001, Newport, Rhode Island, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Leonard Kawell, Jr. , Steven Beckhardt , Timothy Halvorsen , Raymond Ozzie , Irene Greif, Replicated document management in a group communication system, Proceedings of the 1988 ACM conference on Computer-supported cooperative work, September 26-28, 1988, Portland, Oregon, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), ACM SIGOPS Operating Systems Review, v.38 n.5, December 2004
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Kwok-Wa Lam , William Leung , Richard J. Millar , J. R. Paul Hanna, Performance study of using a new approach to transaction processing in real-time systems, Proceedings of the 17th IASTED international conference on Modelling and simulation, p.296-301, May 24-26, 2006, Montreal, Canada
|
|
|
Tatiana Shpeisman , Vijay Menon , Ali-Reza Adl-Tabatabai , Steven Balensiefer , Dan Grossman , Richard L. Hudson , Katherine F. Moore , Bratin Saha, Enforcing isolation and ordering in STM, ACM SIGPLAN Notices, v.42 n.6, June 2007
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael Stonebraker , Samuel Madden , Daniel J. Abadi , Stavros Harizopoulos , Nabil Hachem , Pat Helland, The end of an architectural era: (it's time for a complete rewrite), Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, ACM SIGARCH Computer Architecture News, v.32 n.2, p.102, March 2004
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stavros Harizopoulos , Daniel J. Abadi , Samuel Madden , Michael Stonebraker, OLTP through the looking glass, and what we found there, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Phil McGachey , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Vijay Menon , Bratin Saha , Tatiana Shpeisman, Concurrent GC leveraging transactional memory, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Seth H. Pugsley , Manu Awasthi , Niti Madan , Naveen Muralimanohar , Rajeev Balasubramonian, Scalable and reliable communication for hardware transactional memory, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada
|
|
|
Zachary G. Ives , Todd J. Green , Grigoris Karvounarakis , Nicholas E. Taylor , Val Tannen , Partha Pratim Talukdar , Marie Jacob , Fernando Pereira, The ORCHESTRA Collaborative Data Sharing System, ACM SIGMOD Record, v.37 n.3, September 2008
|
|
|
|
|
|
|
|
|
|
|
|
Xiaoyong Chai , Ba-Quy Vuong , AnHai Doan , Jeffrey F. Naughton, Efficiently incorporating user feedback into information extraction and integration programs, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
H.2