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

Normalize a Legacy Flat Spreadsheet into a 3NF/BCNF System

An algorithmic functional dependency analyzer implementing Armstrong’s Axiom attribute closure X+, candidate key discovery, BCNF violation detection, and lossless-join decomposition.

~40 min Advanced Lessons: Hands-On Build: Normalize a Legacy Flat Spreadsheet into a 3NF/BCNF System, Entity-Relationship Modeling: Cardinality (1:1, 1:N, M:N) & Junction Tables, Functional Dependencies (X → Y), Superkeys, Candidate Keys & Closure, First Normal Form (1NF): Atomic Domains & Repeating Group Anti-Patterns, Second & Third Normal Form (2NF & 3NF): Eliminating Partial & Transitive Dependencies, Boyce-Codd Normal Form (BCNF), Multi-Valued (4NF) & Join Dependencies (5NF)
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

An algorithmic functional dependency analyzer implementing Armstrong’s Axiom attribute closure X+, candidate key discovery, BCNF violation detection, and lossless-join decomposition.

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 Normalize a Legacy Flat Spreadsheet into a 3NF/BCNF System from first principles with deterministic self-test invariants.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Attribute Closure (X+) via Armstrong’s Reflexivity & Transitivity

  • Core Database Concept: Fixed-Point Expansion of Determined Attributes
  • Target Module: index.js (NormalizationEngine.attributeClosure)
  • Engineering Specification: Implement attributeClosure(attrs, fds) to compute the attribute closure X+X^+ of an attribute set attrs under a set of functional dependencies fds = [{ left: [...], right: [...] }].
  • Implementation Hint: Repeatedly add fd.right attributes into closure whenever every attribute in fd.left is already in closure.
  • Verification Invariant: deterministic assertion verified in test.js step 1

Step 2: Superkey & Candidate Key Verification

  • Core Database Concept: Testing Whether X+ Covers All Relation Attributes R
  • Target Module: index.js (NormalizationEngine.isSuperkey)
  • Engineering Specification: Implement isSuperkey(allAttrs, candidateAttrs, fds) by testing whether the attribute closure of candidateAttrs equals the universal attribute set allAttrs.
  • Implementation Hint: Compute attributeClosure(candidateAttrs, fds) and check if every attribute of allAttrs is present.
  • Verification Invariant: deterministic assertion verified in test.js step 2

Step 3: BCNF Violation Detector

  • Core Database Concept: Identifying Non-Trivial FDs X -> Y Where X Is Not a Superkey
  • Target Module: index.js (NormalizationEngine.findBcnfViolations)
  • Engineering Specification: Implement findBcnfViolations(allAttrs, fds) to return every non-trivial functional dependency X→YX \to Y whose determinant XX is not a superkey of allAttrs.
  • Implementation Hint: For each FD, filter out right attributes already in left; if remaining right is non-empty and !isSuperkey(allAttrs, fd.left, fds), record violation.
  • Verification Invariant: deterministic assertion verified in test.js step 3

Step 4: Lossless-Join BCNF Decomposition & Flat-Row Projection

  • Core Database Concept: Splitting R Into R1 = X+ and R2 = (R - (X+ - X)) Without Spurious Tuples
  • Target Module: index.js (NormalizationEngine.decomposeBcnfStep)
  • Engineering Specification: Implement decomposeBcnfStep(allAttrs, violatingFd, fds) to perform one lossless-join BCNF split into { r1, r2 } and project a flat spreadsheet dataset into deduplicated normalized relations.
  • Implementation Hint: Compute closure = attributeClosure(violatingFd.left, fds); R1 = closure, R2 = allAttrs minus (closure - violatingFd.left).
  • Verification Invariant: deterministic assertion verified in test.js step 4

Relational & Storage Engine Guarantees

  • Curriculum Domain: Relational Schema Design & Normalization
  • Difficulty & Time Budget: Advanced (~40 minutes)
  • Key Architectural Highlights:
    • Attribute closure X+ fixed-point computation via Armstrong’s Axioms
    • Minimal superkey / candidate key synthesis over arbitrary functional dependency sets
    • Automated BCNF violation detector and lossless-join relation decomposition
  • Core Primitives & Tags: Functional Dependencies, Attribute Closure, 3NF & BCNF, Lossless Decomposition, Normalization

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.