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

Mini Relational Tuple Filter & Projection Engine

A relational tuple-at-a-time volcano iterator engine implementing Kleene three-valued logic (TRUE/FALSE/UNKNOWN), WHERE filtering, SELECT projection with expressions, ORDER BY NULLS LAST, and LIMIT/OFFSET slicing.

~30 min Beginner Lessons: Hands-On Build: Mini Relational Tuple Filter & Projection Engine, Filesystems vs. Relational DBMS, Codd's 12 Rules & Declarative SQL, Relations, Tuples, Attributes, Domains & SQL Data Types, SELECT Projection, Expressions, Aliases & Logical Execution Order, WHERE Clause, Comparison Operators, BETWEEN, IN, LIKE & SARGability, Boolean Logic, Operator Precedence & Three-Valued Logic (3VL)
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 relational tuple-at-a-time volcano iterator engine implementing Kleene three-valued logic (TRUE/FALSE/UNKNOWN), WHERE filtering, SELECT projection with expressions, ORDER BY NULLS LAST, and LIMIT/OFFSET slicing.

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 Mini Relational Tuple Filter & Projection Engine from first principles with deterministic self-test invariants.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Kleene Three-Valued Logic (3VL) Evaluator

  • Core Database Concept: Evaluating NULL Comparisons as UNKNOWN and Propagating Through AND / OR / NOT
  • Target Module: index.js (RelationalQueryEngine.eval3VL)
  • Engineering Specification: Implement evalComparison(left, op, right) and combine3VL(op, a, b) using Kleene three-valued logic ("TRUE", "FALSE", "UNKNOWN"). Any standard comparison (=, !=, <, >, <=, >=) where either operand is null or undefined must return "UNKNOWN", whereas IS DISTINCT FROM treats null as a comparable value.
  • Implementation Hint: Map TRUE->1, UNKNOWN->0, FALSE->-1: AND is Math.min(a,b), OR is Math.max(a,b), NOT is -a.
  • Verification Invariant: deterministic assertion verified in test.js step 1

Step 2: WHERE Predicate Filtering (Coercing UNKNOWN to FALSE)

  • Core Database Concept: Filtering Relation Tuples Strictly on Logical TRUE
  • Target Module: index.js (RelationalQueryEngine.filterWhere)
  • Engineering Specification: Implement filterWhere(rows, predicateFn) to evaluate a 3VL predicate across every input tuple and retain only rows that evaluate to "TRUE" (or boolean true), discarding both "FALSE" and "UNKNOWN" rows just as SQL WHERE clauses do.
  • Implementation Hint: Keep only rows where predicateFn(row) === "TRUE" or predicateFn(row) === true.
  • Verification Invariant: deterministic assertion verified in test.js step 2

Step 3: SELECT Projection & Derived Column Aliases

  • Core Database Concept: Relational Projection π and Computed Tuple Attributes
  • Target Module: index.js (RelationalQueryEngine.projectSelect)
  • Engineering Specification: Implement projectSelect(rows, projections, distinct = false) to transform each input tuple into a projected tuple containing only the requested column names or computed expressions, optionally deduplicating tuples using structural serialization.
  • Implementation Hint: Map each specification { alias, expr } to outRow[alias] = typeof expr === "function" ? expr(row) : row[expr].
  • Verification Invariant: deterministic assertion verified in test.js step 3

Step 4: Multi-Key ORDER BY (NULLS LAST) & LIMIT / OFFSET Slicing

  • Core Database Concept: Deterministic Tuple Ordering and Cursor Window Slicing
  • Target Module: index.js (RelationalQueryEngine.orderByAndSlice)
  • Engineering Specification: Implement orderByAndSlice(rows, orderSpecs, limit, offset) to sort projected tuples across multiple { col, dir, nullsLast } keys without mutating the source relation, then apply offset and limit window bounds.
  • Implementation Hint: Check nullness before comparing values; respect nullsLast flag, then slice(offset, offset + limit).
  • Verification Invariant: deterministic assertion verified in test.js step 4

Relational & Storage Engine Guarantees

  • Curriculum Domain: Relational Foundations
  • Difficulty & Time Budget: Beginner (~30 minutes)
  • Key Architectural Highlights:
    • Kleene 3-valued truth table evaluation (TRUE, FALSE, UNKNOWN) for NULL-safe predicates
    • Logical execution order pipeline: FROM -> WHERE -> SELECT -> DISTINCT -> ORDER BY -> LIMIT/OFFSET
    • Deterministic multi-key sorting with configurable NULLS FIRST / NULLS LAST ordering
  • Core Primitives & Tags: Relational Algebra, Three-Valued Logic, Tuple Iterator, Query Pipeline, Projection

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.