Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-04-14
1999-01-26
Amsbury, Wayne
Data processing: database and file management or data structures
Database design
Data structure types
707102, 707203, G06F 1730
Patent
active
058648518
ABSTRACT:
Method and system for managing transactions operating on replicated data items at multiple physical sites in a distributed database system. The transactions include local transactions each being processed at one of the physical sites and global transactions each being processed at multiple physical sites. Each transaction originates at one of the physical sites, and is permitted to read data items only at that physical site. In addition, only transactions originating at a physical site at which a primary copy of a data item is located are permitted to update that data item. A number of virtual sites are defined such that a given virtual site VS.sub.i.sup.j at a particular point in time includes a set S.sub.i.sup.j of all data items at a physical site s.sub.j that a given transaction T.sub.i has accessed from an initial operation up to that point in time. A replication graph is maintained to represent the relationships between the transactions and the virtual sites. The replication graph includes a first set of nodes for the transactions, and a second set of nodes for the virtual sites. A node for a transaction T.sub.i and a node for a virtual site VS.sub.i.sup.j are connected in the graph if a schedule of transaction operations includes a write operation by transaction T.sub.i on a replicated data item in the set of data items associated with virtual site VS.sub.i.sup.j. The replication graph is maintained as part of a concurrency-control protocol and the absence of cycles in the graph may be used to indicate whether a given schedule is globally serializable.
REFERENCES:
patent: 4769772 (1988-09-01), Dwyer
patent: 5222217 (1993-06-01), Blount et al.
patent: 5241675 (1993-08-01), Sheth et al.
patent: 5280619 (1994-01-01), Wang
patent: 5504899 (1996-04-01), Raz
patent: 5530851 (1996-06-01), Fortier
A.A Helal, A.A. Heddaya and B.B. Bhargava, "Replication Techniques in Distributed Systems," Kluwer Academic Publishers, 1996.
C. Pu and A. Leff, "Replica Control in Distributed Systems: an Asynchronous Approach," Proceedings of ACM-SIGMOD 1991 International Conference on Management of Data, Denver, Colorado, pp.377-386, May 1991.
J. Sidell, P.M. Aoki, S. Barr, A. Sah, C. Staelin, M. Stonebraker and A. Yu, "Data Replication in Mariposa," Proceedings of the Twelfth International Conference on Data Engineering, New Orleans, Louisiana, 1996.
E. Holler, "Multiple Copy Update," Lecture Notes in Computer Science, Distributed Systems-Architecture and Implementation: An Advanced Course, Springer-Verlag, Berlin, 1981.
H.F. Korth, E. Levy and A. Silberschatz, "A Formal Approach to Recovery by Compensating Transactions," Proceedings of the Sixteenth International Conference on Very Large Databases, Brisbane, Australia, pp. 95-106, Aug., 1990.
J. Gray, P. Helland, P. O'Neil and D. Shasha, "The Dangers of Replication and a Solution," Proceedings of ACM-SIGMOD 1996 International Conference on Management of Data, Montreal, Quebec, pp. 173-182, 1996.
P. Chundi, D.J. Rosenkrantz and S.S. Ravi, "Deferred Updates and Data Placement in Distributed Databases," Proceedings of the Twelfth International Conference on Data Engineering, New Orleans, Louisiana, 1996.
H.F. Korth and T.I. Imielinski, "Introduction to Mobile Computing," in Mobile Computing, pp. 1-39, Kluwer Academic Publishers, 1996.
Y. Breitbart, H. Garcia-Molina and A. Silberschatz, "Overview of Multidatabase Transaction Management," VLDB Journal, 1(2), 1992.
C.A. Ellis, "Consistency and Correctness of Duplicate Database Systems," Operating Systems Review, 11(5), Nov. 1977.
R.H. Thomas, "A Solution to the Concurrency Control Problem for Multiple Copy Databases," CompCon78, 1978.
T. Minoura, "A New Concurrency Control Algorithm for Distributed Database Systems," Proceedings of the Fourth Berkeley Workshop on Distributed Databases and Computer Networks, pp. 221-234, Aug. 1979.
H.F. Korth et al., "A Framework for Understanding Distributed (Deadlock Detection) Algorithms," ACM 0-89791-097, pp. 192-201, 1983.
J. Gray, P. Homan, R. Obermarck and H. Korth, "A Strawman Analysis of Probability of Waiting and Deadlock," IBM Research Report, IBM Research Laboratory, San Jose, CA, Feb. 1981.
K.M. Chandy and J. Misra, "Distributed Deadlock Detection," ACM Transactions on Computer Systems, vol. 1, No. 2, pp. 144-156, May 1983.
E. Gelenbe and K. Sevcik, "Analysis of Update Synchronization for Multiple Copy Databases," Proceedings of the Third Berkeley Workshop on Distributed Databases and Computer Networks, pp. 69-90, Aug. 1978.
Breitbart Yuri
Korth Henry F.
Amsbury Wayne
Lucent Technologies - Inc.
LandOfFree
Method and system for managing replicated data with enhanced con does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for managing replicated data with enhanced con, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for managing replicated data with enhanced con will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1458681