Graph based protocol

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?

Comments

Balaji So deadlock can happen in this protocol?

---

no,I donot think deadlock can happen

https://www.geeksforgeeks.org/dbms-concurrency-control-protocol-graph-based-protocol/

option 2) and 3) correct

---

Early unlock option is there if it will unlock early, other transactions can hold the lock. Starvation can be there, but not deadlock

Answer 1

As far as i have understood, Tree has a direction from top to bottom, and if T2 wants to lock both G and H then it has to lock the common parent of both first, Here T2 is not allowed to request a lock on G, because it can't climb upwards. Now T2 can request lock on J only and not on any other nodes.
"The first lock by Ti can be on any data item", that time itself T2 should have taken care before it locked H if it needed G and H both.

Comments

T2 can lock G as G is independent of H, only not allowed lock after L_X(H) is L_X(D) and its parents.

Please correct me if iam wrong.

Both T1 and T2 are following the above rules. Should we draw precedance graph to check for deadlock??

---

no T2 can't lock G as T2 need to lock a parent of G first. but it can't do lock H and then G. remember it's a tree based protocol.

---

ok... For locking the siblings, we need to lock parent?> is it?

Answer 2

t2 can lock h if it's parent is locked suppose h is currently locked that means first d was locked and still d is locked now d is unlocking by t1 and now d unlocked now t1 comes and it can lock d and  becoz parent is locked so t1 can lock g it is happening locking and unlocking can be happen in any way and becoz of t1 ,t2 ,.....tn will never request to lock d again so deadlock not possible here.