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

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

or

  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