Relational Algebra, Tuple Calculus & SQL

Three query languages appear in this chapter, and they are not three alternatives so much as three views of the same thing.

The organising fact is that relational algebra is procedural, relational calculus is declarative, and SQL is calculus in surface syntax that a query optimiser turns back into algebra.

Algebra says how: select these rows, then join, then project. Calculus says what: the set of tuples satisfying this condition. The two are equivalent in expressive power, a result called relational completeness, and a language is judged complete if it can express everything algebra can.

The second organising fact is that algebra operates on sets while SQL operates on multisets. Projection in algebra removes duplicates automatically; in SQL it does not, which is why DISTINCT exists. Almost every discrepancy between a textbook answer and a real query traces to this.

The third is that nulls break the logic. SQL uses three-valued logic, and conditions evaluating to unknown behave like false in a WHERE clause but not in a NOT or a CHECK, which produces the most reliably examined traps in the subject.

1. The Basic Algebra

Six operators are primitive, and everything else is derived from them.

Selection, written with sigma, chooses rows satisfying a predicate. It never changes the number of columns.

Projection, written with pi, chooses columns and, being a set operation, removes any duplicate rows that result.

Union combines two relations, requiring them to be union compatible: the same number of attributes with corresponding domains.

Set difference removes from the first relation every tuple appearing in the second, and also requires union compatibility.

Cartesian product pairs every tuple of one relation with every tuple of the other. If the operands have $m$ and $n$ tuples, the result has $mn$.

Rename, written with rho, gives a relation or its attributes new names, and is what makes self-joins expressible.

2. Derived Operators

Intersection is the difference of a difference, since $R\cap S=R-(R-S)$.

Natural join pairs tuples agreeing on all common attributes and keeps one copy of each such attribute. It is a Cartesian product followed by a selection followed by a projection.

Theta join applies an arbitrary predicate rather than equality on common names, and equijoin is the case where the predicate is a conjunction of equalities.

Outer joins preserve unmatched tuples, padding with nulls. Left outer join keeps unmatched tuples of the left operand, right outer join those of the right, and full outer join both.

Outer joins are the reason nulls appear in results that came from null-free tables, which matters when a later aggregate silently skips them.

Semijoin keeps only those tuples of the left operand that have a match, without adding any columns from the right. It is what a query optimiser uses to reduce data before shipping it across a network.

Antijoin keeps those with no match, and is exactly how a system evaluates NOT EXISTS.

The natural join is not associative in the presence of differing common attributes, so writing a three-way natural join requires care about which attribute names are shared with which operand.

Division answers "for all" questions. Given $R(A,B)$ and $S(B)$, the quotient $R÷S$ is the set of $A$ values paired in $R$ with every $B$ value in $S$.

The canonical use is finding students who have taken every course. Divide an enrolment relation by the course relation.

Division is expressible in the basic operators, which is a standard exam derivation, and its shape is worth memorising as "all candidates, minus those with a missing pairing".

3. Tuple Relational Calculus

A tuple calculus query is written as the set of tuples $t$ satisfying a formula, using the existential and universal quantifiers.

It is declarative: it states a condition rather than a computation, and any equivalent evaluation strategy is permitted.

Safety is the one issue that must be handled. The expression for all tuples not in a relation denotes an infinite set, which no system can materialise.

A safe expression is one whose result contains only values appearing in the database or in the query itself, formalised through the domain of the expression.

Domain relational calculus uses variables ranging over attribute values rather than whole tuples, and is the basis of query-by-example. It has the same expressive power.

Codd's theorem states that relational algebra, safe tuple calculus and safe domain calculus are exactly equivalent, which is the formal content of relational completeness.

4. SQL as Executed Algebra

A basic SQL query maps directly onto algebra. The FROM clause is a Cartesian product, the WHERE clause is a selection, and the SELECT clause is a projection.

The evaluation order is not the writing order. Conceptually the clauses are evaluated FROM, then WHERE, then GROUP BY, then HAVING, then SELECT, then ORDER BY.

