Transactions & Concurrency

Control-2
Subject- DBMS
Subject Code: BCA-S301T
Faculty: Saurabh Jha
 View Serializability
A Schedule will be view Serializable if it is
View equivalent to a Serial Schedule.
If a Schedule is Conflict Serializable, then it
will be View Serializable.
If a Schedule contains Blind Write the it will
always be View Serializable, No Need to check
it.
 View Equivalent
Two Schedules S1 and S2 are said to be View Equivalent if they Satisfy the following
Conditions:-

1. Initial Read- An Initial Read of both schedules must be the same. Suppose two
Schedules S1 & S2 are there and in Schedule S1, if a Transaction T1 is reading
the data item A, then in Schedule S2, the same transaction T1 should read the
same data item A.

S1 S2
T1 T2 T1 T2
R(A) W(A)
W(A) R(A)

Above Two Schedules are View Equivalent because Initial Read

operation in S1 is done by T1 & in S2 is also done by T1
 View Equivalent
• Update Read- In Schedule S1, If Ti is reading data
Item A which is updated by Tj then in S2 also, Ti
should read A which is updated by Tj.
S1 S2
T1 T2 T3 T1 T2 T3
W(A) W(A)
W(A) W(A)
R(A) R(A)

Above Two Schedules are not View Equivalent because in S1 , T3 is

reading A but it is updated by T2 and Schedule S2, T3 is reading A
which is updated by T1.
 View Equivalent
• Final Write- A Final Write must be the same between both the
schedules. In Schedule S1, if a transaction Ti update A at last then in
S2, Final write operation should also be done by Ti.

S1 S2
T1 T2 T3 T1 T2 T3
W(A) R(A)
R(A) W(A)
W(A) W(A)

Above Two Schedules are View Equivalent because Final Write

operation is done by T3 in S1 and in S2 the Final write operation is
done by T3.
 View Equivalent Example-1
Total No. of Possible Serial T1 T2 T3
Schedule are 3!=6 R(A)
S1=<T1 T2 T3> W(A)
S1=<T1 T3 T2> W(A)
S1=<T2 T1 T3> W(A)

S1=<T2 T3 T1>
S1=<T3 T1 T2> T1 T2 T3
S1=<T3 T2 T1> R(A)
W(A)
W(A)
W(A)
 View Equivalent Example-2
S1 S2 Initial read:
T1 T2 T1 T2 For (X) In S1T1 and S2T1
R(X) R(X) For (Y) In S1T1 & S2T1
W(X) W(X)
R(X) R(Y) Update Read:
W(X) W(Y) For (X) In S1- T2 reads (X) Updated by T1
R(Y) R(X) In S2-T2 reads (X) Updated by T1
W(Y) W(X)
R(Y) R(Y) For (Y) in S1- T2 reads (Y) Updated by T1
W(Y) W(Y) In S2-T2 reads (Y) Updated by T1

Final Write:
For (X) In S1 Final Write is done by T2
Since all three conditions satisfied which means
In S2S1 andWrite
Final S2 are View by T2
is done
Equivalent and S2 is the Serial Schedule of S1.
Recoverability of a Schedule in DBMS
If there is no. of transactions in a Schedule and One
Transactions is reading some others updated instruction and
after that if there is a failure or error held, then if we are
able to return in consistent state then it is recoverable
schedule otherwise Irrecoverable Schedule.
S1 S1
T1 T2 T1 T2
R(a) R(a)
W(a) W(a)
R(a) R(a)
W(a) W(a)
commit commit
commit Failure
 Cascading Roll Back
Due to Failure of one transaction, sometimes we
have to rollback many transactions, which is
called Cascading Rollback.
T1 T2 T3 T4 ----------- Tn
R(a)
RB
W(a)
Failure R(a)
RB W(a)
R(a)
RB W(a) --------- ---------- R(a)
RB W(a)
 Cascade less Schedule
This Schedule avoids the Cascade less Rollback. We
have to commit that transaction which updates
data item before it is read by other transaction
T1 T2 T3 T4 ----------- Tn
R(a)
W(a)
Commit
R(a)
W(a)
Commit ----------- --------- ---------- R(a)
W(a)
commit
 Concurrency Control Techniques
To avoid problems related to concurrency, we have
to apply some protocols(rules) on Transactions
Different Concurrency Control Techniques
1. Lock Based Protocols
2. Time Stamp Based Protocols
3. Validation Based Protocols
4. Multiversion Concurrency Based Protocols
5. Graph Based Protocols
 Lock Based Protocols
Granularity of Locks
The type of information that the lock protect is
called Granularity.
Or
The Size of the Data items that the Data
Manager locks is called Locking Granularity.
Locking can occur on following Levels
A) Coarse Granularity: Locks on Table or File or
Database.
Disadvantages
 It reduces the no. of Transactions to be executed.
 It decreases Throughput.
 It increases Response Time.
 It Decreases Concurrency.
