CSCE-315: Programming Studio (Spring 2016)

Database

a collection of relations

Relation

a table with columns and rows

Attribute

a named column of a relation

Domain

the set of admissible values for one or more attributes

Tuple

a row of a relation (sequence of values, one for each attribute of a relation)

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;

EXIT;

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.