Chapter 3 & 4

Transaction Processing &

Concurrency Control

12/10/24
3-1
Transaction Concept
 A transaction is an executing program that performs single

unit of database processing which includes database

commands such as retrievals, insertions, deletions, and
updates.
 Transaction processing systems are systems with large

databases and hundreds of concurrent users executing

database transactions. Examples of such systems include
airline reservations and banking.
12/10/24
3-2
Example
 An action, or series of actions, carried out by a single user or
application program, which reads or updates the contents of
the database.
E.g., 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)
 Transaction is used to represent a logical unit of database processing that
must be completed in its entirety to ensure correctness.

12/10/24
3-3
 Properties of Transactions
A Atomicity: a transaction is an atomic unit of processing and it
is either performed entirely or not at all

C Consistency Preservation: a transaction's correct execution

must take the database from one correct state to another

I Isolation/Independence: the updates of a transaction must not

be made visible to other transactions until it is committed
(solves the temporary update problem)

D Durability (or Permanency): if a transaction changes the

database and is committed, the changes must never be lost
12/10/24
because of subsequent failure 3-4
 Cont…
 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 - shouldn’t take money from A without giving it to B

 Consistency - money isn’t lost or gained

 Isolation - other queries shouldn’t see A or B change until completion

 Durability - the money does not go back to A

12/10/24
3-5
Processes of Transaction

 Transaction is executed as a series of Reads and

Writes of database objects which are:

 Read Operation

 Find the address of the disk block that contains item X.

 Copy that disk block into a buffer in main memory.
 Copy item X from the buffer to the program variable
named x.

12/10/24
3-6
 Cont…

 Write Operation

 Data base object copy in Main Memory is first

modified then written to Disk.
 Store the updated block from the buffer back to the
disk.

12/10/24
3-7
Operations of Transaction
 Retrieve (Read): to retrieve data stored in a database.

 Insert (Write): to store new data in a database.

 Delete (Write): to delete existing data from a database.

 Update (Write): to modify existing data in a database.

 Commit : to save the work done permanently.

 Rollback: to undo the work done.

R(X);
X = X - 500;
W(X);
Transaction Support
 Two possible outcomes:

Success (Commit)- transaction completely performs all
the read, writes and changes the database state
accordingly (database reaches new consistent state )
 Failure (Abort)- Transaction is unable to complete all
the read and write and hence will undo the operations
that were performed till that point. Database will remain
in the same state as it was prior to the beginning of this
transaction.
 Referred to as rolled back or undone transaction
 Committed transaction cannot be aborted
 Aborted transaction that is rolled back can be restarted later

12/10/24
3-9
 Cont…

Rollback
it undoes all the updates performed by the SQL statements in
the transaction.
Thus, the database state is restored to what it was before the
first statement of the transaction was executed.

12/10/24
3-10
 transaction processing following
these steps
1. Begin a transaction
2. Process database commands
3. Check for error.
If error occurred
rollback the transaction
else
commit the transaction
 note: Not able to see the uncommitted.

12/10/24
3-11
States of Transaction

 Active-The Initial state i.e. state while executing.

 Partially Committed- After the Final Statement has been

executed.
 Failed-When the Normal execution can no longer proceed.

 Aborted-After the transaction has Rolled back and database

has been Restored to its state prior to the start of the

transaction.
 Committed-After successful completion

12/10/24
3-12
State Transition Diagram for
Transaction

12/10/24
3-13
 Cont…
1. A transaction goes into an active state immediately after it starts execution where it
can issue READ or WRITE operations. When the transaction ends, it moves to the
2. partially committed state where certain recovery protocol ensures that a system
failure will not result in an inability to record the changes of the transaction
permanently.
a. If this check is successful the transaction enters into a commit point and enters the committed state.
If so, all its changes must be recorded permanently in the database.
b. If this check fails, it goes to the failed state.
3. Transaction can go the failed state, from the partially committed state if any of the
checks there fails or if the transaction is aborted from its active state itself.
a. The transaction may then have to be rolled back to undo the effect of WRITE
operations.
4. Committed − If a transaction executes all its operations successfully, it is said to be
committed. And permanently established on the database system.
5. 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.
12/10/24
3-14
States of Transaction…
 A transaction has Committed only if it has entered