Locking can occur on following Levels
B) Fine Granularity: Locks on Records or Fields.
Disadvantages
1. Much Lock Overhead
2. High Concurrency
3. High Throughput
4. Decrease Response Time.
Locking can occur on following Levels
C) Intermediate Granularity
Locks on Pages which are of fixed Sizes like 4kb,
8kb,16kb …….
A table may span into several pages and a page
may contains pages and a page may contain
several rows of a table or more tables.
It gives moderate concurrency and moderate lock
overhead.
 Types of Locks
Shared Locks
If Ti has obtained shared lock on data item A then Ti can read A but
cannot modify A. It is denoted by ‘S’ and Ti is said to be in Shared
Locked Mode.
Exclusive Locks
It is a Read-Write Lock. If Ti is having an Exclusive lock on data item A
then it can do both Read and Write on A. It is denoted by X.
T2 T2
S X
T1 S Yes No
T1 X No No
 Locking
Advantages
It maintains Serializabiltiy and solve
concurrency problem.
Disadvantages
It leads to new problem known as
Deadlock
 T1 T2 T1 T2
X-Lock(A) X-Lock(A)
R(A) A=1000 R(A)
A=A-500 A=A-500
W(A) W(A)
A=500
Unlock (A) X-Lock(B)

S-Lock(A) R(B)

R(A) B=B+500
A=500
Unlock(A)
W(B)
S-Lock(B) Unlock (A)
R(B) B=300 Unlock(B)
Unlock(B)
S-Lock(A)
Display(A+B) 800 R(A)
X-Lock(B)
S-Lock(B)
R(B) B=300 R(B)
B=B+500
Display(A+B)
W(B)
B=800
Unlock(B) Unlock(A)

Unlock(B)

Let A=1000 and B=500 Release Lock after All Operations Done
 2 Phase Locking Protocol
In 2PL, every Transaction Lock and Unlock Request in 2
Phases.
1. Growing Phase- Only obtain new locks.
2. Shrinking Phase-Only release the acquired locks.
Lockpoint- It is the point where Last Lock is obtained.
 Basic Two Phase Locking
Advantages
This Protocol ensures Conflict Serializability.
Disadvantages
It creates Cascading Rollbacks Problem.
Does Not Free From T1
Lock-X(B)
Deadlocks
T2

R(B)
B=B-50
W(B)
Lock-S(A)
Read(A)
Lock-S(B)
Lock-X(A)
Strict Two Phase Locking Protocol
In Strict Two Phase Locking Protocol, all X-Locks
are kept until the end of the transaction or it
committed.
Advantages
Cascading rollback can be avoided by
modification in Two Phase Locking Protocol.
Rigorous Two Phase Locking Protocol
In Rigorous Two Phase Locking Protocol, All Locks
will be kept until Transaction commit either its is
Exclusive or Shared.
Lock Conversion
• To Improve the efficiency of 2PL Protocol, modes
of the lock can be converted.
• Upgrade: Shared Lock  Exclusive Lock
• Downgrade: Exclusive Lock  Shared Lock
 Database Recovery
Types of Failure
1. Transaction Failure- Due to some reasons transactions get fail, so
some reasons are:
i. Logical Errors- Bad Inputs, Data Not Found, Overflow, Resource
Limit Exceeded.
ii. System Errors – Deadlock Occurs.

2. System Crash- Hardware malfunction, BUG in Database Software or

Operating System.

3. Disk Failure- A Disk Block looses its contents during data transfer
operations, so copies of data are stored or backed up.
 REDO and UNDO
UNDO- Its stands for undone. It T1
restores the value of data items which R(A)
are updated by any Transaction Ti to R(B)
the old values. R(C)
A+A+B
B+B+C  Failure Undo
REDO- It sets the value of all the data
C=A+C
items updated by Transaction Ti to the
W(A)
new values. COMMIT  Failure Redo
W(B)  Failure Undo
DO- Do Next Instructions. W(C)
COMMIT  Failure Redo
 Types of Recovery Techniques
Log Based Recovery – It is a sequence of Log Records,
recording all the update activities in the database.
Various Log Records are:
Log Record Meaning
<Ti Start> When Transaction Starts

Transaction Ti performs write

<Ti, Xj,V1,V2> operation on Xj. Xj had an old value
V1 and an updated value V2.

<Ti Commit> Ti has committed.

<Ti Abort> Ti has aborted.

*Logs are useful for recovery from system and disk failure, the log must reside in the
stable storage.
 Example
T1 Let A=5 and B=7 <Ti, Start>
R(A)
R(B)
<Ti, A,5,12>
A=A+B
W(A)
<Ti, Commit>
 Types of Recovery Techniques
Deferred DB Modification Technique
This technique ensures Transactions atomicity by recording all
DB Modification in Log, but deferring the execution of write
operation until Transaction Partially Commit.

T0 T1 T0 Log File T1 Log File

R(A) R(C) <T0, Start> <T1, Start>
A=A-50 C=C-100 <T0,A,550> it stores only <T1,C,1100> it stores only
W(A) W(C) updated value updated value
R(B) <T0,B,950> <T1, Commit>
B=B+50 <T0, Commit>
W(B)

Let A=600, B=900 and C=1200