Transactions

April 17, 2025

1

Data 101, Spring 2025 @ UC Berkeley

Aditya Parameswaran https://data101.org/sp25

​

​

LECTURE 22

Wrapping Up:

Reservoir Sampling

MapReduce

MapReduce’s Legacy and Spark

—

Database Sampling

Sampling Tips and Pitfalls

Reservoir Sampling

Reservoir Sampling Probabilities/Proofs

[extra] Algorithm L: Optimization

Stratified Sampling

[extra] Visualizations

2

Lecture 22, Data 101, Spring 2025

What other sampling methods exist?

Database sampling has several drawbacks!

• Have to pick the “right” Bernoulli probability to set for queries
• No control of output size
• Sample only during scan; can’t sample based on data attributes themselves
• Finally, not all data sources support this sort of sampling!

When do you sample the database (i.e., table sample)?

• (Note: sampling is effectively a form of selection pushdown)
• For efficiency: sample as close to scanning the data as possible.
• This allows a smaller amount of data to flow through your pipeline, facilitating throughput.

3

Up Next: Sampling Methods

In this class, we’ll discuss two flexible ways of sampling that address the issues of table sampling.

• Reservoir sampling picks a k-sized simple random sample in a single pass.
• Stratified sampling (using reservoir sampling) to get k-sized samples per grouped attribute.

4

Reservoir Sampling: The idea

Goals: k-sized simple random sample i.i.d. without replacement.� Linear runtime and single pass

5

(i.e., total records n unknown during sampling).

Reservoir Sampling: The idea

Goals: k-sized simple random sample i.i.d. without replacement.� Linear runtime and single pass

6

Strategy:

• Build a reservoir, i.e., a fixed-size array that holds k records.
• Then scan the table.�For record r_i, where i = 1, …, n:
• If i < k, reservoir has space. Insert record r_i into reservoir.
• Else, insert record r_i by evicting a random reservoir record,�with some probability P_i based on the scan order i.

Reservoir sampling process:

• produces an SRS
• is linear in # rows

(i.e., total records n unknown during sampling).

Simple Reservoir Sample

# ported from �# https://en.wikipedia.org/wiki/Reservoir_sampling

from random import randrange

​

def reservoir_sample(data, n, k):

# fill the reservoir array

r = []

for i in range(k):

r.append(data[i])

​

# replace elements w/gradually decreasing prob.

for i in range(k, n):

# generates a uniform integer between 0 and a-1

j = randrange(i+1)

if j < k:

r[j] = data[i]

​

return r

​

data = list(range(1000))

n, k = len(data), 5

r = reservoir_sample(data, n, k)

r

7

Single pass!�Constant sample size!

• n can be unbounded! (w/small changes to the function)
• Can also parallelize (since you know P_i for every record r_i)

Demo

#transactions

Reservoir Sampling Probabilities/�Proofs

MapReduce

MapReduce’s Legacy and Spark

—

Database Sampling

Sampling Tips and Pitfalls

Reservoir Sampling

Reservoir Sampling Probabilities/Proofs

[extra] Algorithm L: Optimization

Stratified Sampling

[extra] Visualizations

8

Lecture 22, Data 101, Spring 2025

Reservoir Sampling SRS Proof Outline

def reservoir_sample(data, n, k):

r = []

for i in range(k):

r.append(data[i])

​

for i in range(k, n-1):

j = randrange(i+1)

if j < k:

r[j] = data[i]

​

return r

9

Reservoir Sampling SRS Proof Outline

def reservoir_sample(data, n, k):

r = []

for i in range(k):

r.append(data[i])

​

for i in range(k, n-1):

j = randrange(i+1)

if j < k:

r[j] = data[i]

​

return r

10

🤔

Pick a rand number from 1..i, if <=k, then add to sample Pi = k/i

What is the probability of record i being in S_n, the nth (and final) reservoir sample?

ⓘ

Click Present with Slido or install our Chrome extension to activate this poll while presenting.

Reservoir Sampling SRS Proof Outline

def reservoir_sample(data, n, k):

r = []

for i in range(k):

r.append(data[i])

​

for i in range(k, n-1):

j = randrange(i+1)

if j < k:

r[j] = data[i]

​

return r

12

Proof by Induction

Property holds until i-1 (after I’ve processed 1…i-1)

every item until i-1 is included with probability k/(i-1)

Now, want to ensure that after i (after I’ve processed 1…i)

every item until i is included with probability k/i

Case 1: ensure that ith item is included with prob k/i

P_i = k/i easy, by definition

Case 2: ensure that remaining items is included with prob k/i

Probabiliity that a given item m from 1…i-i is included in the sample of k after processing i-1 items: k/(i-1)

Probability that it will get to stay at after the ith step:

• case 2a: the ith item isn’t included in the sample
• (1- k/i) = (i-k)/i
• case 2b: ith item is included in the sample, but a diff item got evicted
• k/i * (k-1)/k = (k-1)/i
• sum = (i-1)/i
• Overall probability k/(i-1) * (i-1)/i = k/i

​

13

Empirical Proof

import numpy as np

​

K = 5

N_SAMPLES = 10000

samples = []

​

N = 1000

data = list(range(N))

for j in range(N_SAMPLES):

samples += \

reservoir_sample(data, N, k)

​

unique, counts = np.unique(

samples, return_counts=True)

​

ax = pd.Series(samples).plot.hist(grid=True, bins=20, rwidth=0.9,

color='#607c8e')

ax.set_title(f"Distribution of frequencies of all {N} values")

14

Demo

#transactions

[Extra] Reservoir Sampling SRS Proof Outline

​

15

