1 of 39

CSE 344: Section 7

Transactions, Serializability, and Locking

May 15th, 2025

2 of 39

Announcements

Flight App M1:

Due at 10:00 pm on Friday, May 16th (tomorrow!)
Late days can be used on this assignment

Other updated due dates in pinned ed post!
Questions?

3 of 39

Why Txns or Locks?

Locking is for database internal implementation!

Provides ACID guarantees

Atomicity - all or nothing (the entire transaction takes place at once or doesn’t happen at all)
Consistency - preserve database integrity (the database must be consistent/valid before and after the transaction)
Isolation - execute as if they were run alone (multiple transactions occur independently without interference)
Durability - results aren’t lost by a failure (the changes of a successful transaction occurs even if the system failure occurs)

Pessimistic concurrency control

4 of 39

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

5 of 39

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

6 of 39

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

7 of 39

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

8 of 39

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!)

9 of 39

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

10 of 39

Conflicts

READ-WRITE

WRITE-READ

WRITE-WRITE

Inter-transactional and occur on the same element

Represented with a conflict graph
Conflicts across separate transactions

11 of 39

Conflict Serializability

Checking for conflict serializability -> precedence graph and cycle checking

12 of 39

Conflict Serializability

Checking for conflict serializability -> precedence graph and cycle checking

13 of 39

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?

14 of 39

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

15 of 39

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

16 of 39

Transactions in Java

try {

conn.setAutoCommit(false); // Begin transaction

...

if (we want to rollback changes thus far) {

conn.rollback(); // Roll back any queries executions in transaction thus far

conn.setAutoCommit(true); // End the transaction

}

...

conn.commit(); // Commit our query executions (make them permanent)

conn.setAutoCommit(true); // End the transaction

}

17 of 39

Handling Deadlocks and SQLExceptions

} catch (SQLException e) {

conn.rollback(); // If an error happens, always erase query executions thus far

conn.setAutoCommit(true); // End the transaction

if (error came from deadlock) {

retry from beginning // Deadlocks are transient and usually rare,

// retrying will likely eventually work

}

If deadlock, assume it is transient and will eventually work on retry

Send failure notice back for all other errors

18 of 39

Locking

19 of 39

Locking Overview

Remember - locking is for database internal implementation

A way to provide the ACID guarantees
Pessimistic concurrency control

Assumes transaction executions will conflict

Users of a database need only specify �BEGIN TRANSACTION … COMMIT / ROLLBACK

...and the isolation level...

20 of 39

Database Lock

Table Lock

Predicate Lock

Tuple Lock

Lock Granularity

SQLite!

Less Concurrency

More Concurrency

21 of 39

Binary Locks

22 of 39

2PL with Binary Locks

Lock growing phase

Lock shrinking phase

23 of 39

Worksheet

24 of 39

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!

25 of 39

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 R₁A

26 of 39

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 R₁A

27 of 39

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

28 of 39

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 W₁B

29 of 39

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 R₂B to happen before T3 starts too.

30 of 39

WS PROBLEM 2

T1	T2	T3
R(A)
		R(C)
		W(D)
	R(B)
W(B)
	W(C)

We can safely swap R₂B up since T3 does not have to do with the attribute B!

31 of 39

WS PROBLEM 2

T1	T2	T3
R(A)
	R(B)
		R(C)
		W(D)
W(B)
	W(C)

Now we can go back to W₁B

32 of 39

WS PROBLEM 2

T1	T2	T3
R(A)
	R(B)
		R(C)
		W(D)
W(B)
	W(C)

Now we can go back to W₁B. We can safely swap it up!

33 of 39

WS PROBLEM 2

T1	T2	T3
R(A)
	R(B)
W(B)
		R(C)
		W(D)
	W(C)

Now we can go back to W₁B. We can safely swap it up!

34 of 39

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!

35 of 39

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

36 of 39

Some Alternate Solutions

37 of 39

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

38 of 39

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

39 of 39

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