Consider two database relations R and S having 3 tuples in R and 2 tuples in…

Concept

The natural join R ⋈ S pairs each tuple of R with each tuple of S that agrees on every attribute common to both relations, producing at most one output tuple per (R-tuple, S-tuple) combination. So the join can never have more than |R| × |S| tuples, and this bound is reached whenever every tuple of R agrees with every tuple of S on the shared attribute(s) — for instance when R and S share no attribute at all, so the natural join degenerates into a Cartesian product.

Application

1. |R| = 3 and |S| = 2, so the upper bound on the number of output tuples is 3 × 2 = 6.

2. This bound is attained: if R and S have no common attribute (or the common attribute holds one identical value across every tuple of both relations), every one of the 3 tuples in R pairs with every one of the 2 tuples in S.

3. That gives 3 × 2 = 6 output tuples, the maximum possible.

Cross-check

A common misconception assumes the join is capped at min(|R|, |S|) = 2, as if it were a one-to-one or foreign-key match. That particular cap of 2 follows only when the join attribute is a key of R, the larger relation (3 tuples): each tuple of S can then match at most one tuple of R, giving at most |S| = 2 rows. If instead the join attribute were a key of S only, the bound would be |R| = 3, not 2. Natural join carries no general uniqueness requirement, though: the join-attribute value can repeat across multiple tuples in both relations, letting one S-tuple match several R-tuples at once — so the true upper bound, with no key constraint assumed, is the product |R| × |S| = 6, not the smaller of the two counts.