Transactions and TCL

November 2, 2023

Data 101, Fall 2023 @ UC Berkeley

Lisa Yan https://fa23.data101.org/

1

LECTURE 21

Join at slido.com�#transactions

ⓘ

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

Parallelism is a Big Topic in data systems design!

When updating data, we want correctness as well as speed, particularly when users are accessing and modifying the same database system.

• Complexity in understanding APIs and guarantees of correctness
• (even more complexity in implementation under the covers; see CS186)

Our goal in this course is twofold:

• Genuine understanding of the APIs and subsequent guarantees; and
• To facilitate said understanding, a solid intuition about the underlying implementation.

3

#transactions

Two Main Features We Expect from our Database System

When updating data, we want correctness as well as speed, particularly when users are accessing and modifying the same database system.

• Complexity in understanding APIs and guarantees of correctness
• (even more complexity in implementation under the covers; see CS186)

Our goal in this course is twofold:

• Genuine understanding of the APIs and subsequent guarantees; and
• To facilitate said understanding, a solid intuition about the underlying implementation.

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…

4

We first need to understand the definition of a unit of work that should appear to happen all-at-once: a transaction.

#transactions

Transactions

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Determining Serializability:

• Conflicting Actions
• Conflict Graphs

Formal Terminology: Conflict Serializable

Weak Isolation

Additional Slides

5

Lecture 21, Data 101 Fall 2023

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 transaction�i.e., moving money from�one account (1111) to another (9999).

6

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 is a Transaction?

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

Classic example: Debit/Credit transaction�i.e., moving money from�one account (1111) to another (9999).

7

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 is a Transaction? Observations

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

Classic example: Debit/Credit transaction�i.e., moving money from�one account (1111) to another (9999).

8

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 about defining “happen together”:

1. We need both commands (debit and credit) to happen, i.e., we should not have partial transactions.
2. If the full transaction succeeds, database constraints should still be satisfied.
3. Even if there is another transaction happening simultaneously, one should appear to have finished “first”
4. The transaction should appear to have happened even if there is a power failure/reboot later.

We’ll come back to this!!

#transactions

SQL TCL

9

Image: source

Data Definition Language

Transaction Control Language

Data Manipulation Language

Data�Query Language

Data�Control�Language

our focus today

✅

✅

✅

BEGIN

TCL is used to define transactions as sets of SQL commands that are meant to “happen together.”

#transactions

SQL TCL, Briefly

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

SQL syntax can vary slightly across systems, but generally:

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

10

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

Most systems autocommit, i.e., if BEGIN/COMMIT is not specified, then the system will auto-wrap each individual SQL command in its own transaction.

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

#transactions

Savepoints

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

SQL syntax can vary slightly across systems, but generally:

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

11

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

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.

BEGIN

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

SAVEPOINT debit_done;

UPDATE savings

SET amount = amount + 1000

WHERE acctId = 4322;

SAVEPOINT credit_done;

ROLLBACK TO SAVEPOINT debit_done;

UPDATE savings

SET amount = amount + 1000

WHERE acctId = 4321;

END

destroy

undo

#transactions

The ACID Principle

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Determining Serializability:

• Conflicting Actions
• Conflict Graphs

Formal Terminology: Conflict Serializable

Weak Isolation

Additional Slides

12

Lecture 21, Data 101 Fall 2023

What is a Transaction? Observations

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

Classic example: Debit/Credit transaction�i.e., moving money from�one account (1111) to another (9999).

13

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 about defining “happen together”:

• We need both commands (debit and credit) to happen, i.e., we should not have partial transactions.
• If the full transaction succeeds, database constraints should still be satisfied.
• Even if there is another transaction happening simultaneously, one should appear to have finished “first.”
• The transaction should appear to have happened even if there is a power failure/reboot later.

These four properties, collectively known as ACID, define how transactions can guarantee concurrency control and recovery.

#transactions

ACID: Basic Guarantees

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

​

Atomicity �

​

Consistency

�

Isolation

�.

Durability

​

14

#transactions

ACID: Basic Guarantees

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

​

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

​

Consistency

�

Isolation

�.

Durability

​

15

#transactions

ACID: Basic Guarantees

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

​

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

​

Consistency If COMMIT succeeds, all the database integrity checks hold true.

• primary key/foreign keys, constraints, etc.�

Isolation

�.

Durability

​

16

#transactions

ACID: Basic Guarantees

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

​

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

​

Consistency If COMMIT succeeds, all the database integrity checks hold true.

• primary key/foreign keys, constraints, etc.�

Isolation Concurrent transactions should externally appear to run sequentially.

• i.e., 2 concurrent transactions should not “see” each other’s intermediate results..

Durability

​

17

#transactions

ACID: Basic Guarantees

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

​

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

​

Consistency If COMMIT succeeds, all the database integrity checks hold true.

