Transactions and Schedules, Part II

Data Science 310

Boston University

From the last lecture…

• We can represent a schedule using a table.
  • one column for each transaction
  • operations are performed in the order given by reading from top to bottom

• We can also write a schedule on a single line using this notation:
  • r_i(A) = transaction T_i reads A   w_i(A) = transaction T_i writes A
  • example for the table above: r₁(A);  r₂(B);  w₁(A);  r₂(A);  w₂(A)

Recall: Actions That Conflict

• Actions in different transactions conflict if:
  1. they involve the same data item
  2. and at least one of them is a write
• Pairs of actions that do conflict (assume i != j):
  • w_i(A); r_j(A) — the value read by T_j may change if we swap them
  • r_i(A); w_j(A) — the value read by T_i may change if we swap them
  • w_i(A); w_j(A) — subsequent reads may change if we swap them
  • two actions from the same txn (their order is fixed by the client)
• Pairs of actions that don’t conflict:
  • r_i(A); r_j(A) — two reads of the same item by different txns
  • r_i(A); r_j(B),  r_i(A); w_j(B),  w_i(A); r_j(B),  w_i(A); w_j(B) — operations on two different items by different txns

Recall: Using a Precedence Graph

• Tests for conflict serializability can use a precedence graph.
  • the vertices/nodes are the transactions
  • add an edge for each precedence constraint: T1 → T2 means T1 must come before T2 in an equivalent serial schedule

Example:  r₂(A); r₃(A); r₁(B); w₄(A); w₂(B); r₃(B)

r₂(A) … w₄(A)  means T2 → T4

r₃(A) … w₄(A)  means T3 → T4

r₁(B) … w₂(B)  means T1 → T2

w₂(B) … r₃(B)  means T2 → T3

• After the graph is constructed, we test for cycles (i.e., paths of the form A → … → A).

• if the graph is acyclic, the schedule is conflict serializable
  • use the constraints to determine an equivalent serial schedule (in this case: T1;T2;T3;T4)

• if there’s a cycle, the schedule is not conflict serializable

More Examples

• Determine if the following are conflict serializable:
  • r₁(A); r₃(A); r₁(B); w₂(A); r₄(A); w₂(B); w₃(C); w₄(C); r₁(C)

r₁(A) … w₂(A)  means T1 → T2

r₃(A) … w₂(A)  means T3 → T2

r₁(B) … w₂(B)  means T1 → T2

w₂(A) … r₄(A)  means T2 → T4

w₃(C) … w₄(C)  means T3 → T4

w₃(C) … r₁(C)  means T3 → T1

w₄(C) … r₁(C)  means T4 → T1

More Examples

• Determine if the following are conflict serializable:
  • r₁(A); w₃(A); w₄(A); w₂(B); r₂(B); r₁(B); r₄(B)

r₁(A) … w₃(A)  means T1 → T3

r₁(A) … w₄(A)  means T1 → T4

w₃(A) … w₄(A)  means T3 → T4

w₂(B) … r₁(B)  means T2 → T1

w₂(B) … r₄(B)  means T2 → T4

equivalent serial ordering?

→ equivalent to T2; T1; T3; T4

Is This Schedule Conflict Serializable?

• Draw the precedence graph to find out!
  • w₁(A); r₂(B); r₂(A); r₄(A); w₂(B); r₄(B); w₄(C); r₃(D); w₃(C)

w₁(A) … r₂(A)  means T1 → T2

w₁(A) … r₄(A)  means T1 → T4

w₂(B) … r₄(B)  means T2 → T4

w₄(C) … w₃(C)  means T4 → T3

A.  Yes. It is equivalent to the serial schedule T1;T2;T3;T4

B.  Yes. It is equivalent to the serial schedule T1;T2;T4;T3

C.  No. The graph includes the cycle T1 → T4 → T2 → T1

D.  No. The graph includes the cycle T1 → T2 → T4 → T1

What If We Add This Write?

• Draw the precedence graph to find out!
  • w₁(A); r₂(B); r₂(A); r₄(A); w₂(B); r₄(B); w₄(C); r₃(D); w₃(C); w₁(D)

w₁(A) … r₂(A)  means T1 → T2

w₁(A) … r₄(A)  means T1 → T4

w₂(B) … r₄(B)  means T2 → T4

w₄(C) … w₃(C)  means T4 → T3

r₃(D) … w₁(D)  means T3 → T1

Conflict Serializability vs. Serializability

• Conflict serializability is a sufficient condition for serializability, but it’s not a necessary condition.
  • all conflict serializable schedules are serializable
  • not all serializable schedules are conflict serializable

• Consider the following schedule involving three txns:

• It is not conflict serializable, because:
  • r₂(A) … w₁(A)  means T₂ → T₁

• w₁(A) … w₂(A)  means T₁ → T₂

• It is serializable because its effects are equivalent to either T₁; T₂; T₃  or  T₂; T₁; T₃  — why?

• only A is changed; T₃ writes its final value in all 3 schedules.

• T₃ doesn’t read A.

• → it doesn’t matter what order T₁ and T₂ read/write A

Executing a Transaction

• Issue a command indicating the start of the transaction.
  • in SQL: BEGIN WORK or START TRANSACTION

• Perform the operations in the transaction.
  • in SQL: a set of SQL commands (SELECT, UPDATE, etc.)

