ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

TRANSACTION CONCEPTS
A transaction is a collection of operations that forms single logical unit of work.
Simple Transaction Example
1. Read your account balance
2. Deduct the amount from your balance
3. Write the remaining balance to your account
4. Read your friend‘s account balance
5. Add the amount to his account balance
6. Write the new updated balance to his account
This whole set of operations can be called a transaction
Transaction processing system
– The system with large database and hundreds of concurrent users that are executing database
transaction.
– Eg :reservation system , banking system etc
(i) Concurrent access
 Mutiple user accessing a system at the same time
 Single user-one user at a time can use a system
 Multi user-many user use the system at a time.
 It can be achieved by multiprogramming:
(ii) Parallel- multi-users access different resources at the same time.

(iii) Interleaved- Multiple users access a single resource based on time

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Transaction access data using two operations

• Read(x)
It transfer the data item x from the database to a local buffer belonging to the transaction
that executed the read operation.
• Write(x)
It transfer the data item x from the local buffer of the transaction to the database i.e. it
write back to the database
ACID Properties
To ensure the integrity of data during a transaction, the database system maintains the
following properties. These properties are widely known as ACID properties:
(i) Atomicity − This property states that a transaction must be treated as an atomic unit, that is,
either all of its operations are executed or none.
There must be no state in a database where a transaction is left partially completed.
States should be defined either before the execution of the transaction or after the
execution/abortion/failure of the transaction.
(ii) Consistency −
The database must remain in a consistent state after any transaction. No transaction
should have any adverse effect on the data residing in the database. If the database was in a
consistent state before the execution of a transaction, it must remain consistent after the
execution of the transaction as well.
(iii) Durability −

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

The database should be durable enough to hold all its latest updates even if the system
fails or restarts. If a transaction updates a chunk of data in a database and commits, then the
database will hold the modified data.
If a transaction commits but the system fails before the data could be written on to the
disk, then that data will be updated once the system springs back into action.
(iv) Isolation −
In a database system where more than one transaction are being executed
simultaneously and in parallel, the property of isolation states that all the transactions will be
carried out and executed as if it is the only transaction in the system. No transaction will affect
the existence of any other transaction.
Example : Example of Fund Transfer
transaction to transfer $50 from account A to account B:
1. read(A)
2. A := A – 50
3. write(A)
4. read(B)
5. B := B + 50
6. write(B)
Atomicity requirement
– if the transaction fails after step 3 and before step 6, money will be ―lost‖ leading to
an inconsistent database state
– the system should ensure that updates of a partially executed transaction are not
reflected in the database
Durability requirement
– once the user has been notified that the transaction has completed, the updates to the
database by the transaction must persist even if there are software or hardware failures.
Isolation requirement
— if between steps 3 and 6, another transaction T2 is allowed to access the partially
updated database, it will see an inconsistent database T1 T2
1. read(A)

2. A := A – 50

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

3. write(A)

#read(A), read(B), print(A+B)

4. read(B)

5. B := B + 50

6. write(B)

Isolation can be ensured trivially by running transactions serially– that is, one after the
other.

States of Transactions
A transaction in a database can be in one of the following states −

 Active − In this state, the transaction is being executed. This is the initial state of every
transaction.
 Partially Committed − When a transaction executes its final operation, it is said to be in
a partially committed state.
 Failed − A transaction is said to be in a failed state if any of the checks made by the
database recovery system fails. A failed transaction can no longer proceed further.
 Aborted − If any of the checks fails and the transaction has reached a failed state, then
the recovery manager rolls back all its write operations on the database to bring the
database back to its original state where it was prior to the execution of the transaction.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Transactions in this state are called aborted. The database recovery module can select
one of the two operations after a transaction aborts −
o Re-start the transaction
o Kill the transaction
 Committed − If a transaction executes all its operations successfully, it is said to be
committed. All its effects are now permanently established on the database system.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

SCHEDULES:
Schedule is a sequences of instructions that specify the chronological order in which
instructions of concurrent transactions are executed
 A schedule for a set of transactions must consist of all instructions of those
transactions
 must preserve the order in which the instructions appear in each individual
transaction.
Serial Schedule
It is a schedule in which transactions are aligned in such a way that one transaction is
executed first. When the first transaction completes its cycle, then the next transaction is
executed. Transactions are ordered one after the other. This type of schedule is called a serial
schedule, as transactions are executed in a serial manner.
Schedule 1
• Let T1 transfer 50 from A to B, and T2 transfer 10% of the balance from A to B.
• A serial schedule in which T1 is followed by T2 :

Schedule 2
• A serial schedule where T2 is followed by T1

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Schedule 3
• Let T1 and T2 be the transactions defined previously. The following schedule is not a
serial schedule, but it is equivalent to Schedule 1.

Schedule 4
The following concurrent schedule does not preserve the value of (A + B ).

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

SERIALIZABILITY
 When multiple transactions are running concurrently then there is a possibility that the
database may be left in an inconsistent state.

 Serializability is a concept that helps us to check which schedules are serializable. A

serializable schedule is the one that always leaves the database in consistent state.
• Serializability is the classical concurrency scheme.
• It ensures that a schedule for executing concurrent transactions is equivalent to one
that executes the transactions serially in some order.
Serializable schedule
If a schedule is equivalent to some serial schedule then that schedule is called Serializable
schedule
Let us consider a schedule S.
What the schedule S says ?
 Read A after updation.
 Read B before updation.

Let us consider 3 schedules S1, S2, and S3. We have to check whether they are serializable with
S or not ?

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Types of Serializability
1. Conflict Serializability
2. View Serializability
1. Conflict Serializable
Any given concurrent schedule is said to be Conflict Serializable if and only if it is Conflict
equivalent to one of the possible serial schedule.
Two schedules would be conflicting if they have the following properties
– Both belong to separate transactions.
– Both accesses the same data item.
– At least one of them is "write" operation.
Conflicting Instructions :
li and lj of transactions Ti and Tj respectively, conflict if they are operations by different
transaction on the same data item, and at least one of these instruction is write operation.
1. li = read(Q), lj = read(Q). li and lj don‘t conflict.
2. li = read(Q), lj = write(Q). They conflict.
3. li = write(Q), lj = read(Q). They conflict

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

