Union, intersection, difference; union compatibility

0 · Recall Warm-up

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

1. How many tuples are in πdept(STUDENT)? from Lesson 3.1.1
2. What is |A ∪ B| for finite sets A, B? from Lesson 0.2.1
3. Can a relation be referenced by its own foreign key? from Lesson 2.2.2

1 · The Hook

"Rolls of CS students or students who took Circuits." "Rolls of CS students who took Circuits." "CS students who did not take Circuits." These are the set operations of Lesson 0.2.1, applied to relations. The only new rule: both sides must have the same shape.

2 · Predict First

A = πroll(σdept='CS'(STUDENT)) and B = πroll(σcid='C3'(ENROLL)). What are A ∪ B, A ∩ B and A − B?

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

3 · Core Concept

Predict First — the answer

A = {1, 3} (CS students), B = {1, 2} (took C3). A ∪ B = {1, 2, 3}, A ∩ B = {1}, A − B = {3}.

Union compatibility

R and S are union compatible (type compatible) if they have the same degree and the i-th attributes of both have the same (compatible) domains. Only then are R ∪ S, R ∩ S and R − S defined. The result takes the attribute names of the first relation by convention.

πroll(STUDENT) and πroll(ENROLL) are compatible. STUDENT and ENROLL are not (degrees 4 and 3).

The three operations

Intersection is not needed as a basic operator: R ∩ S = R − (R − S).

Size bounds (GATE asks these)

For |R| = r and |S| = s:

• max(r, s) ≤ |R ∪ S| ≤ r + s
• 0 ≤ |R ∩ S| ≤ min(r, s)
• max(0, r − s) ≤ |R − S| ≤ r

Minimums happen when one relation contains the other (∪, −) or they are disjoint (∩).

Typical uses

• "CS students who took C3": πroll(σdept='CS'(STUDENT)) ∩ πroll(σcid='C3'(ENROLL)) = {1}.
• "Students who took no course": πroll(STUDENT) − πroll(ENROLL). (Here every student took something, so ∅.)
• "Courses nobody took": πcid(COURSE) − πcid(ENROLL).

"Not" in English almost always becomes − in relational algebra: compute everyone, subtract those who did the thing.

4 · Visual

Rolls of CS students vs rolls of students who took C3.

5 · Worked Examples

Example 1 Easy

Are πcid(COURSE) and πroll(ENROLL) union compatible?

Solution

Both have degree 1, but cid values (C1, …) and roll values (1, 2, …) come from different domains, so they are not union compatible.

Example 2 Medium

Find the rolls of students who took C1 but not C2.

Solution

πroll(σcid='C1'(ENROLL)) = {1, 3}; πroll(σcid='C2'(ENROLL)) = {1, 3}. Difference: ∅. Both C1 students also took C2.

Example 3 GATE

Solution

R ∪ S: 6 to 10. R ∩ S: 0 to 4. R − S: 2 to 6.

8 · Connect the Dots

Lesson 3.1.1 worked on one relation; this lesson combined two relations of the same shape. Next: combining relations of different shapes: the Cartesian product and the joins built from it.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Union

πroll(σgrade='A'(ENROLL)) ∪ πroll(σdept='EE'(STUDENT)). How many tuples?

Numerical answer: ________

Q2 · MCQ · 1 mark(s) — Difference

πcid(COURSE) − πcid(σroll=1(ENROLL)) is:

1. (A) ∅
2. (B) {C3, C4}
3. (C) {C4}
4. (D) {C1, C2, C3}

Q3 · MCQ · 1 mark(s) — Compatibility

Which pair is union compatible?

1. (A) STUDENT and COURSE
2. (B) ENROLL and STUDENT
3. (C) πroll(STUDENT) and πroll(ENROLL)
4. (D) πroll, name(STUDENT) and πroll(ENROLL)

Q4 · NAT · 2 mark(s) — Bounds

Numerical answer: ________

Q5 · MSQ · 2 mark(s) — Laws

Which hold for all union-compatible R and S?

1. (A) R ∪ S = S ∪ R
2. (B) |R ∪ S| ≤ |R| + |S|
3. (C) R ∩ S = R − (R − S)
4. (D) R − S = S − R

11 · Concept Ledger

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

union compatibilityunion ∪ (RA)intersection ∩ (RA)difference − (RA)size bounds for set operations