Collection of Primitive Operations

Added on - Sep 2019

Trusted by 2+ million users,
1000+ happy students everyday
Showing pages 1 to 8 of 32 pages
SUR: A SINGLE USER RELATIONAL DBMS1ABSTRACTThis report describes SUR, a single user relational database management system. SUR isdesigned 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 datadefinition 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 routineshave been implemented, new commands can be added to SURLY in a modular way.1If you are reading this document online in MS Word, then turn on View/Document Map to see and move aroundon the outline.
TABLE OF CONTENTSSUR: A SINGLE USER RELATIONAL DBMS........................................................................1ABSTRACT...............................................................................................................................1TABLE OF CONTENTS...........................................................................................................2LIST OF FIGURES....................................................................................................................3I. Core of SUR AND SURLY....................................................................................................4A. SUR – Introduction...........................................................................................................4B. The Syntax of SURLY......................................................................................................5C. The Lexical Analyzer........................................................................................................8D. Basic SURLY Commands.................................................................................................9E. The SURLY Interpreter...................................................................................................12G. INDEX statement (storage structures)............................................................................13H. EXPORT and IMPORT statements.................................................................................17I. Assignments......................................................................................................................17II. Relational Algebra Commands............................................................................................18A. The Relational Assignment Statement and Relexpr's......................................................18B. PROJECT........................................................................................................................19C. JOIN.................................................................................................................................20D. SELECT and Qualifiers...................................................................................................20E. DELETE WHERE...........................................................................................................22F. Intermediate Results – PRINT and ASSIGN...................................................................22G. UNION, INTERSECTION, SET-DI.FFERENCE, and COPY --optional......................23H. Predicates EQUAL? arid SUBSET? --optional...............................................................23I. Pseudo-Relation EMPTY – optional................................................................................23J. Executable SURLY (ESURLY).......................................................................................24K. Interactive SURLY..........................................................................................................25L. Example Queries..............................................................................................................25III. Extensions to SURLY........................................................................................................26A. VIEW...............................................................................................................................26B. TRIGGER........................................................................................................................26C. INTEGRITY CONSTRAINT..........................................................................................27D. RETRIEVE – a calculus operator for SURLY................................................................27E. Hierarchical Formatted PRINT........................................................................................28F. LINK................................................................................................................................31G. INDEX Revisited............................................................................................................31H. B-TREE...........................................................................................................................31I. LOG, UNDO, DUMP, RESTORE...................................................................................31J. READ/WRITE..................................................................................................................32
LIST OF FIGURESFigure 1. The Syntax of SURLY...................................................................................................6Figure 2. Sample Test Data...........................................................................................................7Figure 3: Secondary Indices in SURLY......................................................................................16Figure 4: Sample Data, A Hierarchical, Formatted PRINT Command, and the CorrespondingOutput...................................................................................................................................30
I. Core of SUR AND SURLYA. SUR – IntroductionData 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 dataaccording to each program's particular view of the data, now increasingly enterprises arerecognize 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 objectprimitives and a well defined collection of primitive operations on the data objects. Over theyears, several important data models have emerged in the database area – the hierarchical modelis 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 includeor are based on entity-relationship, unified modeling language (UML), XML, and gridtechnology. Of these, the relational data model has been the industry workhorse over the last 30years because it is simple and easy to work with. Relational query languages are easy to learnand complex queries are expressible in a straightforward way in terms of powerful operators ontables.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 hostlanguage – C++, Java, LISP, ... on a personal computer. SUR is useful in DBMS environmentswhere (single) relations are never too large to fit in a program's address space. This, of course, isa major restriction for large applications, but SUR has clear applicability for middle and smallscale applications where large relations have fewer than O(many thousand) tuples. Theseapplications include individual and small enterprise databases for small businesses, hobbyists,and home computers, The SUR language facility, SURLY, consists of a data definitionlanguage (DDL) and a data manipulation language (DML). The SURLY DDL has facilities forcreating and destroying relations and secondary indices. The SURLY DML allows easyinsertion and deletion of tuples and printing of relations, and offers a relationally completealgebra including relational assignment as well as the nestable operators UNION, SET-DIFFERENCE, PROJECT, SELECT, and JOIN. In a modular way, SURLY can be extended toinclude VIEWS, TRIGGERS, simple INTEGRITY CONSTRAINTS, LINKS, READ/WRITE,the calculus statement RETRIEVE, and a hierarchical formatted PRINT statement.2SURLYcan 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 POINTERSPACE (similar to LISP's FULL- and FREE-WORD space). NAME SPACE stores2Relational algebra and calculus are due to Codd. The syntax of SURLY's algebra wassuggested by Date. The RETRIEVE command is similar to the INGRES-QUEL RETRIEVE.The ideas for VIEWs, TRIGGERs, INTEGRITY CONSTRAINTs and LINKs are taken fromSystem R.4
components of relations uniquely as strings. POINTER SPACE is further divided into a listspace 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, andPRINT statements. Also the HEAP index (a linked list).Section II adds INDEX for storage structures TREE and HASH to make querying moreefficient, 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 computerimplementation of SUR is described here. Instead, suggestions for an implementationare provided.The scale and nature of SURLY gives students an opportunity to put into practice principleslearned in this and earlier courses (especially structured programming and data structures).B. The Syntax of SURLYThe 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 freeto modify the input language to be consistent with the implementation language they choose.3Metasymbols::=meansis defined as{x}meansrepeat x zero or more times[x]meansx is optionalx | ymeanseither x or yx || ymeansconcatenate x to y<x>meansx{[,]x} e.g. x x x ...or x,x,x3So for instance an INSERT command in LISP might appear as:(INSERT “COURSE" @(CS161O "STRUCTURED PROGRAMING IN PL/I" 3)).5
Rulessurlyinput::= {command}command::= RELATION relationname (<attrib format>); |INDEX indexname ON relationnameORDER attriblistSTORAGE 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 relexpr2OVER 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 lengthlength::= an integerrelname::= relationname | indexnamerelationname::= identifierindexname::= identifierattrib::= identifierattriblist::= (<attrib>) | attribtuple::= <value>value::= character string varyingidentifier::= letter || {letter | number | _}--length is implementation dependentqualifier::= qualifier1 | qualifier1 OR qualifierqualifier1::= compare | compare AND qualifier1compare::= attrib relop valuerelop::= = | < | <= | >= | > | ~=comment::= /* comment */Figure1. The Syntax of SURLY6
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, ENDHOURCHAR 5, DAYS CHAR 5, ROOM CHAR 10, INSTRUCTOR CHAR 20);RELATION STAFF (NAME CHAR 20, SPOUSE CHAR 10, RANK CHAR 5, CAMPUSADDR CHAR10, 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;Figure2. Sample Test Data7
C. The Lexical AnalyzerLegal SURLY input consists of SURLY symbols separated by zero or more blanks. SURLYsymbols 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 lineboundaries. To read your input, write function NEXTSYMBOL which has no arguments, readsand 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:NEXTSYMBOLA: 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 isencountered and return the string read.END CASE;END NEXTSYMBOL;It might be useful to you to write a function NEXTCHAR(CHAR} which reads and echoprintsthe next character, setting CHAR to that character and returning that character. NEXTCHARwill then be responsible for keeping track of line boundaries.8
Desklib Logo
You are reading a preview
Upload your documents to download or

Become a Desklib member to get access