4. li = write(Q), lj = write(Q). They conflict

Two schedules having multiple transactions with conflicting operations are said to be conflict
equivalent if and only if
 Both the schedules contain the same set of Transactions.
 The order of conflicting pairs of operation is maintained in both the schedules.
 If a schedule S can be transformed into a schedule S´ by a series of swaps of non-
conflicting instructions, we say that S and S´ are conflict equivalent.
 We say that a schedule S is conflict serializable if it is conflict equivalent to a serial
schedule
 Schedule 3 can be transformed into Schedule 6, a serial schedule where T2 follows T1, by
series of swaps of non-conflicting instructions. Therefore Schedule 3 is conflict
serializable.

Schedule 3

Schedule 6

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

2. View Serializable
Any given concurrent schedule is said to be View Serializable if and only if it is View
equivalent to one of the possible serial schedule.
Let S and S´ be two schedules with the same set of transactions. S and S´ are view equivalent if
the following three conditions are met, for each data item Q,
1. If in schedule S, transaction Ti reads the initial value of Q, then in schedule S’ also
transaction Ti must read the initial value of Q.
2. If in schedule S, transaction Ti executes read(Q), and that value was produced by
transaction Tj (if any), then in schedule S’ also transaction Ti must read the value of Q that was
produced by the same write(Q) operation of transaction Tj .
3. The transaction (if any) that performs the final write(Q) operation in schedule S must
also perform the final write(Q) operation in schedule S’.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

CONCURRENCY CONTROL
Concurrency control is the process of managing simultaneous execution of transactions
in a shared database, to ensure the serializability of transactions, is known as concurrency
control.
• Process of managing simultaneous operations on the database without having them interfere
with one another.
• Prevents interference when two or more users are accessing database simultaneously and at
least one is updating data.
• Although two transactions may be correct in themselves, interleaving of operations may
produce an incorrect result.
Need for Concurrent Execution in DBMS
o In a multi-user system, multiple users can access and use the same database at one time,
which is known as the concurrent execution of the database. It means that the same
database is executed simultaneously on a multi-user system by different users.
o While working on the database transactions, there occurs the requirement of using the
database by multiple users for performing different operations, and in that case,
concurrent execution of the database is performed.
o The thing is that the simultaneous execution that is performed should be done in an
interleaved manner, and no operation should affect the other executing operations, thus
maintaining the consistency of the database. Thus, on making the concurrent execution
of the transaction operations, there occur several challenging problems that need to be
solved.

Problems with Concurrent Execution

Simultaneous execution of transactions over a shared database can create several data
integrity and consistency problems.
• lost updated problem
• Temporary updated problem
• Incorrect summary problem
Problem 1: Lost Update Problems

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

The problem occurs when two different database transactions perform the read/write
operations on the same database items in an interleaved manner (i.e., concurrent execution)
that makes the values of the items incorrect hence making the database inconsistent.
For example:
Consider the below diagram where two transactions TX and TY, are performed on the
same account A where the balance of account A is $300.

 At time t1, transaction TX reads the value of account A, i.e., $300 (only read).
 At time t2, transaction TX deducts $50 from account A that becomes $250 (only
deducted and not updated/write).
 Alternately, at time t3, transaction TY reads the value of account A that will be $300
only because TX didn't update the value yet.
 At time t4, transaction TY adds $100 to account A that becomes $400 (only added but
not updated/write).
 At time t6, transaction TX writes the value of account A that will be updated as $250
only, as TY didn't update the value yet.
 Similarly, at time t7, transaction TY writes the values of account A, so it will write as
done at time t4 that will be $400. It means the value written by TX is lost, i.e., $250 is
lost.
 Hence data becomes incorrect, and database sets to inconsistent.
2. Temporary updated problem

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

 This problem occurs when one transaction updates a database item and then the
transaction fails for some reason. The updated item is accessed by another
transaction before it is changed back to its original value.
 Occurs when one transaction can see intermediate results of another transaction
before it has committed.

 At time t1, transaction TX reads the value of account A, i.e., $300.

 At time t2, transaction TX adds $50 to account A that becomes $350.
 At time t3, transaction TX writes the updated value in account A, i.e., $350.
 Then at time t4, transaction TY reads account A that will be read as $350.
 Then at time t5, transaction TX rollbacks due to server problem, and the value changes
back to $300 (as initially).
 But the value for account A remains $350 for transaction TY as committed, which is
the dirty read and therefore known as the Dirty Read Problem.
Incorrect summary problem
 If one transaction is calculating an aggregate summary function on a number of
records while other transactions are updating some of these records, the aggregate
function may calculate some values before they are updated and others after they
are updated.
 Occurs when transaction reads several values but second transaction updates some
of them during execution of first.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Example:
 T6 is totaling balances of account x (£100), account y (£50), and account z (£25).
 Meantime, T5 has transferred £10 from bal(x) to bal(z), so T6 now has wrong result (£10
too high).
 Problem avoided by preventing T6 from reading bal(x) and bal(z) until after T5 completed
updates.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

LOCKING PROTOCOLS
A lock is a variable associated with a data item that describe the statues of the item with
respect to possible operations that can be applied to it. Locking is an operation which secures
(a) Permission to Read
(b) Permission to Write a data item for a transaction.
Example:
Lock (X). Data item X is locked in behalf of the requesting transaction. Unlocking is an operation
which removes these permissions from the data item. Example:
Unlock (X): Data item X is made available to all other transactions. Lock and Unlock are Atomic
operations.

Lock Manager:
• Managing locks on data items.
Lock table:
• Lock manager uses it to store the identity of transaction locking a data item, the data
item, lock mode and pointer to the next data item locked. One simple way to implement a lock
table is through linked list
Types of lock
 Binary lock
 Read/write(shared / Exclusive) lock
Binary lock –
It can have two states (or) values 0 and 1.
0 – unlocked
1 - locked
▶ Lock value is 0 then the data item can accessed when requested.
▶ When the lock value is 1, the item cannot be accessed when requested.

