Multisets (Bags) and DISTINCT

Sets vs. multisets

The Relational Algebra operates over sets: each tuple appears at most once. Duplicates are automatically eliminated.

SQL is actually based on multisets (bags): a tuple may appear multiple times. The query:

SELECT B, C FROM R;

produces a bag. If $R$ has rows (20, 10, 0, 55) and (11, 10, 0, 7), the result shows (10, 0) twice.

DISTINCT

The DISTINCT keyword brings SQL back to set semantics:

SELECT DISTINCT B, C FROM R;

This eliminates duplicate rows from the output, returning each unique (B, C) pair exactly once.

Why multisets?

Duplicates are essential for aggregate functions (MIN, MAX, AVG, COUNT, SUM, and so on). Consider a marks table:

sid	course	mark
s1	Maths	75
s2	Maths	82
s3	Maths	68
s1	Physics	90
s2	Physics	85

Without keeping duplicates, counting the number of students per course and computing averages would be impossible:

SELECT course, COUNT(*), AVG(mark)
FROM marks
GROUP BY course;

course	COUNT(*)	AVG(mark)
Maths	3	75.0
Physics	2	87.5

GROUP BY

The GROUP BY construct partitions rows into groups based on equality of specified columns. Each group is then reduced by aggregate functions to a single row in the output.

The mental model:

1. Partition the table by the GROUP BY column(s).
2. Within each group, apply the aggregate functions.
3. Output one row per group.

Summary

• RA works on sets; SQL works on multisets (bags).
• DISTINCT restores set semantics by eliminating duplicates.
• Aggregation requires duplicates — without them, counting and averaging are impossible.
• GROUP BY groups rows; aggregate functions reduce each group to a single value.