← 🔣 Relational Algebra & Calculus
Subtopic 3 of 4

2.3Size of query results (minimum and maximum rows)

The idea

The number of rows a set operation or join can return lies in a range that depends only on the sizes of the inputs and on key facts.

Think of it like this: Merging two guest lists: at best they overlap fully, at worst nobody is on both.

Why it exists

GATE asks for the minimum and maximum row counts of an expression.

How it works

  1. Union: from max(m, n) to m + n.
  2. Intersection: from 0 to min(m, n). Difference: from max(0, m − n) to m.
  3. Cross product: exactly m·n.
  4. Join: 0 to m·n; if the join column is a key of S and a NOT NULL foreign key in R, exactly m.

Worked example: |R| = 10, |S| = 6 and the join is on a key of S that is a foreign key of R.

Every R row has exactly one partner, so the join has 10 rows.

Now play with it

  • →Change m and n in the calculator and watch each range.
  • →Write down the minimum of R − S when n > m.
R ∪ S10 to 16
R ∩ S0 to 6
R − S4 to 10
R × S60
R ⋈ S (any join column)0 to 60
R ⋈ S, join column is a key of S, foreign key in R (NOT NULL)10
R left outer join S10 to 60

Try m = 10, n = 6. The join on a key / foreign key pair returns exactly one match per R row, so the result has m rows.

Check yourself

|R| = 5, |S| = 8. The maximum size of R ∪ S is

Remember: Union max(m,n)..m+n; key-FK join returns exactly m.
Exam notes (the dense version)

With |R| = m and |S| = n: R ∪ S has between max(m, n) and m + n rows; R ∩ S between 0 and min(m, n); R − S between max(0, m − n) and m; R × S exactly m·n. A natural join with no matching values gives 0, and if the common attribute is a key of S and a foreign key in R it gives exactly m (when R's foreign key is NOT NULL).

Previous year questions: Relational Algebra & Calculus (12)

PYQs are grouped by topic, so this is the full set for Relational Algebra & Calculus; try the ones that match this subtopic. Open all 12 on the topic page.