Introduction

In this project you will implement a relational database management system. More specifically, you will implement an RDBMS where the entire database is stored in a single file, similar to the popular SQLite system. The goal of this project is for you to understand how databases work internally, and to understand what happens “under the hood” when you run a SQL query.

The project is completed in three stages:

  1. You will implement a series of functions to create and manipulate file-based B-Trees. The chidb file format is based on the SQLite format and, in fact, chidb files can be opened and manipulated using SQLite. This will show you how files are organized in a real RDBMS.

  2. You will implement a database machine (DBM). In most RDBMS’s, SQL queries are compiled into instructions for a virtual machine (as opposed to being compiled down to x86 instructions). These virtual machines include instructions to seek keys in an index, access specific columns in a database record, etc. We provide you with the basic infrastructure of the DBM, but you must implement all the instructions in the DBM.

    Once you have implemented the database machine, you will implement a SQL compiler. We provide you with a parser and lexer that will parse SQL queries and will provide an internal representation that is similar to relational algebra. You will need to take those representations, and translate them into DBM programs.

  3. You will implement a query optimizer. You will improve your SQL compiler to apply a number of query optimization strategies.

The chidb documentation is divided into the following sections:

  • The chidb File Format and The chidb Architecture: These sections specify the chidb file format and the internal architecture of the chidb RDBMS. Don’t worry if you don’t understand everything in these sections at first; they will become clearer in the programming assignments, which will require you to implement specific portions of these specifications.
  • Installing, Building, and Running chidb: Instructions on how to install, build, and run chidb.
  • Assignment I: B-Trees: The B-Tree assignment (NOTE: additional assignments will be added soon). Please note that your instructor may provide additional instructions on how to do these assignments.
  • Testing your Implementation: Suggestions and strategies for testing your implementation.