Proof by induction (see CS 70, Data 140)

🏡

Algorithm L: Reservoir Sampling Optimization

MapReduce

MapReduce’s Legacy and Spark

—

Database Sampling

Sampling Tips and Pitfalls

Reservoir Sampling

Reservoir Sampling Probabilities/Proofs

[extra] Algorithm L: Optimization

Stratified Sampling

[extra] Visualizations

16

not covered (out of scope)

Lecture 22, Data 101, Spring 2025

Algorithm L: Small optimization to Reservoir

def reservoir_sample(data, n, k):

r = []

for i in range(k):

r.append(data[i])

​

for i in range(k, n-1):

j = randrange(i+1)

if j < k:

r[j] = data[i]

​

return r

17

Calling a random number generator for every record can be slow, particularly when we have trillions of records.

Algorithm L: Small optimization to Reservoir

How can we reduce the number of calls to randrange()?

Consider the number of rows skipped between chosen values:

• approximately geometric, has closed form! (we won’t prove this)
• idea: don’t call randrange() on records that will be discarded anyway

​

Algorithm L approach: pick geometrically distributed random gaps, then only call randrange on a much smaller set of records.

18

Sampling gap distribution for S_1000 from 100k records�(gaps between chosen values 1 to 100k)

[Extra] Algorithm L Implementation

[extra]

# This is called Algorithm L, ported from

# https://en.wikipedia.org/wiki/Reservoir_sampling

from random import random, randrange

from math import exp, log, floor

​

def reservoir_sample_L(data, n, k):

# fill the reservoir array

r = []

for i in range(k):

r.append(data[i])

​

# generates a uniform [0,1) random number

w = exp(log(random())/k)

​

while i < n:

i = i + floor(log(random())/log(1-w)) + 1

if i < n:

# replace random reservoir item with item i

r[randrange(k)] = data[i]

w = w * exp(log(random())/k)

return r

19

[wikipedia]

Assume this works as an optimal strategy for reservoir sampling.

Demo

#transactions

[Extra] The plotting code

[extra]

import numpy as np

import pandas as pd

​

def plot_gaps(r):

r.sort()

gaps = pd.Series(np.diff(r))

gaps.plot.hist(grid=True, bins=20, rwidth=0.9,

color='#607c8e')

data = list(range(100000))

n = len(data)

k = 1000

r = reservoirSample(data, n, k)

plot_gaps(r)

​

20

Demo

#transactions

[Extra]

Reservoir Sampling in SQL

MapReduce

MapReduce’s Legacy and Spark

—

Database Sampling

Sampling Tips and Pitfalls

Reservoir Sampling

Reservoir Sampling Probabilities/Proofs

[extra] Algorithm L: Optimization

Stratified Sampling

[extra] Visualizations

21

Lecture 22, Data 101, Spring 2025

Reservoir Sampling as a Table-Valued UDF

%%sql

-- create the reservoir_swaps UDF --

DROP TYPE IF EXISTS reservoir_pair CASCADE;

CREATE TYPE reservoir_pair AS (rownum integer, pos integer);

CREATE OR REPLACE FUNCTION reservoir_swaps(k integer, n integer) RETURNS setof reservoir_pair

AS $$

# optimized reservoir sampling algorithm, � # Algorithm L

$$

LANGUAGE 'plpython3u'

VOLATILE

RETURNS NULL ON NULL INPUT;

​

​

CREATE OR REPLACE FUNCTION

reservoir_rows(k integer, n integer)

RETURNS setof integer

AS $$

SELECT MAX(rownum) AS rownum

FROM reservoir_swaps(k, n)

GROUP by pos $$

LANGUAGE 'sql'

VOLATILE;

22

We skip the details of this User Defined Function (UDF)

It returns a table with one attribute reservoir_rows for the k row numbers in S_n.

Demo

#transactions

Reservoir Sampling in SQL

%%sql

WITH rrows AS (� SELECT reservoir_rows(10, count(*)::integer) � AS rows

FROM batting),

rbatting AS (

SELECT ROW_NUMBER() OVER(), * FROM batting)

SELECT *

FROM rbatting, rrows

WHERE row_number = rows;

23

Demo

#transactions

Stratified Sampling

MapReduce

MapReduce’s Legacy and Spark

—

Database Sampling

Sampling Tips and Pitfalls

Reservoir Sampling

Reservoir Sampling Probabilities/Proofs

[extra] Algorithm L: Optimization

Stratified Sampling

[extra] Visualizations

24

Lecture 22, Data 101, Spring 2025

What about Stratified Sampling?

Stratified sampling: Sample subpopulations.

aka GROUP BY sampling (in SQL):

• want a k-sized sample per GROUP
• "GROUP BY" columns are called subpopulations

​

In PostgreSQL:

• Impossible with table samples (Bernoulli sampling on initial scans, not strata)
• But can be implemented with reservoir_rows UDF and GROUP BY (next slide)

25

Demo

#transactions

What about Stratified Sampling?

%%sql

-- Stratified Sampling with Reservoirs

WITH grprows AS (

SELECT teamid,

reservoir_rows(10, COUNT(*)::integer) AS rows

FROM batting

GROUP BY teamid

),

rbatting AS (

SELECT row_number() OVER(� PARTITION BY teamid),� *

FROM batting�)

SELECT *

FROM rbatting b, grprows g

WHERE row_number = rows AND b.teamid = g.teamid

ORDER BY b.teamid;

26

4181385

Demo

#transactions

Join at slido.com�#transactions

ⓘ

Click Present with Slido or install our Chrome extension to display joining instructions for participants while presenting.

Updates create challenges