the Committed State.

 A transaction has Aborted only if it has entered

the Aborted State.

 A transaction is said to have terminated if it has

either Committed or Aborted.

12/10/24
3-15
Concurrency Control
 When using single user system there is no need to
manage the transaction but when multiple user
access the same database we need to control the
transaction.
 Process of managing simultaneous operations on the
database without having them interfere with one
another is called concurrent control
 Prevents interference when two or more users access
database simultaneously and at least one updates
data. Because Interleaving of operations may
produce incorrect results

12/10/24
3-16
Requirements for Database
Consistency
 it implies interleaving execution of operations of transaction.
 Most DBMS are multi-user systems.
 The concurrent execution of many different transactions
submitted by various users must be organized such that
each transaction does not interfere with another
transaction with one another in a way that produces
incorrect results.
 The concurrent execution of transactions must be such
that each transaction appears to execute in isolation.
 Schedule: the order in which instructions of a transactions
are executed.
 Recovery
 System failures, either hardware or software, must not
result in an inconsistent database
12/10/24
3-17
Advantages of Concurrent Execution of
Transaction

 Improved Throughput

 Average no. of transactions completed in a given time

(CPU Waiting).

 Reduced Waiting Time

 Increased performance and resource utilization.

 Short transaction can complete quickly

12/10/24
3-18
Potential concurrency
problems:
 Potential concurrency problems:

• Lost update problem

• Uncommitted dependency
problem
• Inconsistent analysis problem
12/10/24
3-19
Lost update (W-w conflict)
 an update to an object by some transaction is overwritten by
another interleaved transaction without knowledge of the
initial update.
 update made by one transaction T1is overridden by another
transaction T2.
X=40 T1 T2
R(x)
X=x+10
R(X)
X=x-20
W(X)
 T1 transaction totally meaninglessW(x)
or Transaction 1’s
update is lost
12/10/24
3-20
Uncommitted dependency (W-R
conflict)

 Occurs when one transaction updates a database item

and then the traction fails but its update is read by

some other tractions.
 This problem occurs when one transaction is allowed

to see the intermediate results of another transaction

before it is committed

12/10/24
3-21
 Cont…
 T2 read update but not committed T1-Dirty

T1 T2
R(x)
X=x+20
W(x)
R(x)
X=x+10
W(x)
FAIL

 Since the transaction is Aborted so the database will be

restored to its original state
12/10/24
3-22
Inconsistent Analysis

 If one transaction is calculating on aggregate

summary function on a number of records while

other transaction is updating some of these
records, the aggregate function may calculate
some values before they are updated and others

after they are updated –results in correct summary .

12/10/24
3-23
 Cont…
To calc avg salary of emp

T1 read all(A-Z) tuples from the db meanwhile T 2 update over some

item, then T1 finish its calculation and display avg salary of the emp.
But it calculate over the old value salary so, its calculation is wrong.
T1 T2
Sum=0
Sum=sum+A

R(p)
p=p+100
W(p)
Sum=sum+z
AVG()
12/10/24
3-24
Concurrency control
the process of managing simultaneous operations on the
database without having them interfere with each other.

Schedules Locking
 Serial schedules  Lock manager
 Non-serial  2 Phase Locking
 Serializable schedules  Deadlocks:
 Prevention

 Detection

 avoidance
12/10/24
3-25
Schedules

 Schedule: 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.
 By default transaction assumed to execute commit
instruction as its last step
12/10/24
3-26
 Schedules of Transactions

 A schedule S of n transactions is a sequential

T1

ordering of the operations of the n transactions. read x

write x
 The transactions are interleaved
T2
 A schedule maintains the order of operations read x
write x
within the individual transaction.
 For each transaction T if operation a is performed in T S
before operation b, then operation a will be performed read x
before operation b in S. read x
 write x
The operations are in the same order as they were write x
before the transactions were interleaved
12/10/24
3-27
Schedules
 write schedule by S
 If read is perform over the database item X we write r(x).

 If write operation is perform over the database item x we

write w(x).
 If schedule is given by S: r1(x);r2(w);w2(n),r1(y)

 The number show the transaction number and x show the database
item.

12/10/24
3-28
 Serial Schedules
 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.
 EX T1 T2
R1 R2
W1 W2
 So we can have the following schedules
 R1R2 W1 W2
 R1W1 R2W2 - Serial
 R2R1 W2W1
 R2R1 W1W2
