Motivation

How are relations and relational algebra used in databases, and in what ways do the use of these formal systems facilitate database design and implementation?

Before we examine the formal concepts of relations and relational algebra, we will consider the practical issues that arise when operating on data in the form of tables (or relations).

A Simple Database

Consider a database that might be maintained by the Computer Science Department of the people and machines in the laboratories. The database contains information about the workstations, printers, servers, and registered users. Here are tables that describe the various parts of the database:

  Workstation Table
  
  Name    Room    Mem   Proc  Monitor
  ====================================
  coke     633   16384  SP4   color17      
  bass     633    8124  SP2   color19      
  bashful  633    8124  SP1   b/w
  tab      628    8124  SP4   color17
  crush    628   16384  SP4   color17      
  

  Printer Table
  
  Name    Room    Status    Res.    Color    Speed    
  ================================================
  chaucer  737      up      600       N        12
  keats    706      up      300       N         6
  poe      707     down     300       N         6
  dali     737      up      600       Y         6
  uglab    633      up      600       N        12
  

  Server Table
  
  Name    Status    MB Disk    MB Avail  # Users
  ==============================================
  diamond   up       5120       1024        30
  emerald   up      12228       2048       122
  graphite  down     5120          0        30
  ruby      up       8192        512        60
  frito     up      12228       4096       100
  

  User Table
  
  Login    Name        Status   Idle  Shell  Sever
  ==================================================
  aaron    A. Cohn     UG      29:41  csh    UG
  brown    C. Brown    Faculty 10:24  csh    diamond
  bukys    L. Bukys    Staff    0:00  bsh    slate
  jli      J. Inka     UG       0:00  bsh    UG
  leblanc  T. LeBlanc  Faculty  1:06  csh    ruby
  poulos   A. Poulos   Grad     2:01  csh    ruby
  rfk      R. Kemp     UG       1:11  csh    UG
  

Observations

• Each table has named columns; each row contains information about one item in the table.

• Each table contains one kind of data (machines, printers, servers, or users), although the data in the two tables overlaps (since both the user table and server table contain server names).

• The order of the rows in the table is irrelevant in terms of the information expressed in the table.

• Two rows in the same table may have the same information in one or more columns, but no two rows in the same table are exactly the same.

• The number of rows in a table could be very large. (Image a table containing all workstations in the world, or all users on the internet.)

• Some columns uniquely determine the other entries in a row (such as a user's login or a machine's, printer's, or server's name, all of which must be unique in the lab).

Operations on the Database

Given a database consisting of this information, what operations might we want to perform?

• insert new entries into one or both of the tables

• delete entries from one or both of the tables

• lookup entries in a table based on some search specification

Some lookup operations will be trivial, such as "how long has user bukys been idle?" This operation simply searches the user table for login "bukys" and returns the corresponding "Idle" field.

A slightly more complex operation is "how many servers are currently up and running"? This operation must scan every entry in the server table, check the status field, and increment a counter each time the status is "up".

Some operations might be pretty complex however, because they span multiple tables in the database. For example, suppose we want a list of all the users who have been idle less than an hour, and whose server is currently down. Here's how that operation might be implemented:

• Extract from the server table a list of servers that are down.

• Extract from user table a list of users idle less than an hour.

• For each such user, extract the server field from the entry, and see if that server name appears on the list of servers that are currently down.

• If so, output the name of the user.

There are other ways to get the same information; We could iterate over each server that is down, looking for users of that server.

How can Relations and Relational Algebra Help?

• The design of a (relational) database is an exercise in defining specific relations, and the operations on those relations.

• Relational algebra is an abstract language for expressing queries and other operations on databases against which implementations can be compared (eg., for completeness).

• Query optimization is simply a form of expression simplification in relational algebra.