So far, we’ve largely focused on data science/read-only workloads.�In many settings, we need to also support updates.

• Single-user, one-at-a-time updates are easy.
• But multi-user, simultaneous updates are challenging.

When updating data, we want correctness + speed, particularly when users are accessing and modifying the same relations.

Course/lecture goals:

• Understand challenges that updates cause
• Understand APIs/related guarantees.

28

Today, a glance at database internals: transactions. More in CS186: Database Systems!

transactions

Two Main Features We Expect from our Database System for Updates

Concurrency Control:

• Many users query and update a database simultaneously.
• How do we avoid confusion / incorrect state?

​

Recovery:

• What happens when things fail?
• Many such failure modes: Cancel modification partway,
• app failure, DB engine failure, HW failure…

To understand these features, we need to introduce the concept of transactions.

29

transactions

Transactions/�TCL

Transactions/TCL

The ACID Principle

Isolation

Transaction Schedules

Serializability

Details:

• Strict 2-Phase Locking
• Conflicting Actions

[Extra] Additional slides

30

Lecture 22, Data 101, Spring 2025

What is a Transaction?

Colloquially, a transaction in a database is a unit of work�that should appear to “happen together.”

Classic example: Debit/credit banking transaction, i.e.,�moving $1k from one account (1111) to another (9999).

31

BEGIN

-- "debit" one account

UPDATE checking � SET amount = amount – 1000 � WHERE acctId = 1111;

-- "credit" the other account

UPDATE savings

SET amount = amount + 1000

WHERE acctId = 9999;

COMMIT

transactions

What constitutes “happening together”? Observation #1

BEGIN

-- "debit" one account

UPDATE checking � SET amount = amount – 1000 � WHERE acctId = 1111;

-- "credit" the other account

UPDATE savings

SET amount = amount + 1000

WHERE acctId = 9999;

COMMIT

A few observations:

1. We need both debit and credit to happen, i.e., we should not have partial transactions.
2. …?

​

(to be continued…)

32

transactions

SQL TCL

33

Data Definition Language

Transaction Control Language

Data Manipulation Language

Data�Query Language

Data�Control�Language

✅

✅

✅

BEGIN

transactions

SQL TCL, Briefly

A transaction in SQL is a list of commands sandwiched by BEGIN and COMMIT.

​

If BEGIN/COMMIT not specified, then most systems will autocommit individual SQL commands, i.e., auto-wrap each command in its own transaction.

Generally (with slight syntax variation across systems):

• BEGIN equivalent to START, BEGIN WORK, START TRANSACTION, etc.
• COMMIT equivalent to END, END WORK, END TRANSACTION, etc.

34

Postgres BEGIN, START TRANSACTION, COMMIT, END, ROLLBACK, ABORT, SAVEPOINT

BEGIN� <command 1>� …� <command n>�COMMIT

transactions

[extra] SQL TCL: Savepoints

Savepoints let you break your transactions up into pieces. You can then “partially rollback” to a prior savepoint, or abort altogether.

• ABORT
• SAVEPOINT save_name
• ROLLBACK TO SAVEPOINT save_name
• Undo any commands that happened after the specified savepoint; and
• Implicitly destroy any savepoints created after the specified one.

​

Use case: beyond the scope of this class, but generally used with SQL conditionals or as part of database constraints.

35

BEGIN

UPDATE checking � SET amount = amount – 1000 � WHERE acctId = 1234;

SAVEPOINT debit_done;

UPDATE savings

SET amount = amount + 1000

WHERE acctId = 9999;

SAVEPOINT credit_done;

ROLLBACK TO SAVEPOINT debit_done;

UPDATE savings

SET amount = amount + 1000

WHERE acctId = 4321;

END

(arbitrary example; what is this doing?)

Postgres BEGIN, START TRANSACTION, COMMIT, END, ROLLBACK, ABORT, SAVEPOINT

transactions

The ACID Principle

Transactions/TCL

The ACID Principle

Isolation

Transaction Schedules

Serializability

Details:

• Strict 2-Phase Locking
• Conflicting Actions

[Extra] Additional slides

36

Lecture 22, Data 101, Spring 2025

What constitutes “happening together”? Observations

BEGIN

-- "debit" one account

UPDATE checking � SET amount = amount – 1000 � WHERE acctId = 1111;

-- "credit" the other account

UPDATE savings

SET amount = amount + 1000

WHERE acctId = 9999;

COMMIT

A few observations:

• We need both debit and credit to happen, i.e., we should not have partial transactions.
• At the end of transactions, any database constraints should still be satisfied.
• Even if another transaction happens simultaneously, one should appear to have finished “first.”
• A committed transaction should appear to have happened, even if there is a power failure/reboot later.

37

These four properties, known as ACID, define how transactions guarantee�(1) concurrency control and (2) recovery.

transactions

ACID: Basic Guarantees

ACID defines four properties of transactions that guarantee concurrency control and recovery.

​

Atomicity �

​

Consistency

�

Isolation

�.

Durability

​

38

transactions

ACID: Basic Guarantees

ACID defines four properties of transactions that guarantee concurrency control and recovery.

39

Either all the commands are reflected in the database, or none are.�Ex: Both debit+credit should occur, or both should fail to occur.

If COMMIT succeeds, all the database integrity checks hold true.�(primary key/foreign keys, constraints, etc.)

Concurrent transactions should externally appear to run sequentially, i.e., 2 concurrent transactions should not “see” each other’s intermediate results.

If COMMIT succeeds, all changes from the transaction persist, even if there is a power failure or a reboot, until the transaction is overwritten by a later transaction.

Atomicity�

Consistency�

Isolation��

Durability

transactions

[History] Why ACID? Unknown, but…

40

Gray, 1981, Hearder and Reuter, 1983, Wikipedia (acid test (disambiguation))

[Exercise] ACID

BEGIN

-- "debit" one account

UPDATE checking � SET amount = amount – 1000 � WHERE acctId = 1111;

-- "credit" the other account

UPDATE savings

SET amount = amount + 1000

WHERE acctId = 9999;

COMMIT

A few observations:

• We need both debit and credit to happen, i.e., we should not have partial transactions.
• At the end of transactions, any database constraints should still be satisfied.
• Even if another transaction happens simultaneously, one should appear to have finished “first.”
• A committed transaction should appear to have happened, even if there is a power failure/reboot later.

41

Match 1-4 with A, C, I, and D from the ACID Principle.

🤔

A. D, I, C, A

B. I, C, A, D

C. A, C, I, D

D. A, C, D, I

E. Something else

transactions

Match 1-4 with A, C, I, and D from the ACID Principle.

ⓘ

Click Present with Slido or install our Chrome extension to activate this poll while presenting.

[Solution] ACID

BEGIN

-- "debit" one account

UPDATE checking � SET amount = amount – 1000 � WHERE acctId = 1111;

-- "credit" the other account

UPDATE savings

SET amount = amount + 1000

WHERE acctId = 9999;

COMMIT

A few observations:

A. We need both debit and credit to happen, i.e., we should not have partial transactions.

C. At the end of transactions, any database constraints should still be satisfied.

I. Even if another transaction happens simultaneously, one should appear to have finished “first.”

D. A committed transaction should appear to have happened, even if there is a power failure/reboot later.

43

transactions

How does the database address each ACID property?

44

�

If COMMIT succeeds, all the database integrity checks hold true.�(primary key/foreign keys, constraints, etc.)

​

Atomicity�

Consistency�

Isolation��

Durability

Standard database checks (relatively efficient to check for core things like attribute types, keys, constraints, etc.)

transactions

How does the database address each ACID property?

45

Either all the commands are reflected in the database, or none are.�Ex: Both debit+credit should occur, or both should fail to occur.

�

��

If COMMIT succeeds, all changes from the transaction persist, even if there is a power failure or a reboot, until the transaction is overwritten by a later transaction.

Atomicity�

Consistency�

Isolation��

Durability

The database’s internal recovery system.

After a crash:

• Redo all committed work; and
• Undo all uncommitted work!

See CS186 for the implementation. Devil is in the details!

transactions

How does the database address each ACID property?

46

Atomicity�

Consistency�

Isolation��

Durability

�

�

Concurrent transactions should externally appear to run sequentially, i.e., 2 concurrent transactions should not “see” each other’s intermediate results.

Provided by concurrency control, a component of the database. We’ll grasp the intuition today!!

transactions

Isolation

Transactions/TCL

The ACID Principle

Isolation

Transaction Schedules

Serializability

Details:

• Strict 2-Phase Locking
• Conflicting Actions

[Extra] Additional slides

47

Lecture 22, Data 101, Spring 2025

Isolation

Isolation: Concurrent transactions should externally appear to run sequentially.

• If the database receives these transactions simultaneously, we should be able to successfully execute all three as if they happened “in isolation.”

48

Hire Mercy as the new VP of Engineering!

Move the entire payroll of the London Office to the Cambridge Office!

Prepare tax projections for the 2^nd quarter!

transactions

Isolation,

The challenge: How do we execute these transactions “in isolation” but “concurrently”? With one single machine?

49

Prepare tax projections for the 2^nd quarter!

Hire Mercy as the new VP of Engineering!

Move the entire payroll of the London Office to the Cambridge Office!

Assumption: the precise order of these three transactions doesn’t matter. What matters is that they appeared to have been executed by the DBMS in some order.

​

Isolation,

For simplicity, we will limit our discussion to reads and writes of individual “objects”:

​

“Objects” := records (for now)

​

i-th transaction has Read from O:

R_i(O)

i-th transaction has Write to O:

W_i(O [= value])

50

Prepare tax projections for the 2^nd quarter!

Hire Mercy as the new VP of Engineering!

Move the entire payroll of the London Office to the Cambridge Office!

Transaction Schedules

Transactions/TCL

The ACID Principle

Isolation

Transaction Schedules

Serializability

Details:

• Strict 2-Phase Locking
• Conflicting Actions

[Extra] Additional slides

51

Lecture 22, Data 101, Spring 2025

Determining Transaction Schedules that Maintain Isolation

Our goal: Understand how multiple transactions can run concurrently (for performance) but also in isolation (for ACID).

To do so, we’ll define the following:

1. Define transaction schedules (i.e., list of read/writes).

​

• Define serial schedules, which satisfy isolation by definition.

​

• Define serializable schedules, which allow for concurrency while maintaining isolation.

52

transactions

Example: Two Transactions

53

-- set Parth’s salary to 10% more �-- than Jonah’s

UPDATE employee

SET salary = (SELECT salary*1.1

FROM employee

WHERE name='Jonah')

WHERE name = 'Parth';

-- set Parth’s salary to 10% more �

UPDATE employee

SET salary = (SELECT salary*1.1

FROM employee

WHERE name='Parth')

WHERE name = ‘Parth';

T₁:

T₂:

transactions

Transaction Schedules

A transaction schedule is a ordered list of actions from a set of transactions.

54

A proposed Transaction Schedule�of T1 and T2

time

While there are many possible transaction schedules, a DBMS will pick one with which to schedule and execute read/write actions.

transactions

Transaction Schedules

