Concurrency and recovery for index trees with nodal updates usin

Details Concurrency and recovery for index trees with nodal updates usin Concurrency and recovery for index trees with nodal updates usin

1991-06-25

1994-01-04

Lee, Thomas C.

Boots, shoes, and leggings

3642819, 3642851, 364DIG1, 3642821, 3642823, 3642831, G06F 1100

Patent

active

052768724

ABSTRACT:
The present invention includes an approach to index tree structure changes which provides high concurrency while being usable with many recovery schemes and with many varieties of index trees. The present invention permits multiple concurrent structure changes. In addition, all update activity and structure change activity above the data level executes in short independent atomic actions which do not impede normal database activity. Only data node splitting executes in the context of a database transaction. This feature makes the approach usable with diverse recovery mechanisms, while only impacting concurrency in a modest way. Even this impact can be avoided by re-packaging the atomic actions, at the cost of requiring more from the recovery system.

REFERENCES:
C. Mohan et al., "Aries/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging", Aug. 29, 1989.
C. J. Date, An Introduction to Database Systems, 1986, pp. 63-67 pp. 413-416.
[BASc] Bayer, R., Schkolnick, M., Concurrency of Operations on B-Trees, Acta Informatica, vol. 9 (1977) pp. 1-21.
[EGLT] Eswaren, K., Gray, J., Lorie R. and Traiger, I., The Notions of Consistency and Predicate Locks in a Database System, Communications of ACM vol. 19, No. 11 (Nov. 1976) pp. 624-633.
[LeYa] Lehman, P., Yao, S. B., Efficient Locking for Concurrent Operations on B-Trees, ACM Trans on Database Systems, vol. 6, No. 4 (Dec. 1981) pp. 650-670.
[Lom1] Lomet, D. B. Process structuring, synchronization, and recovery using atomic actions, Proc. ACM Conf. on Language Design for Reliable Software, SIGPLAN Notices 12, 3 (Mar. 1977) pp. 128-137.
[Lom2] Lomet, D. B. Subsystems of Processes with Deadlock Avoidance, IEEE Trans. on Software Engineering, vol. SE-6, No. 3 (May 1980) pp. 297-304.
[LoSa1] Lomet, D., Salzberg, B., Access Methods for Multiversion Data, Proc. ACM SIGMOD Conf. 1989, Portland, OR., pp. 315-324.
[LoSa2] Lomet, D., Salzberg, B. The hB-Tree: a Multiattribute Indexing Method with Good Guarantee Performance [to appear in] ACM Trans on Database Systems, vol. 15, No. 4 (Dec. 1990).
[MHLPS] Aries: A Transaction Recovery Method Supporting Fine-Granularity Locking and Parial Rollbacks Using Write-Ahead Logging, IBM Research Report RJ 6649, (Jan. 1989) IBM Almaden Research Center, San Jose, Calif.
[Sagi] Sagiv, Y., Concurrent Operations on B* trees with overtaking, Journal of Computer and System Sciences, vol. 33, No. 2 (1986) pp. 275-296.
[Salz] Salzberg., B., Restructuring the Lehman-Yao tree, Northeastern University Technical Report TR BS-85-21 (1985), Boston, Mass.
[ShGo] Shasha, D., Goodman, N. Concurrent Search Structure Algorithms, ACM Trans. on Database Systems, vol. 13, No. 1 (Mar. 1988) pp. 53-90.

Affiliated with

Also associated with

Rating

Concurrency and recovery for index trees with nodal updates usin does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Concurrency and recovery for index trees with nodal updates usin, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Concurrency and recovery for index trees with nodal updates usin will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-315737