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

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.

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

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

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.

*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

Workstation TableName 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.

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

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.

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.