Binary Lock

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Lock_item(x)
B : if lock(x) = 0 ( * item is unlocked * )
then lock(x) //1
else begin
wait ( until lock(x) = 0 )
goto B;
end;
Unlock_item(x)
B : if lock(x)=1 ( * item is locked * )
then unlock(x) \\ 0
else
printf (‗ already is unlocked ‗)
goto B;
end;
Read / write(shared/exclusive) lock
Read_lock
o Its also called shared-mode lock
o If a transaction Ti has obtain a shared-mode lock on item X, then Ti can read, but
cannot write , X.
o Outer transactions are also allowed to read the data item but cannot write.
Read_lock(x)
B : if lock(x) = “unlocked” then (1)
begin
lock(x) //“read_locked” )
read(x) //1
else if
lock(x) = “read_locked” then (2)
read(x) //no_of_read(x) +1
else begin
wait (until lock(x) = “unlocked”)
goto B;
end;

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Write_lock(x)
B : if lock(x) = “unlocked” then (1)
begin
lock(x) //”write_locked”
else if
lock(x) = “write_locked” (2)
wait ( until lock(x) = “unlocked”)
else begin
lock(x)=“read_locked” then (3)
wait ( until lock(x) = ―unlocked‖ )
end;

Unlock(x)
If lock(x) = “write_locked” then
begin
unlock(x) \\“unlocked”
else if
lock(x) = “read_locked” then
begin
read(x) \\no_of_read(x) - 1
if ( no_of_read(x) = 0 ) then
begin
unlock(x) \\“unlocked”
end

TWO PHASE LOCKING PROTOCOL

This protocol requires that each transaction issue lock and unlock request in two phases
 Growing phase
 Shrinking phase

Growing phase

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

During this phase new locks can be occurred but none can be released
Shrinking phase
During which existing locks can be released and no new locks can be occurred
Let’s see a transaction implementing 2-PL.

T1 T2

1 lock-S(A)

2 lock-S(A)

3 lock-X(B)

4 ……. ……

5 Unlock(A)

6 Lock-X(C)

7 Unlock(B)

8 Unlock(A)

9 Unlock(C)

10 …….

This is just a skeleton transaction which shows how unlocking and locking works with 2-PL. Note
for:
Transaction T1:
 Growing Phase is from steps 1-3.
 Shrinking Phase is from steps 5-7.
 Lock Point at 3
Transaction T2:
 Growing Phase is from steps 2-6.
 Shrinking Phase is from steps 8-9.
 Lock Point at 6
What is LOCK POINT ? The Point at which the growing phase ends, i.e., when transaction takes
the final lock it needs to carry on its work.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Types of two phase protocol

• Strict two phase locking protocol
• Rigorous two phase locking protocol

Strict two phase locking protocol

This protocol requires not only that locking be two phase, but also all exclusive locks taken
by a transaction be held until that transaction commits
Rigorous two phase locking protocol
This protocol requires that all locks be held until all transaction commits.
Consider the two transaction T1 and T2
T1 :
read(a1);
read(a2);
…….
read(an);
write(a1);
T2:
read(a1);
read(a2);

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

display(a1+a1);
Lock conversion
• Lock Upgrade
• Lock Downgrade
Lock upgrade:
 Conversion of existing read lock to write lock
 Take place in only the growing phase
if Ti has a read-lock (X) and Tj has no read-lock (X) (i != j)
then convert read-lock (X) to write-lock (X)
else
force Ti to wait until Tj unlocks X
Lock downgrade:
 Conversion of existing write lock to read lock
 Take place in only the shrinking phase
Ti has a write-lock (X) (*no transaction can have any lock on X*)
convert write-lock (X) to read-lock (X)

Log
 Log is a history of actions executed by a database management system to guarantee ACID
properties over crashes or hardware failures.
 Physically, a log is a file of updates done to the database, stored in stable storage.
Log rule

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

– A log records for a given database update must be physically written to the log, before
the update physically written to the database.
– All other log record for a given transaction must be physically written to the log, before
the commit log record for the transaction is physically written to the log.
– Commit processing for a given transaction must not complete until the commit log
record for the transaction is physically written to the log.

System log
– [ Begin transaction ,T ]
– [ write_item , T, X , oldvalue,newvalue]
– [read_item,T,X]
– [commit,T]
– [abort,T]
 Assumes fail-stop model – failed sites simply stop working, and do not cause any
other harm, such as sending incorrect messages to other sites.
 Execution of the protocol is initiated by the coordinator after the last step of the
transaction has been reached.
 The protocol involves all the local sites at which the transaction executed
 Let T be a transaction initiated at site Si, and let the transaction coordinator at Si
be Ci

Phase 1: Obtaining a Decision (prepare)

 Coordinator asks all participants to prepare to commit transaction Ti.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

o Ci adds the records <prepare T> to the log and forces log to stable storage
o sends prepare T messages to all sites at which T executed
 Upon receiving message, transaction manager at site determines if it can commit the
transaction
 if not, add a record <no T> to the log and send abort T message to Ci
 if the transaction can be committed, then:
 add the record <ready T> to the log
 force all records for T to stable storage
 send ready T message to Ci
Phase 2: Recording the Decision (commit)
 T can be committed of Ci received a ready T message from all the participating sites:
otherwise T must be aborted.
 Coordinator adds a decision record, <commit T> or <abort T>, to the log and forces record
onto stable storage. Once the record stable storage it is irrevocable (even if failures occur)
 Coordinator sends a message to each participant informing it of the decision (commit or
abort)
 Participants take appropriate action locally.
Handling of Failures - Site Failure
When site Si recovers, it examines its log to determine the fate of transactions active at the time
of the failure.
• Log contain <commit T> record: site executes redo (T)
• Log contains <abort T> record: site executes undo (T)
• Log contains <ready T> record: site must consult Ci to determine the fate of T.
– If T committed, redo (T)
– If T aborted, undo (T)
• The log contains no control records concerning T replies that Sk failed before responding to the
prepare T message from Ci
– since the failure of Sk precludes the sending of such a response Ci must abort T
– Sk must execute undo (T)
Handling of Failures- Coordinator Failure
If coordinator fails while the commit protocol for T is executing then participating sites must
decide on T‘s fate:

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

