Unit - 6 - Transaction and Recovery Management

Unit 6 :Transaction & Recovery Management
Charotar University of Science & Technology

Devang Patel Institute of Advance Technology & Research
CE246:
Databases Management System
Transaction & Recovery Management

Instructor: Prof. Dipak Ramoliya
Email: [email protected]
Mo. +91 999 877 1587
Goals for this pair of lectures

• Transactions are a programming abstraction that enables the DBMS to
handle recovery and concurrency for users.
• Application: Transactions are critical for users

• Even casual users of data processing systems!
• Fundamentals: The basics of how TXNs work

• Transaction processing is part of the debate around new data processing systems
• Give you enough information to understand how TXNs work, and the main
concerns with using them
What is transaction?
• A transaction is a sequence of operations performed as a single logical unit of
work.
• A transaction is a logical unit of work that contains one or more SQL statements.
• Example of transaction Works as a single
logical unit
read (A)
A = A – 50
write (A)
Transaction
Operations
read (B)
B = B + 50
write (B)
ACID properties of transaction

• Atomicity (Either transaction execute 0% or 100%)
• Consistency (database must remain in a consistent state after any
transaction)
• Isolation (Intermediate transaction results must be hidden from
other concurrently executed transactions)
• Durability (Once a transaction completed successfully, the changes it
has made into the database should be permanent)
ACID properties of transaction 0%

• Atomicity read (A)
 This property states that a transaction
must be treated as an atomic unit, that
A = A – 50
is, either all of its operations are write (A)
executed or none. FAIL
read (B)
 Either transaction execute 0% or 100%.
 For example, consider a transaction to B = B + 50
transfer Rs. 50 from account A to account write (B)
B.
100%
 In this transaction, if Rs. 50 is deducted
from account A then it must be added to
account B.
ACID properties of transaction A=500, B=500

A+B=1000
• Consistency
read (A)
 The database must remain in a
consistent state after any transaction. A = A – 50
 If the database was in a consistent state write (A)
before the execution of a transaction, it
must remain consistent after the read (B)
execution of the transaction as well. B = B + 50
 In our example, total of A and B must
remain same before and after the write (B)
execution of transaction. A=450, B=550
A+B=1000
ACID properties of transaction read (A)

A = A – 50
• Isolation
 Changes occurring in a particular write (A)
transaction will not be visible to any read (B)
other transaction until it has been
committed. B = B + 50
 Intermediate transaction results must write (B)
be hidden from other concurrently
executed transactions.
 In our example once our transaction
starts from first step (step 1) its result
should not be access by any other
transaction until last step (step 6) is
completed.
ACID properties of transaction A=500, B=500

read (A)
• Durability
 After a transaction completes A = A – 50
successfully, the changes it has made to write (A)
the database persist (permanent), even
if there are system failures. read (B)
 Once our transaction completed up to B = B + 50
last step (step 6) its result must be stored
permanently. It should not be removed if write (B)
system fails. A=450, B=550
Transaction
• TheState
When
Diagram
transaction enters
a transaction
\ state
State
in this its
executes
Transition
after
final successful
operation, it is said
Diagram
completion of the transaction.
to be in a partially committed state.
• We cannot abort or rollback a committed transaction.
read (A)
Partial
Committed Committed A = A – 50
write (A)
Active End read (B)
B = B + 50
write (B)
Failed Aborted
Commit
• •TheThis
Discover
stateisthat
the
afterinitial
normal state.
executionhas
the transaction canbeen
no longer
rolledproceed.
back and
• •theThe
Once a transaction
transaction
database stays
cannot
has been in be
thiscompleted,
restored state
to its stateany changes
prior to the
thatwhile
start it istransaction.
itofmade
the executing.
must be undone rolling it back.
Transaction State Diagram \ State Transition Diagram
• Active
• This is the initial state.
• The transaction stays in this state while it is executing.
• Partial Committed
• When a transaction executes its final operation/ instruction, it is said to be in
a partially committed state.
• Failed
• Discover that normal execution can no longer proceed.
• Once a transaction cannot be completed, any changes that it made must be
undone rolling it back.
Transaction State Diagram \ State Transition Diagram
• Committed
• The transaction enters in this state after successful completion of the
transaction (after committing transaction).
• We cannot abort or rollback a committed transaction.
• Aborted
• The state after the transaction has been rolled back and the database has
been restored to its state prior to the start of the transaction.
What is schedule?
• A schedule is a process of grouping the transactions into one and
executing them in a predefined order.
• A schedule is the chronological (sequential) order in which instructions
are executed in a system.
• A schedule is required in a database because when some transactions
execute in parallel, they may affect the result of the transaction.
• Means if one transaction is updating the values which the other
transaction is accessing, then the order of these two transactions will
change the result of another transaction.
• Hence a schedule is created to execute the transactions.
Example of schedule
T1 T2 A=B=1000
Read (A) Read (1000)
A = A - 50 A = 1000 - 50
Write (A) Write (950)
Read (B) Read (1000)
B = B + 50 B = 1000 + 50
Write (B) Write (1050)
Commit Commit
Read (A) Read (950)

