Relational algebra meets SQL semantics

Prerequisites: Sets, predicates, and elementary SQL.

Learning objectives

• Translate selection, projection, and joins into query operations.
• Explain bag semantics and three-valued predicates.
• Trace an outer join through filtering and grouping.

Relational algebra describes transformations of relations: selection keeps rows satisfying a predicate; projection keeps attributes; a join combines compatible rows. Classical relations are sets. SQL usually operates on bags, which retain duplicate rows. This difference changes answers, not merely performance. Projecting a department column from ten employee rows can return ten values even if only three departments exist. DISTINCT requests duplicate elimination explicitly.

Consider students Ana and Bo, and enrollment rows (Ana,Databases), (Ana,Networks). Joining students to enrollments on student identifier produces two rows for Ana and none for Bo. A left outer join additionally produces a row for Bo with missing enrollment values represented by NULL. COUNT(*) over that result is three; COUNT(enrollment.course) is two because the latter ignores null inputs. Neither count is automatically the number of distinct students, which is two.

A SQL predicate can evaluate to true, false, or unknown. Comparing a value with NULL using equality produces unknown. WHERE retains only true rows. Use IS NULL to test for missing values. Unknown is not identical to false in every expression: NOT unknown remains unknown. Also distinguish a missing value from the literal empty string, zero, and an absent row. Their meanings and constraints differ.

Placement of a predicate matters for outer joins. Suppose the enrollment join condition includes course='Networks'. Both students remain, with Ana's matching course and Bo's null-extended row. Put the same predicate in WHERE after the outer join, and Bo disappears because his comparison is unknown. The rewritten query now has different semantics. An optimizer can move predicates only when the transformation preserves the query's result under its actual null and duplicate rules.

Grouping partitions rows by grouping keys, computes aggregates, and HAVING filters the groups. WHERE filters rows before grouping. Starting with sales (East,10), (East,20), (West,5), filtering amounts greater than eight before SUM gives only East with thirty. Grouping all sales and applying HAVING SUM(amount)>8 also leaves East, but this coincidence does not justify exchanging arbitrary row and group predicates. Change West to two rows of five and the answers differ.

Finally, no ORDER BY means no promised output order. An index scan appearing sorted today is not a contract. Specify tie-breakers when stable pagination or reproducible presentation matters. Read query plans only after establishing a small, explicit expected result. A fast query returning the wrong multiplicity or excluding unmatched entities is still wrong. The PostgreSQL reference provides precise operator behavior; test portable assumptions separately when changing database engines.

Practice problem

Use people Ana, Bo, and Cy, with purchases (Ana,10), (Ana,20), and (Cy,NULL). Trace a left join from people to purchases. Compute COUNT(), COUNT(amount), and SUM(amount). Then explain which people remain when amount>15 is placed in WHERE, and which remain when that predicate is instead part of the join condition. State why a customer count based on COUNT() would be misleading.

Worked solution

The unfiltered left join has four rows: two for Ana, one null-extended row for Bo, and Cy’s purchase with a null amount. COUNT() is 4, COUNT(amount) is 2, and SUM(amount) is 30. WHERE amount>15 leaves only Ana’s amount 20 row. Placing that test in the join condition retains all three people: Ana has the 20 purchase; Bo and Cy receive null-extended purchase fields. COUNT() then counts joined rows, not distinct people, so purchases can inflate it. COUNT(DISTINCT person_id), or an appropriately grouped query, expresses the customer count directly.

Check your understanding

A left join preserves customer Bo with NULL purchase fields. A predicate purchase.amount>15 is moved from ON into WHERE. What happens to Bo?

• He is retained with amount 0.
• He remains because left joins preserve every left row after all filters.
• He is removed because the comparison is unknown and WHERE keeps only true.
• He becomes two rows because NULL matches every amount.

Explanation

Outer-join preservation occurs before the WHERE filter; null extension does not make later predicates true.

A group contains amounts 5,NULL,5. What are COUNT(*), COUNT(amount), and SUM(amount)?

• 3,3,10
• 2,2,10
• 3,2,NULL
• 3,2,10

Explanation

COUNT(*) counts rows, while COUNT(expression) and SUM omit null inputs.

Primary reading

• Table expressions and query semantics: PostgreSQL Global Development Group
• Database Systems: lectures, notes, and projects: Carnegie Mellon University

Open the study and save your work →