1. If an active site contains a <commit T> record in its log, then T must be committed.
2. If an active site contains an <abort T> record in its log, then T must be aborted.
3. If some active participating site does not contain a <ready T> record in its log, then the
failed coordinator Ci cannot have decided to commit T. Can therefore abort T.
4. If none of the above cases holds, then all active sites must have a <ready T> record in
their logs, but no additional control records (such as <abort T> of <commit T>).
In this case active sites must wait for Ci to recover, to find decision.
• Blocking problem : active sites may have to wait for failed coordinator to recover.

Handling of Failures - Network Partition

 If the coordinator and all its participants remain in one partition, the failure has no effect
on the commit protocol.
 If the coordinator and its participants belong to several partitions:
– Sites that are not in the partition containing the coordinator think the coordinator
has failed, and execute the protocol to deal with failure of the coordinator.
 No harm results, but sites may still have to wait for decision from coordinator.
 The coordinator and the sites are in the same partition as the coordinator think that the
sites in the other partition have failed, and follow the usual commit protocol.
 Again, no harm results

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

DEADLOCK
In a database, a deadlock is an unwanted situation in which two or more transactions are waiting
indefinitely for one another to give up locks. Deadlock is said to be one of the most feared complications
in DBMS as it brings the whole system to a Halt.
Example – let us understand the concept of Deadlock with an example :
Suppose, Transaction T1 holds a lock on some rows in the Students table and needs to
update some rows in the Grades table. Simultaneously, Transaction T2 holds locks on those very
rows (Which T1 needs to update) in the Grades table but needs to update the rows in the Student
table held by Transaction T1.
Now, the main problem arises. Transaction T1 will wait for transaction T2 to give up lock,
and similarly, transaction T2 will wait for transaction T1 to give up the lock. As a consequence,
All activity comes to a halt and remains at a standstill forever unless the DBMS detects the
deadlock and aborts one of the transactions.
System is deadlocked if there is a set of transactions such that every transaction in the
set is waiting for another transaction in the set. Consider the following two transactions:
T1: T2
write (A) write(A)
write (B) write(B)

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Deadlock Handling
Deadlock prevention protocol Ensure that the system will never enter into a deadlock
state.
Some prevention strategies :
Approach1
– Require that each transaction locks all its data items before it begins execution either all are
locked in one step or none are locked.
Disadvantages
o Hard to predict, before transaction begins, what data item need to be locked.
o Data item utilization may be very low.
Approach 2 – Assign a unique timestamp to each transaction. – These timestamps only to
decide whether a transaction should wait or rollback.
Deadlock prevention Schemes:
- wait-die scheme
- wound-wait scheme
(i) wait-die scheme
 Non preemptive technique
 When transaction Ti request a data item currently held by Tj, Ti is allowed to wait
only if it has a timestamp smaller than that of Tj. otherwise ,Ti rolled back(dies)
 Older transaction may wait for younger one to release data item. Younger
transactions never wait for older ones; they are rolled back instead.
 A transaction may die several times before acquiring needed data item

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Example.
Transaction T1,T2,T3 have time stamps 5,10,15,respectively.
 if T 1 requests a data item held by T2,then T1 will wait.
 If T3 request a data item held by T2,then T3 will be rolled back.
(ii) Wound-wait scheme
 Preemptive technique
 When transaction Ti requests a data item currently held by Tj,Ti is allowed to wait
only if it has a timestamp larger than that of Tj. Otherwise Tj is rolled back
 Older transaction wounds (forces rollback) of younger transaction instead of
waiting for it. Younger transactions may wait for older ones.
Example
Transaction T1,T2,T3 have time stamps 5,10,15,respectively.
 if T1 requests a data item held by T2,then the data item will be preempted from T2,and
T2 will be rolled back.
 If T3 requests a data item held by T2,then T3 will wait.
DeadLock Detection
Deadlocks can be described as a wait-for graph, which consists of a pair G = (V,E)
– V is a set of vertices
– E is a set of edges
 If Ti ->Tj is in E, then there is a directed edge from Ti to Tj, implying that Ti is waiting for
Tj to release a data item.
 The system is in a deadlock state if and only if the wait-for graph has a cycle. Must invoke
a deadlock-detection algorithm periodically to look for cycles.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Recovery from deadlock

• The common solution is to roll back one or more transactions to break the deadlock.
• Two action need to be taken
– Selection of victim
– Rollback
Selection of victim
• Set of deadlocked transactions, must determine which transaction to roll back to break the
deadlock.
• Consider the factor minimum cost

Rollback
• once we decided that a particular transaction must be rolled back, must determine how far this
transaction should be rolled back
• Total rollback
• Partial rollback
Starvation :
Starvation or Livelock is the situation when a transaction has to wait for a indefinite
period of time to acquire a lock.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Reasons of Starvation –
 If waiting scheme for locked items is unfair. ( priority queue )
 Victim selection. (same transaction is selected as a victim repeatedly )
 Resource leak.
 Via denial-of-service attack.
Starvation can be best explained with the help of an example
 Suppose there are 3 transactions namely T1, T2, and T3 in a database that are
trying to acquire a lock on data item ‘ I ‘.
 Now, suppose the scheduler grants the lock to T1(maybe due to some priority),
and the other two transactions are waiting for the lock.
 As soon as the execution of T1 is over, another transaction T4 also come over and
request unlock on data item I. Now, this time the scheduler grants lock to T4, and
T2, T3 has to wait again.
 In this way if new transactions keep on requesting the lock, T2 and T3 may have
to wait for an indefinite period of time, which leads to Starvation.
What are the solutions to starvation –
(i) Increasing Priority –
Starvation occurs when a transaction has to wait for an indefinite time, In this situation,
we can increase the priority of that particular transaction/s. But the drawback with this
solution is that it may happen that the other transaction may have to wait longer until the
highest priority transaction comes and proceeds.
(ii) Modification in Victim Selection algorithm –
If a transaction has been a victim of repeated selections, then the algorithm can be
modified by lowering its priority over other transactions.
(iii) First Come First Serve approach –
A fair scheduling approach i.e FCFS can be adopted, In which the transaction can
acquire a lock on an item in the order, in which the requested the lock.
(iv) Wait die and wound wait scheme –
These are the schemes that use the timestamp ordering mechanism of transaction.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Intent locking
• Intent locks are put on all the ancestors of a node before that node is locked explicitly.
• If a node is locked in an intention mode, explicit locking is being done at a lower level
of the tree.
Types of Intent Locking
• Intent shared lock(IS)
• Intent exclusive lock(IX)
• Shared lock (S)
• Shared Intent exclusive lock (SIX)
• Exclusive lock (X)
Intent shared lock(IS)
 If a node is locked in indent shared mode, explicit locking is being done at a lower level