A transaction schedule is a ordered list of actions from a set of transactions.

• The ordered schedule of actions (reads from/writes to objects) represents the actual/potential execution sequence in time, as seen by the DBMS.

55

time

time slot 1

time slot 2

time slot 3

time slot 4

✅

transactions

Transaction Schedules

A transaction schedule is a ordered list of actions from a set of transactions.

• The ordered schedule of actions (reads from/writes to objects) represents the actual/potential execution sequence in time, as seen by the DBMS.
• The order in which two actions from the same transaction T are scheduled must reflect the order in which they appear in T.

56

time

✅

T₁:

T₂:

transactions

Determining Transaction Schedules that Maintain Isolation

Our goal: Understand how multiple transactions can run concurrently (for performance) but also in isolation (for ACID).

To do so, we’ll define the following:

• Define transaction schedules (i.e., list of read/writes).

​

• Define serial schedules, which satisfy isolation by definition.

​

• Define serializable schedules, which allow for concurrency while maintaining isolation.

57

✅

transactions

Serial Schedules

A serial schedule is a transaction schedule for which �actions from different transactions are not interleaved.

58

T₁:

T₂:

serial schedule

time

serial schedule

not a serial schedule;�transactions interleaved

Serial schedules exhibit no concurrency, because actions of a transaction are executed together and separate from those in other transactions.

transactions

Do these schedules satisfy the isolation property?

59

Which of these three schedules satisfy the isolation property? Select all.

🤔

Isolation: Concurrent transactions should externally appear to run sequentially, i.e., 2 concurrent transactions should not (appear to) “see” each other’s intermediate results.

T₁:

T₂:

time

1.

2.

3.

transactions

Which of these three schedules satisfy the isolation property? Select all.

ⓘ

Click Present with Slido or install our Chrome extension to activate this poll while presenting.

Serializability

Transactions/TCL

The ACID Principle

Isolation

Transaction Schedules

Serializability

Details:

• Strict 2-Phase Locking
• Conflicting Actions

[Extra] Additional slides

61

Lecture 22, Data 101, Spring 2025

Do these schedules satisfy the isolation property?

62

T₁:

T₂:

time

1.

2.

3.

Yes

Yes

Yes!

Isolation. If we execute a given schedule, from the DBMS’s POV, individual transactions appear to be executed sequentially.

transactions

All three schedules satisfy the isolation property!

63

T₁:

T₂:

time

1.

2.

3.

It is okay that these two serial schedules produce non-equivalent database outcome states!

Isolation. If we execute a given schedule, from the DBMS’s POV, individual transactions appear to be executed sequentially.

transactions

All three schedules satisfy the isolation property!

64

T₁:

T₂:

time

1.

2.

3.

Isolation. If we execute a given schedule, from the DBMS’s POV, individual transactions appear to be executed sequentially.

Despite the interleaving, this schedule has an equivalent database outcome to one of the serial schedules!

transactions

Schedule 3 is a serializable schedule

65

T₁:

T₂:

time

1.

2.

3.

Despite the interleaving, this schedule has an equivalent database outcome to one of the serial schedules!

Schedule 3 is a serializable schedule: a transaction schedule whose database outcome is equivalent to some serial schedule.

transactions

Unserializable Schedules

66

T₁:

T₂:

time

2.

3.

Not all schedules are serializable! This is an unserializable schedule, because there is no serial equivalent, and therefore transactions do not appear isolated.

serializable schedule

serial schedule

4.

⚠️

transactions

A Joke

67

Strict 2-Phase Locking

Transactions/TCL

The ACID Principle

Isolation

Transaction Schedules

Serializability

Details:

• Strict 2-Phase Locking
• Conflicting Actions

[Extra] Additional slides

68

Lecture 22, Data 101, Spring 2025

Summary so far

Our goal: Allow multiple transactions to run concurrently (for performance)�but also in isolation (for ACID).

To do so, we’ve traced the following steps:

• Define transaction schedules (i.e., list of read/writes).

​

• Define serial schedules, which satisfy isolation by definition.

​

• Define serializable schedules, which allow for concurrency while maintaining isolation.

69

serial schedule

serializable schedule

unserializable schedule

transactions

DBMS goals

Under the covers, a database system can allow serializable schedules that may not be serial, but after execution have the same outcome as some serial schedule.

• Allows multiple transactions to run at the same time.
• Much better for performance!!

​

CS186: Build systems that guarantee serializability for all executed schedules.

70

serial schedule

serializable schedule

unserializable schedule

❌

transactions

Two final goals of this lecture

• Briefly, how do databases build schedule that ensure serializability?
• Strict Two-Phase Locking
• Conceptually, how do we know a schedule is serializable?
• Conflicting actions

71

transactions

Database locking

One of the most straightforward implementations that databases can use to ensure serializability is called Strict Two-Phase Locking (Strict 2PL).

• This is a conservative method to guarantee serializability.
• It prevents certain serializable schedules and therefore may suffer some performance hits, but overall there is no harm done because it is always correct / satisfies ACID principle.
• What theoretical guarantees? See conflict serializability

​

Skipped slides: details on Strict 2PL.

72

transactions

Determining Serializability:

Conflicting Actions

Transactions/TCL

The ACID Principle

Isolation

Transaction Schedules

Serializability

Details:

• Strict 2-Phase Locking
• Conflicting Actions

[Extra] Additional slides

73

Lecture 22, Data 101, Spring 2025

How do we know if a schedule is serializable?

We like serializable schedules.

• Isolation, again: After the dust settles, transactions appear to have happened in some order (which may seem “arbitrary”). However, the order means that:
• the txns appear to have followed a serial schedule.
• that txns can be “rolled back” one-by-one.