This ordering explains two facts students find surprising. A column alias defined in SELECT cannot be used in WHERE, because the alias does not exist yet. But it can be used in ORDER BY, which runs later.

Aggregate functions collapse a group to one value: count, sum, average, minimum and maximum.

WHERE filters rows before grouping; HAVING filters groups after. A condition on an aggregate must go in HAVING, because the aggregate does not exist until groups are formed.

Every column in SELECT must be either grouped or aggregated, since anything else would have no single value per group.

Equivalence Rules

An optimiser rewrites the algebra expression before evaluating it, and the rewrites are the reason declarative querying is practical.

Selections push down through joins, because filtering before joining shrinks both operands and a join is far more expensive than a scan.

Projections push down too, discarding columns as early as they cease to be needed by any later operator.

Selections are commutative among themselves and a conjunction splits into a cascade of separate selections, which is what makes pushing individual conditions to different operands possible.

Joins are commutative and associative, so the optimiser is free to choose the join order, and that choice usually matters more than any other decision it makes.

5. Subqueries

An uncorrelated subquery is evaluated once, independently of the outer query.

A correlated subquery references a column of the outer query, so it is conceptually re-evaluated for each outer row.

EXISTS tests whether a subquery returns any row at all, and what the subquery selects is irrelevant, which is why SELECT 1 is common inside it.

NOT EXISTS is the standard way to express universal quantification, since SQL has no FOR ALL. The pattern of two nested NOT EXISTS expresses "for all x there is a y", and is worth learning as a template.

IN and EXISTS are usually interchangeable, but their null behaviour is not, which the worked examples address.

ANY and ALL compare a value against every row of a subquery. Greater than ALL means greater than the maximum; greater than ANY means greater than the minimum, and reversing the two is a common slip.

A subquery returning no rows makes ALL true and ANY false, which follows from the vacuous truth of a universal statement over an empty set.

Set Operations in SQL

UNION, INTERSECT and EXCEPT correspond to the algebra's union, intersection and difference, and like them require compatible column lists.

They eliminate duplicates by default, which is the one place SQL behaves as a set rather than a multiset.

The ALL variants keep duplicates, and UNION ALL is substantially cheaper because it needs no sorting or hashing to detect them.

EXCEPT ALL uses multiset difference, subtracting occurrence counts rather than removing every matching row, so three copies minus one copy leaves two.

Views

A view is a named query, not stored data. Referencing it substitutes its definition, a process called view expansion.

A materialised view does store its result, trading storage and refresh cost for query speed, which is why data warehouses rely on them.

Not every view is updatable. An update must map unambiguously onto rows of the base tables, so views involving aggregation, DISTINCT, or joins that lose a key are generally read-only.

6. Nulls and Three-Valued Logic

Any arithmetic or comparison involving a null yields null, and null in a boolean context is the third truth value, unknown.

The truth tables extend as expected. Unknown and true gives unknown; unknown and false gives false. Unknown or true gives true; unknown or false gives unknown. Not unknown gives unknown.

A WHERE clause keeps only rows evaluating to true, so unknown behaves like false there.

A CHECK constraint accepts rows evaluating to true or unknown, so unknown behaves like true there. This asymmetry is deliberate and is a favourite examiner target.

Aggregates ignore nulls, except COUNT(*), which counts rows regardless.

If every value in a column is null, SUM and AVG return null, not zero, while COUNT of that column returns zero.

Null is not equal to null, so = NULL never matches and IS NULL must be used. But GROUP BY and DISTINCT treat nulls as equal to each other, which is a second inconsistency worth memorising.

7. Worked Examples

Example 1. Express division $R(A,B)÷S(B)$ using only the basic operators.

The result should be those $A$ values paired with every $B$ in $S$.

Start with all candidate $A$ values, which is ${\pi }_A(R)$.

Form every pairing that would be required, which is ${\pi }_A(R)\times S$. This contains one row for every candidate and every required $B$.

