Relational Algebra

Relational algebra is a formal, procedural query language for the relational model. It provides the theoretical foundation for SQL. Operations take one or two relations a

Introduction

Relational algebra is a formal, procedural query language for the relational model. It provides the theoretical foundation for SQL. Operations take one or two relations as input and produce a new relation as output.

Being procedural means: you specify both WHAT data to retrieve AND HOW to retrieve it (the sequence of operations).

Sample Relations (used in examples)

EmpID	Name	DeptID	Salary
101	Alice	1	75000
102	Bob	2	62000
103	Carol	1	88000
104	David	3	55000

DeptID	DeptName	Location
1	Computer Science	Block A
2	Mathematics	Block B
3	Physics	Block C

EMPLOYEE

DEPARTMENT

Fundamental Operations

1. Selection (σ — Sigma)

Selects tuples from a relation that satisfy a given predicate. Filters rows.

101	Alice	1	75000
103	Carol	1	88000

Result

2. Projection (π — Pi)

Selects specific columns from a relation. Filters columns.

Name	Salary
Alice	75000
Bob	62000
Carol	88000
David	55000

Result

3. Union (∪)

Combines tuples from two relations. The relations must be union-compatible (same number of attributes, compatible domains).

Notation: R ∪ S

Result contains all tuples from R and S (duplicates removed).

SQL Equivalent: SELECT ... UNION SELECT ...

4. Intersection (∩)

Returns tuples that appear in both relations (union-compatible required).

Notation: R ∩ S

SQL Equivalent: SELECT ... INTERSECT SELECT ...

5. Set Difference (−)

Returns tuples in R that are NOT in S (union-compatible required).

Notation	R − S
Example	Employees not in Department 1
SQL Equivalent	SELECT ... EXCEPT SELECT ...

6. Cartesian Product (×)

Combines every tuple of R with every tuple of S. If R has m tuples and S has n tuples, the result has m × n tuples.

Notation: R × S

EMPLOYEE × DEPARTMENT = 4 × 3 = 12 tuples

(Rarely used directly — usually followed by selection to form a join)

SQL Equivalent: SELECT * FROM EMPLOYEE, DEPARTMENT; (no WHERE)

7. Rename (ρ — Rho)

Renames a relation or its attributes.

Notation: ρ_NewName(Relation)

ρ_NewName(A1, A2, ...)(Relation)

Example: Rename EMPLOYEE to EMP

ρ_EMP(EMPLOYEE)

Derived Operations

8. Natural Join (⋈)

Joins two relations on all common attributes. Returns tuples with matching values on common attributes.

EmpID	Name	DeptID	Salary	DeptName	Location
101	Alice	1	75000	Computer Science	Block A
102	Bob	2	62000	Mathematics	Block B
103	Carol	1	88000	Computer Science	Block A
104	David	3	55000	Physics	Block C

Result

SQL Equivalent

9. Theta Join (⋈_θ)

A generalized join — joins two relations based on any condition θ (not just equality on common attributes).

Notation: R ⋈_θ S

EMPLOYEE ⋈_(EMPLOYEE.DeptID = DEPARTMENT.DeptID) DEPARTMENT

SQL Equivalent: JOIN with any ON condition

10. Equi-Join

A theta join where the condition is equality (=). Most common form of join.

11. Division (÷)

Used for "for all" queries. Returns tuples in R that are associated with ALL tuples in S.

Notation	R ÷ S
Example	Find employees who work on ALL projects in ProjectSet S.
SQL Equivalent	Complex nested NOT EXISTS query

Complex Expressions

Relational algebra operations can be combined:

Find names of employees in the CS department

π_Name (σ_DeptName = 'Computer Science' (EMPLOYEE ⋈ DEPARTMENT))

Step 1: EMPLOYEE ⋈ DEPARTMENT (join on DeptID)

Step 2: σ_DeptName='Computer Science' (filter CS rows)

Step 3: π_Name (project only Name column)

SQL

SELECT Name FROM EMPLOYEE e

JOIN DEPARTMENT d ON e.DeptID = d.DeptID

WHERE d.DeptName = 'Computer Science';

Summary of Operations

Unary Operations (one input)

σ Selection → Filter rows

π Projection → Select columns

ρ Rename → Rename relation/attributes

Binary Operations (two inputs)

∪ Union → All tuples from both (union-compatible)

∩ Intersection → Common tuples (union-compatible)

− Difference → In R but not S (union-compatible)

× Cross Product → All combinations

⋈ Join → Meaningful combination based on condition

÷ Division → "For all" queries

Introduction

Being procedural means: you specify both WHAT data to retrieve AND HOW to retrieve it (the sequence of operations).

Sample Relations (used in examples)

EmpID	Name	DeptID	Salary
101	Alice	1	75000
102	Bob	2	62000
103	Carol	1	88000
104	David	3	55000

DeptID	DeptName	Location
1	Computer Science	Block A
2	Mathematics	Block B
3	Physics	Block C

EMPLOYEE

