• Transaction Concept

• ACID Properties
• Serializability
• Concurrency Control: Need of
Concurrency Control, Lock-Based
Protocols
• Recovery: Failure Classification,
Shadow paging
Presented by:
LB Gurung
lbgurung00@gmail.com

7/3/2023 lbgurung00@gmail.com 1
 ✓ What is Transaction?
• A transaction is a set of logically related operations
or
• A transaction is a program unit whose execution may or may not
change the contents of a database.
❑ Introduction to
Or
Transaction • A transaction is a single logical action which accesses and modify
the contents of the database through reading and write
operations
• Logical unit of database processing that includes one or more
access operations(read/retrieval , write/insert, update, delete)

7/3/2023 lbgurung00@gmail.com 2
 Simple Transaction Example:
1. Read your account balance
2. Deduct the amount from your balance
3. Write the remaining balance to your account
❑ Introduction to 4. Read your friend’s account balance
Transaction 5. Add the amount to his account balance

processing: 6. Write the new updated balance to his account

This whole set of operations(read,write,update) can be called a
transaction. But transaction can have operations like read, write,
insert, update, delete.

7/3/2023 lbgurung00@gmail.com 3
 Let’s take an example of a simple transaction. Suppose a bank employee
transfers Rs 500 from A's account to B's account. This very simple and small
transaction involves several low-level tasks.

A’s Account:
B’s Account
Open_Account(A) Open_Account(B)

❑ Introduction to Old_Balance = A.balance Old_Balance = B.balance

New_Balance = Old_Balance - 500 New_Balance = Old_Balance + 500
Transaction B.balance = New_Balance
A.balance = New_Balance
processing: Close_Account(A) Close_Account(B)

Characteristic operations:
✓ Reads (database retrieval, such as SQL SELECT) •
✓ Writes (modify database, such as SQL INSERT, UPDATE, DELETE)

Note: Each execution of a program is a distinct transaction with different

parameters
7/3/2023 lbgurung00@gmail.com 4
 Lets say your account is X and your friend’s account is Y, you are
transferring 10000 from X to Y, the steps of the transaction are:

Steps:
1. R(X);
❑ Introduction to 2. X = X - 10000;
3. W(X);
Transaction
4. R(Y);
processing: 5. Y = Y + 10000;
6. W(Y);
In the above transaction R refers to the Read
operation and W refers to the write operation.

7/3/2023 lbgurung00@gmail.com 5
 Concurrency problems:
Several problems can occur when concurrent transactions are run in an
uncontrolled manner, such type of problems is known as concurrency
problems.
There are following different types of problems or conflicts which
❑ Why occur due to concurrent execution of transaction:
concurrency Problems with Concurrent Execution
• In a database transaction, the two main operations
control is
are READ and WRITE operations.
needed?
• So, there is a need to manage these two operations in the
concurrent execution of the transactions as if these operations are
not performed in an interleaved manner, and the data may become
inconsistent. So, the following problems occur with the Concurrent
Execution of the operations:
7/3/2023 lbgurung00@gmail.com 6
 Problem 1: Lost Update Problems (W - W Conflict)

✓ This problem occurs when two different database

transactions perform the read/write operations on the
same database items in an interleaved manner (i.e.,
❑ Why
concurrent execution) that makes the values of the
concurrency
items incorrect hence making the database
control is
inconsistent.
needed? ✓ If there are two transactions Tx and Ty accessing the same data
item value and then update it, then the second record overwrites
the first record.

7/3/2023 lbgurung00@gmail.com 7
 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.

❑ Why
concurrency
control is
needed?

7/3/2023 lbgurung00@gmail.com 8
 ✓ 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
❑ Why will be $300 only because TX didn't update the value yet.
concurrency ✓ At time t4, transaction TY adds $100 to account A that becomes $400
(only added but not updated/write).
control is
✓ At time t6, transaction TX writes the value of account A that will be
needed? 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.

7/3/2023 lbgurung00@gmail.com 9
 Lost Update Problem:
In the lost update problem, an update done to a data item by a transaction is
lost as it is overwritten by the update done by another transaction.
Example:

❑ Why
concurrency
control is
needed?

In the above example, transaction T1 changes the value of X but it gets

overwritten by the update done by transaction T2 on X. Therefore, the
update done by transaction T1 is lost.
7/3/2023 lbgurung00@gmail.com 10
 Dirty Read Problems (W-R Conflict)