74

transactions

Conflicting Actions

Def: Two actions conflict if:

• They are two different, concurrent transactions.
• They reference the same object.
• At least one is a write.

Alt Def: If T1 and T2 have conflicting actions, then every equivalent serial schedule (i.e., with the same database outcome) must have T1 and T2 in some specific order.

75

transactions

Which of the following are conflicting actions?

Alt Def: If T1 and T2 have conflicting actions, then every equivalent serial schedule (i.e., with the same database outcome) must have T1 and T2 in some specific order.

​

Suppose T1 → T2 in a schedule,�i.e., T1 comes before T2.

76

A.

B.

C.

D.

E.

For which of the following would the resulting flip of actions mean that this transaction order would change, i.e., that now T2 → T1? Select all.

🤔

transactions

Select all for which the following is true: Flipping the order of the two actions in T1 and T2 would result in a different database outcome state.

ⓘ

Click Present with Slido or install our Chrome extension to activate this poll while presenting.

Which of the following are conflicting actions?

78

R₂(P)

W₁(P)

T2 reads �Parth salary �as ????

T1 writes�Parth salary �as ????

W₂(G)

R₁(G)

T2 writes Gabi salary as ????

T1 reads Gabi salary as ????

W₂(J)

W₁(J)

T2 writes Jonah salary as ????

T1 writes Jonah salary as ????

R₂(G)

R₁(G)

T2 reads Gabi salary as ????

T1 reads Gabi salary as ????

W₂(P)

W₁(J)

T2 writes Parth salary as ????

T1 writes Jonah salary as ????

Suppose T1 → T2 in a schedule. For which of the following would the resulting flip of actions mean that this transaction order would change, i.e., that now T2 → T1? Select all.

hypothetically

hypothetically

hypothetically

hypothetically

hypothetically

Which of the following are conflicting actions?

Alt Def: If T1 and T2 have conflicting actions, then every equivalent serial schedule (i.e., with the same database outcome) must have T1 and T2 in some specific order.

​

Suppose T1 → T2 in a schedule,�i.e., T1 comes before T2.

79

For which of the following would the resulting flip of actions mean that this transaction order would change, i.e., that now T2 → T1? Select all.

A.

B.

C.

D.

E.

transactions

Which of the following are conflicting actions?

Alt Def: If T1 and T2 have conflicting actions, then every equivalent serial schedule (i.e., with the same database outcome) must have T1 and T2 in some specific order.

​

Suppose T1 → T2 in a schedule,�i.e., T1 comes before T2.

80

can be flipped! no conflicts!

cannot be flipped! conflicting actions!

For which of the following would the resulting flip of actions mean that this transaction order would change, i.e., that now T2 → T1? Select all.

transactions

How do we know if a schedule is serializable?

We like serializable schedules.

• Isolation, again: After the dust settles, transactions appear to have happened in some order (which may seem “arbitrary”). However, the order means that:
• the txns appear to have followed a serial schedule.
• that txns can be “rolled back” one-by-one.

​

​

A schedule is serializable if all conflicting actions dictate a specific ordering of the transactions (with no cycles)

• A topological sort on the graph of conflicts between transactions.

81

Conflicting actions between transactions determine if a schedule is serializable.

transactions

The example again

82

T₁:

T₂:

3.

serializable

4.

unserializable

5.

⚠️

⚠️

serializable

Schedule 4: The two pairs of conflicting actions imply two different orders to T1 and T2.

transactions

Performance Tradeoffs: Snapshot Isolation

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Conflicting Actions

[Extra] Conflict Graphs

[Extra] Conflict Serializable

Weak Isolation

[Extra] Additional slides

83

Lecture 22, Data 101, Spring 2025

Final thoughts: Why Should Data Engineers Know Transactions?

You may think that transactions (and serializability) are very much in the weeds of DBMS design, which we don’t particularly implement in this course. However…

84

Inevitably you will update a database and manage data from transactional databases!

• This means you should have a sense of its characteristics.

​

If your DB is slow for transactional reasons:

• You should understand why
• And how you can trade-off speed and “correctness,” i.e., redefine your transactions.

Finally, transaction concepts are also quite useful outside of databases.

• Examples: Queueing systems, e.g., RabbitMQ or Kafka.

transactions

Serialized Transactions: A summary

Serialized transactions ensure ACID properties of shared access, particularly Isolation.

• Strict 2PL is a common implementation of serialization, though it is not the only one.

​

85

Life is good?…Except…

• SELECT avg(gpa) FROM students;
• Locks all students!
• But we likely don’t need this to be 100% correct!
• Sometimes we prefer to trade correctness for a little more performance.

transactions

Approximating Serialized Transactions with Weak Isolation

Serialized transactions ensure ACID properties of shared access, particularly Isolation.

• Strict 2PL is a common implementation of serialization, though it is not the only one.

​

86

Enter: Weak Isolation.

• Each isolation can choose to be a “bit sloppy”...
• …as long as it doesn’t mess up other transaction’s choices to do so.
• The most common weak isolation implementation is snapshot isolation.
• This is a much weaker property of isolation than serialized transactions,�but it’s good enough when we prefer more concurrency/higher performance.

Life is good?…Except…

• SELECT avg(gpa) FROM students;
• Locks all students!
• But we likely don’t need this to be 100% correct!
• Sometimes we prefer to trade correctness for a little more performance.

transactions

Snapshot Isolation

Snapshot isolation is a weaker form of isolation than serialization, but it’s good enough when we prefer more concurrency/higher performance.

• Database system requirements: Keep multiple versions of tuples.

87