Subtract what actually exists, giving $({\pi }_A(R)\times S)-R$. What remains is exactly the missing pairings: a row here means candidate $a$ is not paired with $b$ in $R$.

Project onto $A$ to get the disqualified candidates, ${\pi }_A(({\pi }_A(R)\times S)-R)$.

Subtract those from all candidates, giving

$R÷S={\pi }_A(R)-{\pi }_A(({\pi }_A(R)\times S)-R)$

The shape to remember is all candidates minus those with a missing pairing, and it recurs whenever a query says "every" or "all".

Example 2. Write SQL for "students who have enrolled in every course", given Student(sid, name), Course(cid, title) and Enrol(sid, cid).

SQL has no universal quantifier, so restate the requirement as a double negative.

"Enrolled in every course" becomes "there is no course in which this student is not enrolled."

SELECT s.sid, s.name
FROM Student s
WHERE NOT EXISTS (
  SELECT 1 FROM Course c
  WHERE NOT EXISTS (
    SELECT 1 FROM Enrol e
    WHERE e.sid = s.sid AND e.cid = c.cid
  )
);

Read it inside out. The innermost query asks whether this student took this course. The middle NOT EXISTS finds courses the student did not take. The outer NOT EXISTS requires that no such course exists.

Both inner queries are correlated, the innermost on both s and c, which is what makes the pattern work.

A counting alternative is often simpler and is worth knowing:

SELECT sid FROM Enrol
GROUP BY sid
HAVING COUNT(DISTINCT cid) = (SELECT COUNT(*) FROM Course);

The DISTINCT matters because a student might enrol in the same course twice, which would inflate the count and produce a false positive.

Example 3. Relation Emp(eid, name, mgr) has one row with mgr null. Compare the results of these two queries.

SELECT name FROM Emp WHERE eid NOT IN (SELECT mgr FROM Emp);
SELECT name FROM Emp e WHERE NOT EXISTS
  (SELECT 1 FROM Emp m WHERE m.mgr = e.eid);

The intent of both is employees who manage nobody.

The second query is correct. For each employee it looks for a row naming that employee as a manager, and reports those with none.

The first query returns nothing at all.

Here is why. The subquery returns a set of manager identifiers including a null. The condition eid NOT IN (...) expands to a conjunction of inequalities, one per returned value.

One of those comparisons is eid <> NULL, which evaluates to unknown, not to true.

A conjunction containing unknown can be false, if another conjunct is false, or unknown, but it can never be true.

Since WHERE keeps only rows evaluating to true, no row survives, and the query returns an empty result even though the intended answer is non-empty.

The fix is either to use NOT EXISTS, or to exclude nulls explicitly with WHERE mgr IS NOT NULL inside the subquery.

The rule to carry forward: NOT IN is unsafe when the subquery can return a null; NOT EXISTS is always safe. IN is unaffected, because a single true comparison makes the disjunction true regardless of any unknowns.

Example 4. A table Sales(region, amount) has 5 rows, of which 2 have a null amount. Give the value of each aggregate.

COUNT(*) returns 5. It counts rows and ignores the contents entirely.

COUNT(amount) returns 3. Aggregates skip nulls, so only the non-null values are counted.

SUM(amount) returns the sum of the 3 non-null values, not treating nulls as zero, though the numeric answer happens to be the same as if it had.

AVG(amount) divides that sum by 3, not by 5. This is where the distinction becomes visible in the result, and it is the standard exam question.

If all 5 amounts were null, COUNT(*) would still be 5, COUNT(amount) would be 0, and SUM and AVG would both return null rather than zero.

COUNT(DISTINCT amount) counts distinct non-null values, so two rows both holding null contribute nothing.

The one place nulls are treated as equal is grouping. A GROUP BY region over rows with null regions puts all of them in a single group, even though NULL = NULL is unknown.

Example 5. Relations $R$ and $S$ have $m$ and $n$ tuples and share exactly one attribute. Give the minimum and maximum number of tuples in $R\times S$, $R\bowtie S$, and $R\text{ LEFT OUTER JOIN }S$.

Cartesian product is exactly $mn$, with no variation, since every pairing is produced unconditionally.

Natural join ranges from 0 to $mn$.

The minimum is 0, when no tuple of $R$ agrees with any tuple of $S$ on the common attribute.

The maximum is $mn$, achieved when every tuple of $R$ and every tuple of $S$ carry the same value in the common attribute, so all pairs match.

Left outer join ranges from $m$ to $mn$.

The minimum is $m$, not 0, because every tuple of $R$ appears at least once, padded with nulls if unmatched.

The maximum is $mn$, the same as the natural join, since padding adds rows only for tuples that matched nothing.

A useful special case: if the common attribute is a key of $S$ and a foreign key in $R$ referencing it, each $R$ tuple matches exactly one $S$ tuple, so both joins return exactly $m$ tuples. Recognising this makes many join-size questions immediate.

Example 6. Translate this algebra expression into SQL, then state what the DISTINCT is for.

The expression is ${\pi }_{name}({\sigma }_{dept=\text{’CS’}}(Student\bowtie Enrol))$.

Work from the inside out. The natural join becomes a join on the common attribute, the selection becomes a WHERE clause, and the projection becomes the select list.

SELECT DISTINCT s.name
FROM Student s JOIN Enrol e ON s.sid = e.sid
WHERE s.dept = 'CS';

The DISTINCT is required because algebra and SQL disagree about duplicates.

Projection in relational algebra produces a set, so duplicate names are removed automatically.

The SQL select list produces a multiset, so a student enrolled in four courses would appear four times.

Without DISTINCT the SQL query is not a translation of the algebra expression but of a bag-semantics variant of it.

The reverse direction has a matching subtlety. Translating SQL into algebra requires an explicit duplicate-elimination operator wherever the SQL query does not use DISTINCT, which is why real optimisers work in a bag algebra rather than the textbook set algebra.

Summary

Algebra is procedural, calculus is declarative, and SQL is calculus in surface syntax compiled back into algebra. Codd's theorem makes algebra, safe tuple calculus and safe domain calculus exactly equivalent.

The six primitive operators are selection, projection, union, set difference, Cartesian product and rename. Intersection, joins and division are derived.

Union and difference require union compatibility. Cartesian product of $m$ and $n$ tuples gives exactly $mn$.

Division answers "for all" questions and has the derivation ${\pi }_A(R)-{\pi }_A(({\pi }_A(R)\times S)-R)$, whose shape is all candidates minus those with a missing pairing.

Tuple calculus needs safety, because unrestricted negation denotes infinite sets.

SQL clauses evaluate FROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BY, which is why an alias works in ORDER BY but not in WHERE. WHERE filters rows and HAVING filters groups.

Universal quantification is written with two nested NOT EXISTS, or by counting with COUNT(DISTINCT ...) against a total.

Nulls give three-valued logic. Unknown behaves like false in WHERE and like true in CHECK. NOT IN over a subquery returning a null yields no rows at all, while NOT EXISTS is always safe.

Aggregates ignore nulls except COUNT(*); AVG divides by the non-null count; all-null columns give null from SUM and AVG but zero from COUNT. Grouping is the one place nulls are treated as equal.

Natural join returns between 0 and $mn$ tuples, left outer join between $m$ and $mn$, and a foreign-key join returns exactly $m$.

Algebra's projection removes duplicates and SQL's does not, so a faithful translation needs DISTINCT. The exception is the set operations, where UNION, INTERSECT and EXCEPT do eliminate duplicates unless ALL is written.

Semijoin and antijoin are how optimisers implement EXISTS and NOT EXISTS, and pushing selections and projections below joins is the rewrite that makes declarative querying practical.

A view is a stored query expanded at reference time, and is updatable only when the update maps unambiguously back onto base table rows.