Understanding Database Systems: ACID Properties, Transactions, and Serializability

csce 608 database systems n.w
1 / 58
Embed
Share

Explore the essential concepts of database systems, including ACID properties, transaction management, and conflict-serializability. Learn about the key principles governing database operations and the factors that can impact transaction integrity.

  • Database Systems
  • ACID Properties
  • Transactions
  • Serializability
  • Database Management
rayaanacharya
amho532 Follow

Uploaded on | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. CSCE-608 Database Systems Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 38: Conflict serializable schedules

  2. Tranactions Transaction ACID: Atomicity: either all steps of a transaction happen, or none happen Consistency: a transaction transforms a consistent DB into a consistent DB Isolation: execution of a transaction is isolated from that of other transactions Durability: if a transaction commits, its effects persist. T1 Tn What can affect transaction ACID? Accident system failures may destroy Atomicity and Durability, thus Consistency; Concurrent executions of transactions (which is highly desired) may affect Isolation, thus Consistency. Database

  3. lock table DDL DDL language concurrency database file logging & administrator complier control manager recovery transaction manager index/file buffer manager manager query database execution programmer DML (query) DML engine main language complier memory secondary buffers storage DBMS (disks) Graduate Database

  4. Action Swapping swap SC = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) A serial schedule SA= r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) T1 T2 Schedule A Schedule C A B 25 25 A B 25 25 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 125 125 Read(A); A A 2; Write(A); 125 250 Read(A); A A 2; Write(A); Read(B); B B 2; Write(B); 250 125 Read(B); B B 2; Write(B); 250 250 250 250 250 250

  5. Serializability A schedule is serializable if it is equivalent to a serial schedule. Schedule C Schedule A A B 25 25 A B 25 25 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 T1 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); T2 125 125 Read(A); A A 2; Write(A); 125 250 Read(A); A A 2; Write(A); Read(B); B B 2; Write(B); 250 125 Read(B); B B 2; Write(B); 250 250 250 250 250 250 swap SC = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) SA = r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) T2 T1

  6. Conflict-Serializability (A sufficient condition for serializability) Consider: swap? swap? T1: w1(*)r1(*) swap? r1(*)r1(*) swap? Violate T1 s logic! w1(*)w1(*) r1(*)w1(*)

  7. Conflict-Serializability (A sufficient condition for serializability) Consider: swap? swap? T1: w1(*)r1(*) swap? r1(*)r1(*) swap? Violate T1 s logic! w1(*)w1(*) r1(*)w1(*) swap? swap? T1, T2: w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) r1(A)w2(B)

  8. Conflict-Serializability (A sufficient condition for serializability) Consider: swap? swap? T1: w1(*)r1(*) swap? r1(*)r1(*) swap? Violate T1 s logic! w1(*)w1(*) r1(*)w1(*) swap? swap? T1, T2: w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) swap? r1(A)w2(B) swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)

  9. Conflict-Serializability (A sufficient condition for serializability) Consider: swap? swap? T1: w1(*)r1(*) swap? r1(*)r1(*) swap? Violate T1 s logic! w1(*)w1(*) r1(*)w1(*) swap? swap? T1, T2: w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) swap? r1(A)w2(B) swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)

  10. Conflict-Serializability (A sufficient condition for serializability) Consider: swap? swap? T1: w1(*)r1(*) swap? r1(*)r1(*) swap? Violate T1 s logic! w1(*)w1(*) r1(*)w1(*) swap? swap? T1, T2: w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) swap? r1(A)w2(B) swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)

  11. Conflict-Serializability (A sufficient condition for serializability) Consider: swap? swap? T1: w1(*)r1(*) swap? r1(*)r1(*) swap? Violate T1 s logic! w1(*)w1(*) r1(*)w1(*) swap? swap? T1, T2: w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) swap? r1(A)w2(B) swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)

  12. Conflict-Serializability (A sufficient condition for serializability) Consider: swap? swap? T1: w1(*)r1(*) swap? r1(*)r1(*) swap? Violate T1 s logic! w1(*)w1(*) r1(*)w1(*) swap? swap? T1, T2: w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) swap? r1(A)w2(B) swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)

  13. Conflict-Serializability (A sufficient condition for serializability) Consider: swap? swap? T1: w1(*)r1(*) swap? r1(*)r1(*) swap? Violate T1 s logic! w1(*)w1(*) r1(*)w1(*) swap? swap? Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write T1, T2: w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) swap? r1(A)w2(B) swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)

  14. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Conflict-Serializability (A sufficient condition for serializability) Thus: Swapping two non-conflicting actions gives an equivalent schedule.

  15. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Conflict-Serializability (A sufficient condition for serializability) Thus: Swapping two non-conflicting actions gives an equivalent schedule. A schedule S1 is conflict-serializable if it can be converted into a serial schedule by swapping non- conflicting actions.

  16. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Conflict-Serializability (A sufficient condition for serializability) Thus: Swapping two non-conflicting actions gives an equivalent schedule. A schedule S1 is conflict-serializable if it can be converted into a serial schedule by swapping non- conflicting actions. swap SC = r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) SA = r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B) T2 T1

  17. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Conflict-Serializability (A sufficient condition for serializability) Thus: Swapping two non-conflicting actions gives an equivalent schedule. A schedule S1 is conflict-serializable if it can be converted into a serial schedule by swapping non- conflicting actions. A conflict-serializable schedule is serializable.

  18. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Conflict-Serializability (A sufficient condition for serializability) Thus: Swapping two non-conflicting actions gives an equivalent schedule. A schedule S1 is conflict-serializable if it can be converted into a serial schedule by swapping non- conflicting actions. A conflict-serializable schedule is serializable. A serializable schedule may not be conflict-serializable.

  19. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Conflict-Serializability (A sufficient condition for serializability) Thus: Swapping two non-conflicting actions gives an equivalent schedule. A schedule S1 is conflict-serializable if it can be converted into a serial schedule by swapping non- conflicting actions. A conflict-serializable schedule is serializable. A serializable schedule may not be conflict-serializable. S1 = w1(A)w2(A)w3(A)w2(B)w1(B)w3(B) S2 = w1(A)w1(B)w2(A)w2(B)w3(A)w3(B)

  20. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Conflict-Serializability (A sufficient condition for serializability) Thus: Swapping two non-conflicting actions gives an equivalent schedule. A schedule S1 is conflict-serializable if it can be converted into a serial schedule by swapping non- conflicting actions. A conflict-serializable schedule is serializable. A serializable schedule may not be conflict-serializable. How do we know if a schedule is conflict-serializable?

  21. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle.

  22. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B)

  23. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B) 1 2 3

  24. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B) 1 2 3

  25. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B) 1 2 3

  26. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B) 1 2 3

  27. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B) 1 2 3 S2: r2(A)r1(B)w2(A)r2(B)r3(A)w1(B)w3(A)w2(B)

  28. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B) 1 2 3 S2: r2(A)r1(B)w2(A)r2(B)r3(A)w1(B)w3(A)w2(B) 1 2 3

  29. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability conflict- serializable Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B) 1 2 3 S2: r2(A)r1(B)w2(A)r2(B)r3(A)w1(B)w3(A)w2(B) 1 2 3 Not conflict- serializable

  30. Two actions conflict if either they are by the same transaction, or they are by two transactions on the same element and at least one of the actions is write Testing Conflict-Serializability conflict- serializable Algorithm TestCS. Input: a schedule S 1. Build a directed graph GS; 2. Each transaction is a node in GS; 3. If two actions a1 and a2 conflict, where a1 and a2 are by T1 and T2, resp., and a1 is before a2 in S, then add an edge from T1 to T2 in GS; 4. S is conflict-serializable if and only if GS contains no cycle. S1: r2(A)r1(B)w2(A)r3(A)w1(B)w3(A)r2(B)w2(B) 1 2 3 S2: r2(A)r1(B)w2(A)r2(B)r3(A)w1(B)w3(A)w2(B) 1 2 3 Not conflict- serializable Why does the algorithm work? Claim: If GS is acyclic, then S is equivalent to any serial schedule obtained by topologically sorting GS. Proof. Let T1T2 Tk be a topological order of GS. Since there is no edge into T1, for each action a in T1, there is no action from other transactions that conflict a and appears in S before a. Therefore, the actions of T1 can be all swapped with non-conflict actions and move to the front of the schedule, resulting in an equivalent schedule. Now by induction we can also convert the rest of the schedule into an equivalent serial schedule.

  31. Enforcing Conflict-Serializability Using locking protocol T1 T2 Tn lock table scheduler

  32. Enforcing Conflict-Serializability Using locking protocol T1 T2 Tn lock table scheduler Two new actions: lock: (transaction Ti exclusively locks the element A) unlock: (transaction Ti releases the lock on the element A) li(A) ui(A)

  33. Enforcing Conflict-Serializability Using locking protocol T1 T2 Tn lock table scheduler Two new actions: lock: (transaction Ti exclusively locks the element A) unlock: (transaction Ti releases the lock on the element A) li(A) ui(A) A transaction can lock an unlocked element, and must release (unlock) it later. A transaction cannot access a locked element until it is released by the transaction holding the lock.

  34. A transaction can lock an unlocked element, and must release (unlock) it later. A transaction cannot access a locked element until it is released by the transaction holding the lock. Locking is not enough for conflict-serializability Schedule D A B 25 25 T1 T2 Read(A); A A+100 Write(A); Read(B); B B+100; Write(B); Read(A); A A 2; Write(A); Read(B); B B 2; Write(B); 125 250 50 150 250 150

  35. A transaction can lock an unlocked element, and must release (unlock) it later. A transaction cannot access a locked element until it is released by the transaction holding the lock. Locking is not enough for conflict-serializability Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; Write(B); u1(B); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); 125 250 50 150 250 150

  36. A transaction can lock an unlocked element, and must release (unlock) it later. A transaction cannot access a locked element until it is released by the transaction holding the lock. Locking is not enough for conflict-serializability Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; Write(B); u1(B); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); 125 Inconsistent, so isolation was destroyed 250 50 150 250 150

  37. Two phase locking (2PL) (for transactions) Ti: ... li(A) li(B) ui(B) ui(A) ... no unlocks no locks In a transaction, all lockings precede all unlockings

  38. Two phase locking (2PL) (for transactions) Ti: ... li(A) li(B) ui(B) ui(A) ... no unlocks no locks # of locks held by Ti time growing phase shrinking phase In a transaction, all lockings precede all unlockings

  39. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); 125 250 50 l1(B); Read(B); B B+100; Write(B); u1(B); 150 250 150

  40. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); 125 250 50 l1(B); Read(B); B B+100; Write(B); u1(B); 150 250 150 not conflict-serializable even with locks

  41. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); l1(B); Read(B); B B+100; Write(B); u1(B); Try to apply 2PL On the transactions

  42. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); l1(B); Read(B); B B+100; Write(B); u1(B); Try to apply 2PL On the transactions

  43. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); Try to apply 2PL On the transactions

  44. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); Try to apply 2PL On the transactions

  45. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 125 l1(B); Read(B); B B+100; u1(A); Write(B); u1(B);

  46. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); blocked, so delayed 125 l1(B); Read(B); B B+100; u1(A); Write(B); u1(B);

  47. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); blocked, so delayed 125 Write(B); u1(B);

  48. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); blocked, so delayed 125 Write(B); u1(B);

  49. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); 125 l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); Write(B); u1(B);

  50. 2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); 125 l2(A); Read(A); A A 2; Write(A); u2(A); l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 Write(B); u1(B);

Related


Discussion on Supporting 30kHz SCS for Bands n34, n38, n39, and n50 in 3GPP TSG-RAN4 Meeting #95e

Discussion on Supporting 30kHz SCS for Bands n34, n38, n39, and n50 in 3GPP TSG-RAN4 Meeting #95e

yi_794

More Related Content