12/10/24
3-29
Example

 T1 transfers 50 from A to B and then

 T2 transfers 10% from A to B
 so, the schedule is :- T1 T2
R1(A)
A=A-50
W1(A)
R1(B)
B=B+50
W1(B)
R2(A)
temp=A*0.1
A=A-temp
W2(A)
R2(B)
B=B + temp
W2(B)
12/10/24
3-30
Non-serial Schedules
 A schedule S is serial if, for every transaction T
participating in the schedule, all of T's operations are
executed consecutively in the schedule; otherwise it is
called non-serial.
 Disadvantage:
 limits concurrency
 Couse's CPU was
 Smaller transaction may need to wait long
 Non-serial schedules mean that transactions are
interleaved. There are many possible orders or schedules.
 Incorrect result or inconsistence

12/10/24
3-31
Cont…

12/10/24
3-32
Serialisable
 is a given set of interleaved transactions is said to be serialisable if
and only if it produces the same results as the serial execution of the
same transactions
 Serializability is an important concept associated with locking.

Interleaved Schedule
Serial Schedule
T1 Read(X) T2 Read(X)
T2 Read(X) T2 Read(Y)
T2 Read(Y) T2 Read(Z)
T1 Read(Z)
T1 Read(Y) T1 Read(X)
T2 Read(Z) T1 Read(Z)
T1 Read(Y)
This schedule is serialisable:

12/10/24
3-33
Cont…

12/10/24
3-34
 Example of Serial Schedules
SchedulA Schedule B

T1: T2: T1: T2:

read_item(X); read_item(X);
X:= X - N; X:= X + M;
write_item(X); write_item(X);
read_item(Y); read_item(X);
Y:=Y + N; X:= X - N;
write_item(Y); write_item(X);
read_item(X); read_item(Y);
X:= X + M; Y:=Y + N;
write_item(X); write_item(Y);

12/10/24
3-35
Example of Non-serial Schedules
Schedule C Schedule D

T1: T2:
T1: T2:
read_item(X);
read_item(X);
X:= X - N;
X:= X - N;
read_item(X);
write_item(X);
X:= X + M;
read_item(X);
write_item(X);
X:= X + M;
read_item(Y);
write_item(X);
write_item(X);
Y:=Y + N;
read_item(Y);
write_item(Y); Y:=Y + N;
write_item(Y);

12/10/24
3-36
 Equivalent Schedules

 Two schedules S1 and S2 are said to be

equivalent schedule if they are:

 Result equivalent
 Conflict equivalent
 View equivalent

12/10/24
3-37
Result Equivalent Schedules
 Two schedules are called result equivalent if they produce the
same final state of the database.
 Example: check if its result equivalent schedules
 A=100
T1 T2
T1 T2
R(A) R(A)
A=A+10 A=A-5

W(A) W(A)

R(A) R(A)

A=A-7 A=A+8
W(A)
W(A)

 So
12/10/24 its Equivalent Schedules 3-38
 Cont…
 Example of result equivalent schedules
 A=100

S1 S2
R(A) R(A)
A=A+10 A*1.1
W(A) W(A)

 Is that result equivalent ?

 NO because these schedules equivalent for 100 only but to say
result equivalent the schedule should the same database state for
any data item.
 Try the schedules with data item A=10

12/10/24
3-39
Conflict operation
 Two schedules are said to be conflict equivalent if
the order of any two conflicting operations is the
same in both schedules.
 Two operations conflict if :
 They belong to different transactions
 Access the same data item
 At least one of the operation should be a write
operation.

12/10/24
3-40
Conflict operation
 if they belong to different transactions
S:R1(x);w2(x) ;R1(y);R2(z) so the conflict is
R1(x) and w2(x) ,w2(x) and r1(y)….
•Must access the same data item
•At least one of the operation should be a write
operation.
T R1(x) W2(x)
Now the conflicting operation pair :
RW
WR
WW but not RR
12/10/24
3-41
 Formal definition
 Let li and lj be two Instructions of transactions Ti and Tj
respectively. 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.
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
4. li = write(Q), lj = write(Q). They conflict
 Intuitively, a conflict between li and lj forces a (logical) temporal
