Table `emp(eid, mgr)` holds rows with eid 1..5 and mgr values NULL, 1, 1, 2, 3. The query `SELECT eid FROM emp WHERE eid NOT IN (SELECT mgr FROM emp)` returns:

eid 4, 5 and the row whose mgr is NULL

Which of the following are true of relational algebra and relational calculus?

Relational algebra and safe tuple relational calculus have the same expressive power

The transitive closure of a relation cannot be expressed in relational algebra

Division can be expressed using only the five basic operators

Relational algebra and safe tuple relational calculus have the same expressive power

The transitive closure of a relation cannot be expressed in relational algebra

Relational algebra is declarative while tuple calculus is procedural

Division can be expressed using only the five basic operators

Relation `Enrolled(sid, cid)` records which students take which courses, and `Required(cid)` lists three compulsory courses. Which relational algebra operation finds the students taking all three?

Natural join, then projection on sid

Intersection of the two relations

A column `mgr` contains the values NULL, 1, 1, 2, 3. How many groups does `SELECT mgr, COUNT(*) FROM emp GROUP BY mgr` produce?

4 — the nulls form one group of their own

3, and the null row is reported separately without a group

Why does SQL need `WITH RECURSIVE` to compute the ancestors of a node in a `Parent(child, parent)` table?

Because transitive closure is not expressible in relational algebra, so no fixed query can compute it

Because recursive queries run faster than joins

Because transitive closure is not expressible in relational algebra, so no fixed query can compute it

Because the table has a foreign key to itself

Because nulls in the parent column break ordinary joins

ER Model, Relational Algebra, Tuple Calculus and SQL

Section 9 of the Computer Science paper. The chapter follows one pipeline: a design in the ER model, mapped to tables, queried by an algebra, described by a calculus, and written in SQL. Each stage answers a different kind of question and the questions are rarely interchangeable. ER mapping is a counting problem with a rule you can apply without judgement: cardinality decides how many tables, participation decides whether nulls appear — an M:N relationship always needs a table of its own, anything else folds into one of the entity tables. Relational algebra is procedural: five basic operators (selection, projection, union, difference, cross product), everything else derived, and the examinable content is which operators a query needs and how many tuples come out. Tuple calculus is declarative — you describe the answer rather than the route to it — and it is in the syllabus for one reason worth knowing: it is what makes the statement relational algebra and safe tuple calculus have exactly the same expressive power precise, and therefore what makes it meaningful to say that neither can compute a transitive closure. Then SQL, which is neither: it is the algebra with bags instead of sets and, crucially, with three-valued logic. Almost every SQL question that looks hard is a null question underneath — COUNT(*) and COUNT(x) differ, AVG is not SUM/COUNT(*), and a NOT IN subquery that returns a single null returns you nothing at all.

ER to Tables: Cardinality Counts, Participation Nulls

Minimum tables for one binary relationship between two entity sets
Structure	Minimum tables	Why
M:N relationship	3	Neither key determines the other, so the pairs need a table of their own
1:N relationship	2	Each N-side row has at most one partner, so it carries a foreign key
1:1 relationship	2	Fold into either side; prefer the totally participating one
A weak entity set	+1	Its own table, whose primary key includes the owner’s key
A multivalued attribute	+1	One row per value; a column cannot hold a set in 1NF

⚠️ Participation changes the nulls, not the table count

The two ideas get conflated constantly, so keep them apart. Cardinality (1:1, 1:N, M:N) decides how many tables the minimum answer has. Participation (total or partial) decides whether the merged foreign key can be null. In a 1:N relationship where the N side participates partially, folding the relationship in still gives 2 tables — the unrelated rows simply carry a null foreign key. If the N side participates totally, every row has exactly one partner and the column is NOT NULL, which is strictly better but not a different count. So when a question asks for the minimum number of tables, read only the cardinality; when it asks whether a decomposition avoids nulls, or whether a foreign key can be declared NOT NULL, read the participation. The one place participation does move the count is a design that refuses nulls on principle: then a partial 1:1 needs a third table, because merging either way forces them.

