CSE 344: Section 7
Transactions
Feb 20th, 2025
Announcements
Txns and Serializability
Why Txns or Locks?
Locking is for database internal implementation!
Atomicity
What? “Atom” - a transaction is indivisible; data operations inside the transaction work in an all or nothing fashion
How? Transaction commit and rollback
Example: Transfer of funds from one account to another involves an atomic transaction that includes operations of debit and credit
Consistency
What? Only data operations that comply with database validity constraints are allowed.
Once a transaction is completed, it must not leave the database incomplete or inconsistent.
How? Enforcement of consistency rules upon data entry/updation
Example: A database having both first and last name fields will not accept if you enter only one of those - must enter both for the transaction to be complete
Isolation
What? The appearance of a transaction happening by itself irrespective of what other transactions are happening concurrently
How? User views the database that was present right before the view request is made and any further transactions that are in process after it are ignored
Example: A teller looking up a balance must be isolated from a concurrent transaction involving a withdrawal from the same account
Durability
What? Once a transaction is complete the information as changed will survive failures of any kind
How? Creation of data “mirrors”
Example: Trying to make an update that leads to a system failure should not tamper with any of the previous data and transactions
Serializabilities
Serial: A schedule where each transaction would be executed in some order. They do not allow concurrency; only one transaction executes at a time.
Serializable: A schedule equivalent to a serial schedule. We cannot tell them apart from a true serial schedule based on the database input and output states.
Conflict Serializable: A schedule that can be transformed into a serial schedule by swapping adjacent non-conflicting operations. (Easy to check!)
Conflict Serializable
“Conflict serializable” is a stronger constraint than “serializable”
I.e. any schedule that is conflict serializable must be serializable.
Serializable
Conflict
Serializable
Easy to check
Not easy to check
Conflicts
READ-WRITE
WRITE-READ
WRITE-WRITE
Inter-transactional
Conflict Serializability
Checking for conflict serializability -> precedence graph and cycle checking
Conflict Serializability
Checking for conflict serializability -> precedence graph and cycle checking
Serializability Ex.
S1: w1(Y); w2(Y); w1(X); w2(X); w3(X)
S2: w1(Y); w2(Y); w2(X); w1(X); w3(X)
Are these serializable? Conflict serializable?
Serializability Ex.
S1: w1(Y); w2(Y); w1(X); w2(X); w3(X)
S2: w1(Y); w2(Y); w2(X); w1(X); w3(X)
Conflict Serializable
Serial order: T1, T2, T3
Serializability Ex.
S1: w1(Y); w2(Y); w1(X); w2(X); w3(X)
S2: w1(Y); w2(Y); w2(X); w1(X); w3(X)
Conflict Serializable
Potentially Serializable (but not conflict serializable)
Serial order: T1, T2, T3
Serial order: T1, T2, T3
Worksheet
WS Problem 2
T1 | T2 | T3 |
| | R(C) |
| | W(D) |
| R(B) | |
| W(C) | |
R(A) | | |
W(B) | | |
We can start with the serial order the problem requires. This means all transactions are completed sequentially. As long as we do valid swaps, we should have an equivalent schedule at the end!
WS Problem 2
T1 | T2 | T3 |
| | R(C) |
| | W(D) |
| R(B) | |
| W(C) | |
R(A) | | |
W(B) | | |
We want to get T1 to commit before T3 starts! Let’s start with moving R1A
WS PROBLEM 2
T1 | T2 | T3 |
| | R(C) |
| | W(D) |
| R(B) | |
| W(C) | |
R(A) | | |
W(B) | | |
We want to get T1 to commit before T3 starts! Let’s start with moving R1A
WS PROBLEM 2
T1 | T2 | T3 |
R(A) | | |
| | R(C) |
| | W(D) |
| R(B) | |
| W(C) | |
W(B) | | |
Looks like T1 is the only transaction that has any action on A, so we can safely swap it to the top
WS PROBLEM 2
T1 | T2 | T3 |
R(A) | | |
| | R(C) |
| | W(D) |
| R(B) | |
| W(C) | |
W(B) | | |
Now let’s see what we can do with W1B
WS PROBLEM 2
T1 | T2 | T3 |
R(A) | | |
| | R(C) |
| | W(D) |
| R(B) | |
W(B) | | |
| W(C) | |
Uh oh, we can’t swap these! We need to move R2B to happen before T3 starts too.
WS PROBLEM 2
T1 | T2 | T3 |
R(A) | | |
| | R(C) |
| | W(D) |
| R(B) | |
W(B) | | |
| W(C) | |
We can safely swap R2B up since T3 does not have to do with the attribute B!
WS PROBLEM 2
T1 | T2 | T3 |
R(A) | | |
| R(B) | |
| | R(C) |
| | W(D) |
W(B) | | |
| W(C) | |
Now we can go back to W1B
WS PROBLEM 2
T1 | T2 | T3 |
R(A) | | |
| R(B) | |
| | R(C) |
| | W(D) |
W(B) | | |
| W(C) | |
Now we can go back to W1B. We can safely swap it up!
WS PROBLEM 2
T1 | T2 | T3 |
R(A) | | |
| R(B) | |
W(B) | | |
| | R(C) |
| | W(D) |
| W(C) | |
Now we can go back to W1B. We can safely swap it up!
WS PROBLEM 2
T1 | T2 | T3 |
R(A) | | |
| R(B) | |
W(B) | | |
| | R(C) |
| | W(D) |
| W(C) | |
Transaction 1 commits before transaction 3 starts (as specified in the problem). We’re done!
WS PROBLEM 2: Solution 1
T1 | T2 | T3 |
R(A) | | |
| R(B) | |
W(B) | | |
| | R(C) |
| | W(D) |
| W(C) | |
R1(A), R2(B), W1(B), Co1, R3(C), W3(D), Co3, W2(C), Co2
Some Alternate Solutions
WS PROBLEM 2: Solution 2
T1 | T2 | T3 |
| R(B) | |
R(A) | | |
W(B) | | |
| | R(C) |
| | W(D) |
| W(C) | |
R2(B), R1(A), W1(B), Co1, R3(C), W3(D), Co3, W2(C), Co2
WS PROBLEM 2: Solution 3
T1 | T2 | T3 |
R(A) | | |
| R(B) | |
W(B) | | |
| | R(C) |
| W(C) | |
| | W(D) |
R1(A), R2(B), W1(B), Co1, R3(C), W2(C), Co2, W3(D), Co3
WS PROBLEM 2: Solution 4
T1 | T2 | T3 |
| R(B) | |
R(A) | | |
W(B) | | |
| | R(C) |
| W(C) | |
| | W(D) |
R2(B), R1(A), W1(B), Co1, R3(C), W2(C), Co2, W3(D), Co3