Patent
1993-04-14
1997-12-23
Kriess, Kevin A.
39518217, G06F 1500
Patent
active
057014809
ABSTRACT:
In a multi-version database, copies of prior committed versions (snapshots) are kept for access by the read-only transactions. The read-write transactions are selectively aborted to enforce an order of commitment of read-write transactions that is the same as an order of conflicts among the read-write transactions. In a preferred embodiment, the read-write transactions are serialized by maintaining and referencing a graph of conflicts among read-write transactions, and the read-only transactions are serialized by a timestamp mechanism for selection of the snapshots to be read. Each time that a read-write transaction is committed, the read-write transaction is assigned a unique timestamp that is used to timestamp all resources committed by the read-write transaction. Upon starting, each read-only transaction is also assigned a timestamp. Each read-only transaction reads only the latest committed versions of all resources, that are timestamped earlier than the timestamp of the read-only transaction. In a multiprocessing system, the timestamps are issued to global coordinators and distributed locally with atomic commit messages and global queries. Moreover, read-write transactions may selectively access a hierarchy of uncommitted versions to prepare for various possible commitment orders. The hierarchy defines a path for record access and for cascading aborts. A plurality of mutually-conflicting uncommitted versions may be prepared for each transaction to prepare for all possible commitment orders.
REFERENCES:
patent: 4224664 (1980-09-01), Trinchieri
patent: 4249241 (1981-02-01), Aberle et al.
patent: 4627019 (1986-12-01), Ng
patent: 4881166 (1989-11-01), Thompson et al.
patent: 5193188 (1993-03-01), Franaszek et al.
patent: 5212788 (1993-05-01), Lomet et al.
patent: 5263156 (1993-11-01), Bowen et al.
patent: 5369757 (1994-11-01), Spiro et al.
patent: 5504900 (1996-04-01), Raz
H.F. Korth & A. Silberschatz, Database System Concepts, McGraw-Hill, Inc., United States, pp. xiv-xix, 490-503 (1991).
Vassos Hadzilacos, "A Knowledge Theoretic Analysis of Atomic Commitment Protocols," Proc. of the Sixth ACM Symposium on Principles of Database Systems, Association for Computing Machinery, New York, NY, Mar. 23-25, 1987. pp. 129-134.
Joseph Y. Halpern, "Using Reasoning about Knowledge to Analyze Distributed Systems," Research Report RJ 5522 (56421) Mar. 3, 1987, Computer Science, IBM Almaden Research Center, San Jose, California, 1987.
Lampson et al., "Crash Recovery in a Distributed Data Storage System," Technical Report, Xerox, Palo Alto Research Center, Palo Alto, California, 1986.
Litwin et al., "Flexible Concurrency Control Using Value Dates," in Integration of Information Systems: Bridging Heterogeneous Databases, ed. A Gupta, IEEE Press. IEEE, New York, NY, 1989, pp. 144-145.
Weihl, "Distributed Version Management for Read-Only Actions," IEEE Transactions on Software Engineering, vol. SE-13, No. 1, IEEE, New York, NY, Jan. 1987, pp. 55-64.
Christos Papadimitriou, The Theory Database Concurrency Control, Computer Science Press, Inc., Rockville, Maryland, (1986), pp. 93-158, 201-224.
Vassos Hadzilacos, "A Theory of Reliability in Database Systems, " Journal of the ACM, vol. 35, No. 1, Jan., 1988, pp. 121-145, Association for Computing Machinery, New York, New York.
Agrawal et al., "Modular Synchronization in Multiversion Databases: Version Control and Concurrency Control," Proc. of the 1989 ACM SIGMOD Int. Conf. on Management of Data, pp. 408-417, Portland, Oregon, Jun., 1989 Association for Computing Machinery, New York N.Y.
Raghavan et al., "Database Availability for Transaction Processing," Digital Technical Journal, vol. 3, No. 1, Winter 1991, pp. 65-69, Digital Equipment Corp., Maynard, Mass. 1991.
Bober et al., "Multiversion Query Locking," Proc. of the Eighteenth Int. Conf. on Very Large Databases, Vancouver, British Columbia, (Aug. 1992), pp. 497-510.
Agrawal et al., "An Approach to Eliminate Transaction Blocking in Locking Protocols," Proc. of the Eleventh ACM Symposium on Principles of Database Systems, San Diego Calif. (Jun. 1992), pp. 223-235.
Bober et al., "On Mixing Queries and Transactions Via Multiversion Locking, " Proc. of the Eighth Int. Conf. on Data Engineering, Tempe, (Feb. 1992), pp. 535-545.
Vaijalainen et al., "Prepare and Commit Certification for Decentralized Transaction Management in Rigorous Heterogeneous Multidatabase," IEEE, New York, N.Y. (1992), pp. 470-479.
Mohan et al., "Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions," 1992 ACM SIGMOND Conf. Assoc.-Computing Machinery, New York, NY (Jun. 1992), pp. 124-133.
Silberschatz et al., "Database Systems: Achievements and Opportunities," Communications of the ACM, vol. 34, No. 10, Association for Computing Machinery, New York, N.Y., Oct., 1991, pp. 110, 120.
Breitbart et al., "On Rigorous Transaction Scheduling," IEEE Transactions on Software Engineering, vol. 17, No. 9, IEEE, New York, NY (Sept. 1991).
Agrawal et al., "Performance Characteristics of Protocols With Ordered Shared Locks," Proceedings of the Seventh IEEE International Conference on Data Engineering, Institute of Electrical and Electronics Engineers, New York, N.Y. (Apr. 1991), pp. 592-601.
Georgakopoulos et al., "On Serializability of Multidatabase Transactions through Forced Local Conflicts," Proceedings of the Seventh Int. Conf. on Data Engineering, Kobe, Japan (Apr. 1991).
L. Hobbs et al., "Rdb/VMS--A Comprehensive Guide", Digital Press, Digital Equipment Corporation, Maynard, Mass., 1991.
David Lomet, "Consistent Timestamping for Transactions in Distributed Systems," TR CRL 90/3, Digital Equipment Corporation, CRL, Cambridge, Mass. (Sep. 1990).
Sheth et al., "Federated Database System for Managing Distributed Hetergeneous and Autonomous Databases," ACM Computing Surveys, Col. 22, No. 3, Assoc. for Computing Machinery, New York, N.Y. (Sep. 1990), pp. 183-236.
Y. Breitbart, "Multidatabase Inoperability," Sigmond Record, vol. 19, No. 3, Assoc. for Computing Machinery, New York, N.Y. (Sep. 1990), pp. 53-60.
Breitbart et al., "Reliable Transaction Management in a Multidatabase System," Proc. of the ACM SIGMOD Conf. on Management of data, Atlantic City, New Jersey (Jun. 1990), pp. 215-224.
Agrawal et al., "Locks with Constrained Sharing," Proceedings of the Nineth ACM Symposium on Principles of Database Systems, Association for Computing Machinery, New York, N.Y. (Apr. 1990), pp. 85-93.
Elmagarmid et al., "A Paradigm for Concurrency Control in Heterogeneous Distributed Database Systems," IEEE, New York, N.Y. (1990), pp. 17-46.
Georgakopoulos et al., "Transaction Management in Multidatabase Systems," Technical Report #UH-CS-89-20, Depart. of Computer Science, University of Houston, Houston, Texas (Sep. 1989).
Calton Pu, "Transactions across Heterogeneous Databases: the Superdatabase Architecture," Department of Computer Science, Columbia University, New York, N.Y. (Jun. 1988), pp. 1-18.
Carlton Pu, "Superdatabase for Composition of Heterogeneous Databases," 4th International Conference on Data Engineering, Los Angeles, California IEEE, New York, N.Y. (Feb. 1-5, 1988), pp. 548-555.
Garcia-Molina et al., "Node Autonomy in Distributed Systems," IEEE, New York, N.Y. (1988), pp. 158-166.
William E. Weihl, "Distributed Version Management for Read-Only Actions," IEEE Transactions on Software Engineering, vol. SE-13, No. 1, IEEE, New York, N.Y. (Jan. 1987), pp. 55-64.
Bernstein et al., "Concurrency Control and Recovery in Database Systems," Addison-Wesley, Reading, Mass. (1987), pp. 58-78.
Chan et al., "Implementing Distributed Read-Only Transactions," IEEE Transactions on Software Engineering, vol. SE-11, No. 2, IEEE, New York, N.Y. (Feb. 1985), pp. 205-212.
J. Eliot B. Moss, Nested Transactions, The MIT Press, Cambridge, Mass. (1985).
Kung et al., "On Optimistic Methods for Concurrency Control," ACM Transactions on Database Systems, vol. 6, No. 2, Columbus, Ohio (Jun. 1981), pp. 213-226.
Jim Gray, "Operating Systems: An Advanced Course," Lecture Notes in Computer Science 60, IBM Research Lab
Chaki Kakali
Digital Equipment Corporation
Kriess Kevin A.
LandOfFree
Distributed multi-version commitment ordering protocols for guar does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed multi-version commitment ordering protocols for guar, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed multi-version commitment ordering protocols for guar will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1808321