T RANSACTION
Faisal Anwer & Mohammad Nadeem
1
INTRODUCTION
A collection of several operations on the database appears to be a single unit from the point of view of the database user.
Transaction-
A single logical unit of work.
Example-
Transferring money
Many transactions can run simultaneously (concurrent transactions).
Concurrent transactions pose inconsistencies in the database if not handled properly.
2
ACID PROPERTIES OF TRANSACTIONS
To ensure integrity of data, database maintain following properties of a transaction:
Atomicity-
Either all operations of the transaction are reflected properly in the database, or none are.
Consistency-
A transaction should preserve the consistency of the database.
Isolation-
Each transaction should be unaware of other transactions executing concurrently in the system.
Durability –
After a transaction completes successfully, the changes it has made to the database persist, even if there are system failures.
3
E XAMPLE
Transactions access data using two operations:
read(X), which reads the data item X from the database.
write(X), which writes the data item X in the database.
Let Ti be a transaction that transfers Rs. 50 from account A to account B:
4
ACID PROPERTIES OF TRANSACTIONS
Consistency-
The consistency requirement here is that the sum of A and B be unchanged by the
execution of the transaction.
Atomicity-
Suppose that some failure happened after the write(A) operation but before the write(B)
operation.
It will lead database into a inconsistent state.
If the atomicity property is present, all
actions of the transaction are reflected in the database, or none are.
5
ACID PROPERTIES OF TRANSACTIONS
Durability:
Once the user is notified about the successful transfer of funds, no system failure should result in a loss of data, even if there is a
system failure after the transaction completes execution.
Difference between Atomicity and Durability?
Durability and Atomicity are ensured by recovery techniques.
6
ACID PROPERTIES OF TRANSACTIONS
Isolation:
Even if the consistency and atomicity properties are ensured, concurrent transactions may result in an inconsistent database state.
If a second concurrently running transaction
calculates A+B after write(A) but before write(B).
What would be the result?
Such transactions may left the database in an inconsistent state even after both transactions have completed.
Isolation is ensured by concurrency control techniques.
7
T RANSACTION STATE
8
T RANSACTION 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 has been restored to its state prior to the start of the transaction. (Roll back is done either by a restart or kill).
Committed, after successful completion. 9
C ONCURRENCY
Achieving consistency in a concurrent environment is a complicated task.
One way to achieve this is to execute transactions serially.
(But then transactions would not be concurrent.)
However, concurrency provide certain benefits:
Improved throughput (number of transactions executed in a given amount of time) and resource utilization.
Reduced waiting time
There is always a trade-off between degree of concurrency and
associated cost. 10
C ONCURRENT EXECUTION SCENARIOS
Let Transaction T1 transfers $50 from account A to account B.
Transaction T2 transfers 10 percent of the balance from account A to account B.
11
C ONCURRENT EXECUTION SCENARIOS
Schedule- When transactions are executing concurrently in an interleaved fashion, the order of execution of
operations from all the various transactions is known as a
schedule.
If A=1000 and B = 2000
Final A = 855
Final B = 2145
A+B = 3000
It is serial schedule.
12
C ONCURRENT EXECUTION SCENARIOS
If A=1000 and B = 2000
Final A = 850
Final B = 2150
A+B = 3000
Is it a serial schedule?
Executing transactions serially may also produce different
results.
13
C ONCURRENT EXECUTION SCENARIOS
If A=1000 and B = 2000
Final A = 855
Final B = 2145
A+B = 3000
Is it a serial schedule?
Is it behave like a serial schedule?
14
C ONCURRENT EXECUTION SCENARIOS
If A=1000 and B = 2000
Final A = 950
Final B = 2100
A+B = 3050
Concurrent execution of transactions may or may not equivalent to a serial schedule.
An acceptable schedule (serializable schedule) is one which is equivalent to a serial schedule.
15
S ERIALIZABILITY
Serial transactions result in consistent database state.
We are looking for schedules which are equivalent to a serial schedule.
Two ways to ensure serializability in schedules having concurrent instructions:
Conflict serializability.
View serializability.
16
C ONVENTION
17
CONFLICT SERIALIZABILITY
Schedule S has two consecutive instructions, I and J , of transactions Ti and Tj , respectively (i≠ j).
If I and J refer to different data items, then we can swap I and J without affecting the results.
if I and J refer to the same data item Q, then the order of the two steps may matter.
Possible cases, if I and J refer to the same data item Q :
1. I = read(Q), J = read(Q).
2. I = read(Q), J = write(Q).
3. I = write(Q), J = read(Q).
4. I = write(Q), J = write(Q).
18
CONFLICT SERIALIZABILITY
Case 1:
I = read(Q), J = read(Q).
The order of I and J does not matter, since the same value of Q is read by Ti and Tj , regardless of the order.
Case 2:
I = read(Q), J = write(Q).
If I comes before J , then Ti does not read the value of Q that is written by Tj in instruction J.
If J comes before I, then Ti reads the value of Q that is written by Tj.
Order matters.
19
CONFLICT SERIALIZABILITY
Case 3:
I = write(Q), J = read(Q).
The order of I and J matters for reasons similar as in Case 2.
Case 4:
I = write(Q), J = write(Q).
One write instruction will overwrite the other write instruction.
Only the latter of the two write instructions is preserved in the database and is used by next read instruction.
Order matters.
Take Away: write operation Order is important. 20
CONFLICT SERIALIZABILITY
If either of I and J, from different transactions operating on same data set, is a write operation- order of I and J is important.
We say that I and J conflict if they are operations by different transactions on the same data item, and at least one of these instructions is a write operation.
If there is no conflict among I and J, we can achieve serializability.
A schedule is called conflict serializable if it can be
transformed into a serial schedule by swapping non-conflicting
operations. 21
E XAMPLE
22
A serial execution of transactions
CONFLICT SERIALIZABILITY
If a schedule S1 can be transformed into a schedule S2 by a series of swaps of non-conflicting instructions, we say that S1 and S2 are conflict equivalent.
23
CONFLICT SERIALIZABILITY
A schedule S is conflict serializable if it is conflict equivalent to a serial schedule.
24
T ESTING OF CONFLICT SERIALIZABILITY
We need some method for determining conflict serializability of a schedule.
Precedence graph: A directed graph G = (V, E) where V denotes transactions in a schedule and set E has an edge between Ti →Tj if:
1. Ti executes write(Q) before Tj executes read(Q).
2. Ti executes read(Q) before Tj executes write(Q).
3. Ti executes write(Q) before Tj executes write(Q).
If there is a cycle in precedence graph, then that schedule is not conflict serializable.
25
E XAMPLE
26
E XAMPLE
27
EXAMPLE
28
TOPOLOGICAL SORTING
A serializability order of the transactions can be obtained by finding a linear order consistent with the precedence graph. This process is called topological sorting.
29
CONFLICT SERIALIZABILITY
A schedule might have a serial schedule which can not be identified by conflict serializability.
30
V IEW SERIALIZABILITY
Less stringent than conflict serializability.
Every conflict serializable schedule is also view serializable but the reverse is not true.
Two schedules S1 and S2 are view equivalent if:
For each data item Q, if Ti reads the initial value of Q in schedule S1, then transaction Ti must also read the initial value of Q in schedule S2.
For each data item Q, the transaction (if any) that performs the final write(Q) operation in schedule S1 must perform the final write(Q) operation in schedule S2.
For each data item Q, if Ti executes read(Q) in schedule S1, and if that value was produced by a write(Q) executed by transaction Tj, then the read(Q) of Ti must also read the value of Q that was
produced by the same write(Q) operation of Tj in schedule S2.
31
E XAMPLE
32
These schedules are not conflict equivalent but view equivalent.
A schedule S is view serializable if it is view equivalent to a serial schedule.
R ECOVERABILITY
So far, we have studied schedules while assuming there are no transaction failures.
If a transaction Ti fails, we need to undo the effect of this transaction to ensure the atomicity property of the
transaction.
Any transaction Tj that is dependent on Ti (i.e., Tj has read data written by Ti) is also aborted.
33
R ECOVERABLE AND IRRECOVERABLE SCHEDULES
If T6 fails before it commits, T7 must be
aborted. However, T7 has already committed and cannot be aborted.
This is an irrecoverable schedule.
If we commit T7 after T6 then it would be a recoverable schedule.
For each pair of transactions Ti and Tj, if Tj reads a data item previously written by Ti , the commit operation of Ti appears before the commit operation of Tj , then such a schedule is recoverable otherwise irrecoverable.
34
C ASCADING ROLLBACK
Even if a schedule is recoverable, a transaction failure may lead to roll back of several transactions.
Such a series of transaction rollbacks, is called cascading rollback.
Cascading rollback is undesirable.
35
C ASCADELESS S CHEDULE
Cascading rollback is undesirable.
Schedule that restrict cascading rollback is called Cascadeless Schedule.
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.
36