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

Bill-of-Materials & Social Graph Reachability Engine

A fixed-point recursive CTE execution engine supporting working-table iteration, UNION vs UNION ALL deduplication, path-array cycle detection, Bill-of-Materials cost rollup, and NULL-safe NOT EXISTS anti-joins.

~40 min Advanced Lessons: Hands-On Build: Bill-of-Materials & Social Graph Reachability Engine, Subquery Taxonomy: Scalar, Row, Array & Derived Table Subqueries, Correlated Subqueries: Outer Reference Binding & Optimizer Unnesting, EXISTS & NOT EXISTS: Short-Circuit Semi-Joins & Complete NULL Safety, LATERAL Subqueries (CROSS APPLY / OUTER APPLY) & Top-N-Per-Group, Common Table Expressions (WITH): Modular Multi-Stage SQL Pipelines
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 fixed-point recursive CTE execution engine supporting working-table iteration, UNION vs UNION ALL deduplication, path-array cycle detection, Bill-of-Materials cost rollup, and NULL-safe NOT EXISTS anti-joins.

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 Bill-of-Materials & Social Graph Reachability Engine from first principles with deterministic self-test invariants.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Fixed-Point WITH RECURSIVE Iterator with Cycle Detection

  • Core Database Concept: Anchor Member + Iterative Working Table Expansion with Visited Path Array
  • Target Module: index.js (RecursiveGraphEngine.traverseHierarchy)
  • Engineering Specification: Implement traverseHierarchy(edges, rootId, maxDepth) using SQL WITH RECURSIVE working-table semantics. Track path: [...parent.path, childId] on every tuple and skip any edge where parent.path.includes(childId) to prevent infinite recursion on cyclic graphs.
  • Implementation Hint: Seed working table with anchor nodes; in each step expand children where !node.path.includes(childId).
  • Verification Invariant: deterministic assertion verified in test.js step 1

Step 2: Bill-of-Materials (BOM) Multiplicative Quantity & Cost Rollup

  • Core Database Concept: Propagating Component Quantities Down Assembly Trees
  • Target Module: index.js (RecursiveGraphEngine.computeBomCost)
  • Engineering Specification: Implement computeBomCost(bomEdges, unitCosts, rootPartId) to recursively expand sub-assemblies, multiplying component quantities along each root-to-leaf path and summing total unit costs.
  • Implementation Hint: Multiply parent.extendedQty * edge.qty down the hierarchy and sum leaf unit_cost * extendedQty.
  • Verification Invariant: deterministic assertion verified in test.js step 2

Step 3: NULL-Safe NOT EXISTS Anti-Join vs NOT IN Trap

  • Core Database Concept: Why NOT EXISTS Succeeds When Subquery Output Contains NULL
  • Target Module: index.js (RecursiveGraphEngine.notExistsAntiJoin)
  • Engineering Specification: Implement notExistsAntiJoin(outerRows, innerRows, key) so that null values in innerRows never poison the anti-join result (unlike NOT IN).
  • Implementation Hint: Return outer rows where !innerRows.some(inRow => inRow[key] !== null && inRow[key] === outRow[key]).
  • Verification Invariant: deterministic assertion verified in test.js step 3

Step 4: Correlated LATERAL Top-K Per Parent Node

  • Core Database Concept: Evaluating a Parameterized Subquery Per Outer Tuple (CROSS APPLY)
  • Target Module: index.js (RecursiveGraphEngine.lateralTopK)
  • Engineering Specification: Implement lateralTopK(parents, children, fkCol, metricCol, k) to execute a correlated top-kk subquery for each parent row.
  • Implementation Hint: For each parent row, filter childRows matching parent.id, sort descending by metricCol, and take k.
  • Verification Invariant: deterministic assertion verified in test.js step 4

Relational & Storage Engine Guarantees

  • Curriculum Domain: Subqueries, CTEs & Recursion
  • Difficulty & Time Budget: Advanced (~40 minutes)
  • Key Architectural Highlights:
    • Fixed-point iterative working-table evaluation matching SQL WITH RECURSIVE semantics
    • Path-vector cycle detection preventing infinite loops on cyclic dependency graphs
    • Bill-of-Materials component multiplication and NULL-safe NOT EXISTS anti-join evaluation
  • Core Primitives & Tags: Recursive CTE, Graph Traversal, Cycle Detection, Bill of Materials, NOT EXISTS

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.