CSE 414: Transactions

Section 6

February 10th, 2022

​

​

Snigdha

Aaditya

Announcements

• HW4 released (due Feb 16th at 11pm)
• Database design and more…
• Continue asking questions on Ed and utilizing OH!!
• Midterm information coming soon

ACID Properties

• Atomic
• Consistent
• Isolated
• Durable

Ideally a DBMS follows these principles, but sacrificing good behavior for performance gains is common.

​

Atomicity

What? “Atom” - a transaction are 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 requiring both first and last name fields will not accept if one of the fields is missing - must enter both for the transaction to be completed

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

How do ACID properties help us?

• Ensure that a transaction maintains database integrity
• ACID compliance matters to important databases ($$$)

Next: delve into the DB Internals required to guarantee ACID

​

​

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’;

​

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(Country) or R(France), depending on whether the "element" is a table or a row (assuming cname is a key). Let's go with the finer-grained element.

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

Serializable schedule - a schedule that is behaviorally equivalent � to a serial schedule even after interleaving.

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

What are the three types of inter-transaction conflicts we discussed in lecture?

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)

Practice - convert SQL to operations

R₁(France)

​

W₁(France)

​

​

R₂(Spain)

​

R₂(France)

W₂(France)

What type of schedule is this?

SERIAL SCHEDULE

Definitions

Non-conflicting swap - �

Conflicting swap -

Conflict serializable schedule - �

​

Definitions - When viewing a schedule...

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

Can swap if: different txns, acting on different elements OR both are Reads

Conflicting swap - (any two ops in same txn) or RW, WR, WW between any 2 txns acting on the same dataset

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

​

How to check for conflict serializability

2 Ways:

1. Swap non-conflicting operations, if serial order, then conflict serializable!
1. Serial order -> one txns happens after the other after swapping, no mixing
2. Draw serializability graph:
• Nodes denote your txns number, one node for every txns
• Draw an arrow from node 1 to node 2 if (RW, WW, WR) conflict from 1 to 2 in schedule
• These conflicts are only between different txns and same data
• If no cycles in graph, then conflict serializable!

Before we look at any examples...

1. You NEVER swap operations within a transaction.
2. While drawing relations between the 2 transaction (to check for conflict serializability), only draw a line IF the conflicting statements act on the same data
3. You can only swap operations if:
1. The operations are from different transactions acting on different data (no possible conflicts)
2. Basically, in the form of W_1(A), W_2(B)

Practice 1 - conflict serializable or not?

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

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

2b) y = y / 5;

1b) x = x + 200;

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

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

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

​

Practice 1 - conflict serializable or not?

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

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

2b) y = y / 5;

1b) x = x + 200;

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

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

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

​

①

②

1c-2c WR�1c-2d WW 1a-2d RW

Practice 2 - conflict serializable or not?

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

2b) y = y / 5;

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

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

1b) x = x + 200;

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

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

Practice 2 - conflict serializable or not?

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

2b) y = y / 5;

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

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

1b) x = x + 200;

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

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

①

②

Transaction Worksheet!

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)