Database Management Systems

-- Bank Transfer Transaction
BEGIN TRANSACTION;
    UPDATE Accounts SET balance = balance - 500 WHERE id = 1;  -- Debit
    UPDATE Accounts SET balance = balance + 500 WHERE id = 2;  -- Credit
COMMIT;

-- If any operation fails, ROLLBACK undoes all changes

┌─────────┐    begin    ┌──────────────┐
│  Active │ ──────────> │ Partially    │
│         │             │ Committed    │
└────┬────┘             └──────┬───────┘
     │                         │
     │ failure                 │ commit
     ↓                         ↓
┌─────────┐             ┌──────────────┐
│ Failed  │             │  Committed   │
└────┬────┘             └──────────────┘
     │
     │ rollback
     ↓
┌─────────┐
│ Aborted │
└─────────┘

# ACID Example: Bank Transfer

# Atomicity: 
# If credit fails after debit, entire transaction rolls back
# Money doesn't disappear!

# Consistency:
# Total balance before = Total balance after
# CHECK constraints enforced

# Isolation:
# Two transfers happening simultaneously don't mix up
# Each sees consistent snapshot

# Durability:
# Once COMMIT returns, changes are permanent
# Survives power failure, crashes

Transaction T1: R(A), W(A), R(B), W(B)
Transaction T2: R(A), W(A), R(B), W(B)

Serial Schedule S1: T1 then T2
R1(A) W1(A) R1(B) W1(B) R2(A) W2(A) R2(B) W2(B)

Serial Schedule S2: T2 then T1
R2(A) W2(A) R2(B) W2(B) R1(A) W1(A) R1(B) W1(B)

Interleaved Schedule:
R1(A) R2(A) W1(A) W2(A) R1(B) R2(B) W1(B) W2(B)
(May or may not be correct!)

Conflicting Pairs:
• R1(A) ... W2(A)  ← Read-Write conflict
• W1(A) ... R2(A)  ← Write-Read conflict
• W1(A) ... W2(A)  ← Write-Write conflict

Non-conflicting:
• R1(A) ... R2(A)  ← Both reads (OK!)
• R1(A) ... W2(B)  ← Different items (OK!)

A schedule is CONFLICT SERIALIZABLE if it can be transformed 
into a serial schedule by swapping non-conflicting operations.

Testing: Build Precedence Graph
• Node for each transaction
• Edge Ti → Tj if conflicting operation of Ti precedes Tj

If graph has NO CYCLE → Conflict Serializable!
Any topological order gives equivalent serial schedule.

# Schedule: R1(A) W2(A) R2(B) W1(B)

# Conflicts:
# R1(A) before W2(A): T1 → T2 (read-write on A)
# R2(B) before W1(B): T2 → T1 (read-write on B)

# Precedence Graph:
# T1 → T2 (from A)
# T2 → T1 (from B)

# CYCLE DETECTED: T1 → T2 → T1
# Schedule is NOT conflict serializable!

More permissive than conflict serializability.

