SUR: Single User Relational DBMS

This report details SUR, a single-user relational database management system (RDBMS) designed to provide relational database capabilities to host languages like Java, C++, Lisp, Ruby, and Python on personal computers. The report's core focuses on SURLY, SUR's language facility, encompassing a data definition language (DDL) and a relationally complete data manipulation language (DML). SURLY's extensibility is highlighted, allowing for modular addition of commands. The report systematically covers SURLY's core commands (RELATION, DESTROY, INSERT, DELETE, INPUT, PRINT), relational algebra commands (PROJECT, SELECT, JOIN, UNION, INTERSECTION, DELETE WHERE), and advanced features like INDEX statements with various storage structures (HEAP, HASH, TREE), EXPORT/IMPORT functionalities, and assignments. Furthermore, it explores extensions to SURLY, including VIEWS, TRIGGERS, INTEGRITY CONSTRAINTS, the RETRIEVE calculus operator, hierarchical formatted PRINT, LINK, B-trees, LOG/UNDO/DUMP/RESTORE capabilities, and READ/WRITE operations. The document provides a detailed syntax description of SURLY using BNF notation, illustrative examples, and implementation suggestions, making it a comprehensive guide for students and developers alike. The website offers access to past papers and solved assignments related to this report, aiding students in their learning process.

SUR: A SINGLE USER RELATIONAL DBMS 1
ABSTRACT
This report describes SUR, a single user relational database management system. SUR is
designed to offer relational database facilities to a host language – JAVA, C++, LISP, RUBY,
PYTHON on a personal computer. SURLY, the SUR language facility, consists of a data
definition language (DDL) and a relationally complete data manipulation language (DML).
SURLY is designed to be extensible so that after a core of basic commands and utility routines
have been implemented, new commands can be added to SURLY in a modular way.
1 If you are reading this document online in MS Word, then turn on View/Document Map to see and move around
on the outline.

TABLE OF CONTENTS
SUR: A SINGLE USER RELATIONAL DBMS ........................................................................1
ABSTRACT...............................................................................................................................1
TABLE OF CONTENTS...........................................................................................................2
LIST OF FIGURES....................................................................................................................3
I. Core of SUR AND SURLY....................................................................................................4
A. SUR – Introduction...........................................................................................................4
B. The Syntax of SURLY......................................................................................................5
C. The Lexical Analyzer........................................................................................................8
D. Basic SURLY Commands.................................................................................................9
E. The SURLY Interpreter...................................................................................................12
G. INDEX statement (storage structures)............................................................................13
H. EXPORT and IMPORT statements.................................................................................17
I. Assignments......................................................................................................................17
II. Relational Algebra Commands............................................................................................18
A. The Relational Assignment Statement and Relexpr's......................................................18
B. PROJECT........................................................................................................................19
C. JOIN.................................................................................................................................20
D. SELECT and Qualifiers...................................................................................................20
E. DELETE WHERE...........................................................................................................22
F. Intermediate Results – PRINT and ASSIGN...................................................................22
G. UNION, INTERSECTION, SET-DI.FFERENCE, and COPY --optional......................23
H. Predicates EQUAL? arid SUBSET? --optional...............................................................23
I. Pseudo-Relation EMPTY – optional................................................................................23
J. Executable SURLY (ESURLY).......................................................................................24
K. Interactive SURLY..........................................................................................................25
L. Example Queries..............................................................................................................25
III. Extensions to SURLY........................................................................................................26
A. VIEW...............................................................................................................................26
B. TRIGGER........................................................................................................................26
C. INTEGRITY CONSTRAINT..........................................................................................27
D. RETRIEVE – a calculus operator for SURLY................................................................27
E. Hierarchical Formatted PRINT........................................................................................28
F. LINK................................................................................................................................31
G. INDEX Revisited............................................................................................................31
H. B-TREE...........................................................................................................................31
I. LOG, UNDO, DUMP, RESTORE...................................................................................31
J. READ/WRITE..................................................................................................................32

LIST OF FIGURES
Figure 1. The Syntax of SURLY...................................................................................................6
Figure 2. Sample Test Data...........................................................................................................7
Figure 3: Secondary Indices in SURLY......................................................................................16
Figure 4: Sample Data, A Hierarchical, Formatted PRINT Command, and the Corresponding
Output...................................................................................................................................30

