MDA104 Introduction to Databases
6. Transactions
Vlastislav Dohnal
MDA104, Vlastislav Dohnal, FI MUNI, 2024 2
Transactions
Transaction Concept
Transaction State
Concurrent Executions
Serializability
Recoverability
Implementation of Isolation
Transaction Definition in SQL
Testing for Serializability.
MDA104, Vlastislav Dohnal, FI MUNI, 2024 3
Transaction Concept
A transaction is a unit of program execution that accesses and
possibly updates various data items.
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)
7. commit
Main issues to deal with:
Transaction interruption due failures of various kinds
such as hardware failures and system crashes
Concurrent execution of multiple transactions
Termination of transaction using abort command
MDA104, Vlastislav Dohnal, FI MUNI, 2024 4
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)
7. commit
Atomicity requirement
if the transaction fails after step 3 and before step 6, money will be “lost”
leading to an inconsistent database state
Failure could be due to software or hardware
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 (i.e.,
the transfer of the $50 has taken place), the updates to the database by
the transaction must persist even if there are software or hardware
failures.
MDA104, Vlastislav Dohnal, FI MUNI, 2024 5
Example of Fund Transfer (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)
7. commit
Consistency requirement
E.g. the sum of A and B is unchanged by the execution of the transaction
In general, consistency requirements include
Explicitly specified integrity constraints such as primary keys and foreign
keys
Implicit integrity constraints
E.g. sum of balances of all accounts, minus sum of loan amounts must
equal value of cash-in-hand
A transaction must see a consistent database.
During transaction execution the database may be temporarily inconsistent.
When the transaction completes successfully the database must be consistent
Erroneous transaction logic can lead to inconsistency
Example of Fund Transfer (Cont.)
Transaction to transfer $50 from account A to account B:
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
The sum A + B will be less than it should be.
Isolation can be ensured trivially by running transactions serially
that is, one after the other.
However, executing multiple transactions concurrently has significant
benefits, as we will see later.
MDA104, Vlastislav Dohnal, FI MUNI, 2024 6
Transaction
T11.read(A)
2.A := A – 50
3.write(A)
4.read(B)
5.B := B + 50
6.write(B)
7.commit
Transaction
T21.read(A)
2.read(B)
3.print(A + B)
4.commit
MDA104, Vlastislav Dohnal, FI MUNI, 2024 7
ACID Properties
A transaction is a unit of program execution that accesses and possibly updates various
data items.
It is a sequence of operations that form a desired outcome (the unit of program).
To preserve the integrity of data the database system must ensure:
Atomicity.
Either all operations of the transaction are properly reflected in the database or
none are.
Consistency.
Execution of a transaction in isolation preserves the consistency of the database.
Isolation.
Although multiple transactions may execute concurrently, each transaction must
be unaware of other concurrently executing transactions. Intermediate transaction
results must be hidden from other concurrently executed transactions.
That is, for every pair of transactions Ti and Tj, it appears to Ti that either Tj,
finished execution before Ti started, or Tj started execution after Ti finished.
Durability.
After a transaction completes successfully, the changes it has made to the
database persist, even if there are system failures.
Transaction State
Active
the initial state
the transaction stays in this
state while it is executing
Partially committed
after the final statement has
been executed.
Committed
after successful completion.
Failed
after the discovery that normal execution can no longer proceed.
Aborted
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
MDA104, Vlastislav Dohnal, FI MUNI, 2024 8
MDA104, Vlastislav Dohnal, FI MUNI, 2024 9
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
E.g. 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
Analysis of conflicting operations
Locking – of records, tables
MDA104, Vlastislav Dohnal, FI MUNI, 2024 10
Schedules
Schedule – a sequence 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
A transaction that successfully completes its execution
will have a commit instruction as the last statement
by default, transaction assumed to execute commit instruction as
its last step
A transaction that fails to complete its execution
will have an abort instruction as the last statement (rollback command)
MDA104, Vlastislav Dohnal, FI MUNI, 2024 11
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:
MDA104, Vlastislav Dohnal, FI MUNI, 2024 12
Schedule 2
A serial schedule where T2 is followed by T1
MDA104, Vlastislav Dohnal, FI MUNI, 2024 13
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 (serial schedule).
In Schedules 1, 2 and 3,
the sum A + B is preserved.
MDA104, Vlastislav Dohnal, FI MUNI, 2024 14
Schedule 4
The following concurrent schedule does not preserve the value of
(A + B).
These changes to A
will be discarded by
write(A) in T1
MDA104, Vlastislav Dohnal, FI MUNI, 2024 15
Serializability
Basic Assumption: each transaction preserves database
consistency.
Thus serial execution of a set of transactions preserves database
consistency.
A (possibly concurrent) schedule is serializable if it is equivalent to a
serial schedule.
Different forms of schedule equivalence give rise to the notions of:
1. conflict serializability
2. view serializability
MDA104, Vlastislav Dohnal, FI MUNI, 2024 16
Simplified view of transactions
We ignore operations other than read and write instructions
We assume that transactions may perform arbitrary computations on
data in local buffers in between reads and writes.
Our simplified schedules consist of only read and write instructions.
MDA104, Vlastislav Dohnal, FI MUNI, 2024 17
Conflicting Instructions
Instructions li and lj of transactions Ti and Tj respectively, 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 li and lj are consecutive in a schedule and they do not conflict,
their results would remain the same even if they had been
interchanged in the schedule.
MDA104, Vlastislav Dohnal, FI MUNI, 2024 18
Conflict Serializability
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
MDA104, Vlastislav Dohnal, FI MUNI, 2024 19
Conflict Serializability (Cont.)
Schedule 3 can be transformed into Schedule 1, a serial
schedule where T2 follows T1, by a series of swaps of nonconflicting
instructions.
Therefore Schedule 3 is conflict serializable.
Schedule 3 Schedule 1
MDA104, Vlastislav Dohnal, FI MUNI, 2024 20
Conflict Serializability (Cont.)
Example of a schedule that is not conflict serializable:
We are unable to swap instructions in the above schedule to obtain
either the serial schedule < T3, T4 >, or the serial schedule < T4, T3 >.
MDA104, Vlastislav Dohnal, FI MUNI, 2024 27
Recoverable Schedules
Need to address the effect of transaction failures on concurrently
running transactions.
Recoverable schedule — if a transaction 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 (Schedule 11) is not recoverable if T9 commits
immediately after the read
Should T8 abort, T9 would have read (and possibly shown to the user)
an inconsistent database state!
Hence, database must ensure that schedules are recoverable.
abort
MDA104, Vlastislav Dohnal, FI MUNI, 2024 28
Cascading Rollbacks
Cascading rollback – a single transaction failure leads to a series of
transaction rollbacks.
Consider the following schedule where none of the transactions has
yet committed (so the schedule is recoverable)
If T10 fails, T11 and T12 must also be rolled back
Can lead to the undoing of a significant amount of work
MDA104, Vlastislav Dohnal, FI MUNI, 2024 29
Cascadeless Schedules
Cascadeless schedules — cascading rollbacks cannot occur if
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
MDA104, Vlastislav Dohnal, FI MUNI, 2024 30
Concurrency Control
A database must provide a mechanism that will ensure that all
possible schedules are
either conflict or view serializable, and
are recoverable and preferably cascadeless
A policy in which only one transaction can execute at a time generates
serial schedules, but provides a poor degree of concurrency
Are serial schedules recoverable/cascadeless?
Testing a schedule for serializability after it has executed is a little too
late!
Goal – to develop concurrency control protocols that will assure
serializability.
MDA104, Vlastislav Dohnal, FI MUNI, 2024 33
Weak Levels of Consistency
Some applications are willing to live with weak levels of consistency,
allowing schedules that are not serializable and recoverable
E.g.
a read-only transaction that wants to get an approximate total
balance of all accounts
database statistics computed for query optimization can be
approximate
Such transactions need not be serializable with respect to other
transactions
Tradeoff accuracy for performance
MDA104, Vlastislav Dohnal, FI MUNI, 2024 34
Levels of Consistency in SQL-92
Consistency levels (from highest to lowest):
Serializable — default
Snapshot isolation — (not part of SQL-92) only committed records to be
read, reads must return the value present at the beginning of transaction;
better performance while retaining most of serializability.
Repeatable read — only committed records to be read, repeated reads of
same record must return same value.
However, a transaction may not be serializable:
it may find some new records inserted by a committed transaction.
Read committed — only committed records can be read, but successive
reads of record may return different (but committed) values.
Read uncommitted — even uncommitted records may be read.
Lower degrees of consistency useful for gathering approximate information
about the database
Warning: some database systems do not ensure serializable schedules by
default
Levels of Consistency
Snapshot isolation does not mean serializable!
Example:
One transaction turns each of the white marbles into black marbles.
The second transaction turns each of the black marbles into white marbles.
MDA104, Vlastislav Dohnal, FI MUNI, 2024 35
MDA104, Vlastislav Dohnal, FI MUNI, 2024 36
Transaction Definition in SQL
Data manipulation language must include a construct for specifying the
set of actions that comprise a transaction.
A transaction begins implicitly.
Some systems may use begin to start a new transaction
A transaction ends by:
Commit: commits current transaction and begins a new one.
Rollback: causes current transaction to abort.
Often, SQL statement also commits implicitly if it executes successfully
Mainly when libraries are used to access database.
Implicit commit can be turned off
E.g. in JDBC, connection.setAutoCommit(false);
Summary – Takeaways
Definition of transaction
ACID properties
Simultaneous execution of transactions
schedule
serializability of schedules
levels of transaction isolation
MDA104, Vlastislav Dohnal, FI MUNI, 2024 37