Relations

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

one to one: student id --> login
one to many: room --> machines
many to many: user status --> server

Definitions

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.

Since a relation is a set, it doesn't matter in what order we list the tuples (rows) in the table.
Since each of the domains (attributes) has a distinct name, we can list the columns in any order in the table.

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

(Machine)Name-Room-Memory-Processor-Monitor
(Printer)Name-Room-Status-Res-Color-Speed
(Server)Name-Status-MBDisk-MBAvail-#Users
Login-(User)Name-Status-Idle-Shell-Sever

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.

Domain "Status" appears in several relations.
Domain "Name" appears (with different meanings) in every relation, so the names were extended to reflect this meaning.

Keys

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

the value of K uniquely identifies each tuple in R
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

{Machine Name} is a key for the Workstation relation
{Printer Name} is a key for the Printer relation
{Server Name} is a key for the Server relation
{Login} is a key for the User relation
{User Name} is not a key for the User relation
- two users could have the same name

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

{User Name, Server} is a key for the User relation

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

{Room, Color} is a key for the Printer relation

Implementing Relations

A relation is a set of tuples

each tuple can be implemented as a record (structure), with a different field for each attribute (domain)
the relation can be implemented as a set of structures

There are many implementations of sets

an array
a linked list
a hash table (hashing on keys)

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

the size of the relation
the keys
the operations that must be supported
the expected frequency of each operation

Operations on Relations

There are three basic operations on a single relation:

insert(t,R) - Insert tuple t in the relation R (if not already present).
delete(P,R) - Delete every tuple from relation R that satisfies the predicate P.
lookup(P,R) - Return a relation consisting of the tuples in R that satisfy the predicate P.

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

wildcard matching - Each predicate is a list of N items, corresponding to the N domains of the relation. Each item in the list is a value from the corresponding domain or '*', which matches any value.
The predicate (*,633,*,*,*) matches all tuples in the Workstation relation whose value for Room is 633.
The predicate (*,*,up,*,Y,*) matches all the tuples in the Printer relation that correspond to color printers that are in service.
arbitrary arithmetic expressions - Each predicate is an arithmetic expression (consisting of the logical and arithmetic operators) whose operands are either domain names or domain values.
The predicate "Room=633" matches all tuples in the Workstation relation whose value for Room is 633.
The predicate "Status=Faculty AND Server=ruby" matches all tuples in the User relation belonging to faculty whose server is ruby.

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.

linked list
- insert (without lookup) O(1)
- delete O(N)
- lookup O(N)
binary search tree
- insert O(log N)
- delete O(log N) per match
- lookup O(log N) per match
characteristic vector (limited domains)
- insert O(1)
- delete O(1) per match
- lookup O(1) per match
hash table
- insert O(1)
- delete O(1) per match
- lookup O(1) per match

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

h(machine name) = first letter of name

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.

An index is a data structure that efficiently finds tuples in a relation given a value for one or more components in the tuple
A primary index determines the location of tuples in the implementation of a relation

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.

find all machines in room 633
find the names of all SPARC 4's

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.

To insert a tuple, make sure it is not already on the list in the selected bucket, then add it to the list.
To delete a tuple, examine each entry on the list for the selected bucket, evaluate the predicate for each entry, and delete those that match.
To lookup tuples, examine each entry on the list for the selected bucket, evaluate the predicate for each entry, and return as a result those tuples that match.

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.

A secondary index does not determine the location of tuples in the implementation of a relation, but it can efficiently locate them based on the index values.
Every change to the relation requires that we update every index, both primary and secondary.

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.

In this case, "user name" is a secondary index.

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.