Re: Deadlock in Index (where index is B+ tree) Locking with Intention Locks

From: Jan Hidders <hidders_at_REMOVE.THIS.uia.ua.ac.be>
Date: 17 Dec 2002 14:22:40 +0100
Message-ID: <3dff2520$1_at_news.uia.ac.be>

Novice wrote:
>In class I was told that any locking protocol can result in deadlock
>when there is concurrency.

Actually, that is not completely true. It is well known that the socalled "tree locking protocol" which basically outlaws bi-directional traversal cannot dead-lock.

For references see:

SILBERSCHATZ, A. and KEDEM, Z. Consistency in hierarchical database systems. J. of the ACM 27,1 (January 1980) 72-80

Lanin, V. and Shasha, D. 1990. Tree Locking on Changing Trees. Technical Report 503, New York University. http://citeseer.nj.nec.com/lanin90tree.html

If you stick to 2PL then a transaction excludes all other operations of other transactions because it will lock the root, but the beauty of the tree locking protocol is that you don't have to stick to 2PL to guarantee serializability.

Jan Hidders

Received on Tue Dec 17 2002 - 14:22:40 CET

This message: [ Message body ]
Next message: Jone Smide: "Concorrency control"
Previous message: Jan Hidders: "Re: Normalizing the ER model"
In reply to: Novice: "Deadlock in Index (where index is B+ tree) Locking with Intention Locks"
In reply to Novice: "Deadlock in Index (where index is B+ tree) Locking with Intention Locks"
Next in thread: Tony V: "Re: Parts explosion with repeated subtrees"

Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ]

Original text of this message