SQL SQL In Depth
0%
Guided SQL & Engine Coding Lab

Dual-Session Concurrency Anomaly & Isolation Verifier

A multi-session transaction schedule analyzer implementing Adya dependency serialization graphs (WW, WR, RW anti-dependencies), cycle detection for Dirty Read / Lost Update / Write Skew, and Wait-For Graph deadlock victim selection.

~40 min Advanced Lessons: Hands-On Build: Dual-Session Concurrency Anomaly & Isolation Verifier, ACID Under the Hood: Atomicity (Undo), Consistency, Isolation & Durability (WAL), Transaction Lifecycle: BEGIN, COMMIT, ROLLBACK, SAVEPOINT & Autocommit Hazards, Read Anomalies: Dirty Reads, Non-Repeatable Reads & Phantom Reads Visualized, Write Anomalies: Dirty Writes, Lost Updates, Read Skew & Write Skew, READ UNCOMMITTED & READ COMMITTED: Statement-Level Snapshots in Practice
Guided Algorithm Coding Lab 0/4 Steps Completed

Code & Verify SQL & Storage Engine Invariants in the Browser Workbench

Complete 4 progressive algorithmic steps with guided hints in C++20 (WebAssembly), TypeScript, or JavaScript against automated unit test assertions — zero local setup required.

Architectural Overview

A multi-session transaction schedule analyzer implementing Adya dependency serialization graphs (WW, WR, RW anti-dependencies), cycle detection for Dirty Read / Lost Update / Write Skew, and Wait-For Graph deadlock victim selection.

In production relational and analytical database systems—spanning PostgreSQL, SQLite, MySQL/InnoDB, and DuckDB—understanding how query clauses, schema constraints, index structures, and storage engines execute under the hood separates surface-level query authors from staff-level database engineers. This capstone build lab guides you through implementing Dual-Session Concurrency Anomaly & Isolation Verifier from first principles with deterministic self-test invariants.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Conflict Extraction (WW, WR, RW Anti-Dependencies)

  • Core Database Concept: Identifying Conflicting Operations Across Concurrent Transactions on Shared Keys
  • Target Module: index.js (ConcurrencyAnomalySimulator.extractDependencies)
  • Engineering Specification: Implement extractDependencies(schedule) to scan an ordered list of { tx, op: "R"|"W", key } events and emit { from, to, type: "WW"|"WR"|"RW", key } conflict edges.
  • Implementation Hint: Compare earlier op i and later op j from different txIds on the same key where at least one is a Write.
  • Verification Invariant: deterministic assertion verified in test.js step 1

Step 2: Serialization Graph Cycle Detector

  • Core Database Concept: Testing Conflict-Serializability via Directed Graph Cycle Detection
  • Target Module: index.js (ConcurrencyAnomalySimulator.hasSerializationCycle)
  • Engineering Specification: Implement hasSerializationCycle(edges) to return true if the transaction dependency graph contains a directed cycle (meaning the schedule is not conflict-serializable).
  • Implementation Hint: Build adjacency list from dependency edges and run DFS with visiting/visited sets.
  • Verification Invariant: deterministic assertion verified in test.js step 2

Step 3: Lost Update vs Write Skew Anomaly Classifier

  • Core Database Concept: Distinguishing Single-Object R-R-W-W Lost Updates from Multi-Object RW-RW Disjoint Write Skew
  • Target Module: index.js (ConcurrencyAnomalySimulator.classifyScheduleAnomaly)
  • Engineering Specification: Implement classifyScheduleAnomaly(schedule) to return "SERIALIZABLE", "LOST_UPDATE", or "WRITE_SKEW".
  • Implementation Hint: Check if cycle involves WW+RW on the same key (LOST_UPDATE) vs two RW anti-dependencies on distinct keys (WRITE_SKEW).
  • Verification Invariant: deterministic assertion verified in test.js step 3

Step 4: Lock Manager Wait-For Graph & Deadlock Victim Selector

  • Core Database Concept: Breaking Lock Cycles by Aborting the Youngest / Lowest-Log-Weight Transaction
  • Target Module: index.js (ConcurrencyAnomalySimulator.selectDeadlockVictim)
  • Engineering Specification: Implement selectDeadlockVictim(waitEdges, txWeights) to detect a deadlock cycle and return the victim transaction ID with the lowest txWeights[tx].
  • Implementation Hint: Find transactions involved in a Wait-For cycle and return the one with the minimum workDone score.
  • Verification Invariant: deterministic assertion verified in test.js step 4

Relational & Storage Engine Guarantees

  • Curriculum Domain: Transactions, Isolation & Concurrency
  • Difficulty & Time Budget: Advanced (~40 minutes)
  • Key Architectural Highlights:
    • Adya Serialization Graph builder extracting WW, WR, and RW (anti-dependency) edges from interleaved schedules
    • Automated classification of Lost Update (P4) vs Write Skew (A5B) under Snapshot Isolation
    • Wait-For Graph cycle detection and minimum-cost deadlock victim abort selection
  • Core Primitives & Tags: Isolation Levels, Write Skew, Lost Update, Serialization Graph, Deadlock Detection

Related Curriculum Units

Production Database Context & Verification

This from-scratch relational engine component is engineered with zero external dependencies and deterministic verification harnesses. Every internal database invariant—from three-valued logic (TRUE / FALSE / UNKNOWN), referential integrity, and fan-out-free join pre-aggregation to B+Tree page splits, MVCC snapshot visibility (xmin / xmax), slotted-page compaction, and ARIES write-ahead log crash recovery—is asserted directly in test.js. Use the interactive browser workbench above to complete the 4 guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.