of the tree, but with only shared-mode lock
 Suppose the transaction T1 reads record ra2 in file Fa. Then,T1 needs to lock the
database, area A1,and Fa in IS mode, and finally lock ra2 in S mode.
Intent exclusive lock(IX)
 If a node is locked in intent locking is being done at a lower level of the tree, but with
exclusive mode or shared-mode locks.
 Suppose the transaction T2 modifies record ra9 in file Fa. Then,T2 needs to lock the
database, area A1,and Fa in IX mode, and finally to lock ra9 in X mode.
Shared Intent exclusive lock (SIX)
If the node is locked in Shared Intent exclusive mode, the subtree rooted by that node is
locked explicitly in shared mode, and that explicit locking is being done at lower level with
exclusive mode
Shared lock (S)
-T can tolerate concurrent readers but not concurrent updaters in R.
Exclusive lock (X)
-T cannot tolerate any concurrent access to R at all. Lock compatibility

CS3492-DATABASE MANAGEMENT SYSTEMS

📘 Multiple Granularity in DBMS
🧩 1. Introduction

• Granularity → means the size or level of data item on which locking (or
concurrency control) is applied.
• It can range from:
o Entire Database (coarse granularity)
o to Individual Fields/Records (fine granularity)

Example Levels of Data Granularity:

Database → Table → Page → Record → Field

• Multiple Granularity means supporting different levels of locking in a hierarchy —

so that transactions can choose lock size depending on their operations.

⚙️ 2. Need for Multiple Granularity

Without multiple granularity:

• If we always lock at record level → too many locks → high overhead.

• If we always lock at table level → less concurrency → poor performance.

Goal: Allow both coarse-grained and fine-grained locking simultaneously to balance

concurrency and efficiency.

🧱 3. Granularity Hierarchy
Multiple granularity uses a hierarchical structure of data items:
Database
├── Table (Relation)
│ ├── Page (Block)
│ │ └── Record
│ │ └── Field

Each level is considered a node in a tree.

🧩 4. Types of Locks Used

In Multiple Granularity, 5 types of locks are used to control access between levels.

Lock Type Meaning Purpose

S (Shared) Read-only access Allows concurrent reads

No other transaction can

X (Exclusive) Read & write access
read/write

Intends to set S locks on lower

IS (Intention-Shared) Signals shared intention
levels

IX (Intention- Intends to set X locks on lower Signals exclusive

Exclusive) levels intention

SIX (Shared and Holds S lock on item and intends For reading and exclusive
Intention-Exclusive) X locks on lower levels locking subitems

🔁 5. Lock Compatibility Matrix

Current Lock IS IX S SIX X

IS
 IX

SIX

= Compatible (can coexist) = Conflict (cannot coexist)

🧠 6. Locking Rules in Multiple Granularity

To ensure consistency and control, the following rules are used:

Rule 1: Intention Locks on Ancestors

Before locking a node, a transaction must first acquire an intention lock on all its
ancestor nodes.

Example: If a transaction wants to lock a record (X lock):

• It must first set IX on the table containing that record.

• Then it can set X on the record.

Rule 2: Lock Hierarchy

• Locks must be obtained from top (root) → downwards.

• Unlocking must happen bottom-up.
Rule 3: Consistency Checking

The lock manager ensures that no two conflicting locks are granted at the same time by
consulting the compatibility matrix.

Rule 4: Root Lock Requirement

Every transaction must start by locking the root (usually in IS or IX mode) before
proceeding to lower levels.

🧮 7. Example – Step-by-Step
Suppose we have:

Database → Table A → Record R1, R2

Transaction T1: wants to read all records in Table A Transaction T2: wants to update
Record R1

Step Transaction Operation Locks

1 T1 Lock Database in IS IS

2 T1 Lock Table A in S S

3 T2 Lock Database in IX IX

4 T2 Lock Table A in IX IX (conflict with S of T1 → waits)

Result: T1 can continue reading Table A. T2 must wait until T1 releases S lock → ensures
serializability.
⚖️ 8. Advantages of Multiple Granularity

Advantage Description

1. Balances concurrency & Fine locks → high concurrency; coarse locks → less
overhead overhead.

Transactions can choose lock size (record, page, or

2. Flexibility
table).

Large operations can lock higher level instead of many

3. Reduces number of locks
small locks.

4. Deadlock reduction Fewer locks → fewer chances of circular waiting.

5. Efficient resource
Manages both small and large transactions efficiently.
utilization

⚠️ 9. Disadvantages

Disadvantage Description

1. Complexity Managing hierarchy and intention locks adds overhead.

When too many fine locks → system may convert them into one
2. Lock escalation
large (coarse) lock automatically.

3. Possible reduced
Coarser locks prevent parallel access to small data items.
concurrency

🧩 10. Lock Escalation

• Definition: Automatic conversion of many fine-grained locks (e.g., records) into a
single coarse-grained lock (e.g., table).
• Purpose: Reduce lock table size and overhead.
 Example: If a transaction locks 1000 rows in a table, DBMS may escalate it to a table-
level X lock.

🧾 11. Example Locking Scenario

Hierarchy:

Database
├── Table A
│ ├── Record 1
│ └── Record 2
└── Table B

Transactions:

• T1: Read Table A → Lock(Database, IS), Lock(Table A, S)

• T2: Update Record 1 → Lock(Database, IX), Lock(Table A, IX), Lock(Record 1, X)

Both can coexist:

• IS (T1) and IX (T2) on Database → Compatible

• But S (T1) and IX (T2) on Table A → Conflict → T2 waits.

🧠 12. Summary Table

Concept Description

Granularity Level of data item for locking

Fine Granularity More concurrency, more overhead

Coarse Granularity Less overhead, less concurrency

Multiple Granularity Hierarchical locking at different levels

