Relational Algebra

Relational Algebra is a procedural query language. It tells the system how to get the data. Every SQL query you write is internally converted into Relational Algebra expressions for optimization.

---

Learning Objectives

After completing this chapter, you will be able to:

• Understand Relational Algebra as the foundation of SQL.
• Write expressions using Select (σ), Project (π), and Rename (ρ).
• Understand Union, Set Difference, and Cartesian Product.
• Differentiate between types of joins.
• Convert SQL queries to Relational Algebra.
• Answer interview questions on Relational Algebra.

---

Why Relational Algebra Matters

When you run a SQL query:

SELECT Name FROM Students WHERE Age > 20;

The DBMS internally converts it to:

π Name (σ Age > 20 (Students))

This algebraic form allows the query optimizer to find the most efficient execution plan. By understanding Relational Algebra, you understand how the database actually works.

---

Basic Operators

1. Select (σ) — Row Filtering

Selects rows that satisfy a condition.

Syntax:  σ condition (Relation)
SQL:     WHERE clause

σ Age > 20 (Students)      →  All students older than 20
σ Age > 20 AND City = 'Delhi' (Students)  →  Students in Delhi older than 20

Student_ID	Name	Age	City
2	Priya	22	Delhi
3	Amit	23	Mumbai

Select reduces rows (horizontal filtering). σ is the Greek letter Sigma.

2. Project (π) — Column Filtering

Selects specific columns (attributes).

Syntax:  π column1, column2 (Relation)
SQL:     SELECT column1, column2

π Name, Age (Students)  →  Only Name and Age columns

Name	Age
Rahul	22
Priya	23
Amit	21

Project reduces columns (vertical filtering). π is the Greek letter Pi.

3. Rename (ρ) — Renaming

Renames a relation or attribute.

Syntax:  ρ NewName (Relation)
         ρ NewName(attr1, attr2) (Relation)
SQL:     AS keyword

ρ S(Std_ID, Std_Name) (Students)  →  Renames table and columns

---

Set Operations

Relations must be union compatible:

1. Same number of attributes
2. Corresponding attributes have same data types

Union (∪)

All rows from both relations (duplicates removed).

Syntax:  R ∪ S
SQL:     SELECT * FROM R UNION SELECT * FROM S

Set Difference (−)

Rows in R but not in S.

Syntax:  R − S
SQL:     SELECT * FROM R EXCEPT SELECT * FROM S

Intersection (∩)

Rows in both R and S.

Syntax:  R ∩ S
SQL:     SELECT * FROM R INTERSECT SELECT * FROM S

---

Cartesian Product (×)

Every row of R combined with every row of S.

Syntax:  R × S

If R has 100 rows and S has 50 rows, R × S has 5000 rows.

Problem: Most combined rows are meaningless. You need a Join condition to filter.

---

Join Operations

1. Theta Join (⋈θ)

A Cartesian Product followed by a Select condition.

Syntax:  R ⋈θ S    where θ is any condition

Students ⋈ Students.Student_ID = Enrollments.Student_ID Enrollments

2. Natural Join (⋈)

Automatically joins on common attribute names. No duplicate columns in result.

Syntax:  R ⋈ S

If both Students and Enrollments have Student_ID, natural join matches on it automatically.

3. Outer Joins

Join Type	Keeps	Missing values
Left Outer Join (⟕)	All rows from left table	NULLs for right table
Right Outer Join (⟖)	All rows from right table	NULLs for left table
Full Outer Join (⟗)	All rows from both tables	NULLs where no match

---

Operators Summary Table

Operator	Symbol	Purpose	SQL Equivalent
Select	σ	Filter rows (condition)	WHERE
Project	π	Filter columns	SELECT columns
Rename	ρ	Rename table/column	AS
Union	∪	Combine rows (unique)	UNION
Set Difference	−	Rows in R not in S	EXCEPT
Intersection	∩	Rows in both	INTERSECT
Cartesian Product	×	Every combination	CROSS JOIN
Natural Join	⋈	Match on same column names	NATURAL JOIN
Theta Join	⋈θ	Match on condition	JOIN … ON
Division	÷	Rows matching ALL values	(complex)

---

Example: Converting SQL to Relational Algebra

SQL:

SELECT Students.Name, Courses.Title
FROM Students
JOIN Enrollments ON Students.Student_ID = Enrollments.Student_ID
JOIN Courses ON Enrollments.Course_ID = Courses.Course_ID
WHERE Courses.Department = 'CS';

Relational Algebra:

π Name, Title (
    σ Department = 'CS' (Courses) ⋈ Enrollments ⋈ Students
)

This shows the optimizer can: (1) filter courses to CS first, (2) join with Enrollments, (3) join with Students, (4) project only needed columns. Pushing the selection early reduces intermediate result sizes.

---

Interview Deep Dive

---

Key Takeaways

• Relational Algebra is a procedural language — it specifies HOW to get data (vs SQL which specifies WHAT to get).
• σ (Select) filters rows; π (Project) filters columns.
• Union, Intersection, Set Difference require union-compatible relations.
• Cartesian Product × creates all row combinations; Join filters them.
• Natural Join matches on common attribute names.
• Outer Joins preserve unmatched rows with NULLs.
• The query optimizer converts SQL to Relational Algebra to find the best execution plan.