order between them.
 If l and l are consecutive in a schedule and they do not
i j
conflict, their results would remain the same even if they had
been interchanged in the schedule.
12/10/24
3-42
Conflict Equivalent
 Two schedules are said to be conflict equivalent if all
conflicting operations in both the schedule must be executed
in the same order.
 Check for conflict equivalent:
 S1:R1(A),W2(A),R1(B)
 S2:R1(B),R1(A),W2(A)
What if S2:R1(B),W2(A),R1(A)
S1 S2
T1 T2 T1 T2

R(A) R(B)

W(A) R(A)
R(B) W(A)
S1 ⊆S2 because Order should respect R1W2
12/10/24
3-43
Conflict Equivalent
 Check for conflict equivalent:
 S1:R1(A),w1(A),R2(A),W2(B),R1(B)
 S2:R1(A),W1(A),R1(B),R2(B),W2(B)
S1 S2
T1 T2 T1 T2

R(A) R(A)

W(A)
W(A)
R(B)
» R(A)
R(B)
W(B)
W(B)
R(B)

 S1(W2BR1B) S2(R2BW2B) so ,No conflict

12/10/24
3-44
Conflict Equivalent
 Verify if the given schedules are conflict equivalent

 S1:w1(x),R2(z),w2(z),R2(x),R1(y)

 S2:W1(x),R2(x),R2(z),W2(y),R1(z)

 Its not conflict equivalent because two schedules said to be

conflict if and only if

 The order of conflicting pairs of operation is maintained
in both the scheduled
 Both the schedules contain the same set of transaction.

12/10/24
3-45
Purpose of Concurrency control

 To enforce Isolation.:- not interfacing

 To preserve Database consistency

 To resolve Read-Write and Write-Write

conflict.

12/10/24
3-46
Concurrency control

 The second Concurrency control

Techniques :
 Lock based protocol

12/10/24
3-47
Locking
 Locking is a mechanism that allows a transaction to reserve a data item
for its exclusive or shared use, and prevent other transactions from
modifying or reading.
 Locking ensures the consistency and isolation of transactions.
 A lock can be either exclusive or shared, depending on the type of
operation that the transaction performs on the data item.
 An exclusive lock allows the transaction to read and write the data item,
and blocks other transactions from accessing it.
 A shared lock allows the transaction to read the data item, and allows
other transactions to read it as well, but blocks any write operation.
12/10/24
3-48
 Lock Manager
 A Lock manager can be implemented as a separate process to

which transactions send lock and unlock requests

 The lock manager replies to a lock request by sending a lock

grant messages (or a message asking the transaction to roll

back, in case of a deadlock)
 The requesting transaction waits until its request is answered

 The lock manager maintains a data structure called a lock table

to record granted locks and pending requests

 Responsible for assigning and policing the locks used by the

transactions
12/10/24
3-49
Types of lock
 There are different types of locking in DBMS, depending on
the level of granularity, the duration, and the protocol of
the locks.
 The level of granularity refers to the size of the data item
that the lock covers, such as a record, a page, or a table.
 The duration refers to the time period that the lock is held
by the transaction, such as until the end of the transaction,
or until the end of the operation.
 The protocol refers to the rules that the transaction follows
to acquire and release locks, such as two-phase locking,
timestamp ordering, or optimistic concurrency control.

12/10/24
3-50
Lock based protocol

 A lock guarantees exclusive use of a data item to current

transaction.
 Locking is a procedure used

 to control concurrent access to data or

 to ensure Serialisability of concurrent transactions
 This may deny access to other transactions to prevent incorrect

results
 All data item must be accessed in mutually exclusive manner.

12/10/24
3-51
 Lock Granularity
 Indicates the level of lock use
 Locking can take place at the following levels:
 Database-level lock
 Entire database is locked
 Table-level lock
 Entire table is locked
 Page-level lock
 Entire diskpage is locked
 Row-level lock
 Allows concurrent transactions to access different rows of the same
table, even if the rows are located on the same page
 Field-level lock
 Allows concurrent transactions to access the same row, as long as they
require the use of different fields (attributes) within that row

12/10/24
3-52
 A Database-Level Locking Sequence

 Good for batch processing but unsuitable for online multi-user

DBMSs
 T1 and T2 can not access the same database concurrently even if