I. Core of SUR AND SURLY
A. SUR – Introduction
Data is recognized to be an important long-term asset of an enterprise (company, individual, ...).
Where formerly the emphasis was on libraries of programs that manipulate files of data
according to each program's particular view of the data, now increasingly enterprises are
recognize the importance of representing large amounts of data in a uniform way in a central,
formatted database. Advantages of this arrangement – availability of data, redundancy control,
are well documented in textbooks on database management systems by Elmasri and Navathe,
Date and many others.
A data model is a representation for data which is based on a small number of data object
primitives and a well defined collection of primitive operations on the data objects. Over the
years, several important data models have emerged in the database area – the hierarchical model
is based on trees, the network model is based on graphs, the relational model is based on
tables/mathematical relations, the object database model is based on OOP; other data models
include or are based on entity-relationship, unified modeling language (UML), XML, and grid
technology. Of these, the relational data model has been the industry workhorse over the last 30
years because it is simple and easy to work with. Relational query languages are easy to learn
and complex queries are expressible in a straightforward way in terms of powerful operators on
tables.
This report describes a small but powerful relational database management system called SUR.
SUR, a single user relational DBMS, is designed to offer relational database facilities to a host
language – C++, Java, LISP, … on a personal computer. SUR is useful in DBMS environments
where (single) relations are never too large to fit in a program's address space. This, of course, is
a major restriction for large applications, but SUR has clear applicability for middle and small
scale applications where large relations have fewer than O(many thousand) tuples. These
applications include individual and small enterprise databases for small businesses, hobbyists,
and home computers, The SUR language facility, SURLY, consists of a data definition
language (DDL) and a data manipulation language (DML). The SURLY DDL has facilities for
creating and destroying relations and secondary indices. The SURLY DML allows easy
insertion and deletion of tuples and printing of relations, and offers a relationally complete
algebra including relational assignment as well as the nestable operators UNION, SET-
DIFFERENCE, PROJECT, SELECT, and JOIN. In a modular way, SURLY can be extended to
include VIEWS, TRIGGERS, simple INTEGRITY CONSTRAINTS, LINKS, READ/WRITE,
the calculus statement RETRIEVE, and a hierarchical formatted PRINT statement.2 SURLY
can be used as a batch or interactive language. A near variant ESURLY can be used executably.
At the implementation level of SUR, memory is divided into NAME SPACE and POINTER
SPACE (similar to LISP's FULL- and FREE-WORD space). NAME SPACE stores
2 Relational algebra and calculus are due to Codd. The syntax of SURLY's algebra was
suggested by Date. The RETRIEVE command is similar to the INGRES-QUEL RETRIEVE.
The ideas for VIEWs, TRIGGERs, INTEGRITY CONSTRAINTs and LINKs are taken from
System R.
4

components of relations uniquely as strings. POINTER SPACE is further divided into a list
space for tuples, relation heaps, and trees, and a linear address space for hash tables.
This report is arranged in four sections.
 Section I covers SURLY's RELATION, DESTROY, INSERT, DELETE, INPUT, and
PRINT statements. Also the HEAP index (a linked list).
 Section II adds INDEX for storage structures TREE and HASH to make querying more
efficient, as well as EXPORT and IMPORT statements.
 Section III covers the relational algebra: PROJECT, SELECT, JOIN, UNION,
INTERSECTION as well as DELETE WHERE.
 Section IV is a list of extensions to the basic SURLY language. No computer
implementation of SUR is described here. Instead, suggestions for an implementation
are provided.
The scale and nature of SURLY gives students an opportunity to put into practice principles
learned in this and earlier courses (especially structured programming and data structures).
B. The Syntax of SURLY
The syntax of the SURLY language can be described in a variant of BNF as shown in Figure 1.
Figure 2 shows sample data from the CSIT_DEPARTMENT database. Students should feel free
to modify the input language to be consistent with the implementation language they choose.3
Metasymbols
::= means is defined as
{x} means repeat x zero or more times
[x] means x is optional
x | y means either x or y
x || y means concatenate x to y
<x> means x{[,]x} e.g. x x x ...or x,x,x
3 So for instance an INSERT command in LISP might appear as:
(INSERT “COURSE" @(CS161O "STRUCTURED PROGRAMING IN PL/I" 3)).
5

Rules
surlyinput ::= {command}
command ::= RELATION relationname (<attrib format>); |
INDEX indexname ON relationname
ORDER attriblist
STORAGE STRUCTURE storagestructure; |
DESTORY relname; |
INSERT relationname tuple; |
DELETE relationname [WHERE (qualifier)]; |
INPUT {relationname {tuple;} *} END_INPUT; |
PRINT <relexpr>; |
EXPORT <relationname>; |
IMPORT <relationname>; |
relationname = relexpr;
relexpr ::= relname |
JOIN relexprl AND relexpr2
OVER attriblist1 AND attriblist2 |
PROJECT relexpr OVER attriblist |
SELECT relexpr WHERE (qualifier) |
UNION relexprl AND relexpr2 |
SET_DIFFERENCE relexprl AND relexpr2 |
COPY relexpr |
ASSIGN relationname = relexpr |
PRINT relexpr |
(relexpr [GIVING attriblist])
storagestructure ::= HEAP | HASH | TREE (HEAP is default)
format ::= CHAR length | NUM length
length ::= an integer
relname ::= relationname | indexname
relationname ::= identifier
indexname ::= identifier
attrib ::= identifier
attriblist ::= (<attrib>) | attrib
tuple ::= <value>
value ::= character string varying
identifier ::= letter || {letter | number | _}
--length is implementation dependent
qualifier ::= qualifier1 | qualifier1 OR qualifier
qualifier1 ::= compare | compare AND qualifier1
compare ::= attrib relop value
relop ::= = | < | <= | >= | > | ~=
comment ::= /* comment */
Figure 1. The Syntax of SURLY
6

SURLY Test Data (Sample Test File)
/* SURLY COMMAND FILE CONTAINING THE SAMPLE CSIT DEPARTMENT DATABASE */
RELATION COURSE (CNUM CHAR 8, TITLE CHAR 30, CREDITS NUM 4);
RELATION PREREQ (CNUM1 CHAR 8, CNUM2 CHAR 8);
RELATION OFFERING (CNUM CHAR 8, SECTION NUM 5, STARTHOUR CHAR 5, ENDHOUR
CHAR 5, DAYS CHAR 5, ROOM CHAR 10, INSTRUCTOR CHAR 20);
RELATION STAFF (NAME CHAR 20, SPOUSE CHAR 10, RANK CHAR 5, CAMPUSADDR CHAR
10, EXTENSION CHAR 9);
RELATION INTERESTS (NAME CHAR 20, INTEREST CHAR 30);
RELATION DEPT (NAME CHAR 20, DEPT CHAR 4);
INSERT COURSE CMPS161 'ALGORITHM DESIGN AND IMPLEMENTATION I' 3;
INSERT COURSE CMPS257 'DISCRETE STRUCTURES' 3;
INSERT COURSE CMPS280 'ALGORITHM DESIGN AND IMPLEMENTATION II' 3;
INSERT COURSE CMPS390 'DATA STRUCTURES' 3;
INSERT COURSE CMPS400 INTERNSHIP 6;
INSERT COURSE CMPS439 'DATABASE SYSTEMS' 3;
INSERT PREREQ CMPS161 MATH161;
INSERT PREREQ CMPS257 CMPS161;
INSERT PREREQ CMPS257 MATH165;
INSERT PREREQ CMPS280 CMPS161;
INSERT PREREQ CMPS390 CMPS257;
INSERT PREREQ CMPS390 CMPS280;
INSERT PREREQ CMPS390 CMPS285;
INSERT PREREQ CMPS439 CMPS390;
INSERT OFFERING CMPS161 27921 8:55 9:45 MW FAY122 BURRIS;
INSERT OFFERING CMPS390 27922 12:30 13:45 MW FAY213 DENEKE;
INSERT OFFERING CMPS390 27935 8:55 9:45 TR PER108 BURRIS;
INSERT OFFERING CMPS339 27950 9:30 10:45 TR FAY122 DENEKE;
INSERT OFFERING CMPS420 27974 14:00 15:15 MW FAY213 DENEKE;
INSERT OFFERING CMPS439 27977 9:30 10:45 MW FAY122 DENEKE;
INSERT STAFF WITTENBERG DON SEC A8C 0030;
INSERT STAFF DENEKE WHO ASSIS 'FAY 329B' 3769;
INSERT INTERESTS DENEKE AI;
INSERT INTERESTS DENEKE DBMS;
INSERT DEPT DENEKE CMPS;
INSERT DEPT BURRIS CMPS;
INSERT DEPT GREGORY MATH;
PRINT COURSE, PREREQ, OFFERING, STAFF, INTERESTS, DEPT;
Figure 2. Sample Test Data
7

C. The Lexical Analyzer
Legal SURLY input consists of SURLY symbols separated by zero or more blanks. SURLY
symbols can be defined as follows:
'character string containing no single quotes'
character string containing no blanks or break characters
/*comment*/
break characters: ( ) = ~= < <= > >= ; * " ' ,
It is implementation-dependent whether SURLY symbols may be broken across line
boundaries. To read your input, write function NEXTSYMBOL which has no arguments, reads
and echo-prints the input, skips leading blanks and comments, and returns the next symbol,
leaving the “cursor” one position past the end of the symbol (or on the next line}.
For example:
NEXTSYMBOL
A: SKIP BLANKS echoprinting;
CASE current character =
/* --find corresponding */; GO TO A;
, --GO TO A; (ignore commas}
' --read until matching ' and return string
( or ) or = or * --return I ( or ) or = or *
< or > or ~ --see if = follows and return <= >= ~= or < > ~
; --print carriage return and return ';'
ELSE --read until a blank or a break character is
encountered and return the string read.
END CASE;
END NEXTSYMBOL;
It might be useful to you to write a function NEXTCHAR(CHAR} which reads and echoprints
the next character, setting CHAR to that character and returning that character. NEXTCHAR
will then be responsible for keeping track of line boundaries.
8

D. Basic SURLY Commands
1. RELATION relationname (<attrib format>);
Example.
RELATION COURSE (CNUM CHAR 8,
TITLE CHAR 30,
CREDITS NUM 4);
Description. RELATION enters a new relation into the database by simply adding a new
relation descriptor entry to the CATALOG table. If a relation by that name already exists,
DESTROY the old relation before creating the new relation. The new relation is stored as a
'heap' (see "storage structures") and initially contains no tuples. The positional ordering of the
attributes in the RELATION definition and the positional ordering of the values in a tuple
should correspond one to one (see INSERT}. The format of an attribute consists of the type of
the attribute (NUMeric or CHARacter} and the maximum length of the attribute. Character
strings longer than "length" characters should be truncated at the right (ERRMSG1}; Numeric
strings should contain only digits 0-9 (ERRMSG2) and are truncated to the left if longer than
length (ERRMSG3). Both types of data will be stored as character strings, and data values may
be shorter than the attributes maximum length.
2. INDEX indexname ON relationname
ORDER attriblist
STORAGE STRUCTURE storagestructure;
Example.
INDEX OFFERINGBYINSTRBYCOURSE ON OFFERING
ORDER (INSTRUCTOR COURSE)
STORAGE STRUCTURE TREE;
Description. INDEX is used to create secondary indices on existing relations in order to make
retrieval and update with secondary keys more efficient. In order to maintain the integrity of the
index, users will not be allowed to update secondary indices directly. However, when a primary
relation is changed its secondary indices will automatically be updated by the system. If a
DESTROY command is used on the primary relation, all of its secondary indices are destroyed.
If a DESTROY command is used on a secondary index, just that index is destroyed. Secondary
indices on other indices are not allowed. Secondary indices can be stored as either TREE or
HASH storage structures (See "Storage Structures").
3. DESTROY <relname>;
Example.
DESTROY COURSE, OFFERINGBYINSTRBYCOURSE;
/*Destroy the COURSE relation and all its secondary indices
and destroy the OFFERINGBYINSTRBYCOURSE secondary indices*/
Description. For each of the relnames specified,
1) if the relname is a secondary index, delete it from the INDEX table and reclaim storage.
9

2) if the relname is a primary relation, delete it from the CATALOG table, reclaim storage,
and DESTROY any secondary indices as in step 1.
4. INSERT relationname tuple;
Example.
INSERT COURSE CMPS390 'DATA STRUCTURES' 3;
Description. INSERT adds a new tuple to relationname. The relation must already exist and
must not be an index. Tuple values must agree in type and order with the corresponding
attribute list for the relation, with conversion occurring as specified in the section on the
RELATION statement. If relationname has any secondary indices they must be updated as well.
If too many or too few tuple variables are encountered in the tuple, an error message is
generated (ERRMSG4) and the insertion is aborted.
5. DELETE relationname [WHERE qualifier];
Example.
DELETE OFFERING; /*delete all OFFERING tuples*/
DELETE COURSE WHERE CNUM < CMPS2OO AND INSTRUCTOR = DENEKE
OR CNUM >= CMPS300;
Description. DELETE removes tuples which satisfy the qualification (see the discussion on
"Qualification") from the relation, reclaims storage, and updates any secondary indices that may
exist. If the WHERE clause is not present, the result is to delete all tuples in the relation – the
result is a valid but empty relation. Note that DELETE WHERE is related to SELECT WHERE
NOT.
NOTE: A relation may be emptied of tuples but not deleted using the DELETE command.
6. INPUT { relationname {tuple; } * } END_INPUT;
Example.
INPUT COURSE CMPS161 'ALGORITHM DESIGN AND IMPLEMENTATION I' 3;
CMPS400 INTERNSHIP 6;*
INTERESTS DENEKE DBMS;
" AI;*
END_INPUT;
Description. The INPUT command simplifies insertion into relations by:
1) allowing the user to specify sequences of 'relationname tuple tuple... tuple*', without the
words INSERT and relationname for each tuple, and
2) allows the user to specify " (one double quote) as a tuple component indicating that the tuple
component is the same as the tuple component in the corresponding position of the last tuple
encountered. [This ditto feature is optional.]
As in INSERT, too many or too few values in a tuple is an error (ERRMSG4)
10

