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:

• company.dat contains the Company relation, which has 4 attributes. The first attribute is the company symbol, the second is the company name, the third is the total number of shares that have been issued for that company, and the forth is the price of each share.

• share.dat contains the Shares relation, which has 3 attributes. The first attribute is a mutual fund symbol, the second is a company symbol, and the third is the number of shares purchased by that mutual fund in that company.

• investor.dat contains the Investor relation, which also has 3 attributes. The first attribute is an investor's name, the second is a mutual fund identifier, and the third is the amount the investor has invested in that mutual fund.

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

• construct a new relation (initializing that relation to be empty or containing the data from one of the input files provided)

• destruct an existing relation

• print an existing relation

• insert a tuple in an existing relation

• delete tuples in an existing relation that match a given predicate

• lookup tuples in an existing relation that match a given predicate and return those tuples as a new relation

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

• project, which takes an existing relation R and a list of domain identifiers, and produces a new relation that is the projection of R on those domains.

• join, which takes two existing relations, and produces a third, which is simply the cross-product of the two relations.

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:

• c: create a new relation

    	c a 4 filename
        

  This command creates a new relation "a" with 4 attributes (again, all attributes are 20 character strings), and reads the data for the relation from the (optional) file specified.

• o: output a relation

    	o a
        

  This command will print relation "a" created above.

• p: project a relation on a list of attributes

    	p a 2 3 4 b
        

  This command will project relation "a" on 2 attributes (attribute numbers 3 and 4 in relation "a") producing relation "b".

• j: join two relations producing a third

    	j a b c
        

  This command joins all attributes of relations "a" and "b" producing relation "c".

• s: select a subset of the attributes in a relation, producing a new relation

    	s a 1 = 2 b
        

  This command selects those tuples from relation "a" where attribute 1 = attribute 2, and produces a new relation "b" containing those tuples.

    	s a 1 != 'SGI' b
        

  This command selects those tuples from relation "a" where attribute 1 != 'SGI', and produces a new relation "b" containing those tuples.

  The operators allowed in the select command can be any of the comparison operators supported by your implementation of predicates.

• d: delete tuples that match a predicate from a relation

    	d a 1 = 3
        

  This command deletes those tuples in relation "a" where attribute 1 = attribute 3.

  As with the select command, the second operand of the predicate may be a string, and all of the comparison operations are supported.

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.