The dirty read problem occurs when one transaction updates an item of the
database, and somehow the transaction fails, and before the data gets rollback,
the updated database item is accessed by another transaction. There comes the
Read-Write Conflict between both transactions.

❑ Why
For example:
Consider two transactions TX and TY in the below diagram performing read/write
concurrency
operations on account A where the available balance in account A is $300:

control is
needed?

7/3/2023 lbgurung00@gmail.com 11
 ✓ 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
❑ Why changes back to $300 (as initially).

concurrency 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.
control is
needed?

7/3/2023 lbgurung00@gmail.com 12
 ▪ Unrepeatable Read Problem (W-R Conflict)
Also known as Inconsistent Retrievals Problem that occurs when in a
transaction, two different values are read for the same database item.

For example:
Consider two transactions, TX and TY, performing the read/write operations

❑ Why on account A, having an available balance = $300. The diagram is shown

below:
concurrency
control is
needed?

7/3/2023 lbgurung00@gmail.com 13
 Unrepeatable Read Problem (W-R Conflict)

✓ At time t1, transaction TX reads the value from account A, i.e., $300.
✓ At time t2, transaction TY reads the value from account A, i.e., $300.
✓ At time t3, transaction TY updates the value of account A by adding $100
to the available balance, and then it becomes $400.

❑ Why ✓ At time t4, transaction TY writes the updated value, i.e., $400.
✓ After that, at time t5, transaction TX reads the available value of account
concurrency
A, and that will be read as $400.
control is ✓ It means that within the same transaction TX, it reads two different

needed? values of account A, i.e., $300 initially, and after updation made by
transaction TY, it reads $400. It is an unrepeatable read and is therefore
known as the Unrepeatable read problem.
Thus, in order to maintain consistency in the database and avoid such
problems that take place in concurrent execution, management is needed, and
that is where the concept of Concurrency Control comes into role.
7/3/2023 lbgurung00@gmail.com 14
 ✓ A computer failure (system crash):
A hardware or software error occurs in the computer system during
transaction execution. If the hardware crashes, the contents of the
computer’s internal memory may be lost.
❑ Why Recovery
✓ A transaction or system error:
is needed? Some operation in the transaction may cause it to fail, such as integer

Or What causes a overflow or division by zero. Transaction failure may also occur because of
erroneous parameter values or because of a logical programming error. In
Transaction to fail
addition, the user may interrupt the transaction during its execution.
✓ Local errors or exception conditions detected by the transaction:
During transaction execution, certain conditions may occur that necessitate
cancellation of the transaction. For example, data for the transaction may not
be found, insufficient balance in bank account, etc.
7/3/2023 lbgurung00@gmail.com 15
 ✓ Concurrency control environment:
✓ The concurrency control method may decide to abort the
transaction, to be restarted later, because several transactions
❑ Why Recovery are in a state of deadlock

is needed? ✓ Disk failure: Some disk blocks may lose their data because of a
read or write malfunction of because of a disk read/write head
Or What causes a
crash.
Transaction to fail
✓ Physical problems and catastrophes: This refers to an endless
list of problems that includes power or air-conditioning failure,
fire, theft, overwriting disks or tapes by mistake, etc.
.

7/3/2023 lbgurung00@gmail.com 16
 ✓ A transaction is a single logical unit of work which accesses and possibly
modifies the contents of a database.
✓ A transaction is an atomic unit of work that is either completed in its
entirety or not done at all
❑ Transaction and
Transaction states:
System For recovery purposes, the system needs to keep track of when the
Concepts transaction starts, terminates, and commits or aborts. Therefore, the
recovery manager keeps track of the following operations or A transaction in
DBMS can be in one of the following states.

7/3/2023 lbgurung00@gmail.com 17
❑ Transaction and
System State Transaction types

A transaction enters into an active state when the execution process begins.
Concepts Active State
During this state read or write operations can be performed.

A transaction goes into the partially committed state after the end of a
Partially Committed
transaction.
When the transaction is committed to state, it has already completed its
Committed State execution successfully. Moreover, all of its changes are recorded to the
database permanently.
A transaction considers failed when any one of the checks fails or if the
Failed State
transaction is aborted while it is in the active state.

State of transaction reaches terminated state when certain transactions which

Terminated State
are leaving the system can’t be restarted.

