ICS 23 / CSE 23 - Project #4: Lord of the Ringbinders

Due date and time: Friday, February 26, 6:59pm

Three Rings for the Elven-kings under the sky,
Seven for the Dwarf-lords in their halls of stone,
Nine for Mortal Men doomed to die,
One for the Dark Lord on his dark throne
In the Land of Mordor where the Shadows lie.
One Ring to rule them all, One Ring to find them,
One Ring to bring them all and in the darkness bind them
In the Land of Mordor where the Shadows lie.

- from J.R.R. Tolkien, The Lord of the Rings


Consider a major Web site, such as Amazon.com. At any given time, they're storing a tremendous amount of information, e.g., book inventory, and making it available via the Web. Further, the information is fairly fluid; every minute, many thousands of requests pour in, each causing information to be accessed, changed, added, or deleted.

Companies like these store their information in databases. A database is a collection of data, which can be visualized as a table consisting of rows and columns. Each row corresponds to a data record and reach column corresponds to an attribute that the data can have. For example, in a database of books, each data record (row) would correspond to an individual book, and each attribute (column) would correspond to an attribute that a book can have, such as its author, title, or ISBN number. In the case of books, the ISBN is a unique attribute, which is different for each book. In particular, each ISBN number contains a prefix that identifies the originating country and publisher, and additional digits that uniquely identify the book. Thus, one could enumerate all books for a certain country or publisher just by reporting all the data records (rows) in a book database that have ISBN numbers with a certain prefix.

Tables, rows, and columns

For the purposes of this project, our database is a collection of records, each of which corresponds to a book. Each book record consists of five attributes, as shown below:

ISBN Number (key) Author(s) Title Publisher Year
0471128457 Schneier, Bruce Applied Cryptography John Wiley & Sons 1996
0471469831 Goodrich, M., and Tamassia, R. Data Structures and Algorithms in Java John Wiley & Sons 2004
0618517650 Tolkien, J.R.R. The Lord of the Rings George Allen & Unwin 1954

Importantly, one of the attributes (i.e., a column) contains a key value, which is used to uniquely identify the record. No two records will ever have the same key.

The program

Your program for this project is not intended to be anywhere near a production-quality database management system (DBMS). Many of the ideas that I've introduced above are simply to provide you enough background to understand the larger context into which your work fits. Your program will be a prototype of a very simple database system, capable of storing book data, searching that data by keys, updating that data, and removing it. For simplicity, all of the data will be character strings.

Your program will read a sequence of commands from the console (presumably using a BufferedReader wrapped around an InputStreamReader wrapped around System.in) and print output to System.out as directed by the specification below. Your program should not print out any prompts such as "Please enter your next command." It should simply read commands blindly typed into the console, process them, and produce output. Many of the commands, in fact, will produce no output. The reason for this design decision is two-fold. Firstly, this is intended to be a prototype, meaning that it's not intended to be used by anyone who is not familiar with the details of the project, so the user interface need not be all that friendly. Secondly, directly reading commands from the console allows us to redirect input from a file into the program, then redirect output into another file, for ease of automated testing. (I'll talk more about this aspect of the project later in the write-up.)

The commands

Your program needs to support the following commands:


INSERT - Inserts a new book record into your database, with the given ISBN key and the required data values.

INSERT ISBNKey author="authorName" title="bookTitle" publisher="publisherName" year=yearValue 

where all of the fields are character strings, even the ones not in quotes (quotes cannot be used inside names or titles)


  • INSERT 0471469831 author="Goodrich, M., and Tamassia, R." title="Data Structures and Algorithms in Java" publisher="John Wiley & Sons" year=2004
  • INSERT 0618517650 author="Tolkien, J.R.R." title="The Lord of the Rings" publisher="George Allen & Unwin" year=1954

This command should generate no output. The value placed into the ISBN key attribute must be unique in the database (i.e. no book may already exist with that value for is ISBN key).

