How to Build a Minimal Relational Database from Scratch

Relational Database Foundations

Relational databases are based on the relational model, which is mathematically grounded in set algebra. SQL is the declarative language for manipulating relational data, and the theory of normal forms provides design rules that minimise redundancy while preserving relationships.

Architectural Modules of a Database System

Storage layer – core data structures that provide atomic create, read, update, delete (CRUD) operations.

Engine layer – builds on the storage layer to implement transactions, combine storage primitives and expose higher‑level operations (e.g., InnoDB).

SQL parsing layer – parses, analyses and optimises SQL statements, translating them into engine‑layer calls.

UI layer – external interface, typically a network protocol for client interaction.

Additional components such as permission management, caching, logging, backup and binary logs are also common in production systems.

Design of a Minimal Database

The minimal system focuses on three essential functions: persisting data, querying data, and providing a user‑facing interface. These are realised with three thin layers implemented over a few simple files.

Storage Layer Implementation

Data is stored in a binary file where each row has a fixed length. A table schema defines columns with a name, type and declared length. For each column the first four bytes of the field store the actual length, followed by the field content. This layout enables fast offset‑based access while allowing variable‑length values.

A B+‑tree index is built on selected columns. The index stores pointers (file offsets) to rows, providing logarithmic‑time look‑ups – the standard indexing structure in most relational engines.

Typical storage‑layer API: CreateTable([]FieldInfo) – creates a table given column names, types and lengths. AddData(map[string]string) – inserts a row; the map keys are column names. Find(fieldName, fieldValue, op) – queries a single column with operators such as =, >, <. GetData(docId) – retrieves a row by calculating its offset from the document identifier.

Query (Engine) Layer

The engine layer implements a tiny subset of SQL: CREATE TABLE, INSERT and SELECT. Instead of a full parser, regular expressions and string matching recognise these statements and invoke the corresponding storage‑layer functions.

For the WHERE clause the expression is converted to Reverse Polish Notation (RPN) and evaluated with a stack. Logical AND and OR are handled by intersecting or unioning intermediate result sets. After the predicate evaluation, GetData fetches the matching rows.

Public entry point: ExecSqlSentence(sql string) string The function accepts an SQL string and returns the query result as a formatted string.

User Interface Layer

A minimal TCP server listens on a configurable port. Clients (e.g., via telnet) send SQL statements terminated by a semicolon; the server passes each statement to ExecSqlSentence and returns the resulting string to the client.

Reference Implementation

The source code is hosted at https://github.com/wyh267/SparrowSys. Repository layout: src/SparrowDB/DataLayer – storage implementation, binary file handling and B+‑tree utilities. src/SparrowDB/EngineLayer – query parsing and execution (partial implementation). src/SparrowDB/NetLayer – TCP server skeleton for the UI layer. utils – shared utilities, including the B+‑tree implementation used by the storage layer.

Future work will complete the engine and network layers, add comprehensive tests, and demonstrate usage examples.