Neural Sync Active

10 - Relational Algebra

Registry Synced

10 - Relational Algebra

1624 words

8 min read

Reading compass

Now · 🎯 Learning Objectives

10 - Relational Algebra

🎯 Learning Objectives

After reading this topic, you will be able to:

Write relational algebra expressions for database queries
Use σ (select), π (project), ρ (rename), ∪ (union), − (difference), ∩ (intersection), × (Cartesian product)
Write join expressions (natural join, theta join, outer join)
Use the division operator (÷) for "all" queries
Translate between relational algebra and SQL

📋 Prerequisites

03 - Relational Model — Relations, tuples, attributes, keys
Set theory from BSMA1001 (Maths 1) — Sets, subsets, set operations

📖 Core Content

10.1 Intuition: The Mathematical Foundation of SQL

Relational algebra is the theoretical foundation of SQL. Every SQL query can be translated to a relational algebra expression. While SQL is declarative (WHAT), relational algebra is procedural (HOW). Think of it as a recipe:

Take the instructor relation
Select rows where salary > 80000
Project only name and dept_name In relational algebra: $\pi_{name, dept_name}(\sigma_{salary > 80000}(instructor))$

Why This Matters: Understanding relational algebra helps you:

Write complex SQL queries correctly

Understand what the query optimizer does

Reason about query equivalence and optimization

10.2 The Basic Operations

Select: $\sigma$ (Sigma)

Selects rows based on a condition:

\sigma_{condition}(relation)

\sigma_{dept_name = 'Comp. Sci.'}(instructor)

Returns all instructors in Comp. Sci.

\sigma_{salary > 80000 \land dept_name = 'Finance'}(instructor)

Returns Finance instructors earning > 80000.

Symbol	Meaning
$\sigma_{c}(R)$	Select rows from R satisfying condition c
$\land$	AND
$\lor$	OR
$\lnot$	NOT

Project: $\pi$ (Pi)

Selects columns (attributes):

\pi_{name, salary}(instructor)

Returns only the name and salary columns.

\pi_{dept_name}(instructor)