Five Operators, and What Division Is Made Of

Relational algebra has exactly five basic operators — selection σ, projection π, union ∪, set difference −, and cross product × — and everything else is shorthand. Intersection is R − (R − S). A natural join is a cross product, then a selection on the equal attributes, then a projection removing the duplicate column. Division is the one that looks primitive and is not, and deriving it is worth doing once because the derivation is the intuition: R ÷ S asks for the values on R’s remaining attributes that appear with every tuple of S, and the way to compute that with only the basic operators is to find the ones that fail and subtract them.

🧠 Division, derived and then run on an instance

With X = the attributes of R that are not in S, the identity is R ÷ S = π_X(R) − π_X((π_X(R) × S) − R). Read it right to left. π_X(R) × S is every pairing that would have to exist for a value to qualify; subtracting R leaves exactly the missing pairings; projecting those onto X names the values that failed; and removing them from all the values in R leaves the ones that succeeded. Run on an instance: R(sid, cid) records who takes which course, S holds c1, c2, c3, and s1 and s4 take all three while s2 takes two and s3 takes one. Then π_sid(R) is {s1, s2, s3, s4}, the cross product has 12 pairs, subtracting R leaves precisely (s2,c3), (s3,c2), (s3,c3), whose projection is {s2, s3} — and {s1,s2,s3,s4} − {s2,s3} is {s1, s4}, which is what division means. The examinable form of division is always this: find the entities related to all of a set, and the phrase "all of" in a question is what tells you the answer needs it.

Result cardinality: what you can bound without seeing the data
Operation on R (n tuples) and S (m tuples)	Minimum	Maximum
R × S (cross product)	n × m	n × m — it is exact
Natural join on a common attribute	0 — no matching values	n × m — one common value everywhere
R ∪ S (same schema)	max(n, m) — one contains the other	n + m — disjoint
R − S	0 — R ⊆ S	n — disjoint
π on a non-key attribute list	1	n — projection removes duplicates
Left outer join	n — every R tuple survives	n × m

Tuple Calculus, and Why the Syllabus Names It

Tuple relational calculus writes a query as { t | P(t) } — the set of tuples t satisfying a first-order formula P — and it is declarative: it says what the answer contains, never how to compute it. Where algebra writes π_name(σ_{dept = "Sales"}(Emp)), the calculus writes { t.name | Emp(t) ∧ t.dept = “Sales” }. Quantifiers do the work joins do in algebra: an ∃ over a second relation is a join, and a ∀ is a division. Domain relational calculus is the same thing with variables ranging over attribute values rather than whole tuples, and the two are equivalent.

🎯 Safety, and the equivalence the whole topic exists to state

The calculus can write nonsense the algebra cannot. { t | ¬ Emp(t) } is a legal formula and names every tuple in the universe that is not an employee — an infinite answer. An expression is called safe when its result is guaranteed finite, which in practice means every variable is bounded by some relation. The reason this matters is the theorem the syllabus is pointing at: relational algebra, safe tuple calculus and safe domain calculus have exactly the same expressive power. Three notations, one class of queries — which is what makes it meaningful to say a query is not expressible. And the standard example of one that is not is transitive closure: from a relation Parent(x, y) you cannot write Ancestor(x, y) in relational algebra, because a fixed expression has a fixed number of joins and ancestry needs unboundedly many. That is not a gap in your query-writing; it is a proved limit, and it is why SQL had to add WITH RECURSIVE as an extension rather than as sugar. Aggregation is the same story — COUNT and SUM are outside the pure algebra too, which is why SQL is described as the algebra plus aggregation, on bags rather than sets.

SQL Is Three-Valued, and That Is the Question

