GATE CS 1999 Q1.18 — Relational Model: Relational Algebra

To find the maximum and minimum sizes of the join of relation $R$ (with $m$ tuples) and relation $S$ (with $n$ tuples), we consider the behavior of the join condition:

1. Maximum Size ($mn$): The maximum size occurs when every tuple in $R$ matches with every tuple in $S$. This happens if:
   • The join is a Cartesian product (cross join), or
   • The join attribute has the exact same value across all $m$ tuples of $R$ and all $n$ tuples of $S$.
   In this scenario, the total number of resulting tuples is $m imes n = mn$.


2. Minimum Size ($0$): The minimum size occurs when there are no matching values between the join attributes of $R$ and $S$ (i.e., the intersection of the join attribute values is empty). In this scenario, no tuples satisfy the join condition, resulting in $0$ tuples.

Therefore, the maximum and minimum sizes of the join are $mn$ and $0$, respectively.