Relational Foundations

Set vs. Bag Semantics

Relations use set semantics, so a tuple is either present or absent; SQL query results commonly use bag semantics, so equal rows may occur multiple times. Correct SQL reasoning must track when multiplicity is preserved, multiplied, or deliberately removed.

Set semantics record membership, while bag semantics also record the multiplicity of each value.
Plain SQL projection normally preserves duplicates.
Joins can multiply multiplicities: m matching left rows and n matching right rows can produce m × n result rows for a key value.
SQL UNION, INTERSECT, and EXCEPT eliminate duplicates by default; their ALL forms apply bag semantics.
Duplicate elimination has semantic and performance consequences.
C.J. Date argues that duplicates violate the relational model; practical SQL deliberately supports them and defines their behavior.

A duplicate demonstration

`EMPLOYEE(employee_id, department)` input
employee_id	department
1	Engineering
2	Engineering
3	Sales

Projecting department under two semantics
Expression	Result values	Multiplicity
Relational `πdepartment(EMPLOYEE)`	`{Engineering, Sales}`	Each tuple once
SQL `SELECT department FROM employee`	`[Engineering, Engineering, Sales]`	Engineering twice
SQL `SELECT DISTINCT department FROM employee`	`[Engineering, Sales]`	Each result row once

Bag-preserving and duplicate-eliminating forms

SELECT department FROM employee;
SELECT DISTINCT department FROM employee;

SELECT department FROM current_departments
UNION ALL
SELECT department FROM planned_departments;

SELECT department FROM current_departments
UNION
SELECT department FROM planned_departments;