3.1Relational algebra and relational calculus

Relational algebra is a set of operators that produce relations (tables) from relations, and an SQL SELECT statement can internally be interpreted as a combination of these operators. For a database specialist, the value of learning relational algebra is not memorizing formulas but being able to explain, in terms of operator order and cost, why a query in front of you is slow or produces an unintended result. This section covers the meaning of each operator and a common real-world pitfall: choosing the wrong kind of join.

3.1.1Unary operators: selection and projection

• Selection (sigma) extracts only the rows (tuples) that satisfy a condition from a relation. It corresponds to an SQL WHERE clause. Row count decreases, but the column structure is unchanged.
• Projection (pi) extracts only the specified columns (attributes) from a relation. It corresponds to the column list in an SQL SELECT clause. Mathematically, duplicate rows are removed (a property of sets), but note that SQL SELECT retains duplicates by default—DISTINCT is required to remove them.

3.1.2Binary operators: union, difference, product, division

• Union combines two relations with the same attribute structure (union-compatible) into one, removing duplicates. It corresponds to SQL UNION (use UNION ALL to keep duplicates). Difference extracts rows present in one relation but not the other, corresponding to SQL EXCEPT (MINUS in some products).
• Cartesian product produces every combination of rows from two relations (row count is the product of the two). Listing multiple tables in FROM without a join condition produces a Cartesian product—a classic cause of accidentally enormous result sets.
• Division divides relation R by relation S to find the subset of R that is paired with every row of S. It corresponds to queries expressing universal quantification ("for all ...", e.g., "students who passed every subject"), and in SQL the standard idiom is a double NOT EXISTS (verifying in two nested steps that no disqualifying row exists).

3.1.3Join: natural join, equi-join, outer join

• Join conceptually forms a Cartesian product and keeps only the rows matching a join condition (in practice, implementations avoid materializing the full product). An equi-join uses an equality (=) condition. A natural join implicitly joins on identically named columns and removes the duplicate column from the result.
• Inner join keeps only rows that match in both tables. Outer join also keeps unmatched rows, padding the other side with NULL. Left outer join keeps all rows from the left table; right outer join keeps all rows from the right; full outer join keeps all rows from both sides.
• A self join treats a single table as two aliased copies to compare rows against each other. It is used to unfold hierarchical structures, such as looking up each employee's manager's name from the same employee table.

Suppose a DBA receives a requirement to "list students who have passed every required subject." A straightforward approach would be an aggregate one—count each student's passed subjects and compare it to the total number of required subjects—but in relational algebra terms this is a classic case of division. Since SQL has no direct syntax for division, it is built using a double NOT EXISTS: (1) an inner NOT EXISTS subquery finds "a required subject this student has not yet passed," and (2) the outer query keeps only students for whom no such unpassed subject exists. This nested-negation form ("there exists no row failing to satisfy 'does not exist'") is harder to read, but it has the advantage of avoiding miscounts that arise when comparing pass counts involving NULL (confusing an unenrolled subject with a NULL grade). The aggregate approach (comparing via COUNT), while easier to write, has a maintainability drawback: if the list of required subjects changes later, the COUNT baseline must also be updated. If the requirement is that the required-subject list is subject to change, the division approach (double NOT EXISTS) is the design choice that is easier to adapt to future requirement changes. Even when multiple formulations produce the same result, a database specialist chooses based on maintainability, NULL-safety, and resilience to future requirement changes.

3.1.4Section summary

• Selection (sigma) corresponds to narrowing rows (WHERE), projection (pi) to narrowing columns (SELECT)
• A join is a Cartesian product with a condition applied; a natural join implicitly joins on same-named columns, so watch for semantic mismatches
• Division corresponds to universal quantification ("for all"), typically expressed in SQL via a double NOT EXISTS