Join Operations in Relational Algebra

Concept

A join combines tuples from two relations that satisfy a condition. Every join is formally a selection applied to a Cartesian product, and the three kinds differ only in how the condition is written and what the result keeps.

   THETA JOIN     any comparison condition
        |
        |  condition restricted to equality
        v
   EQUI JOIN      equality only, both columns kept
        |
        |  join on ALL common attributes, drop the duplicate
        v
   NATURAL JOIN   no condition written at all

The sample relations

  STUDENT                        ENROL
  +---------+--------+------+    +---------+--------+-------+
  | roll_no | name   | dept |    | roll_no | code   | marks |
  +---------+--------+------+    +---------+--------+-------+
  |   21    | Meera  | CS   |    |   21    | CS201  |  87   |
  |   22    | Ravi   | CS   |    |   21    | CS202  |  74   |
  |   23    | Anitha | EC   |    |   22    | CS201  |  91   |
  |   24    | Kumar  | EC   |    |   23    | EC101  |  65   |
  +---------+--------+------+    +---------+--------+-------+

  Note that student 24 (Kumar) has NO enrolment. He is the
  tuple that reveals the difference between inner and outer
  joins in the next note.

1. Theta join

Joins on any condition built from comparison operators.

  NOTATION   R JOIN[theta] S   =   SELECT[theta]( R x S )

  Example with a non equality condition:

    COURSE JOIN[C1.credits > C2.credits] COURSE

  gives every pair of courses where the first carries more
  credits than the second. Rename is required, because the
  same relation appears twice.

  Theta may be =, <>, <, <=, >, >= or a combination.

2. Equi join

A theta join whose condition uses only equality. Both joined columns appear in the result, which is the point to remember.

  STUDENT JOIN[STUDENT.roll_no = ENROL.roll_no] ENROL

  +---------+--------+------+---------+--------+-------+
  | roll_no | name   | dept | roll_no | code   | marks |
  +---------+--------+------+---------+--------+-------+
  |   21    | Meera  | CS   |   21    | CS201  |  87   |
  |   21    | Meera  | CS   |   21    | CS202  |  74   |
  |   22    | Ravi   | CS   |   22    | CS201  |  91   |
  |   23    | Anitha | EC   |   23    | EC101  |  65   |
  +---------+--------+------+---------+--------+-------+
       ^                          ^
       roll_no appears TWICE - that is the equi join
       signature, and it is why the natural join exists.

  Kumar is absent: he has no matching tuple in ENROL.
  degree = 3 + 3 = 6, cardinality = 4

3. Natural join

Joins automatically on every attribute the two relations have in common, by equality, and keeps only one copy of each common attribute.

  NOTATION   R natural join S

  STUDENT natural join ENROL
     common attribute: roll_no  (found automatically)

  +---------+--------+------+--------+-------+
  | roll_no | name   | dept | code   | marks |
  +---------+--------+------+--------+-------+
  |   21    | Meera  | CS   | CS201  |  87   |
  |   21    | Meera  | CS   | CS202  |  74   |
  |   22    | Ravi   | CS   | CS201  |  91   |
  |   23    | Anitha | EC   | EC101  |  65   |
  +---------+--------+------+--------+-------+

  degree = 3 + 3 - 1 = 5      one common attribute removed
  cardinality = 4             Kumar still absent

Two traps in the natural join

  TRAP 1: NO COMMON ATTRIBUTE
    If the relations share no attribute name, the natural
    join degenerates into a CARTESIAN PRODUCT. It does not
    fail - it silently returns every pair.

  TRAP 2: AN UNINTENDED COMMON ATTRIBUTE
    STUDENT ( roll_no, name, dept )
    COURSE  ( code, name, credits )
                       ^^^^
    Both have "name". A natural join now matches on
    roll_no AND name, requiring a student name to equal a
    course title. The result is almost always EMPTY, and
    nothing warns you.

  This is exactly why explicit join conditions are preferred
  in practice: the natural join depends on column NAMES,
  which change for reasons unrelated to the query.

Properties

Associativity is not a curiosity. Joining three relations can be done in several orders, all giving the same answer but with wildly different costs. Choosing the cheapest order is one of the main jobs of the optimiser in Phase 14.

Joining three relations

  "Names of students with the titles of courses they take"

    PROJECT[name, title](
        ( STUDENT natural join ENROL ) natural join COURSE
    )

  Working:
    STUDENT natural join ENROL   joins on roll_no  -> 4 tuples
    result natural join COURSE   joins on code     -> 4 tuples
    project                                        -> 4 tuples

  +--------+-----------+
  | name   | title     |
  +--------+-----------+
  | Meera  | Databases |
  | Meera  | Networks  |
  | Ravi   | Databases |
  | Anitha | Circuits  |
  +--------+-----------+

Common mistakes

• Forgetting the natural join drops the duplicate column. The equi join keeps it; the natural join does not.
• Miscounting the degree. Subtract one per common attribute, not one in total.
• Assuming a natural join fails with no common attribute. It silently becomes a product.
• Overlooking an accidental common attribute. Two relations both having name quietly empties the result.
• Expecting unmatched tuples to appear. All of these are inner joins; Kumar is excluded. Outer joins are the next note.

Exam and interview questions

1. Define theta join, equi join and natural join, and state how each differs.
2. Express a join using only primitive operators.
3. What is the degree of a natural join of relations with degrees 4 and 5 sharing 2 attributes?
4. What happens to a natural join when the relations share no attribute?
5. Why does associativity of the join matter to a query optimiser?

Practice

1. Compute ENROL natural join COURSE by hand and state the degree and cardinality.
2. Write an expression for the names of students who scored above 80, using a natural join.
3. Explain what would happen if ENROL also had a column called name.
4. Give the two join orders for joining STUDENT, ENROL and COURSE, and say why one might be cheaper.

Conclusion

Every join is a selection over a product. Theta allows any comparison, equi allows equality and keeps both columns, and natural matches on all common attributes and drops the duplicate — which makes it concise, and makes it depend on column names in a way that occasionally surprises.