Intention Locks Indicate intention to acquire lower-level locks

Lock Escalation Convert many small locks into one big lock

Root Locking Rule Must lock ancestors before descendants

Unlock Order Bottom-up

📘 13. Key Exam Points

Question Short Answer

What is multiple
Technique allowing locks at different levels in a hierarchy.
granularity?

Why is it needed? To balance concurrency and locking overhead.

What are intention Locks that show a transaction’s intention to acquire lower-
locks? level locks.

List types of intention

IS, IX, SIX
locks.

What is lock escalation? Conversion of many fine-grained locks to one coarse lock.

Unlocking rule? Unlock bottom-up.

Main advantage? Increases efficiency and flexibility in locking.

🧩 14. Diagram (Conceptual View)

[Database]
/ \
IS/IX IS/IX
/ \
[Table A] [Table B]
 / \ \
S/IX S/IX S/IX
/ \
R1(X) R2(S)

Each node shows possible lock modes at multiple levels.

📘 Timestamp-Based Protocols in DBMS

🧩 1. Introduction
• Concurrency Control ensures that multiple transactions execute without conflict,
maintaining database consistency.
• One important method for concurrency control is the Timestamp-Based Protocol.

🧠 2. What is a Timestamp?
• A timestamp is a unique identifier assigned to each transaction.
• It indicates the start time of a transaction and determines its execution order.
• Usually generated using:
o System clock (time of start)
o Logical counter (incremented each time a new transaction begins)

Example:

T1 → Timestamp = 5
T2 → Timestamp = 10

⇒ T1 is older than T2 (started earlier).

⚙️ 3. Basic Idea of Timestamp Ordering Protocol

Goal: Ensure that transactions execute in timestamp order (older transactions appear to
execute before newer ones).

• Every transaction Ti gets a unique timestamp TS(Ti).

 • For each data item Q, DBMS maintains:
o WTS(Q) → timestamp of the last write on Q
o RTS(Q) → timestamp of the last read on Q

These are used to decide whether a read/write operation of a transaction is allowed or

should be rolled back (aborted).

📋 4. Rules of Timestamp Ordering Protocol

🔹 Rule 1: Read Operation (Read(Q))

If a transaction Ti wants to read a data item Q:

1. If TS(Ti) < WTS(Q) → Reject/Abort Ti (Ti is too late; Q has been written by a
newer transaction)
2. Else → Allow Read, and set RTS(Q) = max(RTS(Q), TS(Ti))

🔹 Rule 2: Write Operation (Write(Q))

If a transaction Ti wants to write Q:

1. If TS(Ti) < RTS(Q) → Abort Ti (Younger transaction has already read this Q →
causes inconsistency)
2. If TS(Ti) < WTS(Q) → Abort Ti (Younger transaction has already written Q)
3. Else → Perform Write, and set WTS(Q) = TS(Ti)

🧩 Rule Summary Table

Operation Condition Action

Read(Q) TS(Ti) < WTS(Q) Abort Ti

Read(Q) Otherwise Read allowed; update RTS(Q)

 TS(Ti) < RTS(Q) or TS(Ti) <
Write(Q) Abort Ti
WTS(Q)

Write(Q) Otherwise Write allowed; update WTS(Q)

🧮 5. Example
Assume:

WTS(Q) = 5, RTS(Q) = 3

Case 1:

Transaction T7 (TS=10) issues Read(Q): → TS(10) > WTS(5) → Read allowed. Update
RTS(Q) = max(3,10) = 10.

Case 2:

Transaction T4 (TS=4) issues Write(Q): → TS(4) < RTS(10) → Abort T4. Reason: a newer
transaction already read Q → cannot allow an old write.

🔁 6. Thomas’s Write Rule (Improved Protocol)

Used to reduce unnecessary aborts in timestamp ordering.

Rule Modification:

• If TS(Ti) < WTS(Q), instead of aborting Ti → ignore the obsolete write.

Reason: A newer transaction has already written Q → Ti’s write is outdated and can be
ignored.
🧠 Example:

WTS(Q) = 8
Ti has TS(Ti) = 5 and issues Write(Q)

Normally → abort Ti. Under Thomas’s Rule → ignore write (since newer value already exists).

This improves concurrency and reduces rollbacks.

⚖️ 7. Advantages

Advantage Explanation

Transactions never wait — they are aborted immediately if

No Deadlocks
conflict occurs.

Simple
Based on comparing timestamps only.
Implementation

Maintains
Always ensures schedule follows timestamp order.
Serializability

Supports
Allows parallel execution of non-conflicting transactions.
Concurrency

⚠️ 8. Disadvantages

Disadvantage Explanation

High Abort Rate Transactions may abort frequently due to timestamp conflicts.

Managing and comparing timestamps for each data item adds

Overhead
complexity.
Starvation Older transactions may get repeatedly aborted if conflicts occur
Possible with newer ones.

No Recovery Using
Transactions cannot wait; they must abort immediately.
Wait

🔍 9. Types of Timestamp-Based Protocols

Type Description

Basic Timestamp
Uses read/write rules based on timestamps.
Ordering (TO)

Thomas’s Write Rule Improved TO that ignores outdated writes instead of

(TWR) aborting.

Multiversion Timestamp Keeps multiple versions of data; each read gets version
Ordering (MVTO) matching its timestamp → higher concurrency.

🧾 10. Comparison with Lock-Based Protocol

Aspect Timestamp-Based Lock-Based

Control Mechanism Timestamp ordering Locking (shared/exclusive)

Deadlocks Not possible Possible

Starvation Possible Possible

Concurrency Level High (if few aborts) Medium

Complexity Moderate Moderate

Waiting No (immediate abort) Yes (wait for locks)

🧠 11. Summary (Key Points for Exam)

Concept Description

Timestamp Unique ID assigned to each transaction

Older Transaction Lower timestamp value

Younger Transaction Higher timestamp value

WTS(Q) Timestamp of last write on Q

RTS(Q) Timestamp of last read on Q

Read Rule Abort if TS(Ti) < WTS(Q)

Write Rule Abort if TS(Ti) < RTS(Q) or TS(Ti) < WTS(Q)

Thomas’s Rule Ignore outdated write instead of aborting

