Relational Algebra Operations from Set Theory

Relational algebra borrows several operations directly from mathematical set theory. Since relations are defined as sets of tuples, these operations apply naturally to relations.

The three primary set-theoretic relational operations are:

1. UNION (∪)

2. INTERSECTION (∩)

3. SET DIFFERENCE / MINUS (−)

All three are binary operations, meaning they operate on two relations.

---

Union Compatibility (Type Compatibility) – A Mandatory Condition

Before applying any set operation, the two relations must be union compatible.

Definition :

Two relations

$$R(A_1, A_2, \dots, A_n) \quad \text{and} \quad S(B_1, B_2, \dots, B_n)$$

are union compatible if:

1. They have the same degree (same number of attributes)

2. The corresponding attributes have the same domain

   $$dom(A_i) = dom(B_i) \quad \text{for } 1 \le i \le n$$
   

👉 Attribute names may differ, but domains and positions must match.

---

1. UNION Operation (∪)

Definition:

$$R \cup S$$

The UNION operation returns a relation that contains:

• All tuples that are in R

• All tuples that are in S

• Tuples that appear in both

• Duplicate tuples are eliminated

---

Example from EMPLOYEE 

Goal:
Retrieve SSNs of employees who:

• Work in department 5 OR

• Supervise someone who works in department 5

Step-by-step:

DEP5_EMPS ← σDno=5(EMPLOYEE)
RESULT1 ← πSsn(DEP5_EMPS)
RESULT2 ← πSuper_ssn(DEP5_EMPS)
RESULT ← RESULT1 ∪ RESULT2

• RESULT1: Employees working in department 5

• RESULT2: Supervisors of those employees

• RESULT: Everyone satisfying either condition

✔ Duplicate SSNs (e.g., 333445555) appear only once

---

Key Properties of UNION

• Commutative

  $$R \cup S = S \cup R$$
  

• Associative

  $$R \cup (S \cup T) = (R \cup S) \cup T$$
  

• Result relation uses attribute names of first relation

---

2. INTERSECTION Operation (∩)

Definition:

$$R \cap S$$

The INTERSECTION operation returns:

• Only those tuples that appear in both R and S

---

Example: STUDENT and INSTRUCTOR Relations

• STUDENT: Names of students

• INSTRUCTOR: Names of instructors

$$STUDENT \cap INSTRUCTOR$$

Meaning:

✔ People who are both students and instructors

From Figure 8.4(c):

• Susan Yao

• Ramesh Shah

---

Key Properties of INTERSECTION

• Commutative

  $$R \cap S = S \cap R$$

• Associative

  $$R \cap (S \cap T) = (R \cap S) \cap T$$

• Always produces a subset of both relations

---

3. SET DIFFERENCE / MINUS Operation (−)

Definition:

$$R - S$$

The MINUS operation returns:

• All tuples that are in R

• But not in S

---

Example:

STUDENT − INSTRUCTOR

✔ Students who are not instructors

(Figure 8.4(d))

INSTRUCTOR − STUDENT

✔ Instructors who are not students

(Figure 8.4(e))

---

Important Property:

❌ NOT commutative

$$R-S\mathrm{\ne }S-R$$

This makes MINUS conceptually different from UNION and INTERSECTION.

$$\mathrm{<br>}$$

---

Expressing INTERSECTION Using UNION and MINUS

 notes that INTERSECTION can be derived:

$$R \cap S = ((R \cup S) - (R - S)) - (S - R)$$

This shows:

• UNION and MINUS are fundamental

• INTERSECTION can be derived logically

---

SQL Correspondence (Important for Students)

Relational Algebra	SQL Equivalent
∪	UNION
∩	INTERSECT
−	EXCEPT

SQL Example:

SELECT Ssn FROM RESULT1
UNION
SELECT Ssn FROM RESULT2;

Multiset Versions (SQL only):

• UNION ALL

• INTERSECT ALL

• EXCEPT ALL

⚠ These do not remove duplicates, unlike relational algebra.

---

Summary Table 

Operation	Meaning	Commutative	Duplicates
UNION	Tuples in R or S	Yes	Eliminated
INTERSECTION	Tuples in both R and S	Yes	Eliminated
MINUS	Tuples in R but not S	No	Eliminated