Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 79 ยท Relational Algebra and Calculus

Joins in Relational Algebra

Understand theta, equi, natural, outer, semijoin and antijoin in relational algebra, how a join is a product plus a selection, and the equivalent SQL.

The Cartesian product pairs everything with everything, and a selection can then keep only the meaningful pairs. That two-step recipe is the most common pattern in all of querying, so algebra gives it a single operator: the join. Every kind of join in SQL (INNER, LEFT, NATURAL, EXISTS-based filters) corresponds to a member of the join family. Knowing the family and its definitions makes it much easier to pick the right one.

The examples use the company dataset: employees(id, first_name, department_id, manager_id, salary, ...), departments(id, name, office), projects(id, name, department_id, budget, ...) and assignments(employee_id, project_id, role, hours_per_week). For the SQL syntax of each join see Joins; here the focus is on what they mean.

The join family

Inner joins

Theta join Product plus any comparison.
Equijoin Theta join where the comparison is equality.
Natural join Equijoin on all same-named attributes, shown once.
1 / 3

Theta join and equijoin

The theta join R โ‹ˆฮธ S is defined as a selection over a product:

TEXT
R โ‹ˆฮธ S  =  ฯƒฮธ ( R ร— S )

The condition ฮธ can be any comparison between attributes of R and S: <, >, <>, or =. When every comparison is an equality, it is an equijoin. Matching employees.department_id with departments.id is the typical equijoin: it follows a foreign key.

Most joins in practice are equijoins, but a theta join with an inequality is useful when you compare ranges or magnitudes.

SQL Theta join: projects that cost over four times an employee's salary ยท database: company

Press Run (or Ctrl + Enter) to see the result here.

Employee 16 earns 60,000, so only projects with a budget above 240,000 qualify: Mobile App Rewrite, Payments Platform and Battery Materials Study. No column matches by equality here, which is why this is a general theta join, not an equijoin.

The algebra definition also tells you how a DBMS can run a join: conceptually "product, then filter". To confirm that the two are equal, here is the same equijoin written both ways.

SQL A join is a product plus a selection ยท database: company

Press Run (or Ctrl + Enter) to see the result here.

Both return 34: there are 36 employees, and two of them (the chief executive Kofi and Amara) have no department, so they match nothing. The engine plans the second form very differently from the first, using a join algorithm instead of building 216 pairs, but the answers are identical.

Natural join

The natural join R โ‹ˆ S has no explicit condition. It equates all attributes that have the same name in both relations and keeps just one copy of each. If the relations share no attribute names, it degenerates into a Cartesian product.

That convenience is a trap. In this dataset, both employees and departments have an attribute called id, and they mean different things.

SQL Natural join joins on every shared name, whether you meant it or not ยท database: company

Press Run (or Ctrl + Enter) to see the result here.

The first query returns only 6 rows, because it matched employees.id = departments.id. The second joins on department_id as intended; employee 2 (Yara) is in Engineering, while employees 1 and 36 do not appear since they have no department. This is where rename earns its keep. In real schemas, an explicit ON condition is safer, because adding a column with a common name later can silently change a natural join's meaning.

Outer joins

The inner joins drop tuples with no partner, and sometimes that is exactly the information you want. An outer join keeps them and pads the missing side with nulls.

  • Left outer join (โŸ•) keeps every tuple of the left relation.
  • Right outer join (โŸ–) keeps every tuple of the right relation.
  • Full outer join (โŸ—) keeps the unmatched tuples from both.

Outer joins are not expressible with the classic five operators alone (selection, projection, union, difference, product) in a single step. They are defined as an inner join union the unmatched tuples padded with nulls. That is also the reason they need nulls, which the pure set-based algebra does not have.

SQL Left and full outer joins ยท database: company

Press Run (or Ctrl + Enter) to see the result here.

The full join shows four rows: Yara matched with Engineering, Kofi and Amara with no department, and Sales with no employee on the slice. Which row is NULL tells you which side failed to match.

FULL JOIN needs SQLite 3.39 or newer, which this site's runner has. Older SQLite versions, and MySQL, have no full outer join and emulate it with a LEFT JOIN union a RIGHT JOIN.

Semijoin and antijoin

Sometimes you do not want columns from the other relation at all. You only want to test whether a match exists.

  • The semijoin R โ‹‰ S returns the tuples of R that have at least one matching tuple in S, with only R's attributes. In terms of other operators: ฯ€attrs(R)(R โ‹ˆ S).
  • The antijoin R โ–ท S returns the tuples of R that have no matching tuple in S.

SQL has no SEMIJOIN keyword; it is written with EXISTS and NOT EXISTS. The distinction from an ordinary join is about duplicates: a semijoin returns each left tuple once, no matter how many partners it has.

SQL Semijoin (EXISTS) versus a plain join ยท database: company

Press Run (or Ctrl + Enter) to see the result here.

The join returns 11 rows with Engineering three times; the semijoin returns the 6 departments once each. If you only need "which departments", the semijoin is both clearer and often faster. The antijoin answers the opposite question:

SQL Antijoin (NOT EXISTS): departments with nobody above 140,000 ยท database: company

Press Run (or Ctrl + Enter) to see the result here.

You get Design, Research and Sales. The antijoin is the standard way to ask "which ones have no ...?". Be careful with NOT IN for this job, because a single NULL in the subquery makes it return nothing (Nulls and Three-Valued Logic); NOT EXISTS has no such trap.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How is a theta join R โ‹ˆฮธ S defined?

    A join is just ฯƒฮธ(R ร— S). Systems use clever algorithms but must return exactly that result.
  2. 2. Why can a natural join be dangerous?

    Natural join picks its condition from attribute names. Unrelated columns with the same name, or a later added column, silently change the result.
  3. 3. Which join keeps unmatched rows from both inputs?

    A full outer join keeps unmatched tuples from both sides and pads the missing side with nulls.
  4. 4. How do you write an antijoin in SQL?

    An antijoin returns left rows without a partner. NOT EXISTS expresses this directly, and avoids the NULL problem of NOT IN.
  5. 5. What is the difference between a semijoin and an inner join?

    A semijoin is a filter: it tests for a match without combining columns, so it cannot multiply left rows.

Summary

  • A theta join is ฯƒฮธ(R ร— S); an equijoin uses only equality; a natural join equates same-named attributes and shows them once.
  • Outer joins keep unmatched tuples (left, right or full) and fill the other side with nulls.
  • A semijoin keeps left tuples that have a match; an antijoin keeps those that do not. Both return only the left attributes.
  • In SQL, semijoin and antijoin are written with EXISTS and NOT EXISTS.
  • Prefer explicit ON conditions over NATURAL JOIN, and NOT EXISTS over NOT IN.

Next: the operator for "for all" questions, in Division, Aggregation and Extended Operators.