A null is not a value; it is the absence of one, and every comparison involving it evaluates to unknown rather than true or false. NULL = NULL is unknown. So is NULL <> NULL. A WHERE clause keeps a row only when its condition is true, so unknown behaves like false there — but not everywhere, and that gap is where the marks are. The results below were produced on a five-row emp table in which one salary and one manager are null.

Five rows, one null salary, one null manager — what each query returns
Query	Result	Why
`COUNT(*)`	5	Counts rows, and a row exists whatever it contains
`COUNT(salary)`	4	Counts non-null values of that column
`COUNT(DISTINCT salary)`	3	Two employees share 70000, and the null is still skipped
`AVG(salary)`	62500	250000 / 4 — the divisor is the non-null count
`SUM(salary) / COUNT(*)`	50000	250000 / 5 — a different question, 12500 apart
`GROUP BY mgr`	4 groups	The nulls form one group — grouping treats them as equal

⚠️ A NOT IN subquery containing one null returns nothing at all

This is the single most valuable null fact in the section, and it is not intuitive. Asking for employees who manage nobody as WHERE eid NOT IN (SELECT mgr FROM emp) returns zero rows, even though two such employees plainly exist. Expand it: eid NOT IN (NULL, 1, 1, 2, 3) means eid ≠ NULL AND eid ≠ 1 AND …, and eid ≠ NULL is unknown, so the whole conjunction can never be true — the best it can be is unknown, and WHERE discards that. Two repairs, both worth knowing. Add WHERE mgr IS NOT NULL to the subquery, and the same query returns the two rows. Or write it as NOT EXISTS (SELECT 1 FROM emp m WHERE m.mgr = e.eid), which returns those two rows without the guard — because NOT EXISTS asks whether a row was found, a genuinely two-valued question that nulls cannot poison. And note the asymmetry that makes this so easy to miss: IN with a null is safe (1 IN (1, NULL) is true, because one disjunct is true), while NOT IN with a null is not. The rule to carry: NOT IN over a nullable column is a bug until proved otherwise; prefer NOT EXISTS.

Key takeaways

Cardinality decides the minimum table count: M:N needs 3, 1:N and 1:1 need 2, a weak entity adds one.
Participation decides whether the foreign key can be null, not how many tables there are.
Five basic operators: σ, π, ∪, − and ×. Intersection, join and division are all derived.
R ÷ S = π_X(R) − π_X((π_X(R) × S) − R): find the values that fail, then subtract them.
A natural join can return anything from 0 to n × m tuples; a left outer join returns at least n.
Algebra, safe tuple calculus and safe domain calculus have identical expressive power.
Transitive closure and aggregation are outside pure relational algebra — a proved limit, not a gap in skill.
COUNT(*) counts rows; COUNT(x) counts non-null values; AVG(x) divides by the non-null count.
NOT IN over a nullable column returns nothing; NOT EXISTS is the safe form.
GROUP BY treats nulls as one group, even though NULL = NULL is unknown.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

