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

"Novice" <6tc1_at_qlink.queensu.ca> wrote in message news:b80e4a77.0212120907.7cfb153d_at_posting.google.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.
>

Assuming the multiple granularity locking protocol with 2PL, would the following schedule achieve the effect you are looking for?

Time | T1           | T2           | T3
-----|--------------|--------------|------------------
T1   | IX(root)     |              |
T2   | IX(B)        |              |
T3   | IX(D)        |              |
T4   | IX(H)        |              |
T5   |              |              | IX(root)
T6   |              |              | IX(B)
T7   |              |              | IX(D)
T8   |              |              | IX(G)
T9   | X(P)         |              |
T10  |              | IX(root)     |
T11  |              | IX(B)        |
T12  |              | IX(D)        |
T13  |              | IX(H)        |
T14  |              | IX(O)        |
T15  |              | waiting X(H) |
T16  | waiting X(H) | waiting X(H) |
T17  | waiting X(H) | waiting X(H) | X(N)
T17  | waiting X(H) | waiting X(H) | X(G)
T18  | waiting X(H) | waiting X(H) | waiting X(O)
T19  | waiting X(H) | waiting X(H) | waiting X(O)

I am also assuming that alternative locking protocols such as B-link trees are not considered in the question you pose.

Dan
> 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
Received on Fri Dec 13 2002 - 21:56:32 CET