Lecture 04: Relational Algebra II & The Join Family

1. The Join Family

Writing Cartesian product followed by selection (r × s followed by σ_θ) is clumsy and generates massive intermediate relation states. The join family formalizes this combination.

1. Theta Join (r ⋈_θ s)

Combines Cartesian product with an explicit selection predicate θ:

r ⋈_θ s = σ_θ(r × s)

• Predicate θ can involve any comparison operator (=, !=, <, <=, >, >=).

2. Equijoin

A Theta Join where the join predicate consists exclusively of equality conditions (=) across attributes from both tables:

r ⋈_(r.A = s.A AND r.B = s.B) s

3. Natural Join (r ⋈ s)

A specialized equijoin that automatically:

1. Identifies all attributes that have the exact same name in both relations.
2. Enforces equality on those shared attributes.
3. Projects out duplicate column copies, returning only one column for each shared attribute name.

Schema(r ⋈ s) = (R ∪ S)

2. Outer Joins

Standard (inner) joins discard tuples that have no matching counterpart in the opposing relation. Outer joins preserve dangling tuples by padding missing attributes with NULL.

Relation R             Relation S
+----+-------+        +----+-------+
| id | name  |        | id | grade |
+----+-------+        +----+-------+
| 1  | Alice |        | 1  | A     |
| 2  | Bob   |        | 3  | B     |
+----+-------+        +----+-------+

Inner Join (R ⋈ S):
+----+-------+-------+
| id | name  | grade |
+----+-------+-------+
| 1  | Alice | A     |
+----+-------+-------+

Left Outer Join (R ⟕ S): Bob is preserved!
+----+-------+-------+
| id | name  | grade |
+----+-------+-------+
| 1  | Alice | A     |
| 2  | Bob   | NULL  |
+----+-------+-------+

Full Outer Join (R ⟗ S): Both Alice, Bob, and student 3 preserved!
+----+-------+-------+
| id | name  | grade |
+----+-------+-------+
| 1  | Alice | A     |
| 2  | Bob   | NULL  |
| 3  | NULL  | B     |
+----+-------+-------+

3. Relational Division (÷)

Relational division is the mathematical equivalent of universal quantification ("FOR ALL" queries).

• Canonical Query Pattern: "Find all students who have taken ALL courses offered by the Computer Science department."
• Let relation r have schema (A, B) and relation s have schema (B).
• The division r ÷ s yields a relation with schema (A) containing tuples t[A] such that for every tuple u ∈ s, the concatenated tuple <t[A], u[B]> exists in r.

Formal Definition From Fundamental Operators

r ÷ s = π_(R - S)(r) - π_(R - S)((π_(R - S)(r) × s) - r)

Step-by-step Intuition:

1. π_(R-S)(r): All candidate entities (e.g., all students).
2. π_(R-S)(r) × s: All possible combinations of candidates and required targets (all students paired with every required course).
3. (...) - r: Pairs that were NOT actually completed (disqualifications).
4. π_(R-S)(r) - Disqualified: Candidates who have zero missing courses!

4. The Complete RA ↔ SQL Translation Table

5. Review Exercises & Practice Problems

π_id(student) - π_id(takes)

student ▷ takes