Module 17: Transactions

Database System Concepts, 7^th Ed.

©Silberschatz, Korth and Sudarshan�See www.db-book.com for conditions on re-use

©Silberschatz, Korth and Sudarshan

17.1

Database System Concepts - 7^th Edition

Outline

• Transaction Concept
• Transaction State
• Concurrent Executions
• Serializability
• Locking
• Recoverability

©Silberschatz, Korth and Sudarshan

17.2

Database System Concepts - 7^th Edition

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)

• Two main issues to deal with:
• Failures of various kinds, such as hardware failures and system crashes
• Concurrent execution of multiple transactions

©Silberschatz, Korth and Sudarshan

17.3

Database System Concepts - 7^th Edition

Example of Fund Transfer

• Transaction to transfer $50 from account A to account B:

1. read(A)

2. A := A – 50

3. write(A)

4. read(B)

5. B := B + 50

6. write(B)

• Atomicity requirement
• If the transaction fails after step 3 and before step 6, money will be “lost” leading to an inconsistent database state
• 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.

©Silberschatz, Korth and Sudarshan

17.4

Database System Concepts - 7^th Edition

Example of Fund Transfer (Cont.)

• Consistency requirement in above example:
• 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.

©Silberschatz, Korth and Sudarshan

17.5

Database System Concepts - 7^th Edition

Example of Fund Transfer (Cont.)

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

� T1 T2

1. read(A)

2. A := A – 50

3. write(A)� read(A), read(B), print(A+B)

4. read(B)

5. B := B + 50

