Cartesian product, theta join, equijoin, natural join

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What is required before R ∪ S is defined? from Lesson 3.1.2
2. What is |A × B| for sets? from Lesson 0.2.2
3. In ENROLL(roll, cid, grade), what do roll and cid reference? from Lesson 2.2.2

1 · The Hook

"Names of students who took DBMS." The names are in STUDENT, the enrolments in ENROLL, the course titles in COURSE. No single table has the answer: you must join them. Joins are where GATE hides its trickiest RA question: a natural join that silently matches on an attribute you did not intend.

2 · Predict First

STUDENT has 4 tuples and ENROLL has 7. How many tuples are in STUDENT × ENROLL? In the natural join STUDENT ⋈ ENROLL?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

28 in the product (4 × 7: every student paired with every enrolment). 7 in the natural join: each enrolment matches exactly one student by roll.

Cartesian product ×

R × S pairs every tuple of R with every tuple of S. Degree = deg(R) + deg(S); cardinality = |R| × |S|. If both have an attribute with the same name, keep them apart as R.A and S.A.

Most pairs are meaningless (Asha with Bhavin's enrolment). A product is almost always followed by a selection.

Theta join and equijoin

R ⋈θ S = σθ(R × S), where θ compares attributes of R and S.

• An equijoin uses only = comparisons: STUDENT ⋈STUDENT.roll = ENROLL.roll ENROLL. Both roll columns stay in the result (degree 7).
• A general theta join may use <, ≥, …: pairs of students where the first has a higher CGPA.

Natural join ⋈

R ⋈ S (no subscript) is an equijoin on all attributes with the same name in R and S, keeping one copy of each common attribute.

• Degree = deg(R) + deg(S) − (number of common attributes).
• If R and S have no common attribute, R ⋈ S = R × S.
• If they have all attributes in common, R ⋈ S = R ∩ S.

STUDENT ⋈ ENROLL joins on roll: 7 tuples, degree 4 + 3 − 1 = 6.

The classic trap: STUDENT and COURSE both have an attribute dept. So STUDENT ⋈ COURSE pairs each student with the courses of their own department, even though no one asked for that. And STUDENT ⋈ ENROLL ⋈ COURSE joins on roll, cid and dept, keeping only enrolments in courses of the student's own department.

Join sizes

• 0 ≤ |R ⋈ S| ≤ |R| × |S| (no matches, or all values equal).
• If the join attributes form a key of S and a non-NULL foreign key in R referencing S, then every R tuple matches exactly one S tuple: |R ⋈ S| = |R|. Example: |ENROLL ⋈ COURSE| = 7.

Joins as "and also"

Typical pattern: join, then select, then project. πname(σcid='C1'(ENROLL) ⋈ STUDENT) = {Asha, Chirag}.

Pushing σcid='C1' inside, before the join, gives the same answer with smaller intermediate tables (Lesson 3.1.6).

4 · Visual

STUDENT ⋈ ENROLL   (common attribute: roll, kept once)

roll name   dept cgpa | cid grade
 1   Asha    CS  9.1  | C1   A
 1   Asha    CS  9.1  | C2   B
 1   Asha    CS  9.1  | C3   A
 2   Bhavin  EE  7.8  | C3   B
 3   Chirag  CS  8.4  | C1   B
 3   Chirag  CS  8.4  | C2   A
 4   Diya    ME  6.9  | C4   C          7 tuples, degree 6

STUDENT ⋈ COURSE   (common attribute: dept!)

CS students {Asha, Chirag} x CS courses {C1, C2}  -> 4 tuples
EE students {Bhavin}       x EE courses {C3}      -> 1 tuple
ME students {Diya}         x ME courses {C4}      -> 1 tuple      total 6 tuples, degree 7

5 · Worked Examples

Example 1 Easy

Degree and cardinality of COURSE × ENROLL?

Solution

Degree 4 + 3 = 7; cardinality 4 × 7 = 28.

Example 2 Medium

Evaluate πtitle(σroll=3(ENROLL) ⋈ COURSE).

Solution

σroll=3(ENROLL) = {(3, C1, B), (3, C2, A)}; join on cid with COURSE: DBMS and Networks. Answer {DBMS, Networks}.

Example 3 GATE

How many tuples are in STUDENT ⋈ ENROLL ⋈ COURSE (all natural joins)? List the names in πname of it.

Solution

Common attributes: roll (STUDENT–ENROLL), then cid and dept with COURSE. Only enrolments in a course of the student's own department survive: (1, C1), (1, C2), (2, C3), (3, C1), (3, C2), (4, C4). (1, C3) is lost: Asha is CS, Circuits is EE. 6 tuples; names = {Asha, Bhavin, Chirag, Diya}.

8 · Connect the Dots

Lesson 3.1.2 combined same-shaped relations; this lesson joined different shapes. A join drops tuples that find no partner. Next: outer joins, which keep those lonely tuples and fill the gaps with NULL.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Product

What is the cardinality of STUDENT × COURSE?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Natural join degree

What is the degree of STUDENT ⋈ COURSE (natural join)?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Natural join

How many tuples are in STUDENT ⋈ COURSE (natural join)?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Definitions

If R and S have no attribute names in common, R ⋈ S equals:

1. (A) ∅
2. (B) R ∪ S
3. (C) R ∩ S
4. (D) R × S

Q5 · MCQ · 2 mark(s) — Evaluate

πname(σgrade='A'(ENROLL) ⋈ STUDENT) returns:

1. (A) {Asha, Bhavin, Chirag}
2. (B) {Chirag}
3. (C) {Asha}
4. (D) {Asha, Chirag}

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

Cartesian product (RA)theta join ⋈θequijoinnatural join ⋈join size boundsjoin-select-project pattern