Graph based protocol

Slide 1: 

Name:Sujoy saha Dept: CSE Roll: 071020101045 Presentation on Graph-Based Protocol

Slide 2: 

What is Graph-Based Protocol? Graph-Based Protocol is a lock based concurrency control mechanism that ensure serializability. Graph-based protocols are an alternative to two-phase locking protocol.

Slide 3: 

Let two transaction T1 and T2 are defined as T1: Read(A) T2: Read(A) A:=A-50 temp:=A*0.1 Write(A) A:=A -temp Read(B) write(A) B:=B+50 read(B) Write (B). B:=B+ temp write(B).

Slide 4: 

A concurrent schedule

Slide 5: 

Concurrent Serializable schedule

Slide 6: 

Serial schedule

Slide 7: 

Impose a partial ordering  on the set D = {d1, d2 ,..., dh} of all data items. If di  dj then any transaction accessing both di and dj must access di before accessing dj. Implies that the set D may now be viewed as a directed acyclic graph, called a database graph. The tree-protocol is a simple kind of graph protocol.

Rules:: : 

Each transaction Ti can lock a data item at most once, and must observe the following rules: Only exclusive locks are allowed. The first lock by Ti may be on any data item. Subsequently, a data Q can be locked by Ti only if the parent of Q is currently locked by Ti. Data items may be unlocked at any time. A data item that has been locked and unlocked by Ti cannot subsequently be relocked by Ti. Rules::

Example: : 

Let us consider a database D= {A,B,C,D,E,F,G,H,I,J }. Database Graph:- Example: x B D E F I C H J A

Slide 10: 

The following 4 transactions follow the tree protocol on previous data base graph. T1:lock –x(B); lock –x(E); lock –x(D); unlock –x(B); unlock –x(E); lock –x(G); unlock –x(D); unlock –x(G). T2:lock –x(D); lock –x(H); unlock –x(D); unlock –x(H). T3:lock –x(B); lock –x(E); unlock –x(E); unlock –x(B). T4:lock –x(H); lock –x(J); unlock –x(H); unlock –x(J).

Slide 11: 

Serializable schedule under the tree protocol Serializable schedule under the tree protocol

Slide 12: 

Here the tree protocol in previous page does not ensure 1.Recoverability and 2.Cascadelessness But if the protocol can be modified to not permit release lock until the end of transaction ,then it ensure Recoverability and Cascadelessness.

Advantages: : 

The tree protocol ensures conflict serializability Freedom from deadlock. Unlocking may occur earlier in the tree-locking protocol than in the two-phase locking protocol. shorter waiting times, and increase in concurrency protocol is deadlock-free, no rollbacks are required Advantages:

Slide 14: 

Disadvantages: In the tree-locking protocol, a transaction may have to lock data items that it does not access. increased locking overhead, and additional waiting time potential decrease in concurrency