Ask a question from expert

Ask now

Collection of Primitive Operations

32 Pages11057 Words213 Views
   

Added on  2019-09-26

Collection of Primitive Operations

   Added on 2019-09-26

BookmarkShareRelated Documents
SUR: A SINGLE USER RELATIONAL DBMS 1ABSTRACTThis 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.
Collection of Primitive Operations_1
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
Collection of Primitive Operations_2
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 Corresponding Output...................................................................................................................................30
Collection of Primitive Operations_3
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 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 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 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 30years 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, isa 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
Collection of Primitive Operations_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 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::= means is defined as{x} means repeat x zero or more times[x] means x is optionalx | y means either x or yx || y means concatenate x to y<x> means x{[,]x} e.g. x x x ...or x,x,x3 So for instance an INSERT command in LISP might appear as:(INSERT “COURSE" @(CS161O "STRUCTURED PROGRAMING IN PL/I" 3)).5
Collection of Primitive Operations_5
Rulessurlyinput ::= {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 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 */Figure 1. The Syntax of SURLY6
Collection of Primitive Operations_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 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;Figure 2. Sample Test Data7
Collection of Primitive Operations_7
C. The Lexical AnalyzerLegal 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: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 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
Collection of Primitive Operations_8

End of preview

Want to access all the pages? Upload your documents or become a member.