7/3/2023 lbgurung00@gmail.com 18
 ❑ Transaction and System Concepts

7/3/2023 lbgurung00@gmail.com 19
 ❑ The system log:
Log or journal: The log keeps tracks of all transaction operations that affect the
values of database items.
• This information may be needed to permit recovery from transactions
failures
• The log is kept on disk , so it is not affected by any type of failure except
❑ Transaction and for disk or catastrophic failure.
• In addition , the log is periodically backed up to archival storage to guard
System
against such catastrophic failure
Concepts

7/3/2023 lbgurung00@gmail.com 20
 ❑ Commit Point of Transaction:

✓ A transaction T reaches its commit point when all its operation that
access the database have been executed successfully and effect of
all the transaction operations on the database has been recorded in

❑ Transaction and the log

✓ Beyond the commit point , the transaction is said to be committed ,
System
and its effect is assumed to be permanently recorded in the
Concepts
database
✓ The transaction writes any entry [commit] into the log

7/3/2023 lbgurung00@gmail.com 21
❑ Desirable Properties of Transaction:
✓ In order to maintain consistency in a database, before and after the
transaction, certain properties are followed. These are
called ACID properties.

7/3/2023 lbgurung00@gmail.com 22
 Example: Let's assume that following transaction T
✓ Atomicity:
consisting of T1 and T2. A consists of Rs 600 and B
• By this, we mean that either the entire consists of Rs 300. Transfer Rs 100 from account A to
transaction takes place at once or doesn’t account B. T1 T2
happen at all. Or Read A Read B
• It states that all operations of the A:=A-100 B:=B+100
transaction take place at once if not, the Write(A) Write(B)
transaction is aborted. After completion of the transaction, A consists of Rs 500
• Atomicity involves the following two and B consists of Rs 400.
operations: If the transaction T fails after the completion of
Abort: If a transaction aborts then all the transaction T1 but before completion of transaction T2,

changes made are not visible. then the amount will be deducted from A but not added to
B. This shows the inconsistent database state. In order to
Commit: If a transaction commits then all the
ensure correctness of database state, the transaction
changes made are visible.
must be executed in entirety.

7/3/2023 lbgurung00@gmail.com 23
 Before: X:500 Y:200
✓ Atomicity:
Transaction T
• Consider the following
T1 T2
transaction T consisting
Read X Read Y
of T1 and T2: Transfer of 100
X:=X-100 Y:=Y+100
from account X to account Y.
Write(X) Write(Y)
After: X:400 Y:300

If the transaction fails after completion of T1 but before completion of T2.( say,
after write(X) but before Write(Y) ), then amount has been deducted from X but not added
to Y. This results in an inconsistent database state. Therefore, the transaction must be
executed in entirety in order to ensure correctness of database state.

7/3/2023 lbgurung00@gmail.com 24
✓ Consistency:
• This means that integrity constraints must be maintained so that the database is consistent
before and after the transaction. It refers to the correctness of a database.
or
• Before the transaction starts and after a transaction ends, the sum of money must be equal in both
states.

Referring to the example above,

The total amount before and after the transaction must be maintained.
Total before T occurs = 500 + 200 = 700.
Total after T occurs = 400 + 300 = 700.
Therefore, database is consistent. Inconsistency occurs in case T1 completes but T2 fails. As a result
T is incomplete.

7/3/2023 lbgurung00@gmail.com 25
✓ Isolation :
• This property ensures that multiple
transactions can occur
simultaneously without causing any
inconsistency. Or Suppose T has been executed till Read (Y) and then T’’ starts. As a

• It shows that the data which is result , interleaving of operations takes place due to which T’’ reads
correct value of X but incorrect value of Y and sum computed by
used at the time of execution of a
T’:(X+Y=50,000+500=50,500)
transaction cannot be used by the
is thus not consistent with the sum at end of transaction:
second transaction until the first T:(X+Y=50,000+450=50,450).
one is completed. This results in database inconsistency, due to a loss of 50 units.
• Let X= 500, Y = 500. Hence, transactions must take place in isolation and changes should

Consider two transactions T and T’’ be visible only after they have been made to the main memory.

7/3/2023 lbgurung00@gmail.com 26
✓ Durability :

• It means once the transaction is done, and updated in the database it is

