| The notions of consistency and predicate locks in a database system |
| Full text |
Pdf
(1.06 MB)
|
Source
|
Communications of the ACM
archive
Volume 19 , Issue 11 (November 1976)
table of contents
Pages: 624 - 633
Year of Publication: 1976
ISSN:0001-0782
|
|
Authors
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 30, Downloads (12 Months): 206, Citation Count: 503
|
|
|
ABSTRACT
In database systems, users access shared data under the assumption that the data satisfies certain consistency constraints. This paper defines the concepts of transaction, consistency and schedule and shows that consistency requires that a transaction cannot request new locks after releasing a lock. Then it is argued that a transaction needs to lock a logical rather than a physical subset of the database. These subsets may be specified by predicates. An implementation of predicate locks which satisfies the consistency condition is suggested.
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
|
|
 |
2
|
|
| |
3
|
Chamberlin, D.D., Boyce, R.F., Traiger, I.L. A deadlockfree scheme for resource locking in a data-base environment, Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp.340-343.
|
 |
4
|
|
| |
5
|
Kleene, S.C. Introduction to Metamathematics. Van Nostrand, Princeton, N.J., 1952, p. 204.
|
| |
6
|
IBM Information Management System for Virtual Storage (IMS/VS), Conversion and Planning Guide. Form No. SH20- 9034, IBM, Armonk, N.Y., 1973, pp. 38-44.
|
| |
7
|
CODASYL, Data Base Task Group Report. ACM, N.Y., 1971.
|
| |
8
|
Eswaran, K.P., Gray, J.N., Lorie, R.A., and Traiger, I.L. On the notions of consistency and predicate locks in a data base system. Res. Rep., RJ 1487, IBM Res. Lab., San Jose, Calif., 1974.
|
CITED BY 504
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Gomer Thomas , Glenn R. Thompson , Chin-Wan Chung , Edward Barkmeyer , Fred Carter , Marjorie Templeton , Stephen Fox , Berl Hartman, Heterogeneous distributed database systems for production use, ACM Computing Surveys (CSUR), v.22 n.3, p.237-266, Sept. 1990
|
|
|
|
|
|
|
|
|
Arvola Chan , Stephen Fox , Wen-Te K. Lin , Anil Nori , Daniel R. Ries, The implementation of an integrated concurrency control and recovery scheme, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
M. J. Stucki , J. R. Cox, Jr. , G. C. Roman , P. N. Turcu, Coordinating concurrent access in a distributed database architecture, Proceedings of the fourth workshop on Computer architecture for non-numeric processing, p.60-64, August 01-04, 1978, Blue Mountain Lake, New York, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Francisco J. Torres-Rojas , Mustaque Ahamad , Michel Raynal, Timed consistency for shared distributed objects, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.163-172, May 04-06, 1999, Atlanta, Georgia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C. Pu , C. H. Hong , J. M. Wha, Performance evaluation of global reading of entire databases, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.167-176, December 05-07, 1988, Austin, Texas, United States
|
|
|
|
|
|
|
|
|
J. B. Rothnie, Jr. , P. A. Bernstein , S. Fox , N. Goodman , M. Hammer , T. A. Landers , C. Reeve , D. W. Shipman , E. Wong, Introduction to a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.1-17, March 1980
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Donald D. Chamberlin , Morton M. Astrahan , Michael W. Blasgen , James N. Gray , W. Frank King , Bruce G. Lindsay , Raymond Lorie , James W. Mehl , Thomas G. Price , Franco Putzolu , Patricia Griffiths Selinger , Mario Schkolnick , Donald R. Slutz , Irving L. Traiger , Bradford W. Wade , Robert A. Yost, A history and evaluation of System R, Communications of the ACM, v.24 n.10, p.632-646, Oct. 1981
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
Alfred Z. Spector , Dean Daniels , Daniel Duchamp , Jeffrey L. Eppinger , Randy Pausch, Distributed transactions for reliable systems, ACM SIGOPS Operating Systems Review, v.19 n.5, p.127-146, Dec. 1-4, 1985
|
|
|
|
|
|
|
|
|
Matthew J. Weinstein , Thomas W. Page, Jr. , Brian K. Livezey , Gerald J. Popek, Transactions and synchronization in a distributed operating system, ACM SIGOPS Operating Systems Review, v.19 n.5, p.115-126, Dec. 1-4, 1985
|
|
|
Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hal Berenson , Phil Bernstein , Jim Gray , Jim Melton , Elizabeth O'Neil , Patrick O'Neil, A critique of ANSI SQL isolation levels, ACM SIGMOD Record, v.24 n.2, p.1-10, May 1995
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A. Fekete , N. Lynch , M. Merrit , W. Weihl, Nested transactions and read-write locking, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.97-111, March 23-25, 1987, San Diego, California, 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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D. Agrawal , J. L. Bruno , A. El Abbadi , V. Krishnaswamy, Relative serializability (extended abstract): an approach for relaxing the atomicity of transactions, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-149, May 24-27, 1994, Minneapolis, Minnesota, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I. Widya , T. G. R. van Leuken , P. van der Wolf, Concurrency control in a VLSI design database, Proceedings of the 25th ACM/IEEE conference on Design automation, p.357-362, June 12-15, 1988, Atlantic City, New Jersey, United States
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Gopi K. Attaluri , Jacob Slonim , Per-Åke Larson, Concurrency control with lock preemption and restoration, Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p.2, November 07-09, 1995, Toronto, Ontario, Canada
|
|
|
|
|
|
|
|
|
Nathan Goodman , Dale Skeen , Arvola Chan , Umeshwar Dayal , Stephen Fox , Daniel Ries, A recovery algorithm for a distributed database system, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
Wei-hsing Wang , Meichun Hsu , Eugene Pinsky, Modeling hot spots in database systems (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.82-91, May 29-31, 1991, Denver, Colorado, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L. Raschid , T. Sellis , C. C. Lin, Exploiting concurrency in a DBMS implementation for production systems, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.34-45, December 05-07, 1988, Austin, Texas, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Vinay K. Chaudhri , Vassos Hadzilacos , John Mylopoulos , Kenneth C. Sevcik, Quantitative evaluation of a transaction facility for knowledge base management system, Proceedings of the third international conference on Information and knowledge management, p.122-131, November 29-December 02, 1994, Gaithersburg, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C. Beeri , P. A. Bernstein , N. Goodman , M. Y. Lai , D. E. Shasha, A concurrency control theory for nested transactions (Preliminary Report), Proceedings of the second annual ACM symposium on Principles of distributed computing, p.45-62, August 17-19, 1983, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stanley Y. W. Su , Ramamohanrao Jawadi , Prashant Cherukuri , Qiang Li , Richard Nartey, OSAM*.KBMS/P: A Parallel, Active, Object-Oriented Knowledge Base Server, IEEE Transactions on Knowledge and Data Engineering, v.10 n.1, p.55-75, January 1998
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yifeng Zhu , Hong Jiang , Xiao Qin , Dan Feng , David R. Swanson, Design, implementation and performance evaluation of a cost-effective, fault-tolerant parallel virtual file system, Proceedings of the international workshop on Storage network architecture and parallel I/Os, p.53-64, September 28-28, 2003, New Orleans, Louisiana
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michel E. Adiba , Jean-Claude Chupin , Robert Demolombe , Georges Gardarin , Jean Le Bihan, Issues in distributed data base management systems: a technical overview, Proceedings of the fourth international conference on Very Large Data Bases, p.89-110, September 13-15, 1978, West Berlin, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rakesh Agrawal , Roberto Bayardo , Christos Faloutsos , Jerry Kiernan , Ralf Rantzau , Ramakrishnan Srikant, Auditing compliance with a Hippocratic database, Proceedings of the Thirtieth international conference on Very large data bases, p.516-527, August 31-September 03, 2004, Toronto, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C. V. Ramamoorthy , Gary S. Ho , T. Kirshnarao , Benjamin W. Wah, Architectural issues in distributed data base systems, Proceedings of the third international conference on Very large data bases, p.121-126, October 06-08, 1977, Tokyo, Japan
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jan Edler , Allan Gottlieb , Clyde P. Kruskal , Kevin P. McAuliffe , Larry Rudolph , Marc Snir , Patricia J. Teller , James Wilson, Issues related to MIMD shared-memory computers: the NYU ultracomputer approach, ACM SIGARCH Computer Architecture News, v.13 n.3, p.126-135, June 1985
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sten Andler , I. Ding , Kapali P. Eswaran , C. Hauser , Won Kim , James W. Mehl , R. Williams, System D: A Distributed System for Availability, Proceedings of the 8th International Conference on Very Large Data Bases, p.33-44, September 08-10, 1982
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jiangming Yang , Haixun Wang , Ning Gu , Yiming Liu , Chunsong Wang , Qiwei Zhang, Lock-free consistency control for web 2.0 applications, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|