they use different tables
12/10/24
 Table-Level Lock

 T1 and T2 can access the same database concurrently as long as they use different tables
 Can cause bottlenecks when many transactions are trying to access the same table (even if the
transactions want to access different parts of the table and would not interfere with each other)
 Not suitable for multi-user DBMSs

12/10/24
 Page-Level Lock

 An entire disk page is locked (a table can span several pages and
each page can contain several rows of one or more tables)
 Most frequently used multi-user DBMS locking method
12/10/24
 Row-Level Lock

 Concurrent transactions can access different rows of the same table

even if the rows are located on the same page
 Improves data availability but with high overhead (each row has a
lock that must be read and written to)
12/10/24
 Field-Level Lock

 Allows concurrent transactions to access the same

row as long as they require the use of different
fields with that row
 Most flexible lock buy requires an extremely high
level of overhead

12/10/24
Modes of locks
 Data items can be locked in two modes :

1. exclusive lock(X) :Data item can be both read as well as

written. X-lock is requested using lock-X instruction.

2. shared lock(S) :Data item can only be read. S-lock is requested

using lock-S instruction.
 Read lock allows several transactions simultaneously to read a

resource (but no transactions can change it at the same time)

 Write lock allows one transaction exclusive access to write to a

resource. no other transaction can read this resource at the same

time.
12/10/24
3-58
Locking
 A transaction may not
 Before reading from a acquire a lock on any
resource that is write-
resource a transaction locked by another
must acquire a read-lock transaction
 A transaction may not
 Before writing to a
acquire a write-lock on a
resource a transaction resource that is locked by
another transaction
must acquire a write-lock
 If the requested lock is not
 Locks are released on available, transaction
waits
commit/rollback
12/10/24
3-59
Cont…
 Compatibility b/n lock modes

Read Write

Read S X

Write X X

Or
S X

S True False

S False False

12/10/24
3-60
 Example
 Ex of lock protocol
T1 T2 Exclusive lock
Lock-X(B)
R(B)
B=B-50
W(B)
Unlock(B) Shared lock
Lock-S(B)
R(B)
Unlock(B)

 Any no of trans can hold shared lock on an item but

exclusive lock can be hold only by one trans at a time.
 Unlock(B)
 12/10/24
There is a cycle in the graph so its not conflict seriable. 3-61
 Lock based protocol
 T1: Transfer AB and T2: Display (A+B)
T1
T2
Lock-x(A)
Lock-S(A)
R(A)
R(A)
A-A-100
Unlock(A)
W(A)
Lock-S(B)
Unlock(A)
R(B)
Lock-x(B) Unlock(B)
R(B) Display(A+
B)
B=B+100

W(B)
12/10/24
Unlock(B) 3-62
Conversion of locks

 Upgrading :- Read-lock Write-Lock

 This means from shared to exclusive lock.

 Downgrading:- Write lock Read-lock.

 This from exclusive lock to shared lock

12/10/24
3-63
Conversion of locks
If we need to read to data item
x, it acquiring share lock similarly ,if the write is over I
want to perform read or some
lock-s(x) other trans read it would not be
Read(x) access because its exclusively
Meanwhile, if we want to write lock, so we downgrade the lock
operation on data item x so, by adding lock-s after write
before we perform write operation
operation we have to upgrade lock(lock-s).
this lock(lock-s). Lock-s(x)
Lock-s(x) Read(x)
Lock-x(x)
Read(x)
Write(x)
Lock-x(x) lock-s(x)
Write(x) Read(x)
12/10/24
3-64
 Two phase Locking protocol
 Defines how transactions acquire and relinquish
locks
 Its requires both locks and unlocks being done in two
phases. (2PL)
 2PL has two phases one is growing where all the
locks are being acquired by the transaction, and
second phase is shrinking ,where the locks held by
the transaction are being released.
 Guarantees serializability, but it does not prevent
deadlocks

12/10/24
3-65
 Two-Phase Locking
o Growing phase, in which a transaction acquires all the
required locks without unlocking any data
o Shrinking phase, in which a transaction releases all locks and
cannot obtain any new lock

Governed by the following rules:

 Two transactions cannot have conflicting locks
 No unlock operation can precede a lock operation in the same transaction
 No data are affected until all locks are obtained—that is, until the transaction is in
