CSC 173, Fall 2006

Assignment 1: Relational Database

DUE DATE:

11:59 p.m. September 25, 2006.

NO EXTENSIONS.

Project Overview

You are to design and build a simple database system in Java. Your system must support databases with a variety of schemes. We will make several simplifying assumptions to keep the project managable:

1. All data will fit in main memory.
2. The columns of a relation will be numbered (and thus ordered), but not named. To make life simple in Java column numbers will start at zero.
3. All data can be stored as character strings.

Relation abstract data type

You should begin by creating a Java class (ADT) to represent a relation. Your relation class should have two constructors. The first will create an empty relation with a given number of columns. The second will take a second argument that specifies a file name from which initial data for the relation should be read. You may assume that tuples in the file are separated by newline characters and that fields (attributes) within a tuple are separated by tabs. You should deal gracefully with invalid file contents (e.g. a line with too few or too many attributes), printing an appropriate error message and producing a well-defined result.

Internally, you may represent a relation as an array of Java strings.

In addition to the constructors, your ADT should provide the following methods:

print

print the relation as lines of tab-separated fields on the screen.

insert

insert a given tuple into the relation.

delete

remove from the relation all tuples matching a given predicate.

lookup

(a.k.a. select) return a new relation containing all tuples from the original relation that match a given predicate.

project

return a new relation that is the projection of the given relation onto a given list of fields. If the original relation has six fields, for example, and [1, 4, 2] is the list onto which to project, tuple (a, b, c, d, e, f) in the original relation would become tuple (b, e, c) in the new.

join

return the join of the original relation and a relation passed as a argument, equating the last field of the original relation with the first field of the argument, in such a way that the fields of the original relation precede those of the argument in the result. Note that this very simplistic notion of join (without attribute names) will generally need to be used in conjunction with projection operations that reorder the fields of the arguments and result.

union

return the union of the original relation and a relation passed as an argument.

intersect

return the intersection of the original relation and a relation passed as an argument.

Several of these methods will be easier to implement if your relation class supports the standard Enumeration or Iterator interface.

For the purposes of delete and lookup methods, a predicate is a triple consisting of

1. attribute identifier (field number)
2. comparison test (<=, <, >=, >, ==, !=) — to be performed lexicographically on strings
3. attribute identifier or string constant

Query language

To allow a user to manipulate the database, you will need a command language and a way to refer to relations. You should maintain, internally, a mapping from single-character relation names (lower case letters will suffice) to the relation (if any) named by that character. This mapping can be a simple array. Your system should then read a sequence of commands from standard input, one command per line. Valid commands are as follows:

• c: create a new relation

    	c a 4 filename
        

  This command creates a new relation a with 4 fields, and reads the data for the relation from the (optional) file specified.

• a: add a tuple to a relation

            a b "foo" "3" "hi, mom"
        

  This command adds a tuple into the existing relation b. The number of additional arguments after the b must equal the number of attributes in relation b.

• o: output a relation

    	o a
        

  This command will print relation a created above.

• p: project a relation on a list of fields

    	p a 2 3 4 b
        

  This command will project relation a onto 2 fields (fields numbers 3 and 4 in relation a) producing relation b.

• j: join two relations producing a third

    	j a b c
        

  This command joins relations a and b on the final field of a and the initial field of b, producing relation c. If a has n fields and b has m, c will have n+m-1.

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

    	s a 1 == 2 b
        

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

    	s a 1 != "foo" b
        

  This command selects those tuples from relation a where field 1 != "foo", 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 field 1 == field 3.

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

• u: create a new relation containing the union of the tuples of two existing relations.

            u a b c
        

  This command creates relation c, giving it all tuples found in a or b. Relations a and b must have the same number of fields.

• i: create a new relation containing the intersection of the tuples of two existing relations.

            i a b c
        

  This command creates relation c, giving it all tuples found in both a and b. Relations a and b must have the same number of fields.

• x: delete an entire relation.

   x a 

  This command deletes relation a, making it unavailable for future operations. You should be certain that the Java garbage collector will remove the data (in other words, remove all references to this Relation).
  
  
• r: read from script file
  
  r script.txt
  
  This command reads all the commands from a script file . The commands in the script file are of the form given above, with each command ending in a newline (i.e., each line in the script file has 1 command). Once all the commands in the file have been executed, you should report the total time taken to execute the whole command. This command will be used to credit you for the efficiency of your database (See the section on database efficiency).
  

In the interests of compact maintainable code, you are encouraged to make maximum use of the Java standard libraries, including the collections framework.

You should of course detect and handle invalid commands. You should print a helpful message, ignore the command, and continue.

If you are not familiar with the Java StringTokenizer class, take a look. It might be useful for parsing your command line or other strings.

Database Efficiency

1. How efficient is an "add tuple" command on your database.
2. How well does your database perform when a large number of tuples are deleted.
   
3. How fast can you merge 2 relations by using union.
4. How fast is the intersection operation on two relations.

1. The time complexity of each operation your database supports. For example, if you store the database as a linked list, a delete would take O(n) time.
2. The actual time taken for you to run the script files provided in the test data (see section on TURN IN for test data).
   

Tools

You are encouraged to work on the CSUG systems (especially exploiting remote access) to become familiar with the environment.

That said, you may work on any platform you like, but (1) your final code must compile and run correctly using the javac compiler and java virtual machine on the csug Linux machines, and (2) you must hand in your work using the appropriate turnin script on those machines.

javac is Sun's version 1.5.0 compiler for Linux. Extensive documentation for javac is available on-line in HTML.

What/how to turn in

Here is the sample test data.  There is a README in the test data, you should read it for instructions on how to use the data.

TURN IN: your turnin should include the following

• As a general guideline, follow the  instructions . Reread the instructions for grading and what to include when you submit your project, specifically the README. Clearly indicate how you tested your project, and include any additional test files you may have created yourself.
• ALSO report in the README, the efficiency as mentioned in the above section on database efficiency.

Extra Credit Suggestions

For extra credit, you might consider the following options:

• Make your database as efficient as possible: You will get extra credit if your database works fast (as compared to the rest of the class) on the script files provided. The TAs
  will also be testing your database on their own test data.
  
• Allow fields (attributes) to have different types, e.g. to support true numeric data.
• Support set difference operations.
• Extend the join operation to permit joins on specified pairs of fields.
• Allow complex queries consisting of combinations of simple queries, specified all together (hard).

If you do any extra credit, remember to document it. If you do not, you will likely not get credit for the work. You should also provide test data, and a description of how to use the test data to show that your extensions do what you claim.