Why is the tree protocol deadlock free?

Question

I have been reading about the tree protocol as an approach in locking management in databases. I read that it is deadlock free but I am not sure how it works.
Example:

Assume that T1 has locked B, D, E in exclusive mode.
According to the rules:

T2 can lock H (allowed by rule 2).
Now if T1 wants to lock H it can not despite the fact that it has locked the parent D since T2 has the lock so it waits.
If T2 now wants to lock G it has to lock D but D is locked by T1 so it has to wait. Hence deadlock.
What am I misunderstanding in the algorithm?

Answer 1

In your example, rule 2 of the tree protocol does not allow T2 to even request a lock on G, thus there cannot be a deadlock.

The first item locked by T2 is H. By rule 2, T2 can request locks only for descendants of H (J in the example).

If T2 needs a lock on both H and G, then the first lock request must be on their parent D (or any ancestor of both H and G).

Answer 2

I suppose your problem is solved until now but I answer just for others.

In your scenario there is a problem and it is that T2 locked H for its first locking position (according to algorithm it's true and you can start from any position), but T2 never can climbing up to root and lock other nodes, so if T2 start from H never allowed to need G. For example if T2 needs G and H, so should start from a node that contain both.

let me know if my answer is true or wrong...

Answer 3

an explanation which i can think of is :

since locks can be released anytime, hence suppose T2 after accessing H in exclusive mode, releases it, hence T1 can access it and then suppose T1 releases all it locks and commits, after which T2 can acquire lock on A,B, D and then G

since it is not 2-phase locking hence locks can be released anytime.

If you have any other explanation, kindly share the same.

Answer 4

T2 cannot lock D as its parent is not locked by T2 at the time.