Returns department names (WITHOUT duplicates — unlike SQL's default behavior).

Rename: $\rho$ (Rho)

Renames relations and/or attributes:

\rho_{X(A_1, A_2, \dots, A_n)}(E)

Returns the result of expression E with the name X and attributes renamed to

A_1, A_2, \dots, A_n

\rho_{emp(ID, n, d, s)}(instructor)

Renames instructor to emp and its columns to ID, n, d, s.

10.3 Set Operations

All set operations require union compatibility: same number of columns, same data types.

Union: $\cup$

r \cup s = \{t \mid t \in r \text{ or } t \in s\}

\pi_{course_id}(teaches_Fall) \cup \pi_{course_id}(teaches_Spring)

Courses taught in Fall OR Spring.

Difference: $-$ (or $\setminus$ )

r - s = \{t \mid t \in r \text{ and } t \notin s\}

\pi_{course_id}(teaches_Fall) - \pi_{course_id}(teaches_Spring)

Courses taught in Fall but NOT in Spring.

Intersection: $\cap$

r \cap s = \{t \mid t \in r \text{ and } t \in s\}

Can be expressed using difference:

r \cap s = r - (r - s)

\pi_{course_id}(teaches_Fall) \cap \pi_{course_id}(teaches_Spring)

Courses taught in BOTH Fall and Spring.

10.4 Cartesian Product: $\times$

Every combination of tuples from both relations:

r \times s = \{t q \mid t \in r \text{ and } q \in s\}

If instructor has 12 tuples and teaches has 15 tuples:

\sigma_{instructor.ID = teaches.ID}(instructor \times teaches)

This is equivalent to a JOIN. In practice, Cartesian product is almost always followed by a select condition.

10.5 Join Operations

Theta Join: $\bowtie_\theta$

R \bowtie_\theta S = \sigma_\theta(R \times S)

instructor \bowtie_{instructor.ID = teaches.ID} teaches

Natural Join: $\bowtie$

Joins on all common attributes (removes duplicate columns):

R \bowtie S

instructor \bowtie teaches

Joins on ID (the common attribute). Equivalent to:

\pi_{ID, name, dept_name, salary, course_id, ...}(\sigma_{instructor.ID = teaches.ID}(instructor \times teaches))

Outer Join

Preserves non-matching rows (like SQL's LEFT/RIGHT/FULL OUTER JOIN):

$R ⟕ S$ — Left outer join
$R ⟖ S$ — Right outer join
$R ⟗ S$ — Full outer join

10.6 Division: $\div$

The division operator answers "all" queries: "Find students who have taken ALL CS courses."

R \div S

Where attributes(R) ⊇ attributes(S). Result has attributes(R) - attributes(S). Intuition: For a tuple t to appear in the result, t must appear in R combined with every tuple in S. (Diagram) Example:

student_id	course_id
1	CS101
1	CS201
2	CS101
2	CS201
3	CS101

S

= {CS101, CS201}

R \div S

= {1, 2} — students 1 and 2 took BOTH CS101 and CS201. Student 3 only took CS101.

10.7 Equivalence Rules

Important equivalences that the optimizer uses:

Cascade selection: $\sigma_{\theta_1 \land \theta_2}(E) = \sigma_{\theta_1}(\sigma_{\theta_2}(E))$
Commuting selection: $\sigma_{\theta_1}(\sigma_{\theta_2}(E)) = \sigma_{\theta_2}(\sigma_{\theta_1}(E))$
Cascade projection: $\pi_{L_1}(\pi_{L_2}(E)) = \pi_{L_1}(E)$
Selection before join: $\sigma_\theta(E_1 \times E_2) = E_1 \bowtie_\theta E_2$
Commuting join: $E_1 \bowtie_\theta E_2 = E_2 \bowtie_\theta E_1$
Associating join: $(E_1 \bowtie E_2) \bowtie E_3 = E_1 \bowtie (E_2 \bowtie E_3)$

10.8 Worked Examples

Example 1: Simple query

Find the names of all instructors in the Physics department.

\pi_{name}(\sigma_{dept_name = 'Physics'}(instructor))

Example 2: Join query

Find the names of all instructors who teach a course.

\pi_{name}(instructor \bowtie teaches)

Example 3: Division

Find the IDs of students who have taken ALL courses offered in Fall 2017. Let

R = \pi_{ID, course_id}(takes)

Let

S = \pi_{course_id}(\sigma_{semester='Fall' \land year=2017}(teaches))

Answer:

R \div S

10.9 Relational Algebra Summary Table

Operation	Symbol	SQL Equivalent	Purpose
Select	$\sigma$	WHERE	Filter rows
Project	$\pi$	SELECT	Choose columns
Rename	$\rho$	AS	Rename relation/attributes
Union	$\cup$	UNION	Rows in either
Difference	$-$	EXCEPT	Rows in first but not second
Intersection	$\cap$	INTERSECT	Rows in both
Cartesian Product	$\times$	CROSS JOIN	All combinations
Natural Join	$\bowtie$	NATURAL JOIN	Join on common attributes
Theta Join	$\bowtie_\theta$	JOIN ON condition	Join on arbitrary condition
Division	$\div$	NOT EXISTS + EXCEPT	"All" queries

⚠️ Common Pitfalls

Pitfall 1: Confusing σ (select) with SQL SELECT

The Mistake: Thinking σ is the same as SQL's SELECT. Why It's Wrong: σ selects rows (filtering), while SQL's SELECT picks columns. The relational algebra equivalent of SQL's SELECT is π (project).

Concept	Relational Algebra	SQL
Row filtering	$\sigma$	WHERE
Column picking	$\pi$	SELECT
Renaming	$\rho$	AS

Pitfall 2: Forgetting Set Operations Need Union Compatibility

The Mistake: Applying ∪, ∩, or - to relations with different schemas. Why It's Wrong: Set operations require the same number of attributes with compatible domains. R(A, B) ∪ S(C, D, E) is invalid. Fix: Use project to match schemas:

\pi_{A,B}(R) \cup \pi_{C,D}(S)

Pitfall 3: Thinking Natural Join is Always Equijoin

The Mistake: Assuming natural join always joins on foreign key = primary key. Why It's Wrong: Natural join joins on ALL common attributes. If two tables accidentally share a column name (e.g., both have name), the join uses that too. Fix: Use theta join (

\bowtie_\theta

) to be explicit about join conditions.

📝 Practice Questions

Q1. Write a relational algebra expression to find the names of all instructors who earn more than 90000.

Answer

$\pi_{name}(\sigma_{salary > 90000}(instructor))$

Step 1: $\sigma_{salary > 90000}(instructor)$ — filter rows with salary > 90000 Step 2: $\pi_{name}$ — keep only the name column

Q2. Express the following SQL query in relational algebra: `SELECT name FROM instructor WHERE dept_name = 'Music';`

Answer

$\pi_{name}(\sigma_{dept_name = 'Music'}(instructor))$

Q3. Write a relational algebra expression to find course IDs taught in Fall 2017 but not in Spring 2018.

Answer

$\pi_{course_id}(\sigma_{semester='Fall' \land year=2017}(teaches)) - \pi_{course_id}(\sigma_{semester='Spring' \land year=2018}(teaches))$

Q4. What is the division operator? Give an intuitive explanation.

Answer

The division operator ( $R \div S$ ) answers "for ALL" queries. For a tuple t to be in the result, t (combined with other attributes) must have a match with every tuple in S.

Example: "Find students who have taken ALL courses offered by the CS department." Use division:

R = (student_id, course_id) — all enrollment records

S = (course_id) — all CS courses

R ÷ S = students who took every CS course

Q5. Show that intersection can be expressed using difference. $R \cap S = ?$

Answer

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

Proof:

$R - S$ = tuples in R but not S

$R - (R - S)$ = tuples in R minus those not in S = tuples in both R and S = $R \cap S$

Q6. Write a relational algebra expression to find the names of instructors and the course IDs they teach.

Answer

$\pi_{name, course_id}(instructor \bowtie teaches)$

This natural joins instructor and teaches on ID, then projects name and course_id.

Q7. What is the difference between natural join ( $\bowtie$ ) and theta join ( $\bowtie_\theta$ )?

Answer

Natural join ( $\bowtie$ ): Automatically joins on ALL common attribute names. Duplicate columns are removed from the result.

Theta join ( $\bowtie_\theta$ ): Joins based on an explicit condition $\theta$ . Can use any comparison operator (=, <, >, etc.). May have duplicate columns.

Natural join is a special case of theta join where $\theta$ is equality on all common attributes.

Q8. Translate: $\pi_{name}(\sigma_{dept_name='CS'}(instructor \bowtie \sigma_{year=2018}(teaches)))$ to English.

Answer

"Find the names of all instructors in the Comp. Sci. department who taught a course in the year 2018."

Step by step:

$\sigma_{year=2018}(teaches)$ — find teaching assignments from 2018

$instructor \bowtie$ (step 1) — join with instructor to get instructor details

$\sigma_{dept_name='CS'}$ — keep only Comp. Sci. instructors

$\pi_{name}$ — return their names

🔗 Cross-References

Next Topic: 11 - Relational Calculus
Previous Topic: 09 - SQL Functions & Triggers
Related: 12 - ER Model (conceptual design before algebra)
Related: 31 - Query Processing (relational algebra in optimization)
Textbook: Silberschatz, Korth, Sudarshan — Chapter 2 (Relational Model), Chapter 6 (Formal Relational Query Languages) Join Discord Previous09 - SQL Functions & TriggersNext11 - Relational Calculus