temp = A * 0.1 temp = 950 * 0.1
A = A - temp A = 950 - 95
B = B + temp B = 1050 + 95
Commit Commit
Example of schedule
T1 T2 A=B=1000
Read (A) Read (1000)
Temp = A * 0.1 Temp = 1000 * 0.1
A = A - temp A = 1000 - 100
B = B + temp B = 1000 + 100
Commit Commit
Read (900)
Read (A)
A = 900 - 50
A = A - 50
Write (850)
Write (A)
Read (1100)
Read (B)
B = 1100 + 50
B = B + 50
Write (1150)
Write (B)
Commit
Commit
Serial schedule
• A serial schedule is one in which no transaction starts until a running
transaction has ended.
• Transactions are executed one after the other.
• This type of schedule is called a serial schedule, as transactions are
executed in a serial manner.
Example of serial schedule

T1 T2
Read (A)
Temp = A * 0.1
A = A - temp
Write (A)
Read (B)
B = B + temp
Write (B)
Commit
Read (A)
A = A - 50
Write (A)
Read (B)
B = B + 50
Write (B)
Commit
Example of serial schedule

T1 T2
Read (A)
A = A - 50
Write (A)
Read (B)
B = B + 50
Write (B)
Commit
Read (A)
Temp = A * 0.1
A = A - temp
Write (A)
Read (B)
B = B + temp
Write (B)
Commit
Interleaved schedule
• Schedule that interleave the execution of different transactions.
• Means second transaction is started before the first one could end
and execution can switch between the transactions back and forth.
Example of interleaved schedule

T1 T2
Read (A)
Temp = A * 0.1
A = A - temp
Read (B) Write (A)
B = B + temp
Write (B)
Commit
Read (A)
A = A - 50
Write (A)
Read (B)
B = B + 50
Write (B)
Commit
Example of interleaved schedule

T1 T2
Read (A)
A = A - 50
Write (A)
Read (B)
B = B + 50
Write (B)
Commit
Read (A)
Temp = A * 0.1
A = A - temp
Write (A)
Read (B)
B = B + temp
Write (B)
Commit
Equivalent schedule
• If two schedules produce the same result after execution, they are
said to be equivalent schedule.
• They may yield the same result for some value and different results
for another set of values.
• That's why this equivalence is not generally considered significant.
Equivalent schedule
T1 T2 T1 T2
Both schedules are equivalent

Read (A) Read (A)
In both schedules the sum “A + B” is preserved.

A = A - 50 A = A - 50
Write (A) Write (A)
Commit Read (A) Read (B)
Temp = A * 0.1 B = B + 50
A = A - temp Write (B)
Write (A) Commit
Commit
Read (A)
Read (B) Temp = A * 0.1
B = B + 50 A = A - temp
Write (B) Write (A)
Commit Read (B) Read (B)
B = B + temp B = B + temp
Write (B) Write (B)
Commit Commit
Classification
of Schedules:
Classification of Schedules:
Serial Schedules Serializable Schedules
No concurrency is allowed. Concurrency is allowed.

Thus, all the transactions necessarily execute serially Thus, multiple transactions can execute
one after the other. concurrently.
Serial schedules lead to less resource utilization and Serializable schedules improve both resource
CPU throughput. utilization and CPU throughput.
Serial Schedules are less efficient as compared to Serializable Schedules are always better than serial
serializable schedules. schedules.
(due to above reason) (due to above reason)
Serializability
• A schedule is serializable if it is equivalent to a serial schedule.
• In serial schedules, only one transaction is allowed to execute at a
time i.e. no concurrency is allowed.
• Whereas in serializable schedules, multiple transactions can execute
simultaneously i.e. concurrency is allowed.
• Types (forms) of serializability
1. Conflict serializability
2. View serializability
Conflicting instructions
• Let li and lj be two instructions of transactions Ti and Tj respectively.
1. li = read(Q), lj = read(Q) T1 T2 T1 T2
li and lj don’t conflict read (Q) read (Q)
read (Q) read (Q)
2. li = read(Q), lj = write(Q)
li and lj conflict
T1 T2 T1 T2
read (Q) write(Q)
write(Q) read (Q)
3. li = write(Q), lj = read(Q)
li and lj conflict T1 T2 T1 T2
write(Q) read (Q)
4. li = write(Q), lj = write(Q) read (Q) write(Q)
li and lj conflict
T1 T2 T1 T2
write(Q) write(Q)
write(Q) write(Q)
Conflicting instructions
• Instructions li and lj conflict if and only if there exists some item Q
accessed by both li and lj, and at least one of these instructions
wrote Q.
• If both the transactions access different data item then they are not
conflict.
If a given non-serial schedule can be converted into a serial

