• RA Operations to Combine Relations
• Product
• Natural Join
• Theta Join
• Outer Join
• Division

❖ RA Operations to Combine Relations

Relational algebra has several ways to combine info from relations

• product   ...   R × S   ...   select * from R join S on (true)
• natural join   ...   R ⨝ S   ...   select * from R natural join S
• (inner) join   ...   R ⨝_C S   ...   select * from R join S on (C)
• outer join   ...   R ⟕_C S   ...   select * from R left outer join S on (C)
• division   ...   R / S   ...   see SQL slides for examples

Join conditions involve related attributes from the two relations

Frequently, primary-key joined with foreign-key

❖ Product

Product (Cartesian product) combines information from two relations pairwise on tuples.

Each tuple in the result contains all attributes from r and s, possibly with some fields renamed to avoid ambiguity.

If t₁ = (A₁...A_n) and t₂ = (B₁...B_n) then (t₁:t₂) = (A₁...A_n,B₁...B_n)

Result size is large:   |r × s| = |r|.|s|     Schema: R∪S

Algorithmic view:

result = {}
for each tuple t1 in relation r
    for each tuple t2 in relation s
        result = result ∪ {(t1:t2)} }

❖ Product (cont)

Example of product:

❖ Natural Join

Natural join is a specialised product:

• containing only pairs that match on common attributes
• with one of each pair of common attributes eliminated

Consider relation schemas R(ABC..JKLM), S(KLMN..XYZ).

The natural join of relations r(R) and s(S) is defined as:

Algorithmic view:

result = {}
for each tuple t1 in relation r
   for each tuple t2 in relation s
      if (matches(t1,t2))
         result = result ∪ {combine(t1,t2)}

❖ Natural Join (cont)

Example of natural join:

❖ Theta Join

The theta join is a specialised product containing only pairs that match on a supplied condition C.

Examples:   (r1 Join[B>E] r2) ... (r1 Join[E<D∧C=G] r2)

All attribute names are required to be distinct (cf natural join)

Can be defined in terms of other RA operations:

Note that   r ⨝_true s   =   r × s.

❖ Theta Join (cont)

Example theta join:

(Theta join is the most frequently-used join in SQL queries)

❖ Theta Join (cont)

Querying with relational algebra (join) ...

• Who drinks in Newtown bars?

  NewtownBars(nbar) = Sel[addr=Newtown](Bars)
  Tmp = Frequents Join[bar=nbar] NewtownBars
  Result(drinker) = Proj[drinker](Tmp)
  

• Who drinks beers made by Carlton?

  CarltonBeers = Sel[manf=Carlton](Beers)
  Tmp = Likes Join[beer=name] CarltonBeers
  Result(drinker) = Proj[drinker)Tmp
  

Reminder: projection removes duplicates

❖ Outer Join

R ⨝_C S does not include in its result

• values from any R tuples that do not match some S tuple under C
• values from any S tuples that do not match some R tuple under C

R ⟕_C S (left outer join) includes

• all tuples that would result from a theta join
• values from all R tuples, even with no matching S tuple

For tuples with no match, assign NULL to "unmatched" attributes

Variants are right outer join and full outer join

❖ Outer Join (cont)

Example left outer join:

❖ Division

Consider two relation schemas R and S where S ⊂ R.

The division operation is defined on instances r(R), s(S) as:

Operationally:

• consider each subset of tuples in R that match on t[R-S]
• for this subset of tuples, take the t[S] values from each
• if this covers all tuples in S, then include t[R-S] in the result

❖ Division (cont)

Example of division:

❖ Division (cont)

Querying with relational algebra (division) ...

Division handles queries that include the notion "for all".

E.g. Which beers are sold in all bars?

We can answer this as follows:

• generate a relation of beers and bars where they are sold
  • r1 = Proj[beer,bar](Sold)
• generate a relation of all bars
  • r2 = Rename[r2(bar)](Proj[name](Bars))
• find which beers appear in tuples with every bar
  • res   = r1  Div  r2