Database Homework of Berkeley University: Implement A Simple Database Management System.
You can get more details in https://sites.google.com/site/cs186fall2013/homeworks
In the project assignments in CS186, you will write a basic database management system called SimpleDB. For this project, you will focus on implementing the core modules required to access stored data on disk; in future projects, you will add support for various query processing operators, as well as transactions, locking, and concurrent queries.
SimpleDB is written in Java. We have provided you with a set of mostly unimplemented classes and interfaces. You will need to write the code for these classes. We will grade your code by running a set of system tests written using JUnit. We have also provided a number of unit tests that you may find useful in verifying that your code works.
In this project, you will write a set of operators for SimpleDB to implement table modifications (e.g., insert and delete records), selections, joins, and aggregates. These will build on top of the foundation that you wrote in Project 1 to provide you with a database system that can perform simple queries over multiple tables.
Additionally, we ignored the issue of buffer pool management in Project 1: we have not dealt with the problem that arises when we reference more pages than we can fit in memory over the lifetime of the database. In Project 2, you will design an eviction policy to flush stale pages from the buffer pool.
You do not need to implement transactions or locking in this project.
In this project, you will implement a query optimizer on top of SimpleDB. The main tasks include implementing a selectivity estimation framework and a cost-based optimizer. You have freedom as to exactly what you implement, but we recommend using something similar to the Selinger cost-based optimizer discussed in class. The remainder of this document describes what is involved in adding optimizer support and provides a basic outline of how you might add this support to your database.
In this project, you will implement a simple locking-based transaction system in SimpleDB. You will need to add lock and unlock calls at the appropriate places in your code, as well as code to track the locks held by each transaction and grant locks to transactions as they are needed.
- Implemented the classes to manage tuples, namely Tuple, TupleDesc .
- Only support integer and fixed length string fields.
- Implemented Catalog, which keeps track of all available tables in the database and their associated schemas.
- Implemented BufferPool, manages the reading and writing of pages into memory from disk.
- Implemented HeapPage and HeapFile, which BufferPool use to read and write tuples from disk.
- Implemented Operators such as SeqScan(read tuples iteratively), Filter(implements a relational select), Join(implements the relational join operation), Aggregate(computes an aggregate, e.g., sum, avg, max, min).
- Implemented page eviction in BufferPool(LRU policy).
- Implemented Insert and Delete operators.
- Implemented a selectivity estimation framework and a cost-based optimizer(Selinger cost-based optimizer).
- Implemented a simple locking-based transaction system.
- Implemented a NO STEAL/FORCE buffer management policy.
- Implemented a simple dead lock detection policy like cycle-detection in a dependency graph.