Path: news.easynews.com!newsfeed1.easynews.com!easynews.com!easynews!newsfeed.news2me.com!newsfeed-west.nntpserver.com!hub1.meganetnews.com!nntpserver.com!telocity-west!DIRECTV!203.109.225.2!nntp-relay.ihug.net!ihug.co.nz!news-hog.berkeley.edu!ucberkeley!newsfeed.stanford.edu!postnews1.google.com!not-for-mail
From: 6tc1@qlink.queensu.ca (Novice)
Newsgroups: comp.databases,comp.databases.theory
Subject: Deadlock in Index (where index is B+ tree) Locking with Intention Locks
Date: 12 Dec 2002 09:07:19 -0800
Organization: http://groups.google.com/
Lines: 39
Message-ID: <b80e4a77.0212120907.7cfb153d@posting.google.com>
NNTP-Posting-Host: 130.15.1.203
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1039712839 8235 127.0.0.1 (12 Dec 2002 17:07:19 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 12 Dec 2002 17:07:19 GMT
Xref: newsfeed1.easynews.com comp.databases:96536 comp.databases.theory:24062
X-Received-Date: Thu, 12 Dec 2002 10:06:53 MST (news.easynews.com)

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

Also in class, the professor gave us a simple example of deadlock
occurring in the tree, if bi-directional traversal (traversing both up
and down the tree) is allowed.  This is very easy to understand how
deadlock can occur in this case.

But I can't come up with an example of deadlock occuring in a tree
based structure when you don't allow this bi-directional traversal.

For example, in the following tree:
http://www.cs.queensu.ca/~cassidy/media/images/tree.jpg

let's say that there are two transactions:
T1 and T2

And they all want to delete database objects - you'll notice in some
cases that an X (exclusive lock) is obtained on the inner nodes of the
tree and not in others.  This is because in some cases the B+ tree's
index will change if one of it's node's order falls beneath its
predefined number and this change could perculate up the tree.

And let's imagine the following scenario:
T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D)
U(B) U(root)
T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
U(B) U(root)
T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
U(B) U(root)

There is no permutation I could find of the above that would result in
deadlock.

If you can think of a more simple set of transactions that would
result in deadlock I would also be interested in that.

Thanks for any suggestions,
Tim