The impetus for this project was to hack on something in OCaml. I had just spent the last few months doing a bunch of functional DSA in OCaml, but was looking to do a larger project. After getting some advice to look into the underlying structure and implementations of database algorithms, I decided to try implementing a minimally-workable B+ tree in OCaml.
The idea for creating the top-level REPL with ocamllex and menhir came from stumbling upon a video going through a small language implementation.
Note
A lot of credit for getting to write to disk, as noted in the acknowledgements, comes from the blogs written by Artjom Plaunov. I encourage you to check out their blogs and work.
High-level overview of todos/roadmap
| # | Step | Status |
|---|---|---|
| 1 | Basic REPL and interpreter setup | ✔ |
| 2 | Disk-writing API | ✔ |
| 3 | B+ Tree algorithms | in progress |
| 4 | Basic Top-level SQL Parsing | ✔ |
| 5 | Stretch goals... TBD | ❌ |
This project is built and executed with Dune. After cloning the repo, from the project root, run:
dune buildTo start the REPL, run
dune exec SQCaml You can then run SQL-style commands like:
INSERT INTO Mbta (id, stop_name, rail_line)
VALUES (100, 'Englewood ave.', 'G');Important
The current implementaiton only has a fixed single-table schema of:
(id:int, stop_name:varchar, rail_line:varchar)For a list of accepted commands, see docs
1. A lot of the lower-level disk-writing API was reimplemented from the work by Artjom Plaunov - check out their work.
2. Ideas were also taken from the well-known Let's Build a Simple Database.
🐫︎