Relational Algebra

An algebra is a formal structure consisting of sets and operations on those sets.

Relational algebra is a formal system for manipulating relations.


Set Operations on Relations

For the set operations on relations, both operands must have the same scheme, and the result has that same scheme.


Selection

Selects tuples from a relation whose attributes meet the selection criteria, which is normally expressed as a predicate.

  
      R2 = select(R1,P)
  
  

That is, from R1 we create a new relation R2 containing those tuples from R1 that satisfy (make true) the predicate P.

A predicate is a boolean expression whose operators are the logical connectives (and, or, not) and arithmetic comparisons (LT, LE, GT, GE, EQ, NE), and whose operands are either domain names or domain constants.

select(Workstation,Room=633) =

  
  Name    Room    Mem   Proc  Monitor
  ====================================
  coke     633   16384  SP4   color17
  bass     633    8124  SP2   color19
  bashful  633    8124  SP1   b/w
  
  

select(User,Status=UG and Idle<1:00) =

  
  Login    Name        Status   Idle  Shell  Sever
  ================================================
  jli      J. Inka     UG       0:00  bsh    UG
  
  

Projection

Chooses a subset of the columns in a relation, and discards the rest.

  
      R2 = project(R1,D1,D2,...Dn)
  
  

That is, from the tuples in R1 we create a new relation R2 containing only the domains D1,D2,..Dn.

project(Server,Name,Status) =

  
  Name    Status
  ==============
  diamond   up
  emerald   up
  graphite  down
  ruby      up
  frito     up
  
  

project(select(User,Status=UG),Name,Status) =

  
  Name        Status
  ==================
  A. Cohn       UG
  J. Inka       UG
  R. Kemp       UG
  
  

Join

Combines attributes of two relations into one.

  
      R3 = join(R1,D1,R2,D2)
  
  

Given a domain from each relation, join considers all possible pairs of tuples from the two relations, and if their values for the chosen domains are equal, it adds a tuple to the result containing all the attributes of both tuples (discarding the duplicate domain D2).

Natural join: If the two relations being joined have exactly one attribute (domain) name in common, then we assume that the single attribute in common is the one being compared to see if a new tuple will be inserted in the result.

Assuming that we've augmented the domain names in our lab database so that we use MachineName, PrinterName, ServerName, and UserName in place of the generic domain "Name", then

  
      join(Workstations,Printers)
  
  
is a natural join, on the shared attribute name Room. The result is a relation of all workstation/printer attribute pairs that are in the same room.

Example Use of Project and Join

Find all workstations in a room with a printer.

  
  R1              R2              R3
  Name    Room    Name    Room    WName   Pname   Room
  ============    ============    ====================
  coke     633    chaucer  737    coke    uglab   633
  bass     633    keats    706    bass    uglab   633
  bashful  633    poe      707    bashful uglab   633
  tab      628    dali     737
  crush    628    uglab    633
  
  

Implementing Set Operations

To implement R1 U R2 (while eliminating duplicates) we can

If we allow duplicates in union (and remove them later) we can

If we have an index and don't want duplicates we can

Intersection and set difference have corresponding implementations.


Implementing Projection

To implement projection we must

To avoid duplicates we can

Implementing Selection

In the absence of an index we

Given an index, and a predicate that uses the index key, we


Implementing Join with Nested Loops

A nested loop join on relations R1 (with N domains) and R2 (with M domains), considers all |R1| x |R2| pairs of tuples.

  
  R3= join(R1,Ai,R2,Bj)
  
  for each tuple t in R1 do
    for each tuple s in R2 do
      if t.Ai = s.Bj then
        insert(R3, t.A1, t.A2, ..., t.AN,
          s.B1, ..., s.B(j-1), s.B(j+1), ..., s.BM)
  
  

This implementation takes time O(|R1|*|R2|).


Index Join

An index join exploits the existence of an index for one of the domains used in the join to find matching tuples more quickly.

  
  R3= join(R1,Ai,R2,Bj)
  
  for each tuple t in R1 do
     for each tuple s in R2 at index(t.Ai) do
        insert(R3, t.A1, t.A2, ..., t.AN,
          s.B1, ..., s.B(j-1), s.B(j+1), ..., s.BM)
  
  

We could choose to use an index for R2, and reverse the order of the loops.

The decision on which index to use depends on the number of tuples in each relation.


Sort Join

If we don't have an index for a domain in the join, we can still improve on the nested-loop join using sort join.

  
  R3= join(R1,Ai,R2,Bj)
  
  


Comparison of Join Implementations

Assumptions

Comparison


Expressing Queries in Relational Algebra

Relational algebra is an unambiguous notation (or formalism) for expressing queries.

Queries are simply expressions in relational algebra.

Expressions can be manipulated symbolically to produce simpler expressions according to the laws of relational algebra.

Expression simplification is an important query optimization technique, which can affect the running time of queries by an order of magnitude or more.


Algebraic Laws for Join

Commutativity (assuming order of columns doesn't matter)

Nonassociativity


Algebraic Laws for Selection

Commutativity

Selection pushing

Selection Splitting (where P = A and B)


Example: Selection Pushing and Splitting

Consider the following 4 relation database

Implement the query "Where is Amy at Noon on Monday?"

Let P be (Name="Amy" and Day="Monday" and Hour="Noon")

We can use a brute-force approach that joins all the data in the relations into a single large relation, selects those tuples that meet the query criteria, and then isolates the answer field using projection.

  
  project(select(join(join(join(CSG,SNAP),CDH),CR),P),Room)
  
  

Selection Pushing and Splitting (cont)

The selection uses only Name, Day, and Hour attributes (and not Course or Room), so we can push the selection inside the outermost join.

We cannot push selection further, because the predicate involves attributes from both operands of the next innermost join (R1,CDH).

We can split the selection into two, one based on Name, and the other based on Day-Hour.


Selection Pushing and Splitting (cont 2)

Now we can push the first selection inside the join, since it involves only attributes from the CDH relation.

Similarly we can push the second selection inside the preceding join, since it involves only attributes from R1 (ie, Name).

Continuing to push the second select inside the first join


Algebraic Laws for Projection

Projection pushing

To push a projection operation inside a join requires that the result of the projection contain the attributes used in the join.

project(join(R,Ai,S,Bj),D1,D2,...Dn)

In this case, we know that the domains in the projection will exist in the relation that results from the join.

In performing projection first (on the two join relations)

Let PDR = {D|D domain in R, D in {D1...Dn}} U Ai

Let PDS = {D|D domain in S, D in {D1...Dn}} U Bi

R1 = project(R,PDR)

R2 = project(S,PDS)

R3 = join(R1,Ai,R2,Bj) = project(join(R,Ai,S,Bj),D1,D2,...Dn)

Example: Projection Pushing

Implement the query "Where is Amy at Noon on Monday?"

This approach carries along unnecessary attributes every step of the way.

We use projection pushing to eliminate unnecessary attributes early in the implementation.

Note that R5 is unnecessary, since the domains in the projection are all the domains of CR.


Projection Pushing (cont)

Implement the query "Where is Amy at Noon on Monday?"

We can continue pushing the projection on Course below the join for R4.


Projection Pushing (cont2)

We can continue pushing the projection on Course for R4 below the join for R2.