Relational Foundations
Relational Algebra
Relational algebra is a compositional language of operators that transform one or more input relations into an output relation. It describes what relation is derived while leaving the database free to choose an equivalent and efficient execution strategy.
- Restriction chooses tuples by a predicate; projection chooses attributes and, in the set model, removes duplicate tuples.
- Join combines compatible tuples from two relations according to a condition; a Cartesian product is a join without a restricting condition.
- Union, intersection, and difference require compatible headings.
- Closure makes complex queries composable.
- Division answers “for all” questions, such as which students completed every required course.
- Equivalent algebraic expressions permit optimizers to reorder and combine operations without changing the result.
From algebra to SQL
| Relational operation | Meaning | Typical SQL |
|---|---|---|
Restrict σP(R) | Tuples of R satisfying predicate P | SELECT * FROM R WHERE P |
Project πA,B(R) | Distinct A/B tuples from R | SELECT DISTINCT A, B FROM R |
Join R ⋈P S | Compatible R/S tuple combinations satisfying P | R JOIN S ON P |
Union R ∪ S | Tuples in R or S or both | R_query UNION S_query |
Difference R − S | Tuples in R and not in S | R_query EXCEPT S_query |
Division R ÷ S | Left-side values paired with every required S value | Nested NOT EXISTS, or grouping plus an exact coverage test |
For ENROLLMENT(student_id, course_id) and REQUIRED(course_id), division returns students whose enrollment set covers every required course. The logical test is “there does not exist a required course for which there does not exist a matching enrollment.”
SELECT DISTINCT e.student_id
FROM enrollment AS e
WHERE NOT EXISTS (
SELECT 1
FROM required AS r
WHERE NOT EXISTS (
SELECT 1
FROM enrollment AS taken
WHERE taken.student_id = e.student_id
AND taken.course_id = r.course_id
)
)