UVA CS 4620 - SDB - Simple Relational Database System A User Guide

Unformatted text preview:

SDB - Simple Relational Database SystemA User Guideby David Betz114 Davenport Ave.Manchester, NH 03103revised: Fall 1990Robert C. BeckingerJohn L. PfaltzDept. of Computer ScienceUniversity of VirginiaSDB - a Simple Database System 11. IntroductionSDB is a simple database manager for small systems. It was developed to provide a relatively lowoverhead system for storing data on machines with limited disk and memory resources. The current ver-sion runs on a PDT-11/150 with 2 RX01 floppy disk drives and 60K bytes of memory under the RT-11operating system. The version, currently used by the Department of Computer Science at the Universityof Virginia, is coded in C and runs in a Unix environment. (It also runs on the VAX under VMS.) Note,that SDB is not a "toy system". It has demonstrated good performance with relations of 50,000 tuples.SDB was originally intended to be a relational database system, so many of the terms used indescribing it are taken from the relational database literature. Within the context of SDB the user cansafely make the following associations:relation can be taken to mean file,tuple can be taken to mean record, andattribute can be taken to mean field.It should be noted that SDB is not a relationally complete system. It provides the relational operations ofselect, project, join, union, and difference, but does not provide the set operation of intersection. Theintersection may be derived, however, by performing two sequential difference operations.2. Relation File FormatsSDB maintains a separate file (with ’.sdb’ suffix) for each relation that the user creates. This filecontains a header block containing the definition of the relation including the names and types of all ofthe relation’s attributes. The remainder of the file contains fixed length records each containing one tuplefrom the relation.Tuples can be of three types:active - tuples that contain actual active datadeleted - tuples that have been deletedunused - tuples that haven’t been used yetInitially, all tuples are unused. When a new tuple is stored into a relation, the first unused tuple is found(they are all contiguous at the end of the relation file). The new tuple is stored as an active tuple.When a tuple is deleted, it is marked as such. The space previously allocated to the deleted tuple isleft unused until the relation is compressed.It is possible that when attempting to store a new tuple, no unused tuple can be found even thoughthe relation contains fewer than the maximum active tuples. This happens when tuples have been deletedsince the time the relation file was last compressed.The compress function allows all of the space lost by deleting tuples to be regained. It does this bycopying all of the active tuples as far backward in the file as possible leaving all of the available spacetoward the end of the file.3. Selection ExpressionsA selection expression specifies a set of tuples over which some SDB operation is to be executed.The syntax for a selection expression is:<tse> ::= <r_names> [ where <boolean> ]<r_names> ::= <rel_name> [ , <rel_name> ] ...<rel_name> ::= <relation-name> [ <alias> ]Tuple selection expressions <tse> are used repeatedly in SDB; they are the basic mechanism for specify-ing subsets of tuples to be used in various operations.SDB - a Simple Database System 2When a single relation name is specified in a selection expression, each tuple within that relationbecomes a candidate for selection.When more than one relation name is specified, the tuples are formed by taking the cross product ofall specified relations. If a relation is to be crossed with itself, an alias must be given to one or both of theoccurances of that relation name in the selection expression. This allows SDB to determine which rela-tion occurance is being referred to in the boolean part of the selection expression. However, selectionfrom multiple relations is not recommended.After the set of candidate tuples is determined, the boolean expression is evaluated for each candi-date. The candidates for which the boolean expression evaluates to TRUE become the selected tuples.Whenever a file name is allowed in the syntax for a command, it is possible to use either a SDBrelation identifier or a quoted string. An identifier is interpreted as the (.sdb) file name; while a string isinterpreted as a full file specification. The string form allows for the specification of an alternate deviceor extension.4. Attribute, Relation Names, and AliasesWhen a relation or attribute name is specified in statement, it is possible to provide an alternatename for that relation or attribute. This can be useful in relational operations when it is necessary to joina relation to itself. It is also useful for attributes when it is desired that the column headers in a table bedifferent from the actual attribute names.The syntax for specifying aliases is:<name> ( <alias> )Alternatively, attributes can be renamed as described later. Attribute names can also be qualified with arelation name, as in<relation>.<attribute>This is important when selecting tuples from multiple relations. Note that the period has a special mean-ing. Neither relation names nor attribute names can contain embedded periods.5. Boolean ExpressionsThe syntax for boolean expressions is:<expr> ::= <land> [ ’|’ <land> ]<land> ::= <relat> [ ’&’ <relat> ]<relat> ::= <factor> [ <relop> <factor> ]<factor> ::= <operand> | ’(’ <expr> ’)’ | ’~’ ’(’ <expr> ’)’<operand> ::= <number> | <string> | <attribute><attribute> ::= [ <rel_name> . ] <aname><relop> ::= ’=’ | ’<>’ | ’<’ | ’>’ | ’<=’ | ’>=’where the semantics of the relational operators, <relop>, are= - equal<> - not equal< - less than> - greater than<= - less than or equal>= - greater than or equalof the logical operators areSDB - a Simple Database System 3& - logical and| - logical or~ - logical notand the operands <operand> are<number> - a literal string of digits containing at most one decimal point,<string> - a literal string of characters enclosed in double quotes, or<attribute> - an attribute name optionally qualified by a relation name.6. Interactive CommandsThe primary purpose of SDB is to create an interactive environment in which the user can createrelations, insert tuples, select tuples, display subsets of relations and perform the basic relational opera-tions on these relations.In this mode, SDB issues the promptSDB>to indicated it is waiting for an


View Full Document

UVA CS 4620 - SDB - Simple Relational Database System A User Guide

Documents in this Course
Load more
Download SDB - Simple Relational Database System A User Guide
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view SDB - Simple Relational Database System A User Guide and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view SDB - Simple Relational Database System A User Guide 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?