Advantages No deadlocks, ensures serializability

Disadvantages High abort rate, overhead, starvation possible

🧮 12. Example Summary Table

Transaction Operation Condition Action

T1 (TS=5) Read(Q) 5 < WTS(Q)=3? No Read allowed; RTS(Q)=5

T2 (TS=2) Write(Q) 2 < RTS(Q)=5 Abort

T3 (TS=8) Write(Q) 8 > RTS(Q)=5 Write allowed; WTS(Q)=8

🧩 13. Simple Diagram (Conceptual)
┌────────────────────────────┐
│ Transaction Ti starts │
└────────────────────────────┘
│
Assign Timestamp TS(Ti)
│
┌───────────────────────────────┐
│ If operation = READ(Q): │
│ If TS(Ti) < WTS(Q) → Abort │
│ Else Read + RTS(Q)=max(...)│
└───────────────────────────────┘
│
┌───────────────────────────────┐
│ If operation = WRITE(Q): │
│ If TS(Ti)<RTS(Q) or WTS(Q) │
│ → Abort / Ignore (TWR) │
│ Else Write + WTS(Q)=TS(Ti) │
└───────────────────────────────┘

✅ 14. Summary in One Line

Timestamp-Based Protocols ensure serializable execution by ordering transactions
based on their timestamps — older transactions execute first, newer ones may wait or
abort, ensuring consistency without using locks.

Would you like me to next give “Multiversion Timestamp Ordering Protocol (MVCC /
MVTO)” — explained in the same structured way with example and diagrams (used in
modern databases like PostgreSQL and Oracle)?
 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

TRANSACTION RECOVERY
Recovery algorithms are techniques to ensure database consistency and transaction
atomicity and durability despite failures

Recovery using Log records (Log-Based Recovery)

o The log is a sequence of records. Log of each transaction is maintained in some stable
storage so that if any failure occurs, then it can be recovered from there.
o If any operation is performed on the database, then it will be recorded in the log.
o But the process of storing the logs should be done before the actual transaction is
applied in the database.

When the system is crashed, then the system consults the log to find which transactions need
to be undone and which need to be redone.

1. If the log contains the record <Ti, Start> and <Ti, Commit> or <Ti, Commit>, then the
Transaction Ti needs to be redone.
2. If log contains record<Tn, Start> but does not contain the record either <Ti, commit> or
<Ti, abort>, then the Transaction Ti needs to be undone.
Recovery algorithms have two parts
1. Actions taken during normal transaction processing to ensure enough information exists
to recover from failures
2. Actions taken after a failure to recover the database contents to a state that ensures
atomicity, consistency and durability
Example
Begin transaction
Update Acc 1001{balance:=Balance-100};
If any error occurred then Goto Undo;
End if;
Update Acc 1002{balance:=balance+100};
If any error occurred then Goto undo;
End if;
Commit;

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Goto finish;
Undo: rollback;
Finish: return;

Requirement for recovery

 Implicit rollback
 Message handling
 Recovery log
 Statement atomicity
 No nested transaction
Transaction recovery
Database updates are kept in buffer in main memory and not physically written to disk
until commit.
System recovery
 Local failures –affect only the transaction which the failure has actually occurred.
 Global failures- affect all the transaction in progress at the time of failure.
 System failure – do not physically damage the DB Eg: power shut down Media failure-
cause damage to the DB. Eg: head crash ARIES

Recovery using Checkpoints:

Checkpoints:

o Keeping and maintaining logs in real time and in real environment may fill out all the
memory space available in the system. As time passes, the log file may grow too big to be
handled at all. The checkpoint is a type of mechanism where all the previous logs are
removed from the system and permanently stored in the storage disk.
o The checkpoint is like a bookmark. While the execution of the transaction, such
checkpoints are marked, and the transaction is executed then using the steps of the
transaction, the log files will be created.
o When it reaches to the checkpoint, then the transaction will be updated into the
database, and till that point, the entire log file will be removed from the file. Then the log
file is updated with the new step of transaction till next checkpoint and so on.
o The checkpoint is used to declare a point before which the DBMS was in the consistent
state, and all transactions were committed.

CS3492-DATABASE MANAGEMENT SYSTEMS

 ROHINI COLLEGE OF ENGINEERING & TECHNOLOGY

Recovery Algorithm
ARIES-Algorithm for Recovery and Isolation Exploiting Semantics
ARIES recovery involves three passes
 Analysis pass: Determines the REDO and UNDO lists.
 Redo pass: Repeats history, redoing all actions from REDO List
 Undo pass: Rolls back all incomplete transactions

The system failure occurred at time Tf , the most recent check point prior to the time Tf was
taken at a time Tc
 Start with two list of transaction the UNDO and REDO list
 Search forward through the log starting from check point.
 If begin transaction log record is found for transaction(T) add T to UNDO list.
 If commit log record is found for transaction(T),add T to REDO list
 When the end of log record is reached the UNDO and REDO list is identified
UNDO : T3 T2
REDO : T5 T4

CS3492-DATABASE MANAGEMENT SYSTEMS

📘 DBMS Recovery System — Lecture
Notes
🧩 1. Introduction

• A Recovery System in DBMS ensures that the database remains consistent even
after failures (like system crash, power failure, or transaction error).
• Its goal is to make the database appear as if the failure never occurred.

Key Idea:

The DBMS must maintain the property that every transaction is Atomic and Durable (A & D
of the ACID properties).

⚙️ 2. Types of Failures

Type Description Example

1. Transaction A transaction fails before Division by zero, logical

Failure completion. error, or system abort.

Hardware/software failure leads

2. System Crash Power failure, OS crash.
to loss of volatile data.

Data on disk is corrupted or

3. Disk Failure Head crash, bad sectors.
inaccessible.

4.
Media/Communica Errors in distributed systems. Network disconnection.
tion Failure
🧠 3. Goals of Recovery System
1. Atomicity: A transaction is either executed completely or not at all.
2. Durability: Once a transaction is committed, its effects must persist even after
failure.
3. Consistency: Database moves from one consistent state to another.
4. Isolation: Recovery must not interfere with concurrent transactions.

💾 4. Storage Structure

Storage Type Property Volatile?

