My Slide- Transaction Management
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View My Slide- Transaction Management as PDF for free.
More details
- Words: 2,134
- Pages: 51
Database Systems Transaction Management Version 1.0
Rushdi Shams, Dept of CSE, KUET
1
Transaction Action,
or series of actions, carried out by user or application, which reads or updates contents of database.
Transforms database from one consistent state to another, although consistency may be violated during transaction.
Rushdi Shams, Dept of CSE, KUET
2
Outcomes of Transaction
Can have one of two outcomes:
Success - transaction commits and database reaches a new consistent state. Failure - transaction aborts, and database must be restored to consistent state before it started. Such a transaction is rolled back or undone.
Committed transaction cannot be aborted. Aborted transaction that is rolled back can be restarted later. Rushdi Shams, Dept of CSE, KUET
3
State Transition Diagram of Transaction
Rushdi Shams, Dept of CSE, KUET
4
Properties of Transaction Management
2. 3. 4. 5.
There are 4 basic properties in transaction managementAtomicity Consistency Isolation and Durability Their acronym is ACID! Rushdi Shams, Dept of CSE, KUET
5
ACID
Atomicity It is the ability of the DBMS that ensures either all of the transactions take place or none of them take place! Kind of weird, huh? Well, let me give an example. If a bank account is debited, another bank account must be credited- that is called atomicity! Rushdi Shams, Dept of CSE, KUET
6
ACID
Consistency Every database has some rules according to the organization to which it belongs. This property ensures that the databases are in legal state after a transaction takes place. For example, if a bank says that its client’s account balance can never be negative, then no such transaction will take place that Rushdi Shams, Dept of CSE, KUET
7
ACID
Isolation This property ensures that no other operation can intervene the transaction operation. For example, a bank manager, during a transaction should be able to see balance of one account, not on both. This is the most relaxed option in ACID properties. Rushdi Shams, Dept of CSE, KUET
8
ACID
Durability This property ensures that once a transaction takes place, it cannot be undone. when an account to account transfer takes place, after completion, it should notify the user that transaction successfully done and you cannot rewind that! Rushdi Shams, Dept of CSE, KUET
9
Concurrency Control
Process of managing simultaneous operations on the database without having them interfere with one another.
Prevents interference when two or more users are accessing database simultaneously and at least one is updating data. Although two transactions may be correct in themselves, interleaving of operations may
Rushdi Shams, Dept of CSE, KUET
10
Why Concurrency Control
Three examples of potential problems caused by concurrency:
Lost update problem. Uncommitted dependency problem. Inconsistent analysis problem.
Rushdi Shams, Dept of CSE, KUET
11
Lost Update Problem
Successfully completed update is overridden by another user. T1 withdrawing £10 from an account with balx, initially £100. T2 depositing £100 into same account. Serially, final balance would be £190. Rushdi Shams, Dept of CSE, KUET
12
Lost Update Problem (continued)
Rushdi Shams, Dept of CSE, KUET
13
Uncommitted Dependency Problem
Occurs when one transaction can see intermediate results of another transaction before it has committed. T4 updates balx to £200 but it aborts, so balx should be back at original value of £100. T3 has read new value of balx (£200) and uses value as basis of £10 reduction, giving a new Rushdi Shams, Dept of CSE, KUET
14
Uncommitted Dependency Problem (continued)
Rushdi Shams, Dept of CSE, KUET
15
Inconsistent Analysis Problem
Occurs when transaction reads several values but second transaction updates some of them during execution of first. Sometimes referred to as dirty read or unrepeatable read. T6 is totaling balances of account x (£100), account y (£50), and account z (£25). Meantime, T5 has transferred £10 Dept of CSE, from balx to Rushdi balShams, T6KUET now has wrong16 z, so
Inconsistent Analysis Problem (continued)
Rushdi Shams, Dept of CSE, KUET
17
Serialzability
Objective of a concurrency control protocol is to schedule transactions in such a way as to avoid any interference. Could run transactions serially, but this limits degree of concurrency or parallelism in system. Serializability identifies those executions of transactions guaranteed to ensure Rushdi Shams, Dept of CSE, KUET
18
Schedule
3. 4.
Sequence of reads/writes by set of concurrent transactions. There are 2 types of schedulingSerial scheduling Non serial scheduling
Rushdi Shams, Dept of CSE, KUET
19
Serial Scheduling
Schedule where operations of each transaction are executed consecutively without any interleaved operations from other transactions.
Rushdi Shams, Dept of CSE, KUET
20
Non Serial Scheduling
Schedule where operations from set of concurrent transactions are interleaved.
Rushdi Shams, Dept of CSE, KUET
21
Objectives of Serializability
Objective of serializability is to find nonserial schedules that allow transactions to execute concurrently without interfering with one another.
In other words, want to find nonserial schedules that are equivalent to some serial schedule. Such a schedule is called serializable. Rushdi Shams, Dept of CSE, KUET
22
Order of Read/ Write
2.
3.
4.
In serializability, ordering of read/writes is important: If two transactions only read a data item, they do not conflict and order is not important. If two transactions either read or write completely separate data items, they do not conflict and order is not important. If one transaction writes a data item and another reads or writes same data item, order of execution is Rushdi Shams, Dept of CSE, KUET 23 important.
Conflict in Serializability
Rushdi Shams, Dept of CSE, KUET
24
Precedence Graph
Used to test for serializability Create node for each transaction; a directed edge T → T , if T reads i j j the value of an item written by Ti; a directed edge T → T , if T writes a i j j value into an item after it has been read by Ti.
If precedence graph contains cycle you are in trouble!! Rushdi Shams, Dept of CSE, KUET
25
Precedence Graph Example
T9 is transferring £100 from one account with balance balx to another account with balance baly.
T10 is increasing balance of these two accounts by 10%. Precedence graph has a cycle and so is not serializable.
Rushdi Shams, Dept of CSE, KUET
26
Precedence Graph Example (continued)
Rushdi Shams, Dept of CSE, KUET
27
Recoverability
Serializability identifies schedules that maintain database consistency, assuming no transaction fails.
Could also recoverability of within schedule.
examine transactions
Rushdi Shams, Dept of CSE, KUET
28
Recoverable Schedule
A schedule is recoverable if, for each pair of transactions Ti and Tj, if Tj reads a data item previously written by Ti, then the commit operation of Ti precedes the commit operation of Tj.
Rushdi Shams, Dept of CSE, KUET
29
Concurrency Control Techniques 1.
Optimistic method: Based on assumption that conflict does not happen very often. So we better let the transaction run to its completion and then check at commit time to see if there is a conflict. If there is, the offending transaction simply starts again from the beginning. Rushdi Shams, Dept of CSE, KUET
30
Concurrency Control Techniques (continued) 1.
Timestamping: For any given database request, the system compares the timestamping of the requesting transaction with the timestamp of the transaction that last retrieved or updated the requested record. If there is a conflict, the requesting transaction can simply be restarted (with new timestamping). Rushdi Shams, Dept of CSE, KUET
31
Concurrency Control Techniques (continued) 1. Locking: When a transaction needs an assurance that transaction will not be affected by others, it requires a lock on that object. Then the first transaction is able to carry out its processing without fear of others’ interference. Rushdi Shams, Dept of CSE, KUET
32
Locks Exclusive Lock (XLock): If anybody is having exclusive lock, the other users will go into wait list until the exclusive lock holder releases it. Shared Lock (SLock): If anybody has shared lock, the other users with request shared lock can also have access to it.
Rushdi Shams, Dept of CSE, KUET
33
Locks (continued) If A has XLock, then if B wants XLock, B has to wait then if B wants SLock, B has to wait then if B wants NoLock, B can see it If A has SLock, then if B wants XLock, B has to wait then if B wants SLock, B gets permission then if B wants NoLock, B can see it If A has NoLock, then if B wants XLock, B will be granted then if B wants SLock, B will be granted then if B wants NoLock, B will be granted Xlock= Exclusive Lock SLock= Shared Lock Rushdi Shams, Dept of CSE, KUET
34
Locks: Basic Rules
If transaction has shared lock on item, can read but not update item. If transaction has exclusive lock on item, can both read and update item. Reads cannot conflict, so more than one transaction can hold shared locks simultaneously on same item. Rushdi Shams, Dept of CSE, KUET
35
Need of a Protocol
Problem is that transactions release locks too soon, resulting in loss of total isolation and atomicity. To guarantee serializability, need an additional protocol concerning the positioning of lock and unlock operations in every transaction. Rushdi Shams, Dept of CSE, KUET
36
2 Phase Locking (2PL)
Transaction follows 2PL protocol if all locking operations precede first unlock operation in the transaction.
Two phases for transaction: Growing phase - acquires all locks but cannot release any locks. Shrinking phase - releases locks but cannot acquire any new locks.
Rushdi Shams, Dept of CSE, KUET
37
Preventing Lost Update Problem using 2PL
Rushdi Shams, Dept of CSE, KUET
38
Preventing Uncommitted Dependency Problem using 2PL
Rushdi Shams, Dept of CSE, KUET
39
Preventing Inconsistent Analysis Problem using 2PL
Rushdi Shams, Dept of CSE, KUET
40
Cascading Rollback
Rushdi Shams, Dept of CSE, KUET
41
Cascading Rollback (continued)
Transactions conform to 2PL. T14 aborts. Since T15 is dependent on T14, T15 must also be rolled back. Since T16 is dependent on T15, it too must be rolled back. This is called cascading rollback. To prevent this with 2PL, leave release of all locks until end of Rushdi Shams, Dept of CSE, KUET
42
Dead Lock
An impasse that may result when two (or more) transactions are each waiting for locks held by the other to be released. Deadlock is a situation in which two or more transactions are in a simultaneous wait state; each one waiting for one of the other to release a lock before it can proceed. Rushdi Shams, Dept of CSE, KUET
43
Dead Lock (continued)
Rushdi Shams, Dept of CSE, KUET
44
Dead Lock (continued)
Deadlock should be transparent to user, so DBMS should restart transaction(s). Three general techniques for handling deadlock:
Timeouts. Deadlock prevention. Deadlock detection and recovery. Rushdi Shams, Dept of CSE, KUET
45
Timeouts
Transaction that requests lock will only wait for a system-defined period of time.
If lock has not been granted within this period, lock request times out.
In this case, DBMS assumes transaction may be deadlocked, even though it may not be, and it aborts and automatically restarts the46 Rushdi Shams, Dept of CSE, KUET
Deadlock Prevention
DBMS looks ahead to see if transaction would cause deadlock and never allows deadlock to occur. Wait-Die only an older transaction can wait for younger one, otherwise If younger transaction requests lock held by older one, younger one is aborted (dies47) Rushdi Shams, Dept of CSE, KUET
Dead Lock Prevention (continued)
Wound-Wait - only a younger transaction can wait for an older one. If older transaction requests lock held by younger one, younger one is aborted (wounded).
Rushdi Shams, Dept of CSE, KUET
48
Dead Lock Detection & Recovery
DBMS allows deadlock to occur but recognizes it and breaks it. Usually handled by construction of wait-for graph (WFG) showing transaction dependencies: Create a node for each transaction. Create edge T -> T , if T waiting to i j i lock item locked by Tj. Deadlock exists if and only if WFG contains cycle. Rushdi Shams, Dept of CSE, KUET
49
Wait For Graph (WFG)
Rushdi Shams, Dept of CSE, KUET
50
References
Database Management Systems by R. Ramakrishnan John Hall, Senior Lecturer, University of Bolton, UK
Rushdi Shams, Dept of CSE, KUET
51
Rushdi Shams, Dept of CSE, KUET
1
Transaction Action,
or series of actions, carried out by user or application, which reads or updates contents of database.
Transforms database from one consistent state to another, although consistency may be violated during transaction.
Rushdi Shams, Dept of CSE, KUET
2
Outcomes of Transaction
Can have one of two outcomes:
Success - transaction commits and database reaches a new consistent state. Failure - transaction aborts, and database must be restored to consistent state before it started. Such a transaction is rolled back or undone.
Committed transaction cannot be aborted. Aborted transaction that is rolled back can be restarted later. Rushdi Shams, Dept of CSE, KUET
3
State Transition Diagram of Transaction
Rushdi Shams, Dept of CSE, KUET
4
Properties of Transaction Management
2. 3. 4. 5.
There are 4 basic properties in transaction managementAtomicity Consistency Isolation and Durability Their acronym is ACID! Rushdi Shams, Dept of CSE, KUET
5
ACID
Atomicity It is the ability of the DBMS that ensures either all of the transactions take place or none of them take place! Kind of weird, huh? Well, let me give an example. If a bank account is debited, another bank account must be credited- that is called atomicity! Rushdi Shams, Dept of CSE, KUET
6
ACID
Consistency Every database has some rules according to the organization to which it belongs. This property ensures that the databases are in legal state after a transaction takes place. For example, if a bank says that its client’s account balance can never be negative, then no such transaction will take place that Rushdi Shams, Dept of CSE, KUET
7
ACID
Isolation This property ensures that no other operation can intervene the transaction operation. For example, a bank manager, during a transaction should be able to see balance of one account, not on both. This is the most relaxed option in ACID properties. Rushdi Shams, Dept of CSE, KUET
8
ACID
Durability This property ensures that once a transaction takes place, it cannot be undone. when an account to account transfer takes place, after completion, it should notify the user that transaction successfully done and you cannot rewind that! Rushdi Shams, Dept of CSE, KUET
9
Concurrency Control
Process of managing simultaneous operations on the database without having them interfere with one another.
Prevents interference when two or more users are accessing database simultaneously and at least one is updating data. Although two transactions may be correct in themselves, interleaving of operations may
Rushdi Shams, Dept of CSE, KUET
10
Why Concurrency Control
Three examples of potential problems caused by concurrency:
Lost update problem. Uncommitted dependency problem. Inconsistent analysis problem.
Rushdi Shams, Dept of CSE, KUET
11
Lost Update Problem
Successfully completed update is overridden by another user. T1 withdrawing £10 from an account with balx, initially £100. T2 depositing £100 into same account. Serially, final balance would be £190. Rushdi Shams, Dept of CSE, KUET
12
Lost Update Problem (continued)
Rushdi Shams, Dept of CSE, KUET
13
Uncommitted Dependency Problem
Occurs when one transaction can see intermediate results of another transaction before it has committed. T4 updates balx to £200 but it aborts, so balx should be back at original value of £100. T3 has read new value of balx (£200) and uses value as basis of £10 reduction, giving a new Rushdi Shams, Dept of CSE, KUET
14
Uncommitted Dependency Problem (continued)
Rushdi Shams, Dept of CSE, KUET
15
Inconsistent Analysis Problem
Occurs when transaction reads several values but second transaction updates some of them during execution of first. Sometimes referred to as dirty read or unrepeatable read. T6 is totaling balances of account x (£100), account y (£50), and account z (£25). Meantime, T5 has transferred £10 Dept of CSE, from balx to Rushdi balShams, T6KUET now has wrong16 z, so
Inconsistent Analysis Problem (continued)
Rushdi Shams, Dept of CSE, KUET
17
Serialzability
Objective of a concurrency control protocol is to schedule transactions in such a way as to avoid any interference. Could run transactions serially, but this limits degree of concurrency or parallelism in system. Serializability identifies those executions of transactions guaranteed to ensure Rushdi Shams, Dept of CSE, KUET
18
Schedule
3. 4.
Sequence of reads/writes by set of concurrent transactions. There are 2 types of schedulingSerial scheduling Non serial scheduling
Rushdi Shams, Dept of CSE, KUET
19
Serial Scheduling
Schedule where operations of each transaction are executed consecutively without any interleaved operations from other transactions.
Rushdi Shams, Dept of CSE, KUET
20
Non Serial Scheduling
Schedule where operations from set of concurrent transactions are interleaved.
Rushdi Shams, Dept of CSE, KUET
21
Objectives of Serializability
Objective of serializability is to find nonserial schedules that allow transactions to execute concurrently without interfering with one another.
In other words, want to find nonserial schedules that are equivalent to some serial schedule. Such a schedule is called serializable. Rushdi Shams, Dept of CSE, KUET
22
Order of Read/ Write
2.
3.
4.
In serializability, ordering of read/writes is important: If two transactions only read a data item, they do not conflict and order is not important. If two transactions either read or write completely separate data items, they do not conflict and order is not important. If one transaction writes a data item and another reads or writes same data item, order of execution is Rushdi Shams, Dept of CSE, KUET 23 important.
Conflict in Serializability
Rushdi Shams, Dept of CSE, KUET
24
Precedence Graph
Used to test for serializability Create node for each transaction; a directed edge T → T , if T reads i j j the value of an item written by Ti; a directed edge T → T , if T writes a i j j value into an item after it has been read by Ti.
If precedence graph contains cycle you are in trouble!! Rushdi Shams, Dept of CSE, KUET
25
Precedence Graph Example
T9 is transferring £100 from one account with balance balx to another account with balance baly.
T10 is increasing balance of these two accounts by 10%. Precedence graph has a cycle and so is not serializable.
Rushdi Shams, Dept of CSE, KUET
26
Precedence Graph Example (continued)
Rushdi Shams, Dept of CSE, KUET
27
Recoverability
Serializability identifies schedules that maintain database consistency, assuming no transaction fails.
Could also recoverability of within schedule.
examine transactions
Rushdi Shams, Dept of CSE, KUET
28
Recoverable Schedule
A schedule is recoverable if, for each pair of transactions Ti and Tj, if Tj reads a data item previously written by Ti, then the commit operation of Ti precedes the commit operation of Tj.
Rushdi Shams, Dept of CSE, KUET
29
Concurrency Control Techniques 1.
Optimistic method: Based on assumption that conflict does not happen very often. So we better let the transaction run to its completion and then check at commit time to see if there is a conflict. If there is, the offending transaction simply starts again from the beginning. Rushdi Shams, Dept of CSE, KUET
30
Concurrency Control Techniques (continued) 1.
Timestamping: For any given database request, the system compares the timestamping of the requesting transaction with the timestamp of the transaction that last retrieved or updated the requested record. If there is a conflict, the requesting transaction can simply be restarted (with new timestamping). Rushdi Shams, Dept of CSE, KUET
31
Concurrency Control Techniques (continued) 1. Locking: When a transaction needs an assurance that transaction will not be affected by others, it requires a lock on that object. Then the first transaction is able to carry out its processing without fear of others’ interference. Rushdi Shams, Dept of CSE, KUET
32
Locks Exclusive Lock (XLock): If anybody is having exclusive lock, the other users will go into wait list until the exclusive lock holder releases it. Shared Lock (SLock): If anybody has shared lock, the other users with request shared lock can also have access to it.
Rushdi Shams, Dept of CSE, KUET
33
Locks (continued) If A has XLock, then if B wants XLock, B has to wait then if B wants SLock, B has to wait then if B wants NoLock, B can see it If A has SLock, then if B wants XLock, B has to wait then if B wants SLock, B gets permission then if B wants NoLock, B can see it If A has NoLock, then if B wants XLock, B will be granted then if B wants SLock, B will be granted then if B wants NoLock, B will be granted Xlock= Exclusive Lock SLock= Shared Lock Rushdi Shams, Dept of CSE, KUET
34
Locks: Basic Rules
If transaction has shared lock on item, can read but not update item. If transaction has exclusive lock on item, can both read and update item. Reads cannot conflict, so more than one transaction can hold shared locks simultaneously on same item. Rushdi Shams, Dept of CSE, KUET
35
Need of a Protocol
Problem is that transactions release locks too soon, resulting in loss of total isolation and atomicity. To guarantee serializability, need an additional protocol concerning the positioning of lock and unlock operations in every transaction. Rushdi Shams, Dept of CSE, KUET
36
2 Phase Locking (2PL)
Transaction follows 2PL protocol if all locking operations precede first unlock operation in the transaction.
Two phases for transaction: Growing phase - acquires all locks but cannot release any locks. Shrinking phase - releases locks but cannot acquire any new locks.
Rushdi Shams, Dept of CSE, KUET
37
Preventing Lost Update Problem using 2PL
Rushdi Shams, Dept of CSE, KUET
38
Preventing Uncommitted Dependency Problem using 2PL
Rushdi Shams, Dept of CSE, KUET
39
Preventing Inconsistent Analysis Problem using 2PL
Rushdi Shams, Dept of CSE, KUET
40
Cascading Rollback
Rushdi Shams, Dept of CSE, KUET
41
Cascading Rollback (continued)
Transactions conform to 2PL. T14 aborts. Since T15 is dependent on T14, T15 must also be rolled back. Since T16 is dependent on T15, it too must be rolled back. This is called cascading rollback. To prevent this with 2PL, leave release of all locks until end of Rushdi Shams, Dept of CSE, KUET
42
Dead Lock
An impasse that may result when two (or more) transactions are each waiting for locks held by the other to be released. Deadlock is a situation in which two or more transactions are in a simultaneous wait state; each one waiting for one of the other to release a lock before it can proceed. Rushdi Shams, Dept of CSE, KUET
43
Dead Lock (continued)
Rushdi Shams, Dept of CSE, KUET
44
Dead Lock (continued)
Deadlock should be transparent to user, so DBMS should restart transaction(s). Three general techniques for handling deadlock:
Timeouts. Deadlock prevention. Deadlock detection and recovery. Rushdi Shams, Dept of CSE, KUET
45
Timeouts
Transaction that requests lock will only wait for a system-defined period of time.
If lock has not been granted within this period, lock request times out.
In this case, DBMS assumes transaction may be deadlocked, even though it may not be, and it aborts and automatically restarts the46 Rushdi Shams, Dept of CSE, KUET
Deadlock Prevention
DBMS looks ahead to see if transaction would cause deadlock and never allows deadlock to occur. Wait-Die only an older transaction can wait for younger one, otherwise If younger transaction requests lock held by older one, younger one is aborted (dies47) Rushdi Shams, Dept of CSE, KUET
Dead Lock Prevention (continued)
Wound-Wait - only a younger transaction can wait for an older one. If older transaction requests lock held by younger one, younger one is aborted (wounded).
Rushdi Shams, Dept of CSE, KUET
48
Dead Lock Detection & Recovery
DBMS allows deadlock to occur but recognizes it and breaks it. Usually handled by construction of wait-for graph (WFG) showing transaction dependencies: Create a node for each transaction. Create edge T -> T , if T waiting to i j i lock item locked by Tj. Deadlock exists if and only if WFG contains cycle. Rushdi Shams, Dept of CSE, KUET
49
Wait For Graph (WFG)
Rushdi Shams, Dept of CSE, KUET
50
References
Database Management Systems by R. Ramakrishnan John Hall, Senior Lecturer, University of Bolton, UK
Rushdi Shams, Dept of CSE, KUET
51
Related Documents
My Slide- Transaction Management
November 2019 5
Transaction Management Overview
November 2019 11
Transaction
November 2019 21
Motivation My Slide
June 2020 1
