Outer Joins, Semi Join and Anti Join

Concept

Every join in the previous note is an inner join: a tuple appears in the result only if it has a match. Sometimes the tuples with no match are exactly what the question is about — students who enrolled in nothing, departments with no staff, products never ordered.

The sample relations

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

  Kumar (24) has no enrolment.
  Enrolment 99 has no matching student - deliberately, to
  show what a RIGHT outer join preserves.

1. Left outer join

Every tuple of the left relation appears. Where there is no match, the right attributes are filled with null.

  STUDENT left outer join ENROL

  +---------+--------+------+--------+-------+
  | roll_no | name   | dept | code   | marks |
  +---------+--------+------+--------+-------+
  |   21    | Meera  | CS   | CS201  |  87   |
  |   22    | Ravi   | CS   | CS201  |  91   |
  |   23    | Anitha | EC   | EC101  |  65   |
  |   24    | Kumar  | EC   | (null) | (null)|   <- preserved
  +---------+--------+------+--------+-------+

  Enrolment 99 is NOT here - it belongs to the right side.

2. Right outer join

The mirror image: every tuple of the right relation appears.

  STUDENT right outer join ENROL

  +---------+--------+--------+--------+-------+
  | roll_no | name   | dept   | code   | marks |
  +---------+--------+--------+--------+-------+
  |   21    | Meera  | CS     | CS201  |  87   |
  |   22    | Ravi   | CS     | CS201  |  91   |
  |   23    | Anitha | EC     | EC101  |  65   |
  |   99    | (null) | (null) | CS202  |  55   |   <- preserved
  +---------+--------+--------+--------+-------+

  Kumar is gone. He belongs to the left side.

  R right outer join S  =  S left outer join R
  Every right outer join can be written as a left one, which
  is why many people use only left joins in practice.

3. Full outer join

  STUDENT full outer join ENROL

  +---------+--------+--------+--------+-------+
  |   21    | Meera  | CS     | CS201  |  87   |
  |   22    | Ravi   | CS     | CS201  |  91   |
  |   23    | Anitha | EC     | EC101  |  65   |
  |   24    | Kumar  | EC     | (null) | (null)|
  |   99    | (null) | (null) | CS202  |  55   |
  +---------+--------+--------+--------+-------+

  Both unmatched tuples preserved. Useful for reconciliation:
  "show me everything on both sides and mark what does not
  line up".

Comparison

The anti join pattern

The most useful thing an outer join does is find tuples that have no match. The pattern is: outer join, then select where the padded column is null.

  "Students who have not enrolled in anything"

    SELECT[code IS NULL](
        STUDENT left outer join ENROL
    )

  +---------+-------+------+--------+-------+
  |   24    | Kumar | EC   | (null) | (null)|
  +---------+-------+------+--------+-------+

  Read it as: keep everyone, then keep only the rows where
  the match failed. The null is the EVIDENCE of no match.

  Equivalent in pure algebra, without outer joins:

    STUDENT - ( STUDENT natural join ENROL projected back )

  which is exactly the ANTI JOIN below.

4. Semi join

Returns the tuples of the left relation that have at least one match, and only the left attributes. No padding, no duplication.

  STUDENT semijoin ENROL

  +---------+--------+------+
  | roll_no | name   | dept |
  +---------+--------+------+
  |   21    | Meera  | CS   |
  |   22    | Ravi   | CS   |
  |   23    | Anitha | EC   |
  +---------+--------+------+

  Kumar excluded - no match.
  Meera appears ONCE even if she had five enrolments,
  which is the important difference from an inner join.

  Defined as:  R semijoin S = PROJECT[attributes of R]( R join S )

5. Anti join

The complement: tuples of the left relation with no match.

  STUDENT antijoin ENROL

  +---------+-------+------+
  |   24    | Kumar | EC   |
  +---------+-------+------+

  Defined as:  R antijoin S = R - ( R semijoin S )

  Semi join and anti join together partition the left
  relation: every tuple is in exactly one of them.

Why semi join matters

  "Which students have enrolled in something?"

  WITH AN INNER JOIN
    a student with 5 enrolments appears 5 times.
    A duplicate removal step is then needed, and the join
    produced far more intermediate tuples than the answer.

  WITH A SEMI JOIN
    each qualifying student appears once. The operator can
    stop searching as soon as ONE match is found.

  In a distributed database this is decisive: a semi join
  moves only the qualifying tuples across the network
  instead of the full join result. Phase 15 returns to it.

Common mistakes

• Confusing which side an outer join preserves. Left preserves the left relation.
• Filtering the padded column in the wrong place. A condition on the right relation applied before the join turns a left outer join back into an inner join.
• Comparing a padded column with equality. Null is never equal to anything; the null test is required.
• Using an inner join to count "how many students enrolled". It counts enrolments, not students.
• Assuming a full outer join is always available. Not every product implements it directly.

Exam and interview questions

1. Differentiate inner, left outer, right outer and full outer joins with one example.
2. Show how to find tuples with no match using an outer join.
3. Define semi join and anti join in terms of primitive operators.
4. Why does a semi join avoid duplicates that an inner join produces?
5. Why is a semi join valuable in a distributed database?

Practice

1. Using the sample relations, compute all four join types and state the cardinality of each.
2. Write the expression for courses in which nobody has enrolled.
3. Explain why SELECT[marks > 80] applied before a left outer join changes the result.
4. Partition STUDENT using semi join and anti join, and verify the two results add up.

Conclusion

Outer joins preserve unmatched tuples by padding with nulls, and the null is what lets you find them. Semi join keeps matching left tuples once, anti join keeps the non matching ones, and together they answer the "which have none" questions that inner joins cannot.