At transaction start: Take a “snapshot” of the database, off which to do reads/writes.

• snapshot reads: All reads of this transaction are from this snapshot.
• write validation: This transaction can commit if none of its writes conflict with other transactions since the snapshot was taken.
• If write-write conflicts, then abort this transaction.

transactions

Snapshot Isolation is Actually Popular

Isolation levels (both default and maximum) vary in support across different database engines.

Marketing also varies!

• When Oracle says “Serializable,” they actually are giving you Snapshot Isolation!!

88

The maximum levels of many cloud DBMSs is not always the theoretical maximum,�which is “serializable” transactions.

• Serializable: Google Cloud Spanner, CockroachDB, Azure SQL Server
• Read Commit: Snowflake, AWS Aurora
• For more about Read Commit and others, check out the bonus slides.

[Bonus] Strict 2-Phase Locking: Details

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Conflicting Actions

[Extra] Conflict Graphs

[Extra] Conflict Serializable

Weak Isolation

[Extra] Additional slides

89

Lecture 22, Data 101, Spring 2025

Database locking

How do databases ensure serializability?

One of the most straightforward implementations is called Strict Two-Phase Locking (Strict 2PL).

• This is a conservative method to guarantee serializability.
• It prevents certain serializable schedules and therefore may suffer some performance hits, but overall there is no harm done because it is always correct / satisfies ACID principle.
• What theoretical guarantees? See conflict serializability

​

Locking is the process of ensuring that 2 conflicting actions happen in order.

• The first action that arrives should “lock” the shared object.
• The second action that arrives needs to wait until the first action’s transaction completes.
• (we’ll define conflicting action more precisely later)

90

transactions

Strict Two-Phase Locking (Strict 2PL)

Phase 1: During the transaction, lock objects before use. �Two types of locks:

• S lock: Before executing R1(O), transaction T1 �must acquire a shared lock on O.
• X lock: Before executing W1(O), transaction T1 �must acquire an exclusive lock on O.

Phase 2: At the end of the transaction (i.e., � COMMIT or ROLLBACK),� release all locks at once.

91

The Strict 2PL algorithm allows only serializable schedules!

Note that schedules can result in deadlock. See Discussion for more info/practice!

transactions

Strict Two-Phase Locking (Strict 2PL), Practically

What objects are we locking?

• For most purposes, assume the DBMS is locking individual records.
• It is sometimes useful to lock entire tables at once (e.g., to change a schema/a default attribute), but we won’t go into detail.

What does it mean to “acquire” or “release” a lock?

• Under the hood: DBMS maintains some of “lock table” according to an internal protocol.
• The system ensures that all transactions follow the internal protocol’s locking rules.
• Analogy: red lights at intersections. You trust the protocol.

92

transactions

[Extra]

Determining Serializability: Conflict Graphs

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Conflicting Actions

[Extra] Conflict Graphs

[Extra] Conflict Serializable

Weak Isolation

[Extra] Additional slides

93

Lecture 22, Data 101, Spring 2025

[Exercise] Determining Conflicting Actions

94

time

1.

2.

🤔

What are the conflicting actions in each of the schedules?

transactions

[Exercise] Determining Conflicting Actions

95

time

1.

2.

What are the conflicting actions in each of the schedules?

1. W1(P) and W2(P)�// write/write to same object

2. R1(G) and W2(G); // read/write same obj� W1(P) and R2(P) // read/write same obj

transactions

[Exercise] Determining Serializability

Suppose we have the following conflicting actions:

1. W1(P) and W2(P)

2. R1(G) and W2(G); W1(P) and R2(P)

Which of the following schedules are serializable?

96

time

1.

2.

A. Serializable schedule, i.e., equivalent to some serial schedule of T1 and T2

B. Unserializable schedule, i.e., no equivalent serial schedule exists

🤔

(no slido)

transactions

[Exercise] Determining Serializability

Suppose we have the following conflicting actions:

1. W1(P) and W2(P)

2. R1(G) and W2(G); W1(P) and R2(P)

Which of the following schedules are serializable?

97

time

1.

2.

A. Serializable! Equivalent to T2 happening before T1.

B. Unserializable! Conflicting actions can’t be “flipped.”

transactions

An Algorithm for Determining Serializability

Serializability of a schedule can be determined by drawing its conflict graph.

• One node per transaction Ti.
• Edge from Ti to Tj if:
• Action a in Ti conflicts with Action b in Tj, AND
• Action a happens before Action b in the schedule.

98

An Algorithm for Determining Serializability

Serializability of a schedule can be determined by drawing its conflict graph.

• One node per transaction Ti.
• Edge from Ti to Tj if:
• Action a in Ti conflicts with Action b in Tj, AND
• Action a happens before Action b in the schedule.

99

time

1.

2.

T₁

T₂

Given: Conflicting actions

1. W1(P) and W2(P)

2. R1(G) and W2(G); � W1(P) and R2(P)

Serializable!

Unserializable!

An Algorithm for Determining Serializability

Serializability of a schedule can be determined by drawing its conflict graph.

• One node per transaction Ti.
• Edge from Ti to Tj if:
• Action a in Ti conflicts with Action b in Tj, AND
• Action a happens before Action b in the schedule.

100

time

1.

2.

T₁

T₂

Given: Conflicting actions

1. W1(P) and W2(P)

2. R1(G) and W2(G); � W1(P) and R2(P)

Serializable!

Unserializable!

T₁

T₂

An Algorithm for Determining Serializability

101

time

1.

2.

Serializable! Equivalent to T2 happening before T1.

Unserializable! Conflicting actions can’t be “flipped.”