An ER diagram has two entity sets E1 and E2 joined by a single M:N relationship R, with R carrying one descriptive attribute of its own. What is the minimum number of tables in the relational schema?
1. 2
2. 3
3. 4
4. 1
Show answer
Answer: B — 3
3. In an M:N relationship neither entity’s key determines the other, so a row of E1 can pair with many rows of E2 and vice versa — there is nowhere in either entity table to put a single foreign key. The pairs therefore need a table of their own, whose primary key is the two foreign keys together, and R’s descriptive attribute goes there as an ordinary column. Note that the attribute does not change the count: it needed a third table already, and an M:N relationship without an attribute still needs one. Option A is the answer for 1:N or 1:1, where the many-side (or either side) can carry a foreign key. Option C would follow from giving the relationship attribute a table of its own, which nothing requires. The rule to apply mechanically: read the cardinality for the table count, and the participation only for whether a foreign key can be NOT NULL.
A table emp has 5 rows. The salary column is 50000, 60000, 70000, 70000 and NULL. The value of AVG(salary) − SUM(salary)/COUNT(*) is ______
Numerical answer — type the value.
Show answer
Answer: 12500
12500. The two expressions differ only in their divisor, and that is the whole point. SUM(salary) skips the null and is 250000. AVG(salary) also skips the null and divides by the count of non-null values, so it is 250000 / 4 = 62500. SUM(salary)/COUNT(*) divides the same numerator by the count of rows, 250000 / 5 = 50000. The difference is 62500 − 50000 = 12500. So AVG(x) is SUM(x)/COUNT(x), never SUM(x)/COUNT(*), and the two agree only when the column has no nulls. Getting 0 means both were treated as the same expression, which is the assumption the question exists to break. For completeness on the same column: COUNT(*) is 5, COUNT(salary) is 4, and COUNT(DISTINCT salary) is 3, because 70000 appears twice and the null is skipped in both column forms.
Table emp(eid, mgr) holds rows with eid 1..5 and mgr values NULL, 1, 1, 2, 3. The query SELECT eid FROM emp WHERE eid NOT IN (SELECT mgr FROM emp) returns:
1. eid 4 and 5
2. No rows at all
3. eid 4, 5 and the row whose mgr is NULL
4. All five rows
Show answer
Answer: B — No rows at all
No rows at all, and this is the most valuable null fact in the section because the intended answer is so obviously 4 and 5. Expand the predicate: eid NOT IN (NULL, 1, 1, 2, 3) is eid ≠ NULL AND eid ≠ 1 AND eid ≠ 1 AND eid ≠ 2 AND eid ≠ 3. The first conjunct is unknown for every row, because no comparison with a null is ever true or false. A conjunction containing unknown is at best unknown, WHERE keeps only rows where the condition is true, and so every row is discarded. Option A is what the query was meant to return, and it is what you get from either repair: add WHERE mgr IS NOT NULL to the subquery, or rewrite as NOT EXISTS (SELECT 1 FROM emp m WHERE m.mgr = e.eid), which is immune because it asks whether a row was found rather than comparing values. Note the asymmetry: plain IN is safe with nulls — 1 IN (1, NULL) is true, since one disjunct is true — so only the negated form is dangerous.
Relations R and S have n and m tuples respectively and share exactly one attribute. The number of tuples in their natural join is:
1. Exactly n × m
2. Between 0 and n × m
3. Between min(n, m) and n × m
4. Exactly min(n, m)
Show answer
Answer: B — Between 0 and n × m
Between 0 and n × m, and both ends are reachable. The lower end: if no value of the common attribute appears in both relations, nothing matches and the result is empty — a join is not obliged to return anything. The upper end: if every tuple of R and every tuple of S carries the same value of the common attribute, every pair matches and the result is the full n × m, exactly as if it had been a cross product. Option C assumes at least one match per tuple, which requires a foreign-key constraint the question does not state — that assumption is precisely what makes join-cardinality questions catch people. Option A is the cross product, which the natural join reduces to only in the degenerate case above. A useful companion bound: a left outer join returns at least n tuples, because every R tuple survives whether or not it matched.
Which of the following are true of relational algebra and relational calculus?
1. Relational algebra and safe tuple relational calculus have the same expressive power
2. The transitive closure of a relation cannot be expressed in relational algebra
3. Relational algebra is declarative while tuple calculus is procedural
4. Division can be expressed using only the five basic operators
Show answer
Answer: A — Relational algebra and safe tuple relational calculus have the same expressive power; B — The transitive closure of a relation cannot be expressed in relational algebra; D — Division can be expressed using only the five basic operators
A, B and D. A is the equivalence theorem the syllabus is pointing at when it names tuple calculus, and the word safe is load-bearing: unrestricted calculus can write { t | ¬ Emp(t) }, an infinite answer that no algebra expression has. B follows from A being about a fixed language — an algebra expression contains a fixed number of joins, while ancestry needs unboundedly many, which is why SQL added WITH RECURSIVE as a genuine extension. D is the identity R ÷ S = π_X(R) − π_X((π_X(R) × S) − R), so division is shorthand rather than primitive; the same is true of intersection and every join. C has it exactly backwards: algebra is procedural — you write the sequence of operations that computes the answer — and calculus is declarative, describing the answer with a formula and saying nothing about how to get it. That is the one distinction between the two worth remembering, and reversing it is the commonest error here.
Relation Enrolled(sid, cid) records which students take which courses, and Required(cid) lists three compulsory courses. Which relational algebra operation finds the students taking all three?
1. Natural join, then projection on sid
2. Division: Enrolled ÷ Required
3. Intersection of the two relations
4. Left outer join on cid
Show answer
Answer: B — Division: Enrolled ÷ Required
Division, and the phrase that tells you so is "all three". Division Enrolled ÷ Required returns exactly the sid values that appear paired with every cid in Required. Option A is the trap and it is worth seeing why it fails: the join followed by a projection returns every student taking at least one required course, because a projection cannot check that all three matches were present — it has already collapsed the rows. The general shape is worth recognising: "at least one" is a join and a projection, "all of" is a division. Option C is not even type-compatible — intersection needs both relations to have the same schema, and these differ. Option D changes which unmatched rows survive and answers nothing about completeness. If you have to compute it with basic operators, the identity is π_sid(Enrolled) − π_sid((π_sid(Enrolled) × Required) − Enrolled): find the students missing a required pairing, then subtract them.
A column mgr contains the values NULL, 1, 1, 2, 3. How many groups does SELECT mgr, COUNT(*) FROM emp GROUP BY mgr produce?
1. 3 — the nulls are discarded
2. 4 — the nulls form one group of their own
3. 5 — one group per row
4. 3, and the null row is reported separately without a group
Show answer
Answer: B — 4 — the nulls form one group of their own
4 — groups for 1, 2, 3, and one group holding the null row. This is a real asymmetry in SQL and worth holding next to the previous question: GROUP BY treats nulls as equal to each other for the purpose of grouping, even though NULL = NULL evaluates to unknown and no WHERE clause could ever match them that way. The same convention applies to DISTINCT, which collapses multiple nulls to one, and to UNION, which removes duplicate nulls. Option A confuses grouping with aggregation: it is the aggregate functions that skip nulls — COUNT(mgr) over this column is 4, not 5 — while GROUP BY keeps them. Option C would need every value to be distinct, but 1 appears twice. The rule: nulls are ignored inside aggregate functions and treated as one value by grouping, DISTINCT and set operations.
Why does SQL need WITH RECURSIVE to compute the ancestors of a node in a Parent(child, parent) table?
1. Because recursive queries run faster than joins
2. Because transitive closure is not expressible in relational algebra, so no fixed query can compute it
3. Because the table has a foreign key to itself
4. Because nulls in the parent column break ordinary joins
Show answer
Answer: B — Because transitive closure is not expressible in relational algebra, so no fixed query can compute it
It is a proved limit on the language, not a performance or convenience matter. A relational algebra expression — and therefore an ordinary SQL query, which is that algebra on bags plus aggregation — contains a fixed number of joins. Self-joining Parent k times finds ancestors exactly k generations up, so any fixed query answers the question only for a bounded depth, while ancestry is unbounded: the answer depends on data you have not seen. No amount of cleverness closes that gap, which is why WITH RECURSIVE is a genuine extension to the language rather than shorthand for something already writable. Option A inverts the reason — recursion is added for expressiveness, and it is not the faster route to anything expressible without it. Option C describes the schema accurately and explains nothing; a self-referencing foreign key is ordinary. Option D is a real hazard elsewhere (NOT IN over a nullable column) but a table with no nulls at all still cannot have its closure computed by a fixed query.