not going to change except the user changes or deletes the transaction.
Durable means here the transaction is once done and saved in a database in
a hardware form as a permanent change.
• Committed data would never be lost, even in hardware failure. It is actually
a backup of the database.

7/3/2023 lbgurung00@gmail.com 27
 ✓ A series of operation from one transaction to another
transaction is known as schedule. It is used to preserve the
order of the operation in each of the individual transaction.
OR
▪ Schedules in DBMS ✓ The order in which the operations of multiple transactions
appear for execution is called as a schedule.
OR
✓ Schedules are sequences that indicate the chronological order
in which instructions of concurrent transactions are executed.

7/3/2023 lbgurung00@gmail.com 28
▪ Types of Schedules

7/3/2023 lbgurung00@gmail.com 29
 a. Serial Schedules-
In serial schedules,
✓ All the transactions execute serially one after the other.
✓ When one transaction executes, no other transaction is allowed to
execute.
Or
▪ Types of Schedules
✓ The serial schedule is a type of schedule where one transaction is
executed completely before starting another transaction. In the
serial schedule, when the first transaction completes its cycle,
then the next transaction is executed.
✓ Serial schedules are always consistent

7/3/2023 lbgurung00@gmail.com 30
 In this schedule,
✓ There are two transactions T1
and T2 executing serially one
▪ Types of Schedules after the other.
a. Serial Schedule ✓ Transaction T1 executes first.
✓ After T1 completes its execution,
transaction T2 executes.
✓ So, this schedule is an example of
a Serial Schedule.

This schedule is an example of a Serial Schedule because

Transaction T2 executes first. After T2 completes its execution,
transaction T1 executes.

7/3/2023 lbgurung00@gmail.com 31
 In non-serial schedules,
✓ Multiple transactions execute concurrently.

▪ Types of Schedules ✓ Operations of all the transactions are interleaved or mixed with
each other.
b. Non- Serial
Schedule ✓ Non-serial schedules are NOT always-consistent

In this schedule,
✓ There are two transactions T1 and T2
executing concurrently.
✓ The operations of T1 and T2 are interleaved or
mixed with each other.
✓ So, this schedule is an example of a Non-
Serial Schedule.

7/3/2023 lbgurung00@gmail.com 32
 ✓ The Non-Serial Schedule can be divided further into:
• Serializable and

▪ Types of Schedules • Non-Serializable.

• Serializable Schedule:
b. Non- Serial
Schedule ✓ This is used to maintain the consistency of the database.
✓ It is mainly used in the Non-Serial scheduling to verify whether the
scheduling will lead to any inconsistency or not. On the other hand, a serial
schedule does not need the serializability because it follows a transaction
only when the previous transaction is complete. The non-serial schedule is
said to be in a serializable schedule only when it is equivalent to the serial
schedules, for an n number of transactions. Since concurrency is allowed in
this case thus, multiple transactions can execute concurrently. A
serializable schedule helps in improving both resource utilization and CPU
throughput.
7/3/2023 lbgurung00@gmail.com 33
 • Types of Serializable Schedule:They are of two types:
✓ Conflict Serializability and
✓ View serializability
▪ Types of Schedules
✓ Conflict serializability defines two instructions of two different
b. Non- Serial
Schedule transactions accessing the same data item to perform a read/write
operation. Or
✓ Conflict Serializability is one of the type of Serializability, which can
be used to check whether a non-serial schedule is conflict serializable
or not.
✓ A schedule is called conflict serializable if we can convert it into a
Conflict operation:
serial schedule after swapping its non-conflicting operations.
R(A) →W(A)
W(A)→>R(A)
W(A) ->W(A)

7/3/2023 lbgurung00@gmail.com 34
 Example of Conflict Serializability
Lets consider this schedule:

To convert this schedule into a serial

▪ Types of Schedules
schedule we must have to swap the
b. Non- Serial
Schedule R(A) operation of transaction T2 with
• Serializable and the W(A) operation of transaction T1.
• Non-Serializable. However we cannot swap these two
operations because they are
conflicting operations, thus we can say
that this given schedule is not
Conflict Serializable.

7/3/2023 lbgurung00@gmail.com 35
 Example of Conflict Serializability Conflict operation:

T1 T2 R(A) --- W(A)

R(A) W(A)--- R(A)