If the conflict graph has no cycles (acyclic), then the schedule is serializable. Otherwise, it has cycles and it is unserializable.

T₁

T₂

T₁

T₂

Given: Conflicting actions

1. W1(P) and W2(P)

2. R1(G) and W2(G); � W1(P) and R2(P)

(proof later)

transactions

How do we know if a schedule is serializable?

We like serializable schedules.

• Isolation, again: For multiple concurrent transactions, after the dust settles, transactions appear to have happened in some order (which may seem “arbitrary”). However:
• The order means that the transactions appear to have followed a serial schedule.
• The order means that transactions can be “rolled back” one-by-one.

102

Conflicting actions between transactions will determine if a schedule is serializable.

We did it!

The strategy for a determining serializability of a given schedule of interleaved transactions:

1. Identify the conflicting actions.
2. Draw the conflict graph.
3. If the conflict graph is acyclic, then the schedule is serializable. Else, it is unserializable.

🌟

transactions

[Extra]

Formal Terminology: Conflict Serializable

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Conflicting Actions

[Extra] Conflict Graphs

[Extra] Conflict Serializable

Weak Isolation

[Extra] Additional slides

103

Lecture 22, Data 101, Spring 2025

Why does acyclic conflict graph → serializability?

Observations:

• The acyclic graph has a natural traversal order.
• An order of conflicting actions will guide us to an equivalent serial schedule.
• To make #1’s serial schedule: Move all T2 actions first, move all T1 actions second.
• We cannot do this “bulk” moving for #2, because of the cycle. So no equiv. serial schedule!!

​

104

W₁(P)

R₂(P)

R₁(G)

W₂(G)

order

1.

2.

T₁

T₂

T₁

T₂

Unserializable! Conflicting actions can’t be “flipped.”

Serializable! Equivalent to T2 happening before T1.

no cycles!

cycles!

transactions

Formal Terminology: Conflict Serializable Schedule

Def A schedule is conflict serializable if and only if the conflict graph is acyclic (has no cycles).

​

​

Observations:

• The acyclic graph has a natural traversal order.
• An order of conflicting actions will guide us to an equivalent serial schedule.
• To make #1’s serial schedule: Move all T2 actions first, move all T1 actions second.
• We cannot do this “bulk” moving for #2, because of the cycle. So no equiv. serial schedule!!

105

transactions

Formal Terminology: Conflict Serializable Schedule

Def A schedule is conflict serializable if and only if the conflict graph is acyclic (has no cycles).

​

​

Observations:

• The acyclic graph has a natural traversal order.
• An order of conflicting actions will guide us to an equivalent serial schedule.
• To make #1’s serial schedule: Move all T2 actions first, move all T1 actions second.
• We cannot do this “bulk” moving for #2, because of the cycle. So no equiv. serial schedule!!

106

Lemma

If a schedule is conflict serializable, then it is serializable.

Proof:

• By definition of conflict serializable, the given schedule has an acyclic conflict graph.
• Any serial schedule that follows the edges of the given conflict graph has the same ordering of conflicting actions and is therefore equivalent to the given schedule.
• By definition of serializable, the given schedule is therefore serializable.

transactions

[Extra] The converse is not true

Note that some serializable schedules are not necessarily conflict serializable!

From R&G Database Management Systems, Third Edition, Section 17.1, Figure 17.1 (p.550-1):

This schedule is equivalent to executing the transactions serially in the order T1, T2, T3, but it is not conflict equivalent to this serial schedule because the writes of T1 and T2 are ordered differently.

107

transactions

[Extra] Weak Isolation: Read Commit

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Conflicting Actions

[Extra] Conflict Graphs

[Extra] Conflict Serializable

Weak Isolation

[Extra] Additional slides

108

Lecture 22, Data 101, Spring 2025

“Read Committed” Isolation level

• What if we dropped each Shared lock right after reading
• But kept our eXclusive locks until COMMIT/ROLLBACK?
• Prevents “dirty” (uncommitted) reads from other transactions
• Each read is of an unlocked/committed item!
• Doesn’t promise much more!

​

• This isolation level is called Read Committed
• Note: respects the locks of other, Strict 2PL transactions

109

transactions

Does it help us?

110

BEGIN � ISOLATION LEVEL serializable;

UPDATE students

SET gpa = 4.0

WHERE sid = 1234;

END;

BEGIN

ISOLATION LEVEL read committed;

SELECT avg(gpa)

FROM students;

END;

Locks every student but doesn’t need to be 100% correct!

Locks 1 student but must be serializable!

transactions

What could go wrong in Read Committed?

• Non-repeatable reads
• Suppose you read a tuple twice in your transaction
• Another transaction could run between the two reads and update it!

​

• Phantoms
• Suppose you run a query with a non-key WHERE clause
• E.g. “find all students with an A grade”
• If you run it again, some brand new tuples (phantoms) could appear!

​

• Staleness: Technically you could read a very old (but committed) “version”
• Still satisfies the definition!

111

transactions

Repeatable Read Isolation

• Prevents dirty reads and non-repeatable reads

​

• A locking-based way to think about it:
• All locks are held until COMMIT/ROLLBACK
• But could be only tuple-level locks

​

• So phantoms are still possible!

​

112

transactions

Snapshot Isolation is not (quite) Serializable

113

Time

Pat (T₁)

Gabi (T₂)

P₀: 200000

G₀: 100000

Set my salary to be 10% bigger than Gabi’s

Set my salary to be 10% bigger than Pat’s

NOT equivalent to either order (not serializable!)

​

Write skew anomaly: concurrent reads, and writes reflect the fact that they didn’t read each other’s writes!

transactions