• End the transaction in one of two ways:
  • commit it: make all of its results visible and persistent
    • all of the changes happen
    • in SQL: COMMIT WORK or COMMIT

• abort it: undo all of its changes, returning the system to its state before the transaction began
  • none of the changes happen
  • in SQL: ROLLBACK WORK or ROLLBACK

Recoverability

• While serializability is important, it isn’t enough for full isolation.

• Consider the serializable schedule at right.

  • includes “c” actions that indicate when the transactions commit

• Imagine that the system crashes:
  • after T1’s commit
  • before T2’s commit

• During recovery from the crash, the system:
  • keeps all of T1’s changes, because it committed before the crash

• undoes all of T2’s changes, because it didn’t commit before the crash

Recoverability (cont.)

• This is problematic!

• T1 reads T2’s write of B
• it then performs actions that may be based on the new value of B

• during recovery from the crash, T2 is rolled back → B’s old value is restored

• it’s possible T1 would have behaved differently if it had read B’s old value

• it’s too late to roll back T1, because it has already committed!

• We say that this schedule is unrecoverable.
  • if a crash occurs between the two commits, the process of recovering from the crash could lead to problematic results

Recoverability (cont.)

• In a recoverable schedule, if T1 reads a value written by T2, T1 must commit after T2 commits.

• This allows us to safely recover from a crash at any point:

Dirty Reads and Cascading Rollbacks

• Dirty data is data written by an uncommitted txn.

• it remains dirty until the txn is either:
  • committed: in which case the data is no longer dirty and it is safe for other txns to read it

• rolled back: in which case the write of the dirty data is undone

• A dirty read is a read of dirty data.

• Dirty reads can lead to cascading rollbacks.
  • if the writer of the dirty data is rolled back, the reader must be, too

Dirty Reads and Cascading Rollbacks (cont.)

• We made our earlier schedule recoverable by switching the order of the commits:

• Could the revised schedule lead to a cascading rollback?

• yes! T1 performs a dirty read of T2’s write of B.

• if T2 is later rolled back, T1 must be, too.

• To get a cascadeless schedule, don’t allow dirty reads.

Extra Practice

• What scenarios involving the schedule at right could produce cascading rollbacks?

A.  T1 is rolled back sometime after T3 reads A.  yes

B.  T2 is rolled back sometime after T1 reads B.  yes

C.  T3 is rolled back sometime after T2 reads C.  yes

D.  two of the above

E.  all three of the above (A, B and C)

Concurrency Control Goals

• Goals: ensure that schedules of concurrent txns are:
  • serializable: equivalent to some serial schedule
  • recoverable: ordered so that the system can safely recover from a crash or undo an aborted transaction
  • cascadeless: ensure that an abort of one transaction does not produce a series of cascading rollbacks

• To achieve these goals, we use some type of concurrency control mechanism.
  • controls the actions of concurrent transactions
  • prevents problematic interleavings

Locking

• Locking is one way to provide concurrency control.

• Involves associating one or more locks with each database element.

  • each page
  • each record
  • possibly even each collection

Locking Basics

• A transaction must request and acquire a lock for a data element before it can access it.

• In our initial scheme, every lock can be held by only one txn at a time.

• As necessary, the DBMS:
  • denies lock requests for elements that are currently locked
  • makes the requesting transaction wait

• A transaction unlocks an element when it’s done with it.

• After the unlock, the DBMS can grant the lock to a waiting txn.
  • we’ll show a second lock request when the lock is granted

Locking and Serializability

• Just having locks isn’t enough to guarantee serializability.

• Example: our problematic schedule can still be carried out.

Two-Phase Locking (2PL)

• One way to ensure serializability is two-phase locking (2PL).

• 2PL requires that all of a txn’s lock actions come before all its unlock actions.

• Two phases:
  • lock-acquisition phase: a txn acquires locks, but it doesn’t release any

• lock-release phase: once a txn releases a lock, it can’t acquire any new ones

• Reads and writes can occur in both phases.
  • provided that a txn holds the necessary locks

• 2PL is per-transaction.
  • one txn could be in its lock-release phase while another txn is still in its lock-acquisition phase

Two-Phase Locking (2PL) (cont.)

• In our earlier example, T1 does not follow the 2PL rule.

• 2PL would prevent this interleaving.

• More generally, 2PL produces conflict serializable schedules.

An Informal Argument for 2PL’s Correctness

• Consider schedules involving only two transactions. To get one that is not conflict serializable, we need:

1. at least one conflict that requires T1 → T2

• T1 operates first on the data item in this conflict

• T1 must unlock it before T2 can lock it:  u₁(A) .. l₂(A)

2. at least one conflict that requires T2 → T1

• T2 operates first on the data item in this conflict

• T2 must unlock it before T1 can lock it:  u₂(B) .. l₁(B)

• Consider all of the ways these pairs of actions could be ordered:

Extra Practice

• Is the schedule at right:  (page 202)

• conflict serializable?

• yes. conflicts are:
• r₁(B) … w₂(B):  T1 → T2
• w₁(A) … r₂(A):  T1 → T2

• → equivalent to T1;T2

• serializable?

• yes. conflict serializable → serializable

• recoverable?

• yes. only dirty read is r₂(A). reader (T2) commits after writer (T1), so it’s okay

• cascadeless?

• no, because of dirty read. if T1 is rolled back after T2 reads A, T2 must be, too!