CSE 414 Section 6

Serializability & Locking

May 4th, 2023

Announcements

• HW 4 late due date tomorrow
• Midterm released TODAY at noon
• Due Saturday 5/6 at noon
• HW 5 released Sunday 5/6
• Another written HW

Recap: 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 different txn on the same element), 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)

Are these serializable? Conflict serializable?

Serializability

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

Conflict Serializable

Recap: ACID

Transactions have 4 main properties:

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

Locking Overview

Remember - locking is for database internal implementation

• A way to provide the ACID guarantees
• Pessimistic concurrency control
• Assumes transaction executions will conflict
• Users of a database need only specify �BEGIN TRANSACTION … COMMIT / ROLLBACK
• ...and the isolation level...

Database Lock

Table Lock

Predicate Lock

Tuple Lock

Lock Granularity

SQLite!

Less Concurrency

More Concurrency

All the Locks!

Binary Locks

2PL with Binary Locks

Lock growing phase

Lock shrinking phase

2PL vs. Strict 2PL

Invalid reads

Trickled unlock and transaction end

2PL vs. Strict 2PL

2PL:

• In every transaction, all lock requests must precede all unlock requests
• Ensures conflict serializability
• Might not be able to recover (Dirty Read: Read on some write that gets rolled back)
• Can result in deadlocks

Strict 2PL:

• Every lock for each transaction is held until commit or abort
• Ensures conflict serializability
• Recoverable as each transaction does not affect others until commit/abort
• Can result in deadlocks