• primary key/foreign keys, constraints, etc.�

Isolation Concurrent transactions should externally appear to run sequentially.

• i.e., 2 concurrent transactions should not “see” each other’s intermediate results.

Durability 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.

​

​

18

#transactions

What part of the database guarantees ACID for transactions?

Designing these DB components are beyond the scope of this course, but here’s the teaser.

​

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

​

Consistency If COMMIT succeeds, all the database integrity checks hold true.

• primary key/foreign keys, constraints, etc.�

Isolation Concurrent transactions should externally appear to run sequentially.

• i.e., 2 concurrent transactions should not “see” each other’s intermediate results.

Durability 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.

​

​

19

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

What part of the database guarantees ACID for transactions?

Designing these DB components are beyond the scope of this course, but here’s the teaser.

​

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

​

Consistency If COMMIT succeeds, all the database integrity checks hold true.

• primary key/foreign keys, constraints, etc.�

Isolation Concurrent transactions should externally appear to run sequentially.

• i.e., 2 concurrent transactions should not “see” each other’s intermediate results.

Durability 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.

20

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

#transactions

What part of the database guarantees ACID for transactions?

Designing these DB components are beyond the scope of this course, but here’s the teaser.

​

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

​

Consistency If COMMIT succeeds, all the database integrity checks hold true.

• primary key/foreign keys, constraints, etc.�

Isolation Concurrent transactions should externally appear to run sequentially.

• i.e., 2 concurrent transactions should not “see” each other’s intermediate results.

Durability 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.

21

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

#transactions

[Exercise] ACID

22

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

​

• We need both commands (debit and credit) to happen, i.e., we should not have partial transactions.
• If the full transaction succeeds, database constraints should still be satisfied.
• Even if there is another transaction happening simultaneously, one should appear to have finished “first.”
• The transaction should appear to have happened even if there is a power failure/reboot later.

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

24

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. We need both commands (debit and credit) to � happen, i.e., we should not have partial transactions.

C. If the full transaction succeeds, database constraints � should still be satisfied.

I. Even if there is another transaction happening � simultaneously, one should appear to have finished � “first.”

D. The transaction should appear to have happened � even if there is a power failure/reboot later.

#transactions

[History] Why ACID? Unknown, but…

25

#transactions

Isolation and Serializability

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Determining Serializability:

• Conflicting Actions
• Conflict Graphs

Formal Terminology: Conflict Serializable

Weak Isolation

Additional Slides

26

Lecture 21, Data 101 Fall 2023

Isolation, discussed in terms of object read/writes

Isolation: Concurrent transactions should externally appear to run sequentially.

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

27

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, discussed in terms of object read/writes

Isolation: Concurrent transactions should externally appear to run sequentially.

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

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

28

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!

#transactions

Notation

Isolation: Concurrent transactions should externally appear to run sequentially.

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

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

29

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!

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

• “Objects” are records (for now)
• i-th transaction has Read:� R_i(O)
• i-th transaction has Write:� W_i(O = value)

R₁(X₁)

W₁(X₁ = X₁-275000)

W₁(Y₁ = (“VPE”, “Mercy”))

W₃(Q₃ = …, Q₁₁=..., )

R₂(X_1-100000)

W₂(Z₁=…)

#transactions

Determining Transaction Schedules that Maintain Isolation

Our goal: Allow multiple transactions to 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.

30

#transactions

1. 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.

31

#transactions

1. 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.

32

-- 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 Gabi’s salary to 10% more �-- than Parth’s

UPDATE employee

SET salary = (SELECT salary*1.1

FROM employee

WHERE name='Parth')

WHERE name = Gabi';

T₁:

T₂:

#transactions

1. 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.

33

T₁:

T₂:

A proposed Transaction Schedule�of T1 and T2

time

In a transaction schedule, we separate the transactions by column.

#transactions

1. 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.

34

T₁:

T₂:

A proposed Transaction Schedule�of T1 and T2

time

#transactions

2. Serial Schedules

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

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

35

T₁:

T₂:

Serial schedules, as defined, satisfy the isolation property of ACID.

serial schedule

time

serial schedule

not a serial schedule;�transactions interleaved

#transactions

2. Serial Schedules

36

serial schedule

time

serial schedule

not a serial schedule;�transactions interleaved

• It is okay that these two serial schedules produce non-equivalent database outcome states!
• What matters for isolation is that if we executed either of these serial schedules, from the DBMS’s POV, transactions were executed sequentially.

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

​

T₁:

T₂:

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

#transactions

3a. Equivalency of Database Outcomes

37

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

​

T₁:

T₂:

time

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

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

serial schedule

#transactions

3b. Serializable Schedules

38

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

​

T₁:

T₂:

time

A serializable schedule is a transaction schedule whose database outcome is equivalent to some serial schedule.

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

serial schedule

#transactions

3c. Unserializable Schedules

39

serial schedule

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

​

T₁:

T₂:

time

A serializable schedule is a transaction schedule whose database outcome is equivalent to some serial schedule.

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

Note that not all schedules are serializable; the above is an unserializable schedule, because there is no serial equivalent, and therefore transactions do not appear isolated.

⚠️

#transactions

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.

40

serial schedule

serializable schedule

unserializable schedule

#transactions

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.

41

We want systems that can provide serializability, i.e., guarantee steps 2 or 3 for all executed schedules.

serial schedule

serializable schedule

unserializable schedule

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

• This allows multiple transactions to run at once.
• Much better for performance!!

❌

#transactions

A Joke

42

#transactions

Strict 2-Phase Locking

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Determining Serializability:

• Conflicting Actions
• Conflict Graphs

Formal Terminology: Conflict Serializable

Weak Isolation

Additional Slides

43

Lecture 21, Data 101 Fall 2023

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 (defined precisely later).

44

#transactions

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 (defined precisely later)

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)

45

#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.

46

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

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.

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.

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

47

#transactions

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 (defined precisely later now).

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 now).

48

#transactions

Determining Serializability:

Conflicting Actions

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Determining Serializability:

• Conflicting Actions
• Conflict Graphs

Formal Terminology: Conflict Serializable

Weak Isolation

Additional Slides

49

Lecture 21, Data 101 Fall 2023

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.

50

#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.

51

#transactions

Which of the following are 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.

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

52

🤔

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.

A.

B.

C.

D.

E.

#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?

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.

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

54

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.

A.

B.

C.

D.

E.

#transactions

Which of the following are 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.

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

55

can be flipped! no conflicts!

cannot be flipped! conflicting actions!

#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.

56

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

You probably still don’t believe me yet! Let’s keep looking.

#transactions

Which of the following are conflicting actions?

57

A.

B.

C.

D.

E.

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.

[for review next time]

#transactions

Determining Serializability: Conflict Graphs

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Determining Serializability:

• Conflicting Actions
• Conflict Graphs

Formal Terminology: Conflict Serializable

Weak Isolation

Additional Slides

58

[for next time]

Lecture 21, Data 101 Fall 2023

Formal Terminology: Conflict Serializable

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Determining Serializability:

• Conflicting Actions
• Conflict Graphs

Formal Terminology: Conflict Serializable

Weak Isolation

Additional Slides

59

[for next time]

Lecture 21, Data 101 Fall 2023

Weak Isolation

Transactions

The ACID Principle

Isolation and Serializability

Strict 2-Phase Locking

Determining Serializability:

• Conflicting Actions
• Conflict Graphs

Formal Terminology: Conflict Serializable

Weak Isolation

Additional Slides

​

60

[for next time]

Lecture 21, Data 101 Fall 2023

Additional Slides

61

Lecture 21, Data 101 Fall 2023

Protocol for Writes (Exclusive locks)

• W₁(O):
• Check: Is O in the lock table?
• If no:
• Add entry (O, X, T₁, NULL) to lock table
• Allow T₁ to write O and proceed
• If so:
• Add T₁ to the Wait Queue for O

62

#transactions

Protocol for Reads (Shared locks)

• R₁(O):
• Check: Is O in the lock table?
• If no:
• Add entry (O, S, T₁, NULL) to lock table
• Allow T₁ to read O and proceed
• If so
• Check: is lock mode S?
• If so:
• Add T₁ to the Granted list for O
• Allow T₁ to read O and proceed
• If no, lock mode is X.
• Add T₁ to the Wait Queue for O

63

#transactions

Protocol for X Lock Release

• Release T₁(O):
• Check: Is Wait Queue empty?
• If so:
• Delete O’s entry from lock table
• If no:
• Remove all mutually compatible items from the head of the wait queue (multiple S locks or a single X lock)
• Set the lock mode for O to the mode of those items
• Let those transactions proceed

​

64

#transactions

You can prove that:

• Strict 2PL guarantees Conflict Serializability
• All conflicts in the conflict graph are in the same order as the commit times of the transactions.
• No cyclic conflict graphs are possible!

​

65

#transactions

One remaining issue: Deadlock

T1 acquires X-lock on O

T2 acquires S-lock on P

T1 requests X-lock on P.

T1 is descheduled, waiting for T2.

T2 requests S-lock on O

T2 is descheduled, waiting for T1.

​

​

Solution: the system periodically detects deadlock cycles, and rolls back one transaction on the cycle.

66

T₁

T₂

Waits-for Graph. A slightly different kind of graph: each edge shows when a transaction is waiting for another transaction.

​

A cycle corresponds to a deadlock. No serializability violations happen, but transactions on the cycle are stuck and objects remain locked.

#transactions