# Database Transaction Schedule A **schedule** (or history) is the chronological order in which operations from concurrent transactions are executed. ## Operations - `r_i(X)` — Transaction `T_i` reads data item `X` - `w_i(X)` — Transaction `T_i` writes data item `X` - `c_i` — Transaction `T_i` commits - `a_i` — Transaction `T_i` aborts ## Serial vs Non-Serial ```text Serial: r1(A) w1(A) c1 r2(A) w2(A) c2 -- correct but slow Non-serial: r1(A) r2(A) w1(A) w2(A) c1 c2 -- faster but risky ``` ## Serializability A non-serial schedule is **serializable** if its effect equals some serial schedule. ### Conflict Serializability Two operations **conflict** if they: (1) belong to different transactions, (2) access the same data item, (3) at least one is a write. A schedule is conflict serializable if its **precedence graph** is acyclic. ### View Serializability Less restrictive than conflict serializability. The difference arises from [[Blind Write]]s. Testing view serializability is NP-complete, so databases typically use conflict serializability. ## Recoverability Hierarchy ```text Strict ⊂ Cascadeless ⊂ Recoverable ``` - **Recoverable** — if `T_i` reads a value written by `T_j`, then `T_j` must commit before `T_i` - **Cascadeless** — `T_i` reads `T_j`'s write only after `T_j` commits (prevents cascading rollbacks) - **Strict** — neither read nor write until the last writer commits/aborts ## Concurrency Control Protocols | Protocol | Mechanism | |----------|-----------| | **Two-Phase Locking (2PL)** | Growing phase (acquire locks) then shrinking phase (release) | | **Timestamp Ordering** | Operations ordered by transaction timestamps; violations rejected | | **MVCC** | Multiple data versions; readers don't block writers (PostgreSQL, Oracle) | | **Optimistic CC** | Execute freely, validate at commit; works well under low contention | --- See also: [[Blind Write]], [[Write-Write Conflict]]