schedule by swapping its non-conflicting operations, then it
is called as a conflict serializable schedule.
Conflict serializability- Conflicting

Operations
• Two operations are called as conflicting operations if all the following
conditions hold true for them-
• Both the operations belong to different transactions
• Both the operations are on the same data item
• At least one of the two operations is a write operation
Conflict serializability –example

• Consider the following schedule..
In this schedule,
• W1 (A) and R2 (A) are called as

conflicting operations.
• This is because all the above conditions
hold true for them.
Conflict serializability Checking Whether a Schedule is Conflict Serializable Or

Not-
–example
Follow the following steps to check whether a given
non-serial schedule is conflict serializable or not-
Step-01:
Find and list all the conflicting operations.
Step-02:
Start creating a precedence graph by drawing one node
for each transaction.
Step-03:
Draw an edge for each conflict pair such that if Xi (V)
and Yj (V) forms a conflict pair then draw an edge from
Ti to Tj.
This ensures that Ti gets executed before Tj.
Step-04:
Check if there is any cycle formed in the graph.
If there is no cycle found, then the schedule is conflict
serializable otherwise not.
Conflict serializability (example)

T1 T2 T1 T2
Read (A) Read (A)
A = A - 50 A = A - 50
Write (A) Write (A)
Read (A) Read (B)
Temp = A * 0.1 B = B + 50
A = A - temp Write (B)
Write (A) Commit
Read (A)
Read (B) Temp = A * 0.1
B = B + 50 A = A - temp
Write (B) Write (A)
Commit Read (B) Read (B)
B = B + temp B = B + temp
Write (B) Write (B)
Commit Commit
Conflict serializability
• Example of a schedule that is not conflict serializable:
T1 T2
Read (A)
Write (A)
Read (A)
• We are unable to swap instructions in the above schedule to obtain either

the serial schedule < T1, T2 >, or the serial schedule < T2, T1 >.
Conflict serializability –Exercise example

• Check whether the given schedule S is conflict serializable or not-
S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) , W2(B)

• Check whether the given schedule S is conflict serializable or not-
S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) , W2(B)
Solution:
• Step-01:
• List all the conflicting operations and determine the dependency
between the transactions-
• R2(A) , W1(A) (T2 → T1)
• R1(B) , W2(B) (T1 → T2)
• R3(B) , W2(B) (T3 → T2)

Step-01:
• List all the conflicting operations and determine the dependency
• R2(A) , W1(A) (T2 → T1)
• R1(B) , W2(B) (T1 → T2)
• R3(B) , W2(B) (T3 → T2)
Step-02:
Draw the precedence graph-

Step-02:
• Clearly, there exists a cycle in the precedence graph.

• Therefore, the given schedule S is not conflict serializable.
View serializability
If a given schedule is found to be view equivalent to some serial schedule,
then it is called as a view serializable schedule.
View equivalent
• Let S1 and S2 be two schedules with the same set of transactions. S1
and S2 are view equivalent if the following three conditions are
satisfied, for each data item Q
1. Initial Read
2. Updated Read
3. Final Write
Initial Read
• If in schedule S1, transaction Ti reads the initial value of Q, then in
schedule S2 also transaction Ti must read the initial value of Q.
S1 S3 S2
T1 T2 T1 T2 T1 T2
Read (A) Read (A) Write (A)
Write (A) Write (A) Read (A)
• Above two schedules S1 and S3 are not view equivalent because initial read
operation in S1 is done by T1 and in S3 it is done by T2.
• Above two schedules S1 and S2 are view equivalent because initial read operation in
S1 is done by T1 and in S2 it is also done by T1.
Thumb Rule
“Initial readers must be same for all the data items”.
Updated Read
• If in schedule S1 transaction Ti executes read(Q), and that value was
produced by transaction Tj (if any), then in schedule S2 also transaction
Ti must read the value of Q that was produced by transaction Tj.
S1 S3
T1 T2 T3 T1 T2 T3
Write (A) Write (A)
Write (A) Write (A)
Read (A) Read (A)
• Above two schedules are not view equal because, in S1, T3 is reading A
that is updated by T2 and in S3, T3 is reading A which is updated by T1.
Updated Read
• If in schedule S1 transaction Ti executes read(Q), and that value was produced
by transaction Tj (if any), then in schedule S2 also transaction Ti must read the
value of Q that was produced by the same write(Q) operation of transaction T j.
S1 S2
T1 T2 T3 T1 T2 T3
Read (A) Read (A)
Write (A) Write (A)
Write (A) Read (A)
Read (A) Write (A)
• Above two schedules are view equal because, in S1, T3 is reading A that is
updated by T2 and in S3 also, T3 is reading A which is updated by T2.
Thumb Rule
“Write-read sequence must be same.”.
Final Write
• If Ti performs the final write on the data value in S1, then it also performs the
final write on the data value in S2.
S1 S2
T1 T2 T3 T1 T2 T3
Write (A) Read (A)
Read (A) Write (A)
Write (A) Write (A)
• Above two schedules is view equal because final write operation in S1 is done by
T3 and in S2 also the final write operation is also done by T3.
Thumb Rule
“Final writers must be same for all the data items”.
Checking Whether a Schedule is View Serializable Or Not