LOOKUP - Retrieves all the books in the database having a specified prefix in their ISBN keys, ordered by ISBN keys.



  • LOOKUP 0471
  • Looks up and prints the attributes of all books whose ISBN key has the prefix 0471 (which corresponds to the publisher John Wiley & Sons).

    The above command should generate output that looks like this:

    0471128457 author="Schneier, Bruce" title="Applied Cryptography" publisher="John Wiley & Sons" year=1996
    0471469831 author="Goodrich, M., and Tamassia, R." title="Data Structures and Algorithms in Java" publisher="John Wiley & Sons" year=2004
  • LOOKUP 0618517650
  • Looks up and prints the attributes of all books whose ISBN key has the prefix 0618517650 (which corresponds to the one Tolkien book).

    The above command should generate output that looks like this:

    0618517650 author="Tolkien, J.R.R." title="The Lord of the Rings" publisher="George Allen & Unwin" year=1954

This command should print all the retrieved book records as space-delimited lists of key-value pairs, ordered by their ISBN keys.

DELETE - Removes a book record with a particular key.



  • DELETE 0471128457
    Deletes the book record with ISBNKey equal to 0471128457, that is, the "Applied Cryptography" book.

This command should generate no output, unless the desired record is not present (in which case the output should simply be ERROR.

EXIT - Exits the program.


This command should generate no output, and should end the program immediately.

Starting point

You're required to write the code for this project from scratch. No code is provided. You should name the class that contains the main method BookDatabase.java .

Handling erroneous commands

Since your program is intended to be a rudimentary prototype, it need not report specific error messages to indicate specific problems. Instead, any command that is not understood or does not follow the rules above should cause your program to simply print the word "ERROR" by itself on a line.

Implementing the Database

You can think of our database as a data structure that is commonly called a map. A map is a set of key/value pairs, where each key uniquely identifies a particular value. In our case, we can conceptually think of each record in the table as a key/value pair, where the key is the string value of the ISBN key for that record, and the value is the set of values for the remaining attributes.

Since our database may contain a very large collection of book records, it will be necessary for us to build an efficient implementation, which will provide fast insertions, lookups, and deletions. For this project, you must implement the database as a random skip list, ordered by ISBN keys. Because it is fundamentally necessary to have your skip list working before you can build any of the other pieces, you should write and test this part of your project before moving on to the rest.

Redirection of input and output

Recall that you can execute a Java program from the command line by using the java command, like this:

java MyProgram

where MyProgram is the name of the class that contains a main( ) method. Ordinarily, a Java program reads its "standard" input from the console, and writes its "standard" output to the console. In other words, when you use the System.out.println( ) method, the output goes to the console.

Most operating systems -- Windows, Unix, and Linux, for example -- allow you to redirect the standard input and output when you execute a program. The contents of an existing file may be redirected into the standard input, meaning that, rather than allowing the user to type input into the console, the program proceeds as though the user has typed the next line of the file each time the program requires input. Similarly, the standard output can be redirected into a file, meaning that all of the output to System.out will be stored in a file, rather than displayed on the console.

The typical mechanism for redirection is to use the < and > operator on the command line, like this:

java MyProgram <my-input.txt >my-output.txt

Using the command above, every time the program needs input, it will read it from the file my-input.txt. Every time it writes output, it will write it to the file my-output.txt. It is possible to redirect the standard input without redirecting the standard output, and vice versa. Note that the operating system deals with the <my-input.txt and >my-output.txt arguments itself before executing the program, so these will not end up in the array of Strings passed to the main( ) method. In fact, the Java program will not even be aware of the redirection! As far as the program is concerned, it's reading input from the console and writing output to the console. The operating system handles the redirection transparently.

This powerful and simple technique will allow you to write test input and reuse it many times while testing this program, so that you can test your database with large sets of data.


You must turn in all of the .java files. Please do not include any .class files or other files generated by your development environment. You should name the class that contains the main method BookDatabase.java .

Follow this link for an explanation of how to turn in your project.

Limitations and advice

You may not use the predefined Java "collection" classes, such as java.util.TreeMap, in your solution. (The "collection" classes are the ones that store a collection of data, and include such classes as ArrayList, LinkedList, HashMap, Vector, Hashtable, and TreeMap.)

I can't stress enough the need to start early. The previous two projects involved a lot of conceptual thinking, but not very much coding. This project, on the other hand, will require you to write more code. It's actually not as big as you may believe, but I would allocate plenty of time to work on it, so that you can get your questions answered early on, and still have plenty of time to write the code.