CSCE-315: Programming Studio (Spring 2016)

Project 1: Database Management System

Due dates and updates

Here are the various due dates. See near the end for details (i.e., what you need to submit for each submission window.

  1. Design documents (due 1/27 Wednesday 11:59pm)
  2. DB core function code (DB engine) (due 2/1 Monday) (due 2/3 Wednesday)
  3. Parser code (due 2/8 Monday)
  4. Integrated Parser + DB engine (due 2/15 Monday)
  5. Final project code + DB app + report (due 2/22 Monday2/24 Wednesday)

Any updated info about the project will also be posted here.

  1. [2/1] DB core function submission postponed to 2/3 11:50pm.
  2. [1/27] For DB core function submission:
    • You don't need to implement the OPEN command since this will require a functioning parser.
    • You do have to implement CLOSE and SAVE.
    • As for condition, you do not need to implement conjunction and disjunction (|| and &&): Implement all comparison operators though.
  3. The language to be used is C++. No other languages are allowed.
  4. Submission files should be named (case sensitive):
    • Main zip file: 315-spring2016-<section>-<team ID>-prj<project ID>-<submission #>.zip (team ID = a, b, c, ...; submission # = 1, 2, 3, 4, etc., for design document, etc., respectively).
    • Development log: development.X (X: docx, pdf, etc.)
    • Test output file: output.X (X: docx, pdf, etc.)
    • Post production note (final submission only): post-production.X (X: docx, pdf, etc.)
    • Any deviations from this will each result in -1/100 for that submission.

Team configuration

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

In a nutshell

This project consits of two parts. The task of the first part is to implement a simple database management system (DBMS). In the second part, you will write a DB application using your DBMS.

PART I: Specification of the DBMS

Database management systems are very complex pieces of software. They support concurrent use of a database, transactions, permission handling, query optimizations, logging, etc. To be efficient, they utilize highly tuned algorithms developed during the course of decades. So obviously, for a one-month 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.


a collection of relations
a table with columns and rows
a named column of a relation
the set of admissible values for one or more attributes
a row of a relation (sequence of values, one for each attribute of a relation)

Relational algebra

The six operations of (the core of) relational algebra are:

  1. Selection: select the tuples in a relation that satisfy a particular condition.
  2. Projection: select a subset of the attributes in a relation.
  3. Renaming: rename the attributes in a relation.
  4. Set union: compute the union of two relations; the relations must be union-compatible.
  5. Set difference: compute the set difference of two relations; the relations must be union-compatible.
  6. Cross product: compute the Cartesian product of two relations.


The communication with the DBMS takes place using a domain-specific language. The grammar of queries in this language is as follows, described in Baccus-Naur Form (BNF). You will implement a Recursive Descent Parser.

query ::= relation-name <- expr ;

relation-name ::= identifier

identifier ::= alpha { ( alpha | digit ) }

alpha ::= a || z | A || Z | _

digit ::= 0 || 9

expr ::= atomic-expr
             | selection
             | projection
             | renaming
             | union
             | difference
             | product

atomic-expr ::= relation-name | ( expr )

selection ::= select ( condition ) atomic-expr

condition ::= conjunction { || conjunction }

conjunction ::= comparison { && comparison }

comparison ::= operand op operand
                     | ( condition )

op ::= == | != | < | > | <= | >=

operand ::= attribute-name | literal

attribute-name ::= identifier
literal ::= intentionally left unspecified (strings, numbers, etc.)

projection ::= project ( attribute-list ) atomic-expr

attribute-list ::= attribute-name { , attribute-name }

renaming ::= rename ( attribute-list ) atomic-expr

union ::= atomic-expr + atomic-expr

difference ::= atomic-expr - atomic-expr

product ::= atomic-expr * atomic-expr

Queries generated from the above grammar compute new relations based on existing relations. Queries can also name those new relations. We need, however, some ways to create some initial relations (constituting a database), update the relations within the database, store the results of queries back to the database, and delete tuples from relations. We use the following commands for these purposes:

command ::= ( open-cmd | close-cmd | save-cmd | exit-cmd | show-cmd | create-cmd | update-cmd | insert-cmd | delete-cmd ) ;

open-cmd ::== OPEN relation-name
close-cmd ::== CLOSE relation-name
save-cmd ::== SAVE relation-name
exit-cmd ::== EXIT
show-cmd ::== SHOW atomic-expr
create-cmd ::= CREATE TABLE relation-name ( typed-attribute-list ) PRIMARY KEY ( attribute-list )

update-cmd ::= UPDATE relation-name SET attribute-name = literal { , attribute-name = literal } WHERE condition

insert-cmd ::= INSERT INTO relation-name VALUES FROM ( literal { , literal } )
                       | INSERT INTO relation-name VALUES FROM RELATION expr

delete-cmd ::= DELETE FROM relation-name WHERE condition

typed-attribute-list ::= attribute-name type { , attribute-name type }
type ::= VARCHAR ( integer ) | INTEGER
integer ::= digit { digit }

A program in our data manipulation language (DML) is then defined as:

program ::= { ( query | command ) }


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;

SAVE animals;

CLOSE animals;


Note that we made a distinction between queries and commands in the grammar of the DML. The result of a query is a view. A view is not stored in the database. Rather, it is a temporary relation whose lifetime ends when a DML program finishes. So only the updates caused by the commands persist from one DML program execution to another.

The relations themselves should be saved in a file in plain ASCII text, using the same DML described above (e.g., CREATE ... INSERT ... INSERT .... ). To make it simple, let us assume that each database file can only store one relation and the filename is the same as the relation name with the suffix ".db". To load a relation from a database file, use the OPEN command. Opening a nonexisting file will result in nothing. To save a new relation or view to a file, use the SAVE command (the filename will be by default "relationname.db"). If you have a new view that you want to save to a file, you can use this SAVE command. To save all changes to the relation in an existing database file and close, use can use the CLOSE command. NOTE: You have to determine the specific behavior of OPEN, etc. For example, if you opened on db file, changed something, and opened the same db file again, does the db on file overwrite what's in memory?

To exit from the DML interpreter, use the EXIT command.

To print a certain relation or a view, use the SHOW command.

PART II: DB Application

The second phase of this project is to build a DB applications that runs on top of your DB implementation.

Interfacing your DB and your host programming language

Since the basic DB language you developed in part I does not include:
  • control flow (conditonal statements, loops, etc.)
  • I/O (keyboard input, arbitrary output)
  • etc.
it is not possible to write a DB app just using the DB language from part I. To overcome this shortcoming, you will have to write a hybrid code where the main language is C++ (the host language). 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.

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;

// create DB command on the fly
string query = string("") + 
               "answer <- project (age) ( select (kind == \"dog\" && name == " + name + ") animals )";

// pass on the query

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

The Application:

For part II, you will design and develop a stand-alone DB application. The application will be a Convention Exhibit management system (for example, think about the Consumer Electronics Show: CES web site). Here are the various objects and actors involved in the exhibit.
  1. Exhibitors: exhibiting company or organization name, address, contact person, email, phone, fax, category (commercial, non-profit, government), booth personnel (name and email), company description, company web site.
  2. Booths: booth locations (row and column; rows 1 to 50, columns 1 to 20; can be more than one booth connected next to each other, but only within the same column), booth type (economy [odd columns], premium [even columns]).
  3. Services: electricity (500W, 1000W, 1500W), furniture (table, chair, sofa, and how many each), electronics (flat-screen TV, computer monitor, laptop, projector, projector screen, and how many each), bar-code scanner, advertisement (exhibitor guide, online exhibitor guide, large banner, small banner, one or more), insurance ($1 million coverage or $10 million coverage). Each item should have a fixed price associated with them.
  4. Attendees: attendee name, organization, address, email, registration fee, category (regular, discounted, or exhibitor booth personnel [free]); exhibits visited (list of exhibits visited); badge status (mailed, on-site, picked up, not picked up);
  5. Inventory: electronics (tv1, tv2, ..., laptop1, laptop2, ...), furniture (table1, table2, .... , chair1, chair2, ....).
The following are some major tasks involved with the exhibit management system.
  1. register new exhibitor, list exhibitors, remove exhibitor, list exhibitors based on certain search criteria.
  2. assign, delete, and list booth location(s) for a given exhibitor.
  3. assign, delete, and list booth services to exhibitor. Must check inventory and assign certain item to the booth held by the exhibitor.
  4. show invoice for exhibitor (booth, service, and the cost for each subitem, and total cost).
  5. show total revenue (add up all the fees).
  6. add, delete, list attendees who visited a certain exhibitor.
  7. register new attendee, delete attendee, list attendees, search attendee based on a certain criteria.
  8. add, delete, list inventory.
There should be three separate user interfaces:
  1. For exhibit manager: has access to all data.
  2. For exhibitor: has access to own exhibit and attendees who visited them.
  3. For attendees: has access to own personal info and a list of exhibitor names they visited.

Additional Requirements for Honors Credit:

Teams in the honors section have an additional requirement as follows.
  • Two teams will pair up (team A and team B).
  • Team A will use Team B's DB implementation and build the DB app on top of it.
  • Team B will use Team A's DB implementation and build the DB app on top of it.
  • Both teams should coordinate early on to make sure that their host programming language interfaces are the compatible.
  • Since a failure in one team will lead to a failure in the second team, most likely this is what will happen:
    Top two teams will be selected, and all other teams will build their DB app based on one of the two team's DB implementation.

Deliverables and Requirements

  • All teams must use Give access to the TA and the Instructor.
  • Each team must maintain a development log (wiki page in titled "Development log") updated by the team members. This log will be graded. There is no designated format, except that you need to time stamp, write down the name, and write a brief description of the activity. We will check your daily progress.
  • Major routines should include unit testing.
  • 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.
    • Set up your design document ("Design document") as a wiki page in
    • The design document should cover both phase 1 (DB engine) and phase 2 (DB app testing).
    • Documents for phase 2 should include ER diagram and corresponding relation schema, besides other things.
    • Grading:
      1. 20%: all four sections included.
      2. 50%: Part I DBMS - parser, DB engine
      3. 30%: Part II DB app testing - ER diagram, relation schema, testing workflow (create, insert, ... )
  2. DB core function code: Upload the core functions. These are C++ classes and functions that implement the core DB functionality. For example, function calls for creating a relation table data structure, etc. You don't need to link this with the parser just yet. You should be able to write a test program in C++ that directly calls the core DB functions create( ....), insert( ... ), etc.
    1. 10%: layout, style, comments
    2. 30%: commands (open, close, ..., delete)
    3. 40%: queries (select, project, ..., product)
    4. 10%: condition (conjunction, comparison, operators, etc.)
    5. 5%: extensive test output
    6. 5%: development log
  3. Parser code: Upload your parser code. It should be able to accept or reject an arbitrary command or query: Accept syntactically correct command or query, and reject anything that violates the syntax.
    1. 10%: layout, style, comments
    2. 30%: commands (open, close, ..., delete)
    3. 40%: queries (select, project, ..., product)
    4. 10%: condition (conjunction, comparison, operators, etc.)
    5. 5%: extensive test output
    6. 5%: development log
  4. Parser+DB engine integrated code: Upload your integrated parser + DB engine. The DBMS engine should compile into a stand-alone executable application so that when you run the application, it works as a DBMS command shell, where you can type in any command or query. Full DB functionality is expected (including file I/O). A full test of the DB shell, based on manually entered commands, should be conducted and the results included in the submission.
    1. 10%: layout, style, comments
    2. 20%: commands (open, close, ..., delete)
    3. 30%: queries (select, project, ..., product)
    4. 10%: condition (conjunction, comparison, operators, etc.)
    5. 20%: full test of all DB commands -- input and output log
    6. 5%: extensive test output
    7. 5%: development log
  5. Final project code + DB app + DB app demo + report:
    • DB app should compile into a stand-alone executable.
    • DB app demo should include a detailed operation of the DB app: input and output log.
    • post production notes (changes you had to make to your design and why, difficulties, solutions, lessons learned). Make it a wiki page "Post production notes".
    • individual work load distribution (percentage, must add up to 100%). Include this in the "Post production notes".
      • Formula for individual score calculation is as follows:
        individual score = min(sqrt(your percentage/25)*team_score,110)
        For example, if your contribution was 20% and your team score was 85, your individual score is min(sqrt(20/25)*85,110) = 76. Note that 25% is the baseline (equal contribution by all four members). If your contribution was 30% and your team score was 85, your individual score is min(sqrt(30/25)*85,110) = 93.
    • Development log (wiki page).
    • Final Grading:
      1. 5%: Layout, style, comments
      2. 35%: DBMS engine: completeness, functionality
      3. 20%: DB app: completeness, functionality
      4. 10%: Extensive test output: completeness, accuracy
      5. 5%: Post production notes
      6. 5%: Development log
      7. 20%: Weighted grades from earlier submissions (design doc, parser, DB core function): this gives you some chance to make up for previous blunders.


  • All submissions should be through
  • Design doc submission should be a single PDF file uploaded to eCampus. This will be a printout of your wiki page.
  • First, fork your latest project into an archival branch named: Submission 1, Submission 2, and Submission 3, etc. for the code submissions, respectively.
  • Use the "Download ZIP" feature in github and upload the resulting zip file. Include all documents like development log and output log, etc. in the zip file (you can add these after you download the zip from GitHub).
  • As for the documents (development log, etc.), we will check the github project.
  • Late penalty is 1% per 1 hour. So, if you're late 1 day, you lose 24%.

Original concept/design/most of the text by Jaakko Järvi. Modifications by Yoonsuck Choe.