CSCE-315: Programming Studio (Fall 2013)

This project is a team project, ideal team size is three. If the number of students is not divisible by three, we can have a few teams with size close to three. The teams will be assigned by the instructor, based on the programming proficiency survey.

This is a two-part project. In the first part, the task is a to implement a simple database management system (DBMS). In the second part, the task is to implement an example application that relies on the DBMS system developed in the first part for its data manipulation needs.

Database management systems are very complex pieces of software. They support concurrent use of a database, transactions, permission handling, query optimizations, logging, you name it. To be efficient, they utilize highly tuned algorithms developed during the course of decades. So obviously, for a four-week long project, we have to simplify a lot. We thus base our DBMS on relational algebra.

Relational algebra is a formal system for manipulating relations. It consists of only six primitive operations. Each of the operations take relations as arguments, and produce a relation as a result. The operations thus compose freely.

The upside of using relational algebra is that the implementation effort of the DBMS stays manageable. The downside is that queries tend to be more verbose and maybe a bit harder to construct than, say, with SQL.

CREATE TABLE animals (name VARCHAR(20), kind VARCHAR(8), years INTEGER) PRIMARY KEY (name, kind);

INSERT INTO animals VALUES FROM ("Joe", "cat", 4);
INSERT INTO animals VALUES FROM ("Spot", "dog", 10);
INSERT INTO animals VALUES FROM ("Snoopy", "dog", 3);
INSERT INTO animals VALUES FROM ("Tweety", "bird", 1);
INSERT INTO animals VALUES FROM ("Joe", "bird", 2);

SHOW animals;

dogs <- select (kind == "dog") animals;
old_dogs <- select (age > 10) dogs;

cats_or_dogs <- dogs + (select (kind == "cat") animals);

CREATE TABLE species (kind VARCHAR(10)) PRIMARY KEY (kind);

INSERT INTO species VALUES FROM RELATION project (kind) animals;

a <- rename (aname, akind) (project (name, kind) animals);
common_names <- project (name) (select (aname == name && akind != kind) (a * animals));
answer <- common_names;

SHOW answer;

WRITE animals;
CLOSE animals;

EXIT;

The second phase of this project is to write a simple DB application written in the DML described above. The DB app will run on your DB engine. Since you will need to take user I/O and implement a custom control flow (conditional statements, loops, etc.), the DML described above alone is not enough. Instead of extending the DML to include such non-DB commands, you will use a host language (e.g., C++) to interact with your DBMS.

The host program will provide most of the user interface: displaying menus, taking user input, and showing results. Based on these user inputs, a custom query or command string can be generated and passed on to the DBMS to be parsed and executed..

optional (i.e., as needed): You may also need to retrieve the results of the queries to feed into the host language's control flow. The DBMS object can contain a member function to access the relations, views, and the attributes by their name (string).

This is what an example interaction might look like:

string name;
cin << name;

string query = string("") + 
               "answer <- project (age) ( select (kind == \"dog\" && name == " + name + ") animals )";

rdbms.execute(query);

if (rdbms.relation(relation_name).int_field(field_name) == 10) {
	...
}

The DB application itself will be of your own design, with the following requirements:

1. The application domain is open-ended: bank, web forum, warehouse app, point-of-sale, auto maintenance shop, etc., but it CANNOT BE one of the following: DVD or any kind of rental app, Library app, or PDA app.
2. The domain needs to be sufficiently complex, and should include at least three entities and two relation (a total of five relational tables, minimum). Thus, having a single table (e.g., a simple TODO list, etc.) is not acceptable.
3. The following command/query needs to be used at least once.
   • open, close, write, exit, show
   • create table, insert into, update, delete
   • select, project, +, - , * (note: you have to think hard how to utilize all these in Phase II)
4. Provide a rough sketch of your application and its functionality in your design document. We will provide you with feedback in case it is too simple or too complex so that you can revise your plan early on.

As an example, here's a spec from the last semester. This was for a DVD rental shop. Think about what should be an entity and what should be a relation.

1. Customer data: USER-ID, Firstname, Lastname, Phone Number
2. DVD data: Inventory number, DVD-ID, Title
3. Rental log: USER-ID, Inventory number, Check out date, Due date
4. Operations: Add new customer, Add new DVD, Remove customer, Remove DVD, Update customer, Update DVD, List customer, Search customer (by name, phone), List DVD, Search DVD (by ID, title), Search inventory, Check out DVD, Check in DVD, Show rental list by customer, Show customer list by DVD-ID.
5. The user interface can be a simple scrolling text with CLI (command-line interface) that prints the menu and takes user input from the keyboard.

Note that most of the code in the host language will be user interface, as you will be able to use the DML for most of the required operations.

• Each team should set up a web page where relevant info are linked. We will maintain a single web page pointing to all team web pages.
• Each team should maintain a development log (Google doc or similar) updated by the team members. Give access to the TA. This log will be graded. There is no designated format. We will check your daily progress. The log should be updated daily.
• Major routines should include unit testing (each function individually tested by some automated means, using a set of tests).
• Demo in the lab may be required.

1. Design documents: Follow the guidelines in Scott' Hackett's "How to Write an Effective Design Document" (Writing for a Peer Developer). Include all four sections described in the guide.
   • The design document should cover both phase 1 (DB engine) and phase 2 (DB app).
   • Phase 2 documents should include ER diagram and corresponding relation schema, besides other things.
2. DBMS engine code: This will be the core DB function library, without the parser.
   • Upload your DBMS engine library code.
   • You should include a test application that tests all functionality (function calls relating to all queries, all commands).
   • Also submit the input and output (text file) from your test application.
   • You may omit the file I/O code since it requires the parser.
   • Theoretically, you should be able to build a DB app just using this library. (However, we will not do this -- you will use the DML command-line for the most part and not directly call the DBMS library functions from your final DB app.)
3. Parser code: Upload your parser code. It should be able to take input from the keyboard and accept or reject an arbitrary command or query: Accept syntactically correct command or query, and reject anything that violates the syntax.
   • Upload your parser code.
   • Also submit the input and output (text file) of your parser.
   • Keep in mind how you will later integrate your parser code with the DB engine as you write the parser code.
4. Integrated DBMS + Parser code: Upload your completed DBMS system.
   • The system should have a CLI (command-line interface) where you can type in the commands and queries and it should be fully functional as a DB.
   • Include example inputs and actual outputs from your DBMS.
5. Final project code + DB application code + report: The DB application should be a stand-alone executable. The report should be
   • an updated version of your design document
   • post production notes (changes you had to make to your design and why, difficulties, solutions, lessons learned)
   • individual work load distribution (percentage)
   • Development log.
   • Include a log of an example session with your DB application: show menu, take user input, application's output and messages, etc.
   • The following should be submitted individually:
     • self-evaluation: rate your performance on the scale of 1 to 5, 5 being the best. Briefly discuss how you contributed to the project.
     • peer evaluation: rate all other team members on the scale of 1 to 5, 5 being best. For each member, briefly comment on their contribution.
     • The initial team will continue on with project 2 and 3, unless there is a serious issue with the current team. If you want to leave your team indicate so and provide justification in writing.