Schedule is view equivalent to serial if:
1. Same initial reads (Ti reads initial value of X in both)
2. Same write-read dependency (if Ti reads X from Tj in S, same in S')
3. Same final writes (last write on X is by same Ti)

View Serializable ⊇ Conflict Serializable
Testing is NP-Complete!

Lock Types:
• Shared Lock (S): For reading, multiple allowed
• Exclusive Lock (X): For writing, exclusive access

Compatibility Matrix:
         | S-lock | X-lock |
---------|--------|--------|
S-lock   |      |      |
X-lock   |      |      |

Rules:
• Read: Acquire S or X lock
• Write: Acquire X lock
• Release when done

Phase 1 (Growing): Only acquire locks, never release
Phase 2 (Shrinking): Only release locks, never acquire

┌──────────────────────────────────────────┐
│  Growing Phase    │   Shrinking Phase    │
│  (acquire only)   │   (release only)     │
│                   │                      │
│     /    LOCK   │           UNLOCK     │
│    /     POINT   │                     │
│   /             │                      │
│──/──────────────│──────────────────────│
│                  │                        │
└──────────────────────────────────────────┘
                Time →

2PL GUARANTEES: Conflict Serializability

-- Strict 2PL Example
BEGIN;
LOCK TABLE Accounts IN ROW EXCLUSIVE MODE;

-- All operations...
UPDATE Accounts SET balance = balance - 100 WHERE id = 1;
UPDATE Accounts SET balance = balance + 100 WHERE id = 2;

-- Locks held until COMMIT
COMMIT;  -- Now all locks released

T1: Lock(A), Lock(B)
T2: Lock(B), Lock(A)

Timeline:
T1: Lock(A)
T2: Lock(B)
T1: Lock(B) - WAIT (T2 holds B)
T2: Lock(A) - WAIT (T1 holds A)

DEADLOCK! Both waiting forever.

# Wait-Die (older waits, younger dies)
# If Ti requests lock held by Tj:
#   if Ti is older: Ti waits
#   if Ti is younger: Ti aborts (dies)

# Wound-Wait (older wounds, younger waits)
# If Ti requests lock held by Tj:
#   if Ti is older: Tj aborts (wounded by Ti)
#   if Ti is younger: Ti waits

# Both prevent deadlock by ensuring one direction of waiting

Wait-For Graph:
• Node for each transaction
• Edge Ti → Tj if Ti is waiting for Tj

If graph has CYCLE → DEADLOCK!

Resolution: Pick a victim transaction and abort it
Victim selection criteria:
• Least work done
• Most locks held
• Newest transaction
• Least likely to deadlock again

Each transaction Ti gets timestamp TS(Ti) when it starts.

For each data item X:
• WTS(X) = Timestamp of last successful write
• RTS(X) = Timestamp of last successful read

Read Rule (Ti wants to read X):
• If TS(Ti) < WTS(X): Ti too old, ABORT and restart
• Else: Read OK, update RTS(X) = max(RTS(X), TS(Ti))

Write Rule (Ti wants to write X):
• If TS(Ti) < RTS(X): Someone newer already read, ABORT
• If TS(Ti) < WTS(X): Thomas Write Rule (skip or abort)
• Else: Write OK, update WTS(X) = TS(Ti)

If TS(Ti) < WTS(X):
• Standard: Abort Ti
• Thomas Rule: Ignore obsolete write (don't abort!)

Why? The value Ti would write is already obsolete.
A newer transaction has already written.
So we can skip Ti's write without affecting correctness.

Benefits: Fewer aborts, better throughput

Rule: Log record written to disk BEFORE data page.

Log Record Format:
<Ti, X, old_value, new_value>

Operations:
UNDO(Ti): Restore X to old_value
REDO(Ti): Apply new_value to X

Recovery guarantees durability even after crash.

ARIES = Algorithms for Recovery and Isolation

Three Phases:
1. ANALYSIS: Scan log, identify dirty pages and active txns
2. REDO: Reapply all logged changes (even for aborted txns)
3. UNDO: Undo changes of uncommitted transactions

Key Concepts:
• LSN (Log Sequence Number): Unique ID for each log record
• Pagelsn: LSN of last log record affecting page
• Checkpointing: Periodic snapshot to limit recovery work

Checkpoint = Consistent snapshot point in log

Simple Checkpoint:
1. Stop all transactions
2. Write dirty pages to disk
3. Write checkpoint record to log

Fuzzy Checkpoint:
• Allows transactions to continue
• Records active transactions and dirty pages
• Recovery starts from checkpoint

-- SQL Standard Isolation Levels
SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
SET TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

Dirty Read:
T1 writes, T2 reads, T1 aborts
→ T2 read uncommitted (dirty) data

Non-repeatable Read:
T1 reads X, T2 updates X, T1 reads X again
→ T1 sees different values for same read!

Phantom Read:
T1 reads rows matching condition, T2 inserts new matching row
→ T1's second read sees "phantom" new rows