Operations that Span Relations

All of the operations we've considered so far operate on a single relation.

Relationships between tuples in different relations may also exist.

In order to explore these relationships, we require operations that span relations.


Multi-Relation Operations: Example

Find the name of all users who have been idle less than 1 hour, and whose server is down.

  
  for all tuples t in User relation do
     for all tuples u in Server relation do
        if (t.Idle < 1:00) and (u.Name = t.Server) then
           if u.Status = down then
              print t.Name
  
  

The running time of the algorithm is O(|Users| * |Servers|).

In general, any query that requires that we look at every item in one relation for every item in another relation is inefficient.

To improve the algorithm, we can


Reordering Operations: Example

We can improve the previous implementation by reordering operations so that we select items from one relation before iterating over the other relation.

Find the name of all users who have been idle less than 1 hour, and whose server is down.

  
  for all tuples t in User relation do
     if (t.Idle < 1:00) then
        for all tuples u in Server relation do
           if (u.Name = t.Server) then
  	    if (u.Status = down) then
                 print t.Name
  
  

Assume that there are k users idle less than 1 hour.

The running time of the algorithm is O(|Users| + k|Servers|).

This implementation is considerably more efficient than the previous one in cases where k << |Users|.


Reordering Again: Example

Suppose we reorder the two loops, and select from the Server relation before iterating over the User relation?

Find the name of all users who have been idle less than 1 hour, and whose server is down.

  
  for all tuples u in Server relation do
     if (u.Status = down) then
        for all tuples t in User relation do
           if (t.Idle < 1:00) then
  	     if (u.Name = t.Server) then
  		print t.Name
  
  

Assume that j servers are down.

The running time of the algorithm is O(|Servers| + j|Users|).

Which is better?


Indexes for Complex Queries

Rather than search among all tuples in a relation we can use an index to quickly find the relations that match a given predicate.

In general, we would like to answer queries in time O(k)