W(A) -- W(A)
▪ Types of Schedules W(A) Steps:
R(A) 1. Find and list all the conflict operation
b. Non- Serial
W(A)
Schedule 2. Create a precedence graph by drawing one
R(B)
• Serializable and node for each transaction.
W(B)
• Non-Serializable. 3. Draw an edge for each conflict pair such that
R(B)
W(B) if Xi (V) and Yj (V) forms a conflict pair then
draw an edge from Ti to Tj.
Checking Whether a
This ensures that Ti gets executed before Tj.
Schedule is Conflict
4. Check if there is any cycle formed in the
Serializable Or Not-
graph.
If there is no cycle found, then the schedule is
conflict serializable otherwise not.

7/3/2023 lbgurung00@gmail.com 36
 Example of Conflict Serializability
Conflict operation:
T1 T2
R(A) --- W(A)
R(A)
W(A)--- R(A)
▪ Types of Schedules W(A)
W(A) -- W(A)
R(A)
b. Non- Serial
W(A)
Schedule
R(B)
• Serializable and T1 T2
W(B)
• Non-Serializable.
R(B)
T1 T2 W(B)
R(A)
Here, no cycle found, then the
W(A)
Checking Whether a schedule is conflict serializable
R(B)
W(B)
Schedule is Conflict And to make serial schedule here T1
R(A) Serializable Or Not- executes first then after T2
W(A)
R(B)
W(B)
7/3/2023 lbgurung00@gmail.com 37
 Example of Conflict Serializability
Conflict operation:
T1 T2 T3 R(A) --- W(A)

R(x) W(A)--- R(A)

▪ Types of Schedules
R(y) W(A) -- W(A)
b. Non- Serial
Schedule R(x) Check conflict pairs in other

• Serializable and R(y) transaction and draw edge.

• Non-Serializable. R(z) Draw precedence graph
Possibility: W(y)
T1 T2 T3 T1
W(z) T2
T1 T3 T2
R(z)
T2 T1 T3
W(x)
T2 T3 T1
T3 T1 T2
W(z) T3

T3 T2 T1
Check: Indegree=0 Here, no cycle/loop found, then the schedule is
T2 T3 T1 conflict serializable
7/3/2023 lbgurung00@gmail.com 38
 Example of Conflict Serializability
Conflict operation:
T2 T3 T1 R(A) --- W(A)
R(y)
W(A)--- R(A)
▪ Types of Schedules R(z)
W(A) -- W(A)
W(z)
b. Non- Serial
Schedule Check conflict pairs in other
R(y)
• Serializable and transaction and draw edge.
R(x)
• Non-Serializable. Draw precedence graph
W(y)
Possibility:
T1 T2 T3 R(x) T1
T2
T1 T3 T2 R(z)

T2 T1 T3 W(x)
W(z)
T2 T3 T1
T3 T1 T2 T3

T3 T2 T1
Check: Indegree=0 Here, no cycle/loop found, then the schedule is
T2 T3 T1 conflict serializable
7/3/2023 lbgurung00@gmail.com 39
 ✓ View Serializability
As we know if there is no loop in graph then it will be conflict
serializable but if there is a loop in the graph then it may or may not
▪ Types of Schedules
be a serializable which will be check through View Serializability.
b. Non- Serial
Schedule • It is a concept that is used to compute whether schedules are
• Serializable and View-Serializable or not. A schedule is said to be View-
• Non-Serializable.
Serializable if it is view equivalent to a Serial Schedule (where no
interleaving of transactions is possible).

T1 T2 T3
R(A) T1 T2
Checking Whether a W(A)
Schedule is Conflict W(A)
Serializable Or Not- W(A) T3
Non-Conflict Serializable
7/3/2023 lbgurung00@gmail.com 40
 ✓ View Serializability
▪ Two schedules S1 and S2 are said to be view equal if below conditions are
satisfied :
▪ Types of Schedules ▪ Initial read
b. Non- Serial An initial read of the data item in both the schedule must be same. For
Schedule example, lets two schedule S1 and S2. If transaction T1 reads the data item X
• Serializable and in schedule S1, then in schedule S2 transaction T1 also reads X.
• Non-Serializable.

Schedule S1 Time Transaction T1 Transaction T2

t1 Read(X)
t2 Write(X)

Time Transaction T1 Transaction T2

Schedule S2 t1 Write(X)
t2 Read(X)
7/3/2023 lbgurung00@gmail.com 41
 ✓ View Serializability
