CSE 414 Section 6:

Transactions and Serializability

November 5th, 2026

Announcements

• HW4 due Monday, Nov 9th @ 11:59pm
• Midterm tomorrow during lecture time – Covers everything from beginning of the class up to Relational Algebra

​

HW 4 Q3: What is “Closed”?

• A set of attributes X is called “closed” (given set of FDs) if X⁺ = X.
• Example: Suppose the only closed sets of a relation R(A, B, C) are {}, {A}, {B, C}, and {A, B, C}. Find FDs to satisfy this condition.
• One solution: A → A (trivial FD), B → C, C → B
• {A}⁺ = {A}
• {B}⁺ = {BC}
• {C}⁺ = {BC}
• {AC}⁺ = {ABC}
• Empty set: {}⁺ = {}

​

Motivation for Transactions

ACID

Atomic�Consistent�Isolated�Durable

Everything a concurrent database user wants…

How do ACID properties help us?

• Ensure that a transaction maintains database integrity
• ACID compliance matters to important databases ($$$)
• In this section: delve into the DB Internals required to guarantee ACID

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

Txn Perspective

A database is a collection of "elements" that can be written to or read from.

Operation - A read or write to an element (later: or an insert or delete)

• example of read (R): SELECT
• example of write(W): UPDATE

Example: What operation does the following SQL query contain?�SELECT cases FROM Country WHERE cname = ‘France’;

​

Txn Perspective

A database is a collection of "elements" that can be written to or read from.

Operation - A read or write to an element (later: or an insert or delete)

​

Example: What operation does the following SQL query contain?�SELECT cases FROM Country WHERE cname = ‘France’;

Answer: R(France)

Practice - convert SQL to operations

Txn 1:

1a) x = SELECT cases FROM Country WHERE cname = ‘France’;

1b) x = x + 200;

1c) UPDATE Country SET cases = `x` WHERE cname = ‘France’;

​

Txn 2:

2a) y = SELECT cases FROM Country WHERE cname = ‘Spain’;

2b) y = y / 5;

2c) z = SELECT cases FROM Country WHERE cname = ‘France’;

2d) UPDATE Country SET cases = `y + z` WHERE cname = ‘France’;

Practice - convert SQL to operations

Txn 1:

1a) x = SELECT cases FROM Country WHERE cname = ‘France’;

1b) x = x + 200;

1c) UPDATE Country SET cases = `x` WHERE cname = ‘France’;

​

Txn 2:

2a) y = SELECT cases FROM Country WHERE cname = ‘Spain’;

2b) y = y / 5;

2c) z = SELECT cases FROM Country WHERE cname = ‘France’;

2d) UPDATE Country SET cases = `y + z` WHERE cname = ‘France’;

1a) R(France)

1b)

1c) W(France)

​

​

2a) R(Spain)

2b)

2c) R(France)

2d) W(France)

Definitions

Operation -

Transaction -

Schedule -

Serial schedule -�

Serializable schedule - �

Definitions

Operation - read or write of an element (later: insert or delete)

Transaction - series of operations meant to have the ACID guarantees

Schedule - ordering of the operations of some txns

Serial schedule - schedule where each txn is executed one after another.� No interleaving

Serializable schedule - a schedule that is behaviorally equivalent � to a serial schedule

Definitions

Non-conflicting swap - �

Conflicting swap -

Conflict serializable schedule - �

​

Definitions

Non-conflicting swap - a pair of adjacent operations in a schedule � that can be reversed without affecting the schedule's behavior

Conflicting swap - (any two ops in same txn), RW, WR, WW

Conflict serializable schedule - a schedule that can be transformed � into a serial schedule via a series of non-conflicting swaps

​

Conflict Serializability

Checking for conflict serializability -> precedence graph and cycle checking

Conflict Serializability

Checking for conflict serializability -> precedence graph and cycle checking

Serializability

“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

Serializability

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

S1: w1(Y); w2(Y); w1(X); w2(X); w3(X)

S2: w1(Y); w2(Y); w2(X); w1(X); w3(X)

Conflict Serializable

Serializable (but not conflict serializable)

Worksheet

WS Problem 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 B

We want to get T1 to commit before T3 starts! Let’s start with moving R₁A

WS Problem B

We want to get T1 to commit before T3 starts! Let’s start with moving R₁A

WS Problem 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 B

Now let’s see what we can do with W₁B

WS Problem B

Uh oh, we can’t swap these! We need to move R₂B to happen before T3 starts too.

WS Problem B

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

WS Problem B

Now we can go back to W₁B

WS Problem B

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

WS Problem B

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

WS Problem B

Transaction 1 commits before transaction 3 starts (as specified in the problem). We’re done!

WS Problem B: Solution 1

R1(A), R2(B), W1(B), Co1, R3(C), W3(D), Co3, W2(C), Co2

​

Some Alternate Solutions

WS Problem B: Solution 2

R2(B), R1(A), W1(B), Co1, R3(C), W3(D), Co3, W2(C), Co2

​

WS Problem B: Solution 3

R1(A), R2(B), W1(B), Co1, R3(C), W2(C), Co2, W3(D), Co3

​

WS Problem B: Solution 4

R2(B), R1(A), W1(B), Co1, R3(C), W2(C), Co2, W3(D), Co3

​

Takeaways

• You can always swap two reads (even if they are on the same element!)
• Be careful about swapping writes
• If they are writing on different attributes, like W1(A) and W2(B), then it’s ok to swap.
• Otherwise, you can’t safely swap two writes on the same attribute (write conflict). For example, W1(A) and W2(A) can’t be swapped. Swapping writes within a given transaction would also be a conflict, like if a transaction had W1(A) followed by W1(A).