CSTE 2201

Database Management System

Transaction

Fateha Khanam Bappee, Ph.D.

Department of Computer Science and Telecommunications Engineering
Noakhali Science and Technology University
May 2025

Courtesy: Database System Concepts (7th Edition) by

Silberschatz, Korth & Sudarshan
Md. Mahbub Alam (Dalhousie University)
 Lesson Agenda

§Introduction to Transaction Processing

§Desirable Properties of Transaction
§Transaction States
§Serializability
§Recoverability

2
 Introduction to Transaction Processing

§Single-User System: At most one user at a time can use the system.
§Multiuser System: Many users can access the system concurrently.
§Concurrency
- Interleaved processing: Concurrent execution of processes is interleaved in
a single CPU
- Parallel processing: processes are concurrently executed in multiple CPUs.
§Problem
How to make the simultaneous interactions of multiple users with
the database safe, consistent, correct, and efficient?

3
Concurrent Processing

4
 What is it?

§Transaction:
§ Unit of program execution that accesses and possibly updates various data items.
§ Logical unit of database processing that includes one or more access operations (read -
retrieval, write - insert or update, delete).
§ E.g. transaction to transfer $50 from account A to account B:

5
 Transaction? (Cont.)

§A transaction (set of database operations) can either be

embedded within an application program or they can be
specified interactively via a high-level query language such as
SQL.
§Transactions access data using two operations:
§read(X): Transfers the data item X from the database to a local buffer
belonging to the transaction that executed the read operation.
§write(X): transfers the data item X from the local buffer of the
transaction that executed the write back to the database.

6
 Read and Write Operations

§read(X)
1. Find the address of the disk block that contains data item X
2. Copy the disk block into a buffer in main memory.
3. Copy the item X from the buffer to the program variable named X
§write(X)
1. Find the address of the disk block that contains data item X.
2. Copy that disk block into a buffer in main memory
3. Copy item X from the program variable named X into its correct location in
the buffer.
4. Store the updated block from the buffer back to disk (either immediately
or at some later point in time).

7
 Transaction? (Cont.)

§Two main issues to deal with:

§Failures of various kinds, such as hardware failures and system crashes.
§Concurrent execution of multiple transactions.

8
 Why is Concurrency Control needed?

§The Lost Update Problem: This occurs when two transactions that access the
same database items have their operations interleaved in a way that makes
the value of some database item incorrect.

Item has an incorrect value because

its update by T1 is lost (overwritten).

9
 Why is Concurrency Control needed? (Contd.)

§The Temporary Update (or Dirty Read) Problem

– This 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.

10
 Why is Concurrency Control needed? (Contd.)

• The 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.

11
 Why is recovery needed?

§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.
§A transaction or system error:
§Some operation in the transaction may cause it to fail, such as
integer overflow or division by zero. Transaction failure may also
occur because of erroneous parameter values or because of a
logical programming error. In addition, the user may interrupt
the transaction during its execution.

12
 Why is recovery needed? (Contd.)

§Local errors or exception conditions detected by the transaction:

§Certain conditions necessitate cancellation of the transaction. For example,
data for the transaction may not be found. A condition, such as insufficient
account balance in a banking database, may cause a transaction, such as a
fund withdrawal from that account, to be canceled. A programmed abort in
the transaction causes it to fail.
§Concurrency control enforcement:
§The concurrency control method may decide to abort the transaction, to be
restarted later, because it violates Serializability or because several
transactions are in a state of deadlock.

13
 Why is recovery needed? (Contd.)

§Disk failure:
§Some disk blocks may lose their data because of a read or write
malfunction or because of a disk read/write head crash. This may
happen during a read or a write operation of the transaction.
§Physical problems and catastrophes:
§This refers to an endless list of problems that includes power or
air-conditioning failure, fire, theft, sabotage, overwriting disks or
tapes by mistake, and mounting of a wrong tape by the operator.

14
 Lesson Agenda

§Introduction to Transaction Processing

§Desirable Properties of Transaction
§Transaction States
§Serializability
§Recoverability

15
 ACID Properties

• To preserve the integrity of data in the database. Transactions should

posses several properties called ACID properties.
• Atomicity. Either all operations of the transaction are performed its entirety or not
performed at all.
• Consistency. A transaction is consistency preserving if its complete execution takes
the database from one consistent state to another.
• Isolation. A transaction should not make its updates visible to other transactions
until it is committed; this property, when enforced strictly, solves the temporary
update problem and makes cascading rollbacks of transactions unnecessary
• Durability or Permanency. After a transaction completes successfully, the changes
it has made to the database persist, even if there are system failures.