▪ Updated Read
In schedule S1, if Ti is reading A which is updated by Tj then in S2 also, Ti
▪ Types of Schedules
should read A which is updated by Tj.
b. Non- Serial
Schedule
• Serializable and
• Non-Serializable.

Above two schedules are not view equal because, in S1, T3 is reading A
updated by T2 and in S2, T3 is reading A updated by T1.

7/3/2023 lbgurung00@gmail.com 42
 ✓ View Serializability
▪ Final Write
A final write must be the same between both the schedules. In schedule S1, if a
▪ Types of Schedules
transaction T1 updates A at last then in S2, final writes operations should also
b. Non- Serial be done by T1.
Schedule
.
• Serializable and
• Non-Serializable.

Above two schedules is view equal because Final write operation in S1 is done
by T3 and in S2, the final write operation is also done by T3.

7/3/2023 lbgurung00@gmail.com 43
 Non-Serializable Schedules-
✓ A non-serial schedule which is not serializable is called as a non-
serializable schedule.
✓ A non-serializable schedule is not guaranteed to produce the same
b. Non- Serial effect as produced by some serial schedule on any consistent
Schedule
database.
• Serializable and
✓ It may or may not be consistent, recoverable
• Non-Serializable.
• Recoverable Schedule –
A schedule is said to be recoverable if it is recoverable as name
suggest. Only reads are allowed before write operation on same data.

• Cascadeless Schedule –
When no read or write-write occurs before execution of transaction
then corresponding schedule is called cascadeless schedule.

7/3/2023 lbgurung00@gmail.com 44
 Non-Serializable Schedules-
✓ Strict Schedule –
If schedule contains no read or write before commit then it is known as
b. Non- Serial strict schedule. Strict schedule is strict in nature.
Schedule
• Serializable and
• Non-Serializable.

7/3/2023 lbgurung00@gmail.com 45
 ▪ When more than one transactions are running
simultaneously there are chances of a conflict to occur
which can leave database to an inconsistent state. To
handle these conflicts we need concurrency control in
DBMS, which allows transactions to run simultaneously
❑ Concurrency
but handles them in such a way so that the integrity of
Control
data remains together.
▪ The concurrency control is the process to maintain the
data where there are multiple resources or users are
accessing the data element and performing the database
operations.
7/3/2023 lbgurung00@gmail.com 46
 ▪ Concurrency control protocols in DBMS are procedures that are used
for managing multiple simultaneous operations without conflict with
each other
▪ Concurrency control protocols are the techniques used to maintain
data consistency, atomicity, and serializability. Following are some of
the concurrency control protocols
❑ Concurrency
Control ✓ Lock-based protocol
✓ Validation based protocol
Protocols
✓ Timestamp based protocol
✓ Two-phase protocol

7/3/2023 lbgurung00@gmail.com 47
 • One of the main techniques used to control concurrency execution of
transactions is based on the concept of locking data items.
• A lock is a variable associate with a data item in the database and
describes the status of that data item with respect to possible
operations that can be applied to the item.

✓ Lock-based protocol • Generally speaking, there is one lock for each data item in the
database. The overall purpose of locking is to obtain maximum
concurrency and minimum delay in processing transactions
• Types of locks:

There are several types of locks that can be used in concurrency

control.
✓ Binary locks are the simplest, but are somewhat restrictive in
their use.
✓ Shared and exclusive locks
7/3/2023 lbgurung00@gmail.com 48
 • Binary lock:
✓ A binary lock can have two states or values: locked and unlocked
(or 1 and 0, for simplicity). A distinct lock is associated with each

✓ Lock-based protocol database item X.

✓ If the value of the lock on X is 1, item X is locked and cannot be
accessed by a database operation that requests the item.
✓ If the value of the lock on X is 0, item X is unlocked, and it can
be accessed when requested. We refer to the value of the lock
associated with item X as LOCK(X).
✓ The DBMS has a lock manager subsystem to keep track of and
control access to locks.

7/3/2023 lbgurung00@gmail.com 49
 • Shared and exclusive lock
Shared lock(S):
✓ It is also known as a Read-only lock. In a shared lock, the data item
can only read by the transaction.
✓ It can be shared between the transactions because when the
✓ Lock-based protocol
transaction holds a lock, then it can't update the data on the data
item.
For example, consider a case where two transactions are reading
the account balance of a person. The database will let them read by
placing a shared lock. However, if another transaction wants to
update that account's balance, shared lock prevent it until the
reading process is over.

7/3/2023 lbgurung00@gmail.com 50
 2. Exclusive Lock (X):

✓ With the Exclusive Lock, a data item can be read as well as written.

✓ This is exclusive and can't be held concurrently on the same data

item. X-lock is requested using lock-x instruction.
✓ Lock-based protocol
✓ Transactions may unlock the data item after finishing the 'write'
operation.

✓For example,

When a transaction needs to update the account balance of a person. You

can allows this transaction by placing X lock on it. Therefore, when the
second transaction wants to read or write, exclusive lock prevent this
operation.

7/3/2023 lbgurung00@gmail.com 51
 • Two-phase locking (2PL)
✓ The two-phase locking protocol divides the execution phase of the
transaction into three parts.
✓ In the first part, when the execution of the transaction starts, it seeks
permission for the lock it requires.
✓ In the second part, the transaction acquires all the locks. The third
✓ Types of lock protocol
phase is started as soon as the transaction releases its first lock.
✓ In the third phase, the transaction cannot demand any new locks. It only
releases the acquired locks.

7/3/2023 lbgurung00@gmail.com 52
 • Two-phase locking (2PL)
There are two phases of 2PL:
Growing phase: In the growing phase, a new lock on the data item may be
acquired by the transaction, but none can be released.
Shrinking phase: In the shrinking phase, existing lock held by the transaction
may be released, but no new locks can be acquired.
✓ Types of lock protocol

7/3/2023 lbgurung00@gmail.com 53
 ✓ What is transaction? Draw states of transaction and explain.
✓ What is concurrency control? What are its advantages in DBMS?
✓ Explain ACID properties of transaction.
✓ What is schedule? Explain serializability and conflict schedule.
▪ Review questions: ✓ What is transaction? State and explain properties of transaction.
✓ Why do we need database recovery? Discuss shadow paging technique
for database recovery
✓ Define Transaction and explain its desirable properties.

7/3/2023 lbgurung00@gmail.com 54
 ✓ Database recovery is the process of restoring the database to a
correct (consistent) state in the event of a failure.
✓ In other words, it is the process of restoring the database to the
most recent consistent state that existed shortly before the

❑ Recovery time of system failure.

✓ The failure may be the result of a system crash due to hardware
Concepts: or software errors, a media failure such as head crash, or a
software error in the application such as a logical error in the
program that is accessing the database. Recovery restores a
database form a given state, usually inconsistent, to a previously
consistent state.

7/3/2023 lbgurung00@gmail.com 55
❑ Recovery
Technique:

Log-Based Recovery (Most Important)

7/3/2023 lbgurung00@gmail.com 56
 • Shadow paging:
✓ Shadow Paging is a recovery technique that provides atomicity and
durability in database system. Shadow Paging recovery technique is also
known as On-Write Technique.
✓ Shadow Paging maintains 2 page table. A current page table and shadow
page table.
❑ Recovery ✓ When a transaction begins, all the entries of the current page table are copied
to the shadow page table and the current table is updated for each write
Technique: operation.
✓ The shadow page is never changed during the life of the transaction. When the
current transaction is committed, the shadow page entry becomes a copy of
the current page table entry and the disk block with the old data is released.
✓ The shadow page table is stored in non-volatile memory. If the system crash
occurs, then the shadow page table is copied to the current page table.

7/3/2023 lbgurung00@gmail.com 57
❑ Recovery
Technique:
The above figure illustrates the concepts of shadow and current
directories. For pages updated by the transaction, two versions are
kept. The old version is referenced by the shadow directory and the
new version by the current directory.

7/3/2023 lbgurung00@gmail.com 58
❑ Recovery
Technique:

7/3/2023 lbgurung00@gmail.com 59
 Advantages
The advantages of shadow paging are as follows −
✓ No need for log records.
✓ No undo/ Redo algorithm.
✓ Recovery is faster.

❑ Recovery Disadvantages

Technique:
The disadvantages of shadow paging are as follows −
✓ Data is fragmented or scattered.
✓ Garbage collection problem. Database pages containing old versions of
modified data need to be garbage collected after every transaction.
✓ Concurrent transactions are difficult to execute.

7/3/2023 lbgurung00@gmail.com 60