its locked point
 if a transaction release one lock it cant ask any more lock after reaching lock
point. This to enforce Serialisability.

12/10/24
3-66
Two-Phase Locking Protocol

T1: R(A), W(A), Abort

T2: R(A), W(A), R(B), W(B)

12/10/24
Problem with 2phase Locking
 2PL protocol enforces serializability but may reduce
concurrency due to the ff reasons
 Holding Lock un-necessarily
 Operation can wait even if the data whichis no longer
required for other transaction. So there is unnessarily
wait due to early lock
 Deadlock
 Cascading Rollback
 To guarantee serializability, need an additional protocol
concerning the positioning of lock and unlock operations in
every transaction.
12/10/24
3-68
Problem. Unnecessarily…

Example
If T2 want to read a data item A
T1 T2 lock-s(A)It cant be data item A
Lock-x(A) Exclusively locked by T1 until all
Operation finish it has be wait,
R(A)
which Unnecessarily wait this
W(A) because of early lock
Lock-X(B)
Lock-s(A)

12/10/24
There is a cycle in the graph so its not conflict seriable. 3-69
 Deadlock
 A system is in a deadlock state if there exists a set
of transactions such that every transaction in the set
is waiting for another transaction in the set.
 Assume both T1 and T2 need data items x and y to
complete the transaction.

T1 T2
Lock-x(X) T1 waiting to release lock y and
X=x+y T2 also waiting T1 to release lock
Lock-x(Y)
On x .this state is
Deadlock state.
Y-y-x

12/10/24
3-70
 Time stamping
 Each transaction is assigned a unique time-stamp.

 There are two main strategies

 A. Wait/die
 Older transaction waits and the younger is rolled back and rescheduled
 B. Wound/wait
 Older transaction rolls back the younger transaction and reschedules it
 In the situation where a transaction is requests multiple locks,

each lock request has an associated time-out value. If the lock

is not granted before the time-out expires, the transaction is
rolled
12/10/24 back
3-71
 Cont…

12/10/24
Problem. Cascading
rollback…
Example
First T1 acquire lock and r and w
T1 T2 then unlock. What ever Write byT1
Lx(A) on A read By T2 for data item A,
Similar to T2 and T3.
R(A)
But T1 not yet committed T2 read
W(A) Dirty data if T1 fails some where
u(A) T2 roll back and T3 also rollback
XL(A)
R(A)
W(A)
U(A)
XL(A)
12/10/24
There …..
is a cycle in the graph so its not conflict seriable. 3-73
 Possible solution for problem in 2PL
 Conservative 2-phase lock protocol
 Lock all that you need before transaction start
 This means you have to do predicted how many data item
are used before you start.
 If T1 has used data item A,B,C,D ,it request lock on all
then if all data item are guaranteed it start if it waits until
guaranteed ,
 We don’t have growing phase. It have only shrinking.
 Advantage : No deadlock situation because all acquired
before start
 Disadvantage : practical implementation is difficult

12/10/24
3-74
 Possible solution for problem in 2PL
 Strict 2-phase lock protocol
 Transaction T does not release any of exclusive lock until