16
 Lesson Agenda

§Introduction to Transaction Processing

§Desirable Properties of Transaction
§Transaction States
§Serializability
§Recoverability

17
 Transaction States

• A transaction is an atomic unit of work that is either completed in

its entirety or not done at all. For recovery purposes, the system
needs to keep track of when the transaction starts, terminates, and
commits or aborts.
• Transaction states:
• Active state
• Partially committed state
• Committed state
• Failed state
• Aborted State

18
 Transaction States (Cont.)

§Active – the initial state; the transaction stays in this state while it is executing.
§Partially committed – after the final statement has been executed.
§Failed -- after the discovery that normal execution can no longer proceed.
§Aborted – the transaction has ended unsuccessfully; after the transaction has
been rolled back and the database restored to its state prior to the start of the
transaction. Two options after it has been aborted:
§ Restart the transaction (can be done only if no internal logical error)
§ Kill the transaction
§Committed – after successful completion of transaction.

19
 Why Concurrent Executions?

§Multiple transactions are allowed to run concurrently in the system.

§Advantages are:
§ Increased processor and disk utilization, leading to better transaction throughput
§ E.g. one transaction can be using the CPU while another is reading from or writing to the
disk
§ Reduced average response time for transactions: short transactions need not wait
behind long ones.
§Concurrency control schemes – mechanisms to achieve isolation
§ that is, to control the interaction among the concurrent transactions in order to
prevent them from destroying the consistency of the database

20
 Schedules of Transactions

§We have discussed that multiple transactions can be executed

concurrently by interleaving their operations
§Schedule:
§Ordering of execution of operations from various transactions T1, T2, … , Tn is
called a schedule S.
§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.

21
 Example of a Schedule

§T1: r1(X); w1(X); r1(Y); w1(Y);

§T2: r2(X); w2(X);
§A schedule, S:
r1(X); r2(X); w1(X); r1(Y); w2(X); w1(Y);

22
 Conflicts

§Two operations in a schedule are said to conflict if they satisfy ALL

three of the following conditions:
1. they belong to different transactions AND
2. they access the same item X AND
3. at least one of the operations is a write(X)
§Example.:

23
 Schedules of Transaction (Cont.)

§Complete schedule: A schedule S of n transactions T1, T2, ..., Tn , is

said to be a complete schedule if the following conditions hold:
[Link] operations in S are exactly those operations in T1, T2, ..., Tn including a
commit or abort operation as the last operation for each transaction in
the schedule.
[Link] any pair of operations from the same transaction Ti , their order of
appearance in S is the same as their order of appearance in Ti.
[Link] any two conflicting operations, one of the two must occur before the
other in the schedule.

24
 Serial Schedule

§Serial & Non-Serial schedule: A schedule S is serial if, for every

transaction T participating in the schedule, all the operations of T
are executed consecutively in the schedule; For a set of n
transactions, there exist n! different valid serial schedule.

25
 Example of Serial Schedule:

§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 S1

26
 Example of Serial Schedule:

§A serial schedule where T2 is followed by T1

Schedule S2

27
 Example of Serial Schedule:

§When several transactions executes

concurrently, the corresponding schedule no
longer needs to be serial. Let T1 and T2 be the
transactions defined previously. The following
schedule is not a serial schedule, but it is
equivalent to schedule S1.

Schedule S3
Concurrent schedule equivalent to
schedule S1

28
 Example of Serial Schedule:

§The following concurrent schedule does not

preserve the correct value.

Schedule S4

29
 Lesson Agenda

§Introduction to Transaction Processing

§Desirable Properties of Transaction
§Transaction States
§Serializability
§Recoverability

30
 Serializability

§ Assumption: Every serial schedule is correct.

§ Goal: Find non-serial schedules which are also correct.
§ A schedule S of n transactions is serializable if it is equivalent to some serial schedule of
the same n transactions.
§ Conflict Serializable
§ View Serializable
§ A non-serial schedule S is serializable is equivalent to saying that it is correct because it is
equivalent to a serial schedule, which is considered correct.
§ When are two schedules equivalent?
§ If they lead to same result (result equivalent)
§ If the order of any two conflicting operations is the same in both schedules. (conflict equivalent)

31
 Result Equivalent Schedules

§Two schedules are result equivalent if they produce the same final state of the
database
§Problem: May produce same result by accident!

Schedules S1 and S2 are result equivalent for X=100 but not in general
32
 Conflict Equivalent Schedules

§Two schedules are conflict equivalent, if the order of any two conflicting
operations is the same in both schedules

S1’ and S1 are conflict equivalent (S1’ produces the same result as S1)
33
Conflict Equivalent Schedules

34
 Conflict Equivalence (Example)

S1’’ and S1 are conflict equivalent (S1’’ produces the same result as S1)
36
 Conflict Equivalence (Example)

S1’’’ and S1 is not conflict equivalent (S1’’’ produces different result than S1)
37
 Conflict Serializable

§Schedule S is conflict serializable if it is conflict equivalent to some

serial schedule S’
§We can reorder the non-conflicting operations to improve efficiency
§Non-conflicting operations:
§Reads and writes from same transaction
§Reads from different transactions
§Reads and writes from different transactions on different data items
§Conflicting operations:
§Reads and writes from different transactions on same data item

38
Conflict Serializable (Example)

B is conflict equivalent to A B is serializable

39
 Conflict Serializable

§ Read Section 17.6 (Book: Database System Concepts)

§ Precedence Graph:
• This graph consists of a pair G = (V, E), where V is a set of vertices and E is a set of edges. The
set of vertices consists of all the transactions participating in the schedule. The set of edges
consists of all edges Ti → Tj for which one of three conditions holds:
- Ti executes write(A) before Tj executes read(A).
- Ti executes read(A) before Tj executes write(A).
- Ti executes write(A) before Tj executes write(A).
• If the precedence graph for S has a cycle, then schedule S is not conflict serializable. If the
graph contains no cycles, then the schedule S is conflict serializable.

40
 Conflict Serializable

§Precedence Graph:

Not conflict serializable

41
 View Serializability

• A schedule S is view serializable if it is view equivalent to a serial schedule.

Two schedules are said to be view equivalent if the following three conditions
hold:
1. The same set of transactions participates in S and Sʹ, and S and Sʹ include the same
operations of those transactions.
2. For any operation Ri(X) of Ti in S, if the value of X read by the operation has been written
by an operation Wj(X) of Tj (or if it is the original value of X before the schedule started),
the same condition must hold for the value of X read by operation Ri(X) of Ti in Sʹ.
3. If the operation Wk(Y) of Tk is the last operation to write item Y in S, then Wk(Y) of Tk
must also be the last operation to write item Y in Sʹ.

42
 View Serializability (Contd.)

§Any conflict serializable schedule is also view serializable, but not vice versa.
Below is a schedule which is view-serializable but not conflict serializable.
§Every view serializable schedule that is not conflict serializable has blind
writes.

43
 View Serializability (Contd.)

§The premise behind view equivalence:

§As long as each read operation of a transaction reads the result of the same
write operation in both schedules, the write operations of each transaction
must produce the same results.
§“The view”: the read operations are said to see the the same view in both
schedules.

44
 Lesson Agenda

§Introduction to Transaction Processing

§Desirable Properties of Transaction
§Transaction States
§Serializability
§Recoverability

45
 Recoverable Schedules

§ Recoverable Schedule: Schedule in which for each pair of transactions Ti and Tj such that
Tj reads a data item previously written by a transaction Ti, then the commit operation of Ti
appears before the commit operation of Tj.
§ The following schedule is not recoverable if T9 commits immediately after the read.
§ If T8 should abort, T9 would have read (and possibly shown to the user) an inconsistent
database state. Hence, database must ensure that schedules are recoverable.

46
 Cascading Rollbacks
§ Cascading Rollback – a single transaction failure leads to a series of transaction rollbacks, is
called Cascading Rollback.
§ Consider the following schedule where none of the transactions has yet committed.
§ If T10 fails, T11 and T12 must also be rolled back.
§ Cascading Rollback is undesirable, since it leads to the undoing of a significant amount of
work.

47
 Cascadeless Schedules

§Cascadeless schedules: Cascading Rollbacks cannot occur; Since for each pair
of transactions Ti and Tj such that Tj reads a data item previously written by Ti,
the commit operation of Ti appears before the read operation of Tj.
§Every Cascadeless schedule is also recoverable.
§It is desirable to restrict the schedules to those that are cascadeless.

48
Thank you
J