Method-01:

Check whether the given schedule is conflict serializable or not.
•If the given schedule is conflict serializable, then it is surely view serializable. Stop
and report your answer.
•If the given schedule is not conflict serializable, then it may or may not be view
serializable. Go and check using other methods.
Thumb Rules
•All conflict serializable schedules are view serializable.
•All view serializable schedules may or may not be conflict serializable.

Method-02:

Check if there exists any blind write operation.
(Writing without reading is called as a blind write).
• If there does not exist any blind write, then the schedule is surely not view
serializable. Stop and report your answer.
• If there exists any blind write, then the schedule may or may not be view
serializable. Go and check using other methods.
Thumb Rule
No blind write means not a view serializable schedule.
Method-03:

• In this method, try finding a view equivalent serial schedule.
• By using the above three conditions, write all the dependencies.
• Then, draw a graph using those dependencies.
• If there exists no cycle in the graph, then the schedule is view

serializable otherwise not.
Check whether the given schedule S is view serializable or not. If yes, then give the
serial schedule.
S : R1(A) , W2(A) , R3(A) , W1(A) , W3(A)
For simplicity and better understanding, we can represent the given schedule
pictorially as-
We know, if a schedule is conflict serializable, then it is surely view serializable.

So, let us check whether the given schedule is conflict serializable or not.
Checking Whether S is Conflict Serializable Or Not-

Step-01:

List all the conflicting operations and determine the dependency
•R1(A) , W2(A) (T1 → T2)
•R1(A) , W3(A) (T1 → T3)
•W2(A) , R3(A) (T2 → T3)
•W2(A) , W1(A) (T2 → T1)
•W2(A) , W3(A) (T2 → T3)
•R3(A) , W1(A) (T3 → T1)
•W1(A) , W3(A) (T1 → T3)
•Clearly, there exists a cycle in the precedence graph.

•Therefore, the given schedule S is not conflict serializable.
Now,
•Since, the given schedule S is not conflict serializable, so, it may or may not be view serializable.
•To check whether S is view serializable or not, let us use another method.
•Let us check for blind writes.
Checking for Blind Writes-

• There exists a blind write W2 (A) in the given schedule S.
• Therefore, the given schedule S may or may not be view
serializable.

Now,
• To check whether S is view serializable or not, let us use
another method.
• Let us derive the dependencies and then draw a
dependency graph.
• Drawing a Dependency Graph-
• T1 firstly reads A and T2 firstly updates A.

• So, T1 must execute before T2.
• Thus, we get the dependency T1 → T2.
• Final updation on A is made by the transaction T3.
• So, T3 must execute after all other transactions.
• Thus, we get the dependency (T1, T2) → T3.
• From write-read sequence, we get the dependency T2 → T3
• Now, let us draw a dependency graph using these dependencies-
•Clearly, there exists no cycle in the dependency graph.

•Therefore, the given schedule S is view serializable.
•The serialization order T1 → T2 → T3.
Two phase commit protocol

• Two phase commit protocol ensures that all participants perform the same
action (either to commit or to rollback a transaction).
• It is designed to ensure that either all the databases are updated or none of
them, so that the databases remain synchronized.
• In two phase commit protocol there is one node which is act as a coordinator
or controlling site and all other participating node are known as cohorts or
participant or slave.
• Coordinator (controlling site) – the component that coordinates with all the
participants.
• Cohorts (Participants/Slaves) – each individual node except coordinator are
participant.

• As the name suggests, the two phase commit protocol involves two
phases.
1. Commit request phase OR Prepare phase
2. Commit/Abort phase
Reque
st to prep
are
Prepare
Phase Prepared
Comm
it /Abort
Commit
Phase Done
Coordinator
Coordinator
Participant
Send toinform
send
“ack” send to do
reply
inform
commit
request asking
whether ready for
commit readyor
todone
to commit
commit
not or not

