Relational Database

This is a two-part assignment (you will have one week for each part) in which you will implement a simple database system and perform some sample queries on your database.

Part I: Abstract Data Type Relation

In this part of the assignment you will implement an ADT for relations, and build a sample database using your ADT. The data for the relations in the database is located in /u/cs173/pub/assign1 and consists of three separate relations stored in the following text files:

You are to build an in-memory database containing the information in these files. For each relation you should implement an appropriate index structure.

Although all tuples in a relation have the same number of attributes, tuples from different relations may not have the same number of attributes.

For purposes of simplicity, you may represent all attributes in all relations as a character string of length 20.

Programming in C++, you must implement operations to

A predicate is simply a triple consisting of

  1. domain identifier (eg, field number)
  2. operator (<,>,=,!=,<=,>=)
  3. domain identifier or domain value

This part of the assignment is due at the start of class on Tuesday, Jan 26.

Part II: Query Language

In this part of the assignment you will augment your implementation of relations from Part I to incorporate additional operations (projection and join), and in addition, implement a simple query language to access your database.

The new operations are

The format of the query language has been designed to be sufficiently powerful to access the database, while remaining very simple in structure.

Every relation in the input language will be given a name that is a single letter. Every command is also a single letter.

The commands are:

The input to your program is a set of commands that perform some interesting queries on the database.

As a demonstration of your program, write a command language program to perform the following query: find the names of all investors that own stock in Silicon Graphics Inc (indirectly) through a mutual fund.

To illustrate the full functionality of your program, you should also show the results of other queries of your own choosing.

This part of the assignment is due at the start of class on Tuesday, Feb 2rd.


last modified Dec 18 1998 / Randal Nelson