Lab 8 - BST-based Database
Due: Monday, April 21th at 11:59PM


This lab asks you to implement a simple BST-based database. Like a real database1, it will be composed of several different trees -- one for each key.

Each record has associate with it two different types of keys: One primary key and more than one secondary key. The primary key is a unique identifier for the record -- there are no duplicates. The seocndary key is an attribute that might apply to multiple records.

A search for a primary key will result in not more than one match. A search for a secondary key may result in multiple matches.

Additionally the database allows for search based on multiple secondary keys using the logical operators AND and OR. For example "Give me a list of all cars that are red and have 4 doors" or "Give me a list of all cars that have 2 doors or a sunroof"

Overall Architecture

This assignment will consist of (at least) several classes and one interface, each of which you are asked to implement.

The SuperComparable interface

This interface is used to specify the classes that can be stored in the BSTs. It extends Comparable and, therefore, should implement compareTo(). The compareTo() method should compare SuperComparables based on only the primary (unique) key.

In addition to the inherited compareTo() definition SuperComparables should implement the following method:

This overloaded compareTo() method should have semantics similar to the inherited compareTo() method, except that the name of the key field is specified, instead of assumed to be the primary key. In other words, it will compare Records based on whatever field, primary or secondary, is named by the parameter. This method will allow the database to implement BSTs that organize secondary keys.

The Record class

The Record class can actually be named whatever you like. In fact, it should probably be named something contextually meaningful within your application, for example Receipe, Car, BaseballCard, &c.

It should contain the attributes of the data type, for example, the uniqueReceipeName, preparationInstructions, ingredientsList, and cookingInstructions.

It should also contain methods that make the class useful for the application. For example, a version of toString() that provides for a pretty display of the record's content is almost certainly required.

Additionally, it should implement the SuperComparable interface so that it can be organized by your BST.

The BST class

The BST class should be your own implementation of a binary search tree. It should organize SuperComparable objects. Minimally, it should implement insert() and retrieve() methods. It need not support delete. The constructor of the tree should specify the key to be used for the comparison as below:

Additionally, it should have a default constructor, which will automatically compare nodes based on the primary key. In other words, if the default constructor is used, the comparison should be made based on the new, overloaded compareTo() method, instead of the inherited compareTo() method:

It is important to note that this BST must be able to handle duplicates. since secondary keys are not unique. You may handle this any way you choose. Three ideas, which just ideas, are the following:

The Database, itself

The Database, itself, should contain one BST for each of the keys. You are required to support one primary key, and at least two secondary keys. So, at a minimum, the Database will contain three BSTs. You are welcome and encouraged to support more than two secondary keys -- but this is not required.

The database should provide the folloing functionality:

One thing we want to stress: Your database's user interface needs to be functional, not pretty or super-friendly. You are welcome to use a simple menu and prompt system -- or, only if you'd like, something more sophisticated.

An Important Caution -- And Some Piece of Mind

This assignment is significantly more complex than those of the past. We expect that you'll need some help. We want to provide it. Please get started early and dig in. We'll be there to help the whole way. And, yes, we'll roll up our sleeves and get dirty along the way. We're here to help.


1 Real data bases are actually based on derivatives of the B-Tree data structure, not BSTs. You'll learn about B-Trees in 15-211. They are balanced trees, so, unlike BSTs, they don't have degenerate cases. The nodes also contain many keys and child pointers, unlike BSTs, where each node contians one key and two pointers.