CSC 459- Project #1 - Relational Algebra Interpreter

Theme ...

Build an application program that lets a user identify and open tables and perform Relational Algebra Operations on them.

You have two choices for this project:

  1. Build a real interpreter that can evaluate Relational Algebra Expressions.
  2. Design a user interface that helps the user formulate, interactively, what he/she wants.

If you follow the first choice, the assumption is that the user will develop a command file and your interpreter will go through it one command line at a time and perform each task. Each command line must be checked for syntax and semantics before getting executed.

If choice two is followed, then the user needs to be guided to achieve the same functionality. The advantage of the second option is in controlling what is legal for the user to ask for at any point in time (i.e. you really shouldn't have to deal with syntax or semantic errors).

Part#1 -- The FrontEnd for RAI

No actual RA operations take place.

if you choose to build a command file interpreter: you will only deal with finding errors in the syntax or the semantics of each line and reporting the status of the line. When there is an error in a line; in this part, you need to display a message that appropriately describes the error. When TYPE statements are successful, you simply report their success. When OPEN statements are successful, you identify the relation name as an open relation and display its type. When an expression is correct, you need to report the type of the resulting relation (key-list and attribute-list).

If you build an interactive interface for the user: what you complete up to this point must make clear how your application will work and that the user will, in fact, have the same level of power of expression as he/she would with the command file interpreter.

The language for the command file

The BNF syntax below defines the language that must be used in the command file to express the tables and the queries on them.

char 	     ::=	'a' | ..| 'z' | '0' | .. | '9' | ' '
const-str    ::=        char,rest-of-c
rest-of-c    ::=	const-str | null
alpha-num    ::=	'a' | ..| 'z' | '0' | .. | '9'
string       ::=	alpha-num,rest-of-s
rest-of-s    ::=	string | null
attr-name    ::=	string
rel-name     ::=	string
type-name    ::=	string
attr-lst     ::=	attr-name,rest-of-attr 
rest-of-attr ::=	',' attr-lst | null
key-lst      ::=	attr-lst

type-def     ::=	TYPE type-name '[' key-lst ']' attr-lst
open-rel     ::=       	OPEN rel-name type-name

infix-op     ::=	UNION | INTERSECT | MINUS | TIMES | JOIN
operand      ::=        rel-name | '(' expr ')'
infix-expr   ::=        operand infix-op operand
comp-op      ::=        < | > | =
condition    ::=	attr-name comp-op '"' const-str '"'
selection    ::=        operand WHERE condition
projection   ::=        operand '[' attr-lst ']'
expr	     ::=	selection | projection | infix-expr

definition   ::= 	type-def | open-rel | expr
definitions  ::=        definition '',rest-of-d
rest-of-d    ::=        definitions | ''

command-file ::=	definitions

Each line/definition in the command file is read and echoed; it will then need to be validated and a reasonable message displayed as mentioned earlier.

Types, Relations, attributes, and keys

In this part, relations don't have any data in them; only their name and type (attribute-list, key-list) are known.

Relations are either permanent, created via OPEN, or they temporary resulting from an algebraic operation. Temporary relations go away once the processing of an expression is completed.

A relation type identifies a list of attributes and the subset of those attributes that constitute its key. A key list is the minimum subset of attributes in the relation that make each row of data in it unique.

We will consider attribute names as unique in our system. No relation type may have two attributes with the same name. This is true for both permanent and temporary relations.

Two relations obviously have the same type if they have the same type name. You must not create a new type, implicitly or explicitly, if it has the same attribute-list and key-list, irrespective of their order, as an existing type. For example, the attribute list snum,sname,address should be treated as the same as sname,snum,address when comparing two types.

The key-list is not mutually exclusive from the attribute-list in a type definition. In fact, a relation type can only be correct if all attributes listed in its key-list exist in its attribute list.


As mentioned in the previous section, in part 1, relations/tables don't actually have any rows of data; only their name, type and how they have been derived is known. Relations and their types may be defined explicitly via the TYPE and OPEN instructions. It is also possible for relations and relation types to get defined implicitly. such relations and types are temporary They only exist during the evaluation of parts or all of one algebraic expression.

Here, I'll describe definitions better via some examples:

Your program stops processing a command line once an error is found in it. A reasonable error message is needed once a error is found. The following describe the behavior of definitions that are algebraic expressions and the rules that the users of your interpreter must Adhere to: