Relational Algebra & SQL

Relational Algebra — The Math Behind SQL

Think of relational algebra as the blueprint language, and SQL as the human-friendly version. Every SQL query can be translated to relational algebra.

---

Basic Operations — The Building Blocks

Selection (σ) — Filter Rows

Analogy: Like a coffee filter — only what matches passes through.

σ_condition(R) = all rows in R satisfying condition

Example: σ_salary>50000(Employee)
→ Returns all employees earning more than 50,000

SQL equivalent: SELECT * FROM Employee WHERE salary > 50000;

Projection (π) — Pick Columns

Analogy: Like cutting out only certain columns from a spreadsheet.

π_col1,col2(R) = only those columns (duplicates removed!)

Example: π_name,dept(Employee)
→ Returns unique (name, dept) combinations

SQL equivalent: SELECT DISTINCT name, dept FROM Employee;

Rename (ρ) — Give a New Name

ρ_NewName(R) = relation R renamed to NewName

---

Set Operations — Combine Tables

Requirement: Both tables must be union-compatible (same number of columns, compatible domains).

R ∪ S  = all rows in R OR S (no duplicates)
R ∩ S  = rows that appear in BOTH R and S
R − S  = rows in R but NOT in S

Example:

Students_2023: {Alice, Bob, Carol}
Students_2024: {Bob, Carol, Dave}

Union:       {Alice, Bob, Carol, Dave}
Intersection: {Bob, Carol}
2023 - 2024:  {Alice}  (students who left)

---

Cartesian Product (×) — Every Combination

R × S = every row from R paired with every row from S
If R has 3 rows and S has 4 rows → R × S has 12 rows

Very expensive! Usually used only as base for joins.

---

Joins — The Heart of Multi-Table Queries

Natural Join (⋈)

Analogy: Match puzzle pieces — join on ALL common column names automatically.

R ⋈ S = match rows where ALL common attributes are equal,
        remove duplicate columns in result

STUDENT(RollNo, Name, DeptID) ⋈ DEPARTMENT(DeptID, DeptName)
→ All students with their department name, DeptID appears once

Theta/Equi Join

R ⋈_condition S = σ_condition(R × S)
Equi join: condition uses only = comparisons

Outer Joins — Include Non-Matching Rows

Analogy: Left outer join = "keep ALL left rows, even if no match on right side."

Left Outer  (R ⟕ S): All R rows; unmatched get NULL for S columns
Right Outer (R ⟖ S): All S rows; unmatched get NULL for R columns
Full Outer  (R ⟗ S): All rows from both, NULLs where no match

Example:
EMPLOYEE ⟕ DEPARTMENT (on DeptID)
→ Even employees with no department appear (DeptName = NULL)

Division (R ÷ S) — "For ALL"

Analogy: Find students who passed ALL mandatory subjects.

R ÷ S = rows in R's extra columns that appear with EVERY S row

Example:
PASSED(Student, Subject)  ÷  MANDATORY(Subject)
= Students who passed ALL mandatory subjects

Formula: R ÷ S = π_x(R) − π_x( (π_x(R) × S) − R )

---

SQL — The Practical Language

Basic Query Structure

SELECT column1, column2        -- What to show
FROM table1                    -- Where to look
WHERE condition                -- Filter rows
GROUP BY column                -- Group for aggregation
HAVING group_condition         -- Filter groups (after aggregation)
ORDER BY column DESC;          -- Sort results

Aggregation Functions

COUNT(*) -- counts all rows including NULLs
COUNT(col) -- counts non-NULL values
SUM(salary) -- sum of values
AVG(salary) -- average (ignores NULLs)
MIN(salary), MAX(salary)

-- Example: Average salary by department, only depts with avg > 50000
SELECT dept, AVG(salary) as avg_sal
FROM Employee
GROUP BY dept
HAVING AVG(salary) > 50000;

KEY RULE: WHERE vs HAVING

WHERE  = filter individual ROWS (before grouping)
HAVING = filter GROUPS (after aggregation)

WRONG: SELECT dept FROM Employee WHERE AVG(salary) > 50000 GROUP BY dept;
RIGHT: SELECT dept FROM Employee GROUP BY dept HAVING AVG(salary) > 50000;

JOINs in SQL

-- Inner join: only matching rows
SELECT s.name, d.dname
FROM Student s INNER JOIN Department d ON s.dept_id = d.id;

-- Left join: all students, even without a department
SELECT s.name, d.dname
FROM Student s LEFT JOIN Department d ON s.dept_id = d.id;

-- Right join: all departments, even without students
SELECT s.name, d.dname
FROM Student s RIGHT JOIN Department d ON s.dept_id = d.id;

Subqueries

-- Scalar subquery (returns single value)
SELECT name FROM Employee
WHERE salary > (SELECT AVG(salary) FROM Employee);

-- EXISTS (check if rows exist)
SELECT name FROM Student s
WHERE EXISTS (
  SELECT 1 FROM Enrolled e
  WHERE e.sid = s.id AND e.course = 'GATE-Prep'
);

-- IN
SELECT name FROM Employee
WHERE dept IN (SELECT dept FROM Department WHERE location = 'Mumbai');

---

NULL Handling — The Tricky Part

NULL = unknown or not applicable
NULL + anything = NULL
NULL = NULL → UNKNOWN (not TRUE!)
NULL != NULL → UNKNOWN

WHERE and HAVING discard UNKNOWN (only TRUE passes)

So: WHERE salary = NULL  ← Never works! Use:
    WHERE salary IS NULL
    WHERE salary IS NOT NULL

COUNT(*) counts NULLs; COUNT(col) ignores NULLs
SUM, AVG, MIN, MAX all IGNORE NULLs

---

Quick Check

Q1. Write RA for: "Names of employees earning more than 50000 in CS dept" Answer: π_name(σ_salary>50000 AND dept='CS'(Employee))

Q2. What does LEFT JOIN return that INNER JOIN does not? Answer: Rows from the left table that have NO matching row in the right table (with NULLs for right columns)

Q3. Is: SELECT dept, COUNT() FROM Employee WHERE COUNT() > 5 GROUP BY dept — correct? Answer: No — cannot use aggregate function in WHERE. Use HAVING: ... GROUP BY dept HAVING COUNT() > 5*