MODULE: 5
TRANSACTION PROCESSING
TECHNIQUES
SOMANAGOWDA PATIL
Assistant Professor,
Dept. of Computer Science [M.Sc.]
BCU, Central College Campus,
Bangalore – 560 001.
Phone No.: 9731475111
Syllabi…
❖ Introduction to Transaction Processing
❖ Transaction and System Concepts
❖ Desirable properties of transactions
❖ Transaction support in SQL
❖ Concurrency Control Techniques:
✓ Two-Phase Locking Techniques
✓ Concurrency Control based on Timestamp Ordering
✓ Multi-version concurrency control techniques
✓ Validation concurrency control techniques.
❖ Recovery Techniques
✓ Recovery Concepts
✓ Recovery in multi-database Systems
✓ Database backup and recovery from catastrophic failures
What is Transaction
For example, work is withdrawing money. To withdraw money, it needs to transaction some
amount from one account to other account through ATM or online etc.
Operations in Transaction
Transaction and System Concepts
Transaction States
Transaction States in DBMS
States through which a transaction goes during its lifetime are known as transaction states. These
states tells about the current state of the Transaction.
Types Of Transaction States
There are six major types of Transaction states which are as given below
1. Active state
2. Partially committed state
3. Committed state Detail diagram of transaction states as below
4. Failed state
5. Aborted state
6. Terminated state
1. Active State
✓ When the instructions of the transaction are executing then the transaction is in active state.
✓ In case of execution of all instruction of transaction, Transaction can go to “partially committed
state” otherwise go to “failed state” from active state.
2. Partially Committed State
✓ After the execution of all instruction of a transaction, the transaction enters into a partially
committed state from active state.
✓ At this stage, Still Changes are possible in transaction because all the changes made by the
transaction are still store in the buffer of main memory.
3. Committed State
✓ Committed state permanently store all changes made by the transaction into the database
✓ Now, the transaction is consider as fully committed.
4. Failed State
✓ When a transaction is in the “active state” or “partially committed state” and some failure occurs
then it becomes impossible to resume its execution, So it enters into a failed state.
Note: At this stage, Transaction cannot go to “partially committed state” or “active state” .
5. Aborted State
✓ As we know failed state can never be resuming but it is possible to restart the failed transaction. To
restart the failed transaction Rollback method comes into picture.
✓ When we rollback (restart) the failed transaction the all the changes made by that transaction
earlier have to be undone.
6. Terminated State
✓ This is the last stage of transaction in its life cycle.
✓ If any transaction comes from “Aborted state” or “committed state” then that transaction is
terminated and get ready to execute the new transactions.
DESIRABLE PROPERTIES OF TRANSACTION
Transaction Properties
▪ The transaction has the four properties which ensure that the database remains consistent,
accuracy, completeness, and data integrity, before and after the transaction execution.
▪ These properties are called as ACID Properties of a transaction.
ACID Properties
1. Atomicity
2. Consistency
3. Isolation
4. Durability
Above Mention properties are commonly known as ACID properties.
1. Atomicity:
✓ This property states that either all of its operations are executed or none.
✓ Execution of a transaction should be start from first-step (fetch) and end with last-step (Commit).
There should be no abortion or failure in-between the execution of any atomicity transaction.
✓ If there is any failure or abortion even at point 99.9 out of 100 then there must be Rollback.
✓ Rollback, eliminate all previous execution and transfer the control from start of execution where it
restart the transaction
Let explain with example
If we want to transfer the money from one account (Account “A”) to other account (Account “B”) then a
transaction will be
Transaction = (Debit account “A”) + (Credit Account “B”)
In the following diagram, we can be seen that
✓ If there is no atomicity then debiting the account “A” with Rs.1000 does not credit the Account “B”.
✓ If there is an atomicity then debiting the account “A” with Rs.1000 will credit the Account “B” with
Rs.1000.
2. Consistency:
The database will be in consistent state if
“Sum of balance, before and after the transaction execution, is same”.
Let explain with example
Suppose SUM1 is balance of two accounts before to transaction and SUM2 is balance after the
transaction.
The condition for consistency is SUM1 Must be equal to SUM2
Balance before transaction
▪ Sum1 = Account A + Account B
Balance after the transaction
▪ Sum2 = Account A + Account B
Now, suppose Account A has 1500 and transfer 1000 to Account B which already contain 3000, let
execute
Balance before transaction
▪ Sum1 = 1500 + 3000 =4500
Balance after the transaction
▪ Sum2 = 500 + 4000 = 4500
Hence it proved that SUM1=SUM2
Note: if account debited and money not received then it should be in consistently. To resolve this, again
Rollback is used
3. Isolation:
The term ‘isolation’ means separation. In Isolation, the data of one transaction should not affect by
other transaction.
Conversion of parallel schedule to serial schedule is called isolation. Serial schedule is always consistent.
Parallel Vs. Serial Schedules
Parallel Schedule: it means performing of more than one transaction at a time
Serial Schedule: it means performing only one transaction at a time. After completion of one
transaction than other should be performed.
Example: In the following diagram, Account “A” is making two transactions T1 and T2 to account B
and C. These both transactions T1 and T2 are executing independently without affecting each other. It
is an isolation example.
IMPORTANT NOTE:
✓ If two operations are running parallel on two different accounts or databases, then the value of both
accounts should not get affected by each other.
✓ If two operations are running parallel on same accounts, then the value of both accounts can get
affected by each other. To resolve this problem make transaction serial.
4. Durability:
Durability ensures the permanency of something.
The database should be durable. It means, when the database is updated after transaction then it
should holds the permanent changes in database. Permanent changes means, these modified
information’s does not change automatically after sometime until unless other transaction has to
perform some actions.
Note: Commit command is use to store or update the data permanently.
Transaction Support in SQL
The COMMIT, ROLLBACK, and SAVEPOINT are collectively considered as Transaction Commands
(1) COMMIT: The COMMIT command is used to save permanently any transaction to database.
When we perform, Read or Write operations to the database then those changes can be undone by rollback
operations. To make these changes permanent, we should make use of commit
(2) ROLLBACK: The ROLLBACK command is used to undo transactions that have not already saved to
database.
For example,
Consider the database table as
Student Table
Following command will delete the record from the database, but if we immediately perform
ROLLBACK, then this deletion is undone.
For instance -
DELETE FROM Student WHERE RollNo = 2;
ROLLBACK;
Then the resultant table will be
(3) SAVEPOINT: A SAVEPOINT is a point in a transaction when you can roll the transaction back to a
certain point without rolling back the entire transaction. The SAVEPOINT can be created as
SAVEPOINT savepoint_name;
Then we can ROLLBACK to SAVEPOIT as
ROLLBACK TO savepoint_name;
For example - Consider Student table as follows –
Student Table
Consider Following commands
SQL> SAVEPOINT S1
SQL>DELETE FROM Student Where RollNo=2;
SQL> SAVEPOINT S2
SQL>DELETE FROM Student Where RollNo=3;
SQL> SAVEPOINT S3
SQL>DELETE FROM Student Where RollNo=4
SQL> SAVEPOINT S4
SQL>DELETE FROM Student Where RollNo=5
SQL> ROLLBACK TO S3;
Then the resultant table will be
Thus, the effect of deleting the record having RollNo 2, and RollNo3 is undone.
Multi-version Concurrency Control
• The DBMS maintains multiple physical versions of single logical object in the database.
• When a transaction writes to an object, the database creates a new version of that object.
• When a transaction reads an object, it reads the newest version that exists when the transaction started
• In this technique, the writers don't block readers or readers don't block writer.
• This scheme makes use of:
i) Locking protocol and
ii) Timestamp protocol.
• The multiversion is now used in almost all database management system as a modern technique of
concurrency control
Validation Based Protocols
Validation-based protocols, also known as Optimistic Concurrency Control (OCC), are a set of techniques that
aim to increase system concurrency and performance by assuming that conflicts between transactions will be rare.
Unlike other concurrency control methods, which try to prevent conflicts proactively using locks or timestamps,
OCC checks for conflicts only at transaction commit time.
Here’s how a typical validation-based protocol operates:
1.Read Phase
1. The transaction reads from the database but does not write to it.
2. All updates are made to a local copy of the data items.
2.Validation Phase
1. Before committing, the system checks to ensure that this transaction's local updates won't cause conflicts
with other transactions.
2. The validation can take many forms, depending on the specific protocol.
3.Write Phase
1. If the transaction passes validation, its updates are applied to the database.
2. If it doesn't pass validation, the transaction is aborted and restarted.
Testing for serializability
Following method is used for testing the serializability: To test the conflict serializability, we can draw
a graph G = (V, E) where V = vertices which represent the number of transactions. E = edges for
conflicting pairs.
Step 1: Create a node for each transaction.
Step 2: Find the conflicting pairs (RW, WR, WW) on the same variable (or data item) by different
transactions.
Step 3: Draw edge for the given schedule. Consider following cases
1. Ti executes write(Q) before Tj executes read(Q), then draw edge from Ti to Tj
2. Ti executes read(Q) before Tj executes write(Q), then draw edge from Ti to Tj
3. Ti executes write(Q) before Tj executes write (Q), then draw edge from Ti to Tj
Step 4: Now, if precedence graph is cyclic then it is a non-conflict serializable schedule and if the
precedence graph is acyclic then it is conflict serializable schedule.
Ex: Consider the following two transactions and schedule (time goes from top to bottom).
Is this schedule conflict-serializable.
Solution:
Step 1: To check whether the schedule is conflict serializable or not we will check from top
to bottom. Thus, we will start reading from top to bottom as
T1: R(A) -> T1: W(A) ->T2: R(A) -> T2: R(B) ->T1: R(B)->T1: W(B)
Step 2: We will find conflicting operations. Two operations are called as conflicting
operations if all the following conditions hold true for them-
i) Both the operations belong to different transactions.
ii) Both the operations are on same data item.
iii) At least one of the two operations is a write operation
From above given example in the top to bottom scanning we find the conflict as
T1: W(A) -> T2: R(A).
i) Here note that there are two different transactions T1 and T2,
ii) Both work on same data item i.e. A and
iii) One of the operation is write operation.
Step 3: We will build a precedence graph by drawing one node from each transaction. In above given scenario as there
are two transactions, there will be two nodes namely T1 and T2
Step 4: Draw the edge between conflicting transactions.
For example, in above given scenario, the conflict occurs while moving from T1:W(A)
to T2:R(A). Hence edge must be from T1 to T2.
Step 5: Repeat the step 4 while reading from top to bottom. Finally, the precedence graph
will be as follows
Precedence graph
Step 6: Check if any cycle exists in the graph. Cycle is a path using which we can start from one node and reach to the same
node. If the is cycle found then schedule is not conflict serializable. In the step 5 we get a graph with cycle, that means given
schedule is not conflict serializable.
Ex: Check whether following schedule is conflict serializable or not. If it is not conflict
serializable then find the serializability order.
Step 1: We will read from top to bottom, and build a precedence graph for
conflicting entries. We will build a precedence graph by drawing one node from
each transaction. In above given scenario as there are three transactions, there will
be two nodes namely T1, T2, and T3
Step 2: The conflicts are found as follows:
Step 3: The precedence graph will be as follows –
Step 4: As there is no cycle in the precedence graph, the given sequence is conflict serializable. Hence, we can
convert this non serial schedule to serial schedule. For that purpose, we will follow these steps to find the
serializable order.
Step 5: A serializability order of the transactions can be obtained by finding a linear order consistent with the
partial order of the precedence graph. This process is called topological sorting.
Step 6: Find the vertex which has no incoming edge which is T1. If we delete T1 node then T3 is a node that has
no incoming edge. If we delete T3, then T2 is a node that has no incoming edge.
Thus, the nodes can be deleted in a order T1, T3 and T2. Hence the order will be T1-T3-T2
Ex: Consider the three transactions T1, T2, and T3 and schedules S1 and S2 given below.
Determine whether each schedule is serializable or not? If a schedule is serializable write
down the equivalent serial schedule(S).
T1: R1(x); R1(z); W1(x);
T2: R2(x); R2(y); W2(z); W2(y)
T3: R3(x); R3(y); W3(y);
S1: R1(x); R2(z); R1(z); R3(x); R3(y); W1(x); W3(y); R2(y); W2(z); W2(y);
S2: R1(x); R2(z); R3(x); R1(z); R2(y); R3(y); W1(x); W2(z); W3(y); W2(y);
Solution:
Step 1: We will represent the schedule S1 as follows
Step (a): We will find conflicting operations. Two operations are
called as conflicting operations if all the following conditions hold
true for them -
i) Both the operations belong to different transactions.
ii) Both the operations are on same data item.
iii) At least one of the two operations is a write operation
The conflicting entries are as follows -
Step (b): Now we will draw precedence graph as follows-
Precedence graph
As there is no cycle in the precedence graph, the given sequence is conflict
serializable. Hence, we can convert this non serial schedule to serial schedule.
For that purpose, we will follow these steps to find the serializable order.
Step (c): A serializability order of the transactions can be obtained by finding a
linear order consistent with the partial order of the precedence graph. This
process is called topological sorting.
Step (d): Find the vertex which has no incoming edge which is T3. If we delete
T3, then T1 is the edge that has no incoming edge. Finally find the vertex
having no outgoing edge which is T2. Hence the order will be T3-T1-T2.
S2: R1(x); R2(z); R3(x); R1(z); R2(y); R3(y); W1(x); W2(z); W3(y); W2(y);
Step 2: We will represent the schedule S2 as follows -
Step (a): We will find conflicting operations. Two operations are called as
conflicting operations if all the following conditions hold true for them -
i) Both the operations belong to different transactions.
ii) Both the operations are on same data item.
iii) At least one of the two operations is a write operation
The conflicting entries are as follows -
Step (b): Now we will draw precedence graph as follows-
Precedence graph
As there is no cycle in the precedence graph, the given sequence is conflict serializable. Hence, we can
convert this non serial schedule to serial schedule. For that purpose, we will follow these steps to find
the serializable order.
Step (c): A serializability order of the transactions can be obtained by finding a linear order consistent
with the partial order of the precedence graph. This process is called topological sorting.
Step (d): Find the vertex which has no incoming edge which is T3. Finally find the vertex having no
outgoing edge which is T2. So in between them is T1. Hence the order will be T3-T1-T2
Ex: Decide whether following schedule is conflict serializable or not.
Solution:
T1 T2
Step 1: We will read from top to bottom, and build a precedence graph Read (A)
for conflicting entries. Write (A)
The conflicting entries are as follows- Read (A)
Write (A)
T1 T2 Read (B)
Read (A) Write (B)
Write (A) Read (B)
Read (A) Write (B)
Write (A)
Read (B)
Write (B)
Read (B)
Write (B)
Step 2: Now we will build precedence graph as follows
T1 T2
Step 3: There is no cycle in the precedence graph. That means this schedule is conflict serializable.
Hence, we can convert this non serial schedule to serial schedule. For that purpose, we will follow the
following steps to find the serializable order.
1) Find the vertex which has no incoming edge which is T1.
2) Then find the vertex having no outgoing edge which is T2. In between them there is no other
transaction.
3) Hence the order will be T1-T2.
❖Recovery Techniques
