Data values, such as machine names, user names, and room numbers, are not meaningful in isolation.

However, when we create relationships between data values, as we do when we say "user leblanc is on machine coke in room 633" we create meaningful and useful information.

A relationship is really a mapping between members of two sets. Given the set of machine names and the set of rooms, we can create a mapping from machine name to room, which conveys information about the location of machines.

There are an infinite number of relationships in the real world that we might want to model: machine location, student address, employee salary, book author.

These relationships can be


Formally, a relation on the set of domains D1, D2, ... Dn is a set of n-tuples, each of which is an element of the Cartesian product D1 x D2 x D3 x ... x Dn.

Informally, we can think of a relation as a table, where the columns (attributes) correspond to the domains of the relation, and the rows correspond to the tuples.

The scheme of a relation is the list of domain names D1...Dn.

A database is simply a collection of relations. The scheme for a database is just the set of schemes for the relations in the database.

We require domain names within a relation to be unique, but not all domain names in a database.


A key K for relation R on domains D1...Dn is a subset of the domains D1...Dn such that

  1. the value of K uniquely identifies each tuple in R

  2. no proper subset of K exhibits property 1

Since every tuple in R must be unique, it follows that the set {D1,D2,...,Dn} obeys property 1. To find a key then, we need only look for subsets that obey property 2.

In our simple database

If we assume that two people with the same name are never assigned to the same file server

If we assume no room has more than one B/W printer or more than one color printer

Implementing Relations

A relation is a set of tuples

There are many implementations of sets

Ultimately the decision on how best to implement a relation depends on

Operations on Relations

There are three basic operations on a single relation:

Depending on the complexity of the queries to be supported, the predicates can be based on

Implementation Tradeoffs

Insert requires that we not insert a tuple that is already present, therefore it requires an efficient test of membership.

Delete and Lookup require only those tuples that match a predicate. Usually, the predicates are expressed in terms of keys, therefore we need an efficient lookup mechanism based on keys.

Hash Table Representation for Relations

  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

Assume a simple hash function

The resulting hash table:

      a  --> NIL
      b  --> [bass,633,8124,SP2,c19]
  	   --> [bashful,633,8124,SP2,c19] --> NIL
      c  --> [coke,633,16384,SP4,c17]
  	   --> [crush,628,16834,SP4,c17] --> NIL
      d  --> NIL
      t  --> [tab,628,16384,SP4,c17]
      z  --> NIL

We use the machine name to index (via hashing) our representation for relations.

Primary Index Structures

When we use the machine name to index the hash table for the Workstation relation, we in effect implement a function (or binary relation) that maps from a single domain (machine name) to the corresponding tuple.

In this case, "machine name" is a primary index.

Any set of attributes (domains) can be an index; usually we use a particular key (which is a set of attributes) as a primary index, where we expect most operations to use that key.

Any query based on the key will be efficient; queries based on other fields will require that we look at all tuples in the relation.

Hash Table Implementation
of Primary Index Structure

Use a hash table based on the primary index (key) for the relation.

Given a tuple t, the hash function retrieves the components of t corresponding to the key attributes, combines them in some way, and chooses a bucket based on the result.

Operations that specify the key attributes are efficient; all other operations are O(N), where N is the number of tuples in the relation.

Secondary Index Structures

To facilitate operations on domains other than those in the primary key, we can construct a secondary index.

Example- In the User relation, we might want a secondary index based on the user's name, so we don't have to know user logins in order to make queries.

Each secondary index will have its own hash table and hash function; the contents of the hash table will be pointers to tuples in the primary index structure.