7. PRINT <relexpr>;
Example.
PRINT COURSE;
COURSE
CNUM TITLE CREQ
CS251O STRUCTURED PROGRAMMING IN JAVA 4
CS141O BUSINESS FORTRAN 3
CS341 COBOL 3
Description. PRINT formats and prints in tabular form each of the named relations in its
argument list. If a secondary index is specified, PRINT prints the primary relation tuples in the
order specified by the secondary index. What action is taken by PRINT when the tuple length
exceeds the line length is implementation dependent. Attribute names are truncated to fit the
specified format. If a relexpr is not a relname, no relation name is printed. Instead,
*TEMPORARY* is printed for the table name.
11

E. The SURLY Interpreter
The SURLY interpreter has a very simple organization: read an operation, branch to code which
reads the operation's arguments, execute the operation and loop back to read the next operation:
DO WHILE (TRUE);
CASE NEXTSYMBOL =
'RELATION' --create a new relations descriptor in the RELATION
class.
'INDEX' --create a new index descriptor in the INDEX class; add
to the corresponding RELATION.INDICES; and build the
new index with the indicated storage structure.
'INPUT' --DO WHILE (SETC (RELNAME, NEXTSYMBOL) ~= 'END INPUT');
REL# = RELNUM(RELNAME); -
DO WHILE (SETN(T, READTUPLE(REL#)) ~= 0);
CALL INSERT (REL#,T);
END;
END;
CALL MATCH(';' );
'INSERT' -–CALL INSERT(SETN(REL#,RELNUM(NEXTSYMBOL)),
READTUPLE(REL#));
That is, insert tuple into relation and update any
secondary indices.
'DELETE' --read RELNAME; if WHERE clause is not present, reclaim
storage of all tuples.
'DESTROY' --delete all primary tuples and/or all secondary
indices, and destroy relation and/or secondary index
descriptors
'PRINT' --beautifully format the named relations and indices
ELSE --print 'BYE BYE' and STOP.
END CASE;
END DO WHILE;
Each of these operations is a module and can be written and tested more or less independently:
INPUT calls INSERT, DESTROY calls DELETE, and so you may wish to write a "dummy"
INSERT and DELETE to test INPUT and DESTROY. The programming of these modules is
fairly straightforward though you will find some hints in the "Programming Notes" section.
[A high-end alternative is to use a compiler-compiler to read the SURLY grammar specification
and translate to code that executes SURLY commands. For instance, see the javacc parser
generator.]
12