1. Commit Request Phase (Obtaining Decision)
• After each slave has locally completed its transaction, it sends a “DONE”
message to the controlling site.
• When the controlling site has received “DONE” message from all slaves, it
sends a “Prepare” (prepare to commit) message to the slaves.
• The slaves vote on whether they still want to commit or not.
• If a slave wants to commit, it sends a “Ready” message.
• A slave that does not want to commit sends a “Not Ready” message.
• This may happen when the slave has conflicting concurrent transactions or
there is a timeout.

2. Commit Phase (Performing Decision)
1) After the controlling site has received “Ready” message from all the slaves:
• The controlling site sends a “Global Commit” message to the slaves.
• The slaves commit the transaction and send a “Commit ACK” message to the
controlling site.
• When the controlling site receives “Commit ACK” message from all the
slaves, it considers the transaction as committed.

2. Commit Phase (Performing Decision)
2) After the controlling site has received the first “Not Ready” message from any slave:
• The controlling site sends a “Global Abort” message to the slaves.
• The slaves abort the transaction and send a “Abort ACK” message to the
controlling site.
• When the controlling site receives “Abort ACK” message from all the slaves,
it considers the transaction as aborted.
What is concurrency?
• Concurrency is the ability of a database to allow multiple (more than
one) users to access data at the same time.
• Three problems due to concurrency
1. Lost update problem
2. Dirty read problem
3. Incorrect retrieval problem
Lost update problem

• This problem indicate that if two X=100
transactions T1 and T2 both read the T1 Time T2
same data and update it then effect --- T0 ---
of first update will be overwritten by
the second update. Read X T1 ---
--- T2 Read X
• How to avoid: A transaction T2 must Update X
not update the data item (X) until the X=75
T3 ---
transaction T1 can commit data item Update X
(X). --- T4
X=50
--- T5 ---
Dirty read problem

• The dirty read arises when one X=100
transaction update some item and T1 Time T2
then fails due to some reason. This --- T0 ---
updated item is retrieved by Update X
another transaction before it is --- T1
X=50
changed back to the original value. Read X T2 ---
• How to avoid: a transaction T1 must --- T3 Rollback
not read the data item (X) until the
transaction T2 can commit data item --- T4 ---
(X).
The incorrect retrieval problem

• The incorrect retrieval problem arises when one transaction retrieves data to use
in some operation but before it can use this data another transaction updates
that data and commits.
• Through this change will be hidden from first transaction and it will continue to
use previous retrieved data. This problem is also known as inconsistent analysis
problem.
• In below Execution T1 reads A=500, T2 read A=500. T1 modifies A=600. When T2
rereads A it gets A=600. This should not be the case. T2 in the same execution
should get only one value of A(500 or 600 and not both)
What is lock?
• A lock is a variable associated with data item to control concurrent
access to that data item.
Locking is a strategy that is used to
prevent such concurrent access of data.
Lock variable
0
1
Database
Lock based protocol

• Data items can be locked in two modes :
1. Shared (S) mode: When we take this lock we can just read the item but
cannot write.
2. Exclusive (X) mode: When we take this lock we can read as well as write
the item.
 Lock-compatibility matrix
T1
T2 Shared lock Exclusive lock

Shared lock Yes No
Compatible Not Compatible
Exclusive lock No No
Not Compatible Not Compatible
Lock based protocol

• A transaction may be granted a lock on an item if the requested lock
is compatible with locks already held on the item by other
transactions.
• If a lock cannot be granted, the requesting transaction is made to
wait till all incompatible locks held by other transactions have been
released. The lock is then granted.
• Any number of transactions can hold shared locks on an item, but if
any transaction holds an exclusive on the item no other transaction
can hold any lock on the item.
Lock based protocol

• This locking protocol divides transaction execution phase into three
parts:
1. When transaction starts executing, create a list of data items on which they
need locks and requests the system for all the locks it needs.
2. Where the transaction acquires all locks and no other lock is required.
Transaction keeps executing its operation.
3. As soon as the transaction releases its first lock, the third phase starts. In
this phase a transaction cannot demand for any lock but only releases the
acquired locks.
Transaction
Lock acquisition execution Lock releasing
phase phase
Transaction
T begin T end Time
Two phase locking protocol

• This protocol works in two phases,
1. Growing Phase
• In this phase a transaction obtains locks, but can not release any lock.
• When a transaction takes the final lock is called lock point.
2. Shrinking Phase
• In this phase a transaction can release locks, but can not obtain any lock.
• The transaction enters the shrinking phase as soon as it releases the first
lock after crossing the Lock Point.
Growing phase Shrinking phase
Transaction
T begin T end Time
Strict two phase locking protocol

• In this protocol, a transaction may release all the shared locks after
the Lock Point has been reached, but it cannot release any of the
exclusive locks until the transaction commits or aborts.
• It ensures that if data is being modified by one transaction, then
other transaction cannot read it until first transaction commits.
• This protocol solves dirty read problem.
Rigorous two phase locking protocol