Yes (e.g., Main Memory,

Volatile Storage Lost on power failure
Cache)

Non-Volatile
Retains data permanently No (e.g., Disk, SSD)
Storage

Never lost (theoretical

Stable Storage Idealized for logs/backups
model)

Stable Storage is simulated by storing redundant copies on different devices.

📋 5. Transaction States (Recap)

Active → Partially Committed → Committed
↓ ↓
Failed ← Aborted

• Active: Transaction is executing.

• Partially Committed: Final statement executed.
• Committed: All changes made permanent.
• Failed: Error detected.
 • Aborted: Changes undone; transaction rolled back.

🧱 6. Concept of Log-Based Recovery

Log: A sequential record of all database modifications. Stored in stable storage.

• Each log record contains:

<Transaction_ID, Data_Item, Old_Value, New_Value>

Purpose: To redo committed transactions and undo incomplete transactions after a

crash.

Example Log Records

Transaction Log Record

Start of T1 <T1, Start>

Update A from 200 → 500 <T1, A, 200, 500>

Commit <T1, Commit>

🔁 7. Log-Based Recovery Steps

After a crash:

1. Scan the log backwards.

2. Identify transactions that:
a. Committed → REDO them.
b. Incomplete (no COMMIT) → UNDO them.
REDO (Reapply Changes):

Re-execute all updates of committed transactions to ensure durability.

UNDO (Rollback Changes):

Reverse updates of uncommitted transactions to maintain atomicity.

⚖️ 8. Deferred and Immediate Update

Technique Description Action before Commit

Changes written to log first;

Deferred Update No changes on disk
database updated only after
(NO-UNDO/REDO) before commit.
commit.

Immediate Update Changes written to both log and Requires both undo and
(UNDO/REDO) database before commit. redo during recovery.

Deferred update is safer (atomicity), Immediate update improves performance

(parallelism).

🧮 9. Checkpoints
Definition: A checkpoint is a snapshot of the current database state written to disk
periodically.

Purpose:

• Limits the amount of log data to process after crash.

• Reduces recovery time.
Checkpoint Process:

1. Suspend new transactions.

2. Flush all log records to disk.
3. Write all modified (dirty) buffers to disk.
4. Write a <Checkpoint> record in the log.
5. Resume transaction processing.

During Recovery:

• Start scanning logs from the last checkpoint instead of the beginning → faster
recovery.

🔁 10. Shadow Paging (Non-Logging Recovery)

An alternative recovery technique without using logs.

📘 Concept:

• Maintain two page tables:

o Current Page Table
o Shadow Page Table
• Shadow table → points to original database pages (stable).
• Current table → points to new updated pages.

Commit: Swap the shadow and current tables. Failure: Discard current table →
shadow table remains intact.

Advantages:

• No need for logs.

• Easy rollback — just switch page tables.
Disadvantages:

• High overhead (copy of page table).

• Poor performance with large databases.

⚙️ 11. ARIES Recovery Algorithm (Advanced)

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) → Used in modern
DBMS (Oracle, SQL Server).

Steps:

1. Analysis Phase: Identify committed and uncommitted transactions.

2. Redo Phase: Reapply all actions to ensure durability.
3. Undo Phase: Roll back incomplete transactions.

Uses Write-Ahead Logging (WAL): → Log record is written before actual data is written
to disk.

📘 12. Write-Ahead Logging (WAL) Rule

Before any data item is written to disk:

1. Its log record must be written to stable storage.

2. Ensures that database can redo or undo any change using logs.

⚠️ 13. Recovery with Concurrent Transactions

• Uses log sequence numbers (LSN) to maintain order of updates.
• Each log entry is uniquely identified by its LSN.
• DBMS ensures serializability and consistency even with multiple transactions.
🧾 14. Summary Table

Concept Description Purpose

Sequence of transaction
Log File Base for recovery
updates

Undo Rollback uncommitted changes Maintain atomicity

Redo Reapply committed changes Maintain durability

Checkpoint Snapshot of database state Faster recovery

Deferred Update Changes only after commit No undo needed

Immediate
Changes before commit Undo + Redo needed
Update

Shadow Paging Uses duplicate page tables No log required

ARIES Modern log-based recovery Used in real DBMS

Guarantees recovery
WAL Rule Write log before data
correctness

🧠 15. Example – Crash Scenario

Transactions:

<T1, Start>
<T1, A, 200, 500>
<T2, Start>
<T2, B, 100, 300>
<T1, Commit>
System Crash

During Recovery:
 • T1 committed → REDO (A=500)
• T2 incomplete → UNDO (B=100)

Final Database:

A = 500
B = 100

⚖️ 16. Advantages of Recovery System

Advantage Explanation

Ensures Atomicity Uncommitted changes removed

Ensures Durability Committed data persists

Maintains Consistency DB always in valid state

Reduces Data Loss Uses log and checkpoints

Supports Concurrent Transactions Works with multiple users safely

⚠️ 17. Limitations

Limitation Description

Performance Overhead Logging and checkpointing consume resources

Complex Implementation Recovery management is intricate

Requires Stable Storage Assumes reliable non-volatile media

Delays Checkpointing may briefly halt system

🧩 18. Diagram — Recovery Process
┌──────────────────┐
│ Transaction Log │
└──────┬───────────┘
│
┌─────────────┴──────────────┐
│ │
REDO (Committed Tx) UNDO (Incomplete Tx)
│ │
▼ ▼
Apply changes Rollback changes
▼ ▼
Database restored to consistent state

🧠 19. Key Terms (for Exams)

Term Definition

Stable Storage Non-volatile media for logs

WAL Rule Write log before data

Checkpoint Synchronization point for recovery

Redo/Undo Recovery operations

ARIES Advanced recovery algorithm

Shadow Paging Recovery without logging

Deferred/Immediate Update Two log-based approaches

✅ 20. Summary in One Line
The Recovery System ensures that a database remains consistent and durable after any
failure by using logs, checkpoints, and recovery algorithms (Redo/Undo/ARIES) to
restore the database to its last consistent state.

Would you like me to next give “ARIES Recovery Algorithm (Detailed Steps with Example
and Diagram)” — explained in the same exam-note style (step-by-step)?