DBMS Notes
Relational algebra is a formal, procedural query language for the relational model. It provides the theoretical foundation for SQL. Operations take one or...
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).
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
Continue the lesson path