6. write(B

• Isolation can be ensured trivially by running transactions serially
• That is, one after the other.
• However, executing multiple transactions concurrently has significant benefits, as we will see later.

©Silberschatz, Korth and Sudarshan

17.6

Database System Concepts - 7^th Edition

ACID Properties

• 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 T_i and T_j, it appears to T_i that either T_j, finished execution before T_i started, or T_j started execution after T_i finished.
• Durability. After a transaction completes successfully, the changes it has made to the database persist, even if there are system failures.

A transaction is a unit of program execution that accesses and possibly updates various data items. To preserve the integrity of data the database system must ensure:

©Silberschatz, Korth and Sudarshan

17.7

Database System Concepts - 7^th Edition

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.
• 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
• Committed – after successful completion.

©Silberschatz, Korth and Sudarshan

17.8

Database System Concepts - 7^th Edition

Transaction State (Cont.)

©Silberschatz, Korth and Sudarshan

17.9

Database System Concepts - 7^th Edition

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

©Silberschatz, Korth and Sudarshan

17.10

Database System Concepts - 7^th Edition

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.
• A transaction that successfully completes its execution will have a commit instructions as the last statement
• A transaction that fails to successfully complete its execution will have an abort instruction as the last statement

©Silberschatz, Korth and Sudarshan

17.11

Database System Concepts - 7^th Edition

Schedule 1

• Let T₁ transfer $50 from A to B, and T₂ transfer 10% of the balance from A to B.
• A serial schedule in which T₁ is followed by T₂ :

©Silberschatz, Korth and Sudarshan

17.12

Database System Concepts - 7^th Edition

Schedule 2

• A serial schedule where T₂ is followed by T₁

​

©Silberschatz, Korth and Sudarshan

17.13

Database System Concepts - 7^th Edition

Schedule 3

• Let T₁ and T₂ be the transactions defined previously. The following schedule is not a serial schedule, but it is equivalent to Schedule 1

​

​

​

​

​

​

​

​

​

​

​

• In Schedules 1, 2 and 3, the sum A + B is preserved.

©Silberschatz, Korth and Sudarshan

17.14

Database System Concepts - 7^th Edition

Schedule 4

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

©Silberschatz, Korth and Sudarshan

17.15

Database System Concepts - 7^th Edition

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

©Silberschatz, Korth and Sudarshan

17.16

Database System Concepts - 7^th Edition

Conflicting Instructions

• Instructions l_i and l_j of transactions T_i and T_j respectively, conflict if and only if there exists some item Q accessed by both l_i and l_j, and at least one of these instructions wrote Q.

1. l_i = read(Q), l_j = read(Q). l_i and l_j don’t conflict.� 2. l_i = read(Q), l_j = write(Q). They conflict.� 3. l_i = write(Q), l_j = read(Q). They conflict� 4. l_i = write(Q), l_j = write(Q). They conflict

​

• If l_i and l_j 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.

©Silberschatz, Korth and Sudarshan

17.17

Database System Concepts - 7^th Edition

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

©Silberschatz, Korth and Sudarshan

17.18

Database System Concepts - 7^th Edition

Conflict Serializability

Ex:

T1

T2

T3

R(X)

R(Y)

R(X)

R(Y)

R(Z)

W(Y)

W(Z)

R(X)

W(X)

W(Z)

T1

T2

T3

Precedence Graph

Conflict pairs

R-W

W-R

W-W

©Silberschatz, Korth and Sudarshan

17.19

Database System Concepts - 7^th Edition

Conflict Serializability

Ex:

T1

T2

T3

R(X)

R(Y)

R(X)

R(Y)

R(Z)

W(Y)

W(Z)

R(X)

W(X)

W(Z)

T1

T2

T3

Precedence Graph

Conflict pairs

R-W

W-R

W-W

T2

T3

T1

©Silberschatz, Korth and Sudarshan

17.20

Database System Concepts - 7^th Edition

View Serializability

• Let S and S’ be two schedules with the same set of transactions. S and S’ are view equivalent if the following three conditions are met, for each data item Q,

1. If in schedule S, transaction T_i reads the initial value of Q, then in

schedule S’ also transaction T_i must read the initial value of Q.

2. If in schedule S transaction T_i executes read(Q), and that value was

produced by transaction T_j (if any), then in schedule S’ also

transaction T_i must read the value of Q that was produced by the

same write(Q) operation of transaction T_j .

3. The transaction (if any) that performs the final write(Q) operation in

schedule S must also perform the final write(Q) operation in schedule S’.

• As can be seen, view equivalence is also based purely on reads and writes alone.

©Silberschatz, Korth and Sudarshan

17.21

Database System Concepts - 7^th Edition

View Serializability (Cont.)

• A schedule S is view serializable if it is view equivalent to a serial schedule.
• Every conflict serializable schedule is also view serializable.
• Below is a schedule which is view-serializable but not conflict serializable.�

​

​

​

T27

Precedence Graph

T28

T29

©Silberschatz, Korth and Sudarshan

17.22

Database System Concepts - 7^th Edition

Lock-Based Protocols

• A lock is a mechanism to control concurrent access to a data item
• Data items can be locked in two modes :

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

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

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

requested using lock-S instruction.

• Lock requests are made to concurrency-control manager. Transaction can proceed only after request is granted.

©Silberschatz, Korth and Sudarshan

17.23

Database System Concepts - 7^th Edition

Lock-Based Protocols (Cont.)

• Example of a transaction performing locking:

T₂: lock-S(A);

read (A);

unlock(A);

​

lock-S(B);

read (B);

unlock(B);

display(A+B)

• Locking as above is not sufficient to guarantee serializability

©Silberschatz, Korth and Sudarshan

17.24

Database System Concepts - 7^th Edition

Schedule With Lock Grants

• Grants omitted in rest of chapter
• Assume grant happens just before the next instruction following lock request
• This schedule is not serializable (why?)
• A locking protocol is a set of rules followed by all transactions while requesting and releasing locks.
• Locking protocols enforce serializability by restricting the set of possible schedules.

©Silberschatz, Korth and Sudarshan

17.25

Database System Concepts - 7^th Edition

Deadlock

• Consider the partial schedule

​

​

​

�

​

​

​

• Neither T₃ nor T₄ can make progress — executing lock-S(B) causes T₄ to wait for T₃ to release its lock on B, while executing lock-X(A) causes T₃ to wait for T₄ to release its lock on A.
• Such a situation is called a deadlock.
• To handle a deadlock one of T₃ or T₄ must be rolled back �and its locks released.

©Silberschatz, Korth and Sudarshan

17.26

Database System Concepts - 7^th Edition

Deadlock (Cont.)

• The potential for deadlock exists in most locking protocols. Deadlocks are a necessary evil.
• Starvation is also possible if concurrency control manager is badly designed. For example:
• A transaction may be waiting for an X-lock on an item, while a sequence of other transactions request and are granted an S-lock on the same item.
• The same transaction is repeatedly rolled back due to deadlocks.
• Concurrency control manager can be designed to prevent starvation.

©Silberschatz, Korth and Sudarshan

17.27

Database System Concepts - 7^th Edition

The Two-Phase Locking Protocol

• A protocol which ensures conflict-serializable schedules.
• Phase 1: Growing Phase
• Transaction may obtain locks
• Transaction may not release locks
• Phase 2: Shrinking Phase
• Transaction may release locks
• Transaction may not obtain locks
• The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points (i.e., the point where a transaction acquired its final lock).

©Silberschatz, Korth and Sudarshan

17.28

Database System Concepts - 7^th Edition

The Two-Phase Locking Protocol (Cont.)

• Two-phase locking does not ensure freedom from deadlocks
• Extensions to basic two-phase locking needed to ensure recoverability of freedom from cascading roll-back
• Strict two-phase locking: a transaction must hold all its exclusive locks till it commits/aborts.
• Ensures recoverability and avoids cascading roll-backs
• Rigorous two-phase locking: a transaction must hold all locks till commit/abort.
• Transactions can be serialized in the order in which they commit.
• Most databases implement rigorous two-phase locking, but refer to it as simply two-phase locking

©Silberschatz, Korth and Sudarshan

17.29

Database System Concepts - 7^th Edition

The Two-Phase Locking Protocol (Cont.)

• Two-phase locking is not a necessary condition for serializability
• There are conflict serializable schedules that cannot be obtained if the two-phase locking protocol is used.
• In the absence of extra information (e.g., ordering of access to data), two-phase locking is necessary for conflict serializability in the following sense:
• Given a transaction T_i that does not follow two-phase locking, we can find a transaction T_j that uses two-phase locking, and a schedule for T_i and T_j that is not conflict serializable.

​

©Silberschatz, Korth and Sudarshan

17.30

Database System Concepts - 7^th Edition

Concurrency Control and Recovery

• With concurrent transactions, all transactions share a single disk buffer and a single log
• A buffer block can have data items updated by one or more transactions
• We assume that if a transaction T_i has modified an item, no other transaction can modify the same item until T_i has committed or aborted
• i.e., the updates of uncommitted transactions should not be visible to other transactions
• Otherwise, how to perform undo if T₁ updates A, then T₂ updates A and commits, and finally T₁ has to abort?
• Can be ensured by obtaining exclusive locks on updated items and holding the locks till end of transaction (strict two-phase locking)
• Log records of different transactions may be interspersed in the log.

​

©Silberschatz, Korth and Sudarshan

17.31

Database System Concepts - 7^th Edition

Undo and Redo Operations

• Undo and Redo of Transactions
• undo(T_i) -- restores the value of all data items updated by T_i to their old values, going backwards from the last log record for T_i
• Each time a data item X is restored to its old value V a special log record <T_i , X, V> is written out
• When undo of a transaction is complete, a log record �<T_i abort> is written out.
• redo(T_i) -- sets the value of all data items updated by T_i to the new values, going forward from the first log record for T_i
• No logging is done in this case

​

​

©Silberschatz, Korth and Sudarshan

17.32

Database System Concepts - 7^th Edition