DEPARTMENT

Fundamental Operations

1. Selection (σ — Sigma)

Selects tuples from a relation that satisfy a given predicate. Filters rows.

101	Alice	1	75000
103	Carol	1	88000

Result

2. Projection (π — Pi)

Selects specific columns from a relation. Filters columns.

Name	Salary
Alice	75000
Bob	62000
Carol	88000
David	55000

Result

3. Union (∪)

Combines tuples from two relations. The relations must be union-compatible (same number of attributes, compatible domains).

Notation: R ∪ S

Result contains all tuples from R and S (duplicates removed).

SQL Equivalent: SELECT ... UNION SELECT ...

4. Intersection (∩)

Returns tuples that appear in both relations (union-compatible required).

Notation: R ∩ S

SQL Equivalent: SELECT ... INTERSECT SELECT ...

5. Set Difference (−)

Returns tuples in R that are NOT in S (union-compatible required).

Notation	R − S
Example	Employees not in Department 1
SQL Equivalent	SELECT ... EXCEPT SELECT ...

6. Cartesian Product (×)

Combines every tuple of R with every tuple of S. If R has m tuples and S has n tuples, the result has m × n tuples.

Notation: R × S

EMPLOYEE × DEPARTMENT = 4 × 3 = 12 tuples

(Rarely used directly — usually followed by selection to form a join)

SQL Equivalent: SELECT * FROM EMPLOYEE, DEPARTMENT; (no WHERE)

7. Rename (ρ — Rho)

Renames a relation or its attributes.

Notation: ρ_NewName(Relation)

ρ_NewName(A1, A2, ...)(Relation)

Example: Rename EMPLOYEE to EMP

ρ_EMP(EMPLOYEE)

Derived Operations

8. Natural Join (⋈)

Joins two relations on all common attributes. Returns tuples with matching values on common attributes.

EmpID	Name	DeptID	Salary	DeptName	Location
101	Alice	1	75000	Computer Science	Block A
102	Bob	2	62000	Mathematics	Block B
103	Carol	1	88000	Computer Science	Block A
104	David	3	55000	Physics	Block C

Result

SQL Equivalent

9. Theta Join (⋈_θ)

A generalized join — joins two relations based on any condition θ (not just equality on common attributes).

Notation: R ⋈_θ S

EMPLOYEE ⋈_(EMPLOYEE.DeptID = DEPARTMENT.DeptID) DEPARTMENT

SQL Equivalent: JOIN with any ON condition

10. Equi-Join

A theta join where the condition is equality (=). Most common form of join.

11. Division (÷)

Used for "for all" queries. Returns tuples in R that are associated with ALL tuples in S.

Notation	R ÷ S
Example	Find employees who work on ALL projects in ProjectSet S.
SQL Equivalent	Complex nested NOT EXISTS query

Complex Expressions

Relational algebra operations can be combined:

Find names of employees in the CS department

π_Name (σ_DeptName = 'Computer Science' (EMPLOYEE ⋈ DEPARTMENT))

Step 1: EMPLOYEE ⋈ DEPARTMENT (join on DeptID)

Step 2: σ_DeptName='Computer Science' (filter CS rows)

Step 3: π_Name (project only Name column)

SQL

SELECT Name FROM EMPLOYEE e

JOIN DEPARTMENT d ON e.DeptID = d.DeptID

WHERE d.DeptName = 'Computer Science';

Summary of Operations

Unary Operations (one input)

σ Selection → Filter rows

π Projection → Select columns

ρ Rename → Rename relation/attributes

Binary Operations (two inputs)

∪ Union → All tuples from both (union-compatible)

∩ Intersection → Common tuples (union-compatible)

− Difference → In R but not S (union-compatible)

× Cross Product → All combinations

⋈ Join → Meaningful combination based on condition

÷ Division → "For all" queries

Introduction

Sample Relations (used in examples)

Fundamental Operations

1. Selection (σ — Sigma)

2. Projection (π — Pi)

3. Union (∪)

4. Intersection (∩)

5. Set Difference (−)

6. Cartesian Product (×)

7. Rename (ρ — Rho)

Derived Operations

8. Natural Join (⋈)

9. Theta Join (⋈_θ)

10. Equi-Join

11. Division (÷)

Complex Expressions

Find names of employees in the CS department

SQL

Summary of Operations

Unary Operations (one input)

Binary Operations (two inputs)

Continue learning this concept

Introduction

Sample Relations (used in examples)

Fundamental Operations

1. Selection (σ — Sigma)

2. Projection (π — Pi)

3. Union (∪)

4. Intersection (∩)

5. Set Difference (−)

6. Cartesian Product (×)

7. Rename (ρ — Rho)

Derived Operations

8. Natural Join (⋈)

9. Theta Join (⋈_θ)

10. Equi-Join

11. Division (÷)

Complex Expressions

Find names of employees in the CS department

SQL

Summary of Operations

Unary Operations (one input)

Binary Operations (two inputs)

Continue learning this concept