after it commits or abort.
 Most popular one because it is recover easily.

)
C
l(
U
)R
l(A
B
l(
)W ).
A .U
l( L(
C)
R
End Tx
StartTx Commit
..
 But there is deadlock. UL(B)
12/10/24
3-75
Strict 2-phase
What kind of locking the following schedule?
T1

Lock-s(A)

Read(A)

Lock-x(B)

Read(B)

Write(B)

commit

Unlock(B)

Unlock(A)
12/10/24
3-76
Deadlock

 Occurs when two transactions wait indefinitely for each

other to unlock data

 Known as deadly embrace

 Control techniques

 Deadlock prevention
 Deadlock detection
 Deadlock avoidance

 Choice of deadlock control method depends on database

environment
12/10/24
3-77
 Deadlock Prevention
 We can prevent deadlocks by giving each transaction a priority
and ensuring that lower priority transactions are not allowed to
wait for higher priority transactions
 One way to assign priorities is to give each transaction a
timestamp when it starts up.
 The lower the timestamp, the higher the transaction's priority,
that is, the oldest transaction has the highest priority.
 Assume Ti requests a lock, but Tj holds a conflicting lock. We
can follow two strategies:
 Wait-die: if Ti has higher priority, it waits; else Ti aborts.
 Wound-wait: if Ti has higher priority, abort Tj; else Ti waits.
 Note: after aborting, restart with original timestamp!

12/10/24
3-78
Deadlock Detection
 DBMS must periodically check for deadlocks.

 When a transaction Ti is suspended because a lock that it

requests cannot be granted, it must wait until all

transactions Tj that currently hold conflicting locks release
them.
 Lock Manager maintains a “Waits-for” graph:
 Node for each transaction.
 Arc from Ti to Tj if Tj holds a lock and Ti
 is waiting for it.
 Periodically check graph for cycles.
 “Shoot” some transaction to break the cycle.
12/10/24
3-79
 Simpler hack: time-outs.
 Deadlock Avoidance
 Detect potential deadlocks in advance and take actions to ensure
that a deadlock will not occur.
 Transactions are allowed to proceed unless a requested resource
is unavailable
 Two different approaches:
 Ordering of data items: Order data items and sites; locks can
only be requested in that order.
 Prioritize transactions: Resolve deadlocks by aborting
transactions with higher or lower priority.
 The following schemes assume that Ti requests a lock hold by
Tj:
 Wait-Die Scheme:if ts(Ti) <ts(Tj) then Ti waits else Ti dies
 Wound-WaitScheme:if ts(Ti) <ts(Tj) then Tj wounds(aborts) else Ti waits
12/10/24
3-80
Transaction Failure …
 What are the transaction failure?
 System failure/crash- HW or SW error during
transaction execution.
 Transaction Error-Failure caused by an operation in the
transaction. Ex Division by zero
 Local Errors-conditions that Couse the cancellation of
transaction.
 Ex data needed for transaction not found.
 Concurrency control enforcement.- transaction may be
aborted by the concurrency control method. Ex
Deadlock

12/10/24
3-81
Transaction Failure …
 What are the transaction failure?
 Disk Failure –loss of data in disk blocks during a
transaction. i.e. the system cant read/write the disk
properly
 Physical problem and catastrophes – problems s like
power failure,

12/10/24
3-82
 Scenarios ….
 System crashes in the middle of a transaction T;

 partial effects of T were written to disk

 How do we undo T (atomicity)?

 System crashes right after a transaction T commits; not all

effects of T were written to disk

 How do we complete T (durability)?

 Media fails; data on disk corrupted

 How do we reconstruct the database (durability)?

12/10/24
3-83
Logging
 Log is Sequence of log records, recording all changes made

to the database
 Written to stable storage (e.g.,disk) during normal operation
 Used in recovery

 • Hey, one change turns into two!

 – Isn’t it bad for performance?

 – But writes are sequential (append to the end of log)

 – Can use dedicated disk(s) to improve performance

12/10/24
3-84
 Transaction Failure and
recovery and log
 When the transaction submitted to database
system. In this the DBMS responsible to excused
ALL of operation because in any case the DBMS
should not allow to half execute and half of
bypass.
 When the transaction was running its operation
some system failed occurred.
 In this case we should have a mechanism to do
recovery and this the help of log file.

12/10/24
3-85
Recovery Algorithms
 Recovery algorithms are techniques to ensure database

consistency and transaction atomicity and durability despite

failures
 Recovery algorithms have two parts
 Actions taken during normal transaction processing to ensure

enough information exists to recover from failures.

 Actions taken after a failure to recover the database contents

to a state that ensures atomicity, consistency and durability.

12/10/24
3-86
Log-Based Recovery
 A log is kept on stable storage.
 The log is a sequence of log records, and maintains a record of
update activities on the database.
 When transaction Ti starts, it registers itself by writing a <Ti
start>log record
 Before Ti executes write(X), a log record <Ti, X, V1, V2> is
written,where V1 is the value of X before the write, and V2 is
the value to be written to X.
 Log record notes that Ti has performed a write on data item Xj Xj had
value V1 before the write, and will have value V2 after the write.
 When Ti finishes it last statement, the log record <Ti
commit> is written.
12/10/24
3-87
Log-Based Recovery...

 Transaction ID
 [ Start_transaction,Tid]
 [write-item.Tid, X,old-value, new-value]
 [read-item,Tid,X]
 [commit,Tid] [Abort,Tid]

12/10/24
3-88