Operations that Span Relations

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

• insert

• delete

• lookup

Relationships between tuples in different relations may also exist.

• Users have a server and Servers have a status

• Machines and Printers both have a room

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

• lookup users whose server is down

• lookup machines in a room with a printer

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

• reorder the steps taken

• use an index

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?

• Are there more servers or users?
• Are there more idle users or down servers?

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.

• To implement a query about idle time and server status, we would have to implement a secondary index for each of those domains.

  • Such queries are not likely to be common, and such an index may not be worthwhile.

• An index based on the room number may make sense for both the Workstation and Printer relations.

• An index based on User Name may be valuable for the User relation.

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

• k is a constant

• k is independent of the size of the relations