A language for queries
Before SQL there was relational algebra, a small set of operations that take tables (relations) and produce tables. Query optimisers still translate your SQL into these operations before running it.
Selection σ (which rows?)
σ condition (R) keeps the rows of R for which the condition is true. All columns stay.
σ dept='CS' (Students) returns Asha, Meera and Kabir.
Projection π (which columns?)
π columns (R) keeps only the listed columns. Because a relation is a set, identical result rows are merged.
π dept (Students) returns CS, EE and ME, only 3 rows from 6 students.
Combining operations
Operations nest from the inside out:
π name (σ gpa>8 (Students)) selects the students with gpa above 8 (Asha, Meera, Zara), then keeps their names.
| Algebra | SQL |
|---|---|
| σ dept=‘CS’ (Students) | SELECT * FROM Students WHERE dept = ‘CS’ |
| π name, dept (Students) | SELECT DISTINCT name, dept FROM Students |
| π name (σ gpa>8 (Students)) | SELECT DISTINCT name FROM Students WHERE gpa > 8 |
Other operators
- Union ∪, intersection ∩, difference − combine two tables with the same columns.
- Cartesian product × pairs every row of one table with every row of another.
- Join ⋈ is a product followed by a selection, see SQL joins.
- Rename ρ gives a table or column a new name.
Why it matters
An optimiser can rewrite σ and π into cheaper equivalents, for example pushing selections down so that fewer rows reach an expensive join. An index such as a B+ tree makes a selection on an indexed column fast.
Code
students = [
(1, 'Asha', 'CS', 9.1), (2, 'Ravi', 'EE', 7.4), (3, 'Meera', 'CS', 8.2),
(4, 'John', 'ME', 6.9), (5, 'Zara', 'EE', 8.8), (6, 'Kabir', 'CS', 7.1),
]
def select(rows, test):
return [r for r in rows if test(r)]
def project(rows, cols):
out = []
for r in rows:
t = tuple(r[c] for c in cols)
if t not in out: # a relation is a set
out.append(t)
return out
print(project(select(students, lambda r: r[3] > 8), [1])) # [('Asha',), ('Meera',), ('Zara',)]Common mistakes
- Mixing up the symbols: σ picks rows, π picks columns.
- Forgetting that projection removes duplicates, while SQL’s plain SELECT keeps them.
- Writing the operations in the wrong order. The innermost one runs first.
Complexity at a glance
| Case / operation | Time | Why |
|---|---|---|
| Selection σ | O(n) | One test per row, or O(log n) with an index. |
| Projection π | O(n) | Plus duplicate removal, which needs hashing or sorting. |
| Duplicate elimination | O(n) hashing, O(n log n) sorting | |
| Extra space | O(n) for the result |
Quick check
Test yourself — pick an answer to see if you got it.
1. What does σ gpa > 8 (Students) return?
Selection σ filters rows. All columns are kept.
2. What does π name (Students) return?
Projection π chooses columns, and because a relation is a set, duplicate rows are removed.
3. Which expression gives the names of students with gpa above 8?
Select the rows first (σ), then keep only the name column (π).
4. The SQL command SELECT dept FROM Students corresponds to which operation, ignoring duplicates?
SQL's SELECT list is projection. The WHERE clause is selection.