• In this protocol, a transaction is not allowed to release any lock
(either shared or exclusive) until it commits.
• This means that until the transaction commits, other transaction can
not acquire even a shared lock on a data item on which the
uncommitted transaction has a shared lock.
Time stamp based protocol

• This protocol uses either system time or logical counter to be used as a time-
stamp.
• Every transaction has a time-stamp associated with it and the ordering is
determined by the age of the transaction.
• A transaction ‘T1’ created at 0002 clock time would be older than all other
transaction, which come after it.
• For example, any transaction ‘T2' entering the system at 0004 is two seconds
younger than transaction ‘T1’ and priority is given to the older one.
• In addition, every data item is given the latest read and write time-stamp.
This lets the system know, when last read and write operations was made on
the data item.
Time stamp ordering protocol

• This is the responsibility of the protocol system that the conflicting
pair of tasks should be executed according to the timestamp values of
the transactions.
• Time-stamp of Transaction Ti is denoted as TS(Ti).
• Read time-stamp of data-item X is denoted by R-timestamp(X).
• Write time-stamp of data-item X is denoted by W-timestamp(X).
Time stamp ordering protocol

• Timestamp ordering protocol works as follows:
• If a transaction Ti issues read(X) operation:
• If TS(Ti) < W-timestamp(X)
• Operation rejected.
• If TS(Ti) >= W-timestamp(X)
• Operation executed.
• If a transaction Ti issues write(X) operation:
• If TS(Ti) < R-timestamp(X)
• Operation rejected.
• If TS(Ti) < W-timestamp(X)
• Operation rejected and Ti rolled back.
• Otherwise, operation executed.
What is deadlock?
• Consider the following two transactions:
T1 T2

Granted for (A) Lock-X (A)
Write (A)
Lock-X (B) Granted for (B)
Write (B)
Lock-X (A) Waiting for (A)
Write (A)
Waiting for (B) Lock-X (B)

Write (B)
• A deadlock is a situation in which two or more transactions are waiting for one another to
give up locks.
Deadlock detection
• A simple way to detect deadlock is with the help of wait-for graph.
• One node is created in the wait-for graph for each transaction that is
currently executing.
• Whenever a transaction Ti is waiting to lock an item X that is currently
locked by a transaction Tj, a directed edge from Ti to Tj (Ti→Tj) is created
in the wait-for graph.
• When Tj releases the lock(s) on the items that Ti was waiting for, the
directed edge is dropped from the wait-for graph.
• We have a state of deadlock if and only if the wait-for graph has a cycle.
• Then each transaction involved in the cycle is said to be deadlocked.
Deadlock detection
B D
• Transaction A is waiting for transactions B and C.
• Transactions C is waiting for transaction B.
A • Transaction B is waiting for transaction D.
• This wait-for graph has no cycle, so there is no
deadlock state.
C
• Suppose now that transaction D is requesting an
item held by C. Then the edge D C is added
to the wait-for graph.
Deadlock detection
• Now this graph contains the cycle.
•B D C B
B D
• It means that transactions B, D and C are all
deadlocked.
A
CK
LO
AD
DE
C
Deadlock recovery
• When a deadlock is detected, the system must recover from the
deadlock.
• The most common solution is to roll back one or more transactions
to break the deadlock.
• Choosing which transaction to abort is known as Victim Selection.
Choice of deadlock victim

• In this wait-for graph transactions B, D and C are
deadlocked.
B D
• In order to remove deadlock one of the
A
transaction out of these three (B, D, C)
CK
transactions must be roll backed.
LO
AD • We should rollback those transactions that will
DE
C incur the minimum cost.
• When a deadlock is detected, the choice of
which transaction to abort can be made using
following criteria:
The transaction which have the fewest locks
The transaction that has done the least work
The transaction that is farthest from completion
Deadlock prevention
• A protocols ensure that the system will never enter into a deadlock
state.
• Some prevention strategies :
• Require that each transaction locks all its data items before it begins
execution (predeclaration).
• Impose partial ordering of all data items and require that a transaction can
lock data items only in the order specified by the partial.
Deadlock prevention
• Following schemes use transaction timestamps for the sake of
deadlock prevention alone.
1. Wait-die scheme — non-preemptive
• If an older transaction is requesting a resource which is held by younger
transaction, then older transaction is allowed to wait for it till it is available.
• If an younger transaction is requesting a resource which is held by older
transaction, then younger transaction is killed.
Wait-Die
O needs a resource held by Y O waits
Y needs a resource held by O Y dies
Deadlock prevention
2. Wound-wait scheme — preemptive
• If an older transaction is requesting a resource which is held by younger
transaction, then older transaction forces younger transaction to kill the
transaction and release the resource.
• If an younger transaction is requesting a resource which is held by older
transaction, then younger transaction is allowed to wait till older transaction
will releases it.
Wound-Wait
O needs a resource held by Y Y dies
Y needs a resource held by O Y waits
Deadlock prevention
3. Timeout-Based Schemes :
• A transaction waits for a lock only for a specified amount of time. After that,
the wait times out and the transaction is rolled back. So deadlocks never
occur.
• Simple to implement; but difficult to determine good value of the timeout
interval.
Database recovery
• There are many situations in which a transaction may not reach a
commit or abort point.
• Operating system crash
• DBMS crash
• System might lose power (power failure)
• Disk may fail or other hardware may fail (disk/hardware failure)
• Human error
• In any of above situations, data in the database may become
inconsistent or lost.
Database recovery
• For example, if a transaction has completed 30 out of 40 write
instructions to the database when the DBMS crashes, then the
database may be in an inconsistent state as only part of the
transaction’s work was completed.
• Database recovery is the process of restoring the database and the
data to a consistent state.
• This may include restoring lost data up to the point of the event (e.g.
system crash).
Log based recovery method

 The log is a sequence of log records, which maintains information about update
activities on the database.
• A log is kept on stable storage (i.e HDD).
• Log contains
1. Start of transaction
2. Transaction-id
3. Record-id
4. Type of operation (insert, update, delete)
5. Old value, new value
6. End of transaction that is committed or aborted.
Log based recovery method

• When transaction Ti starts, it registers itself by writing a record
<Ti start> to the log
• Before Ti executes write(X), a log record <Ti, X, V1, V2> is written, where V1 is the
value of X before the write (the old value), and V2 is the value to be written to X
(the new value).
• When Ti finishes it last statement, the log record <Ti commit> is written.
• Undo of a log record <Ti, X, V1, V2> writes the old value V1 to X
• Redo of a log record <Ti, X, V1, V2> writes the new value V2 to X
• Types of log based recovery method
1. Immediate database modification
2. Deferred database modification
Immediate v/s Deferred database modification

Immediate database modification Deferred database modification
Updates (changes) to the database are Updates (changes) to the database are
applied immediately as they occur without deferred (postponed) until the transaction
waiting to reach to the commit point. commits.
A=500, B=600, C=700 T1 T2 A=500, B=600, C=700

Read (A)
A = A - 100
Write (A)
Read (B)
<T1 start> B = B + 100
<T1 start>
<T1,<T1 start>
A, 500, 400> Write (B)
<T1A,
<T1, start>
400>
<T1
<T1, start> <T1A,
start>
<T1, A, 500, 700>
B, 600, 400>
Commit
<T1,
<T1, B, 400>
700>
<T1,
<T1, A,
B, 500,
600, 400>
700>
A=400,B=700,C=700 <T1,
<T1, A,
B, 400>
700>
A=500,B=600,C=700
<T1, Read (C)
<T1,B,Commit>
600, 700> <T1,Commit>
<T1, B, 700>
C = C - 200
<T1,
<T2Commit>
start> Write (C) <T1,
<T2Commit>
start>
<T2,<T2 start>
C, 700, 500> Commit <T2 C,
<T2, start>
500>
<T2,
<T2,C,Commit>
700, 500> <T2,Commit>
<T2, C, 500>
A=400,B=700,C=500 A=400,B=700,C=700
A=400,B=700,C=500
Immediate v/s Deferred database modification

Immediate database modification Deferred database modification
Updates (changes) to the database are Updates (changes) to the database are
applied immediately as they occur without deferred (postponed) until the transaction
waiting to reach to the commit point. commits.
If transaction is not committed, then we If transaction is not committed, then no

need to do undo operation and restart the need to do any undo operations. Just
transaction again. restart the transaction.
If transaction is committed, then no need If transaction is committed, then we need

to do redo the updates of the transaction. to do redo the updates of the transaction.
Undo and Redo both operations are Only Redo operation is performed.
performed.
Problems with Deferred & Immediate Updates
• Searching the entire log is time consuming.

1. Immediate database modification
• When transaction fail log file is used to undo the updates of transaction.
2. Deferred database modification
• When transaction commits log file is used to redo the updates of transaction.
 To reduce the searching time of entire log we can use check point.
Checkpoint
• It is a point which specifies that any operations executed before it
are done correctly and stored safely (updated safely in database).
• At this point, all the buffers are force-fully written to the secondary
storage (database).
• Checkpoints are scheduled at predetermined time intervals.
• It is used to limit:
• Size of transaction log file
• Amount of searching
Checkpoint works when failure occurs

Time TC Tf
T1
T2
T3
T4
Checkpoint time Failure
• At failure time:
• Ignore the transaction T1 as it has already been committed before checkpoint.
• Redo transaction T2 and T3 as they are active after checkpoint and are committed before failure.
• Undo transaction T4 as it is active after checkpoint and has not committed.
Page table structure

1 2 1
• The database is partitioned into 2 1 2
fixed-length blocks referred to as 3 4 3
PAGES. 4 101 4
• Page table has n entries – one for 5 202 :
each database page. . :
• Each entry contain pointer to a page n n 101
on disk. :
Page Table :
201
Pages 202
n
Pages on disk
Shadow paging technique

• Shadow paging is an alternative to log-based recovery.
• This scheme is useful if transactions execute serially.
• It maintain two page tables during the lifetime of a transaction
• current page table
• shadow page table
• Shadow page table is stored on non-volatile storage.
• When a transaction starts, both the page tables are identical. Only
current page table is updated for data item accesses (changed) during
execution of the transaction.
• Shadow page table is never modified during execution of transaction.

Page 1 Page 1 Page 1
Current page table Pages Shadow page table
• Two pages - page 2 & 5 - are affected by a transaction and copied to

new physical pages. The current page table points to these pages.

• Whenever any page is updated first time
• A copy of this page is made onto an unused page
• The current page table is then made to point to the copy
• The update is performed on the copy

Page 2 Page 2 (old) Page 2
Page 2 (new)
Page 5 (new)
• Two pages - page 2 & 5 - are affected by a transaction and copied to

new physical pages. The current page table points to these pages.

Page 2 (new)
Page 5 (new)
• The shadow page table continues to point to old pages which are not changed
by the transaction. So, this table and pages are used for undoing the
transaction.

• When transaction start, both the page tables are identical.
• The shadow page table is never changed over the duration of the transaction.
• The current page table will be changed when a transaction performs a write
operation.
• All input and output operations use the current page table.
• Whenever any page is about to be written for the first time
• A copy of this page is made onto an unused page
• The current page table is then made to point to the copy
• The update is performed on the copy
 When the transaction completes, the current page table becomes shadow page table. At this
time, it is considered that the transaction has committed.
Thanks..!
96

Unit - 6 - Transaction and Recovery Management

Uploaded by

Copyright:

Available Formats

Unit - 6 - Transaction and Recovery Management

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit - 6 - Transaction and Recovery Management

Uploaded by

Copyright:

Available Formats

Unit 6 :Transaction & Recovery Management

Charotar University of Science & Technology

Transaction & Recovery Management

Goals for this pair of lectures

• Application: Transactions are critical for users

• Fundamentals: The basics of how TXNs work

ACID properties of transaction

ACID properties of transaction 0%

ACID properties of transaction A=500, B=500

ACID properties of transaction read (A)

ACID properties of transaction A=500, B=500

Transaction State Diagram \ State Transition Diagram

Transaction State Diagram \ State Transition Diagram

Read (A) Read (950)

Example of serial schedule

Example of serial schedule

Example of interleaved schedule

Example of interleaved schedule

Both schedules are equivalent

In both schedules the sum “A + B” is preserved.

No concurrency is allowed. Concurrency is allowed.

If a given non-serial schedule can be converted into a serial

Conflict serializability- Conflicting

Conflict serializability –example

• W1 (A) and R2 (A) are called as

Conflict serializability Checking Whether a Schedule is Conflict Serializable Or

Conflict serializability (example)

• We are unable to swap instructions in the above schedule to obtain either

Conflict serializability –Exercise example

Conflict serializability –Exercise example

Conflict serializability –Exercise example

Conflict serializability –Exercise example

• Clearly, there exists a cycle in the precedence graph.

Checking Whether a Schedule is View Serializable Or Not

Checking Whether a Schedule is View Serializable Or Not

Checking Whether a Schedule is View Serializable Or Not

• By using the above three conditions, write all the dependencies.

• Then, draw a graph using those dependencies.

• If there exists no cycle in the graph, then the schedule is view

Checking Whether a Schedule is View Serializable Or Not

Checking Whether a Schedule is View Serializable Or Not

We know, if a schedule is conflict serializable, then it is surely view serializable.

Checking Whether S is Conflict Serializable Or Not-

Checking Whether a Schedule is View Serializable Or Not

Draw the precedence graph-

•Clearly, there exists a cycle in the precedence graph.

Checking Whether a Schedule is View Serializable Or Not

Checking for Blind Writes-

Checking Whether a Schedule is View Serializable Or Not

• Drawing a Dependency Graph-

• T1 firstly reads A and T2 firstly updates A.

• Now, let us draw a dependency graph using these dependencies-

•Clearly, there exists no cycle in the dependency graph.

Two phase commit protocol

Two phase commit protocol

Two phase commit protocol

Two phase commit protocol

Two phase commit protocol

Two phase commit protocol