# Minimum and Maximum Number of Tuples

Consider Relations R and S where are R is having m tuples and S is having n tuples . m<=n . What would be the minimum and maximum number of tuples in each of the following cases (Assume that nothing is mentioned about key constraints)

1. R union S
2. R intersection S
3. R-S
4. S-R
5. R NATURAL JOIN S
6. R Left OUTER Join S
7. R/S

My Work

1. R UNION S

max : n+m ( union we add all the tuples from both relations)

min: 0 ( taking m=n=null )

1. R INTERSECTION S

max : m ( m < n both relation contains same keys then we may get maximum m keys )

min: 0 ( taking m=n=null if no common keys in both relations)

1. R - S

max : m ( if they are disjoint then in R-S we will get all tuples of R )

min: 0 ( if all tuples in R is also present in S)

1. S-R

max : n ( as explained above )

min: 0 ( as explained above )

1. R natural join S

max : n*m ( if no matching key constraints natural join will produce Cartesian product )

min: m ( m < n when key constraints are taken into consideration )

1. R LEFT OUTER JOIN S

max : m ( everything from left table will be output even if no match)

min: 0 ( when m=0 )

1. R/S

max : m ( when n=0 )

min: Im Not able to make a conclusion

1. `R UNION S`

• max : n+m ( union we add all the tuples from both relations)
Correct, when R and S have no common tuple.

• min: 0 ( taking m=n=null )
Wrong, the minimum is `n` (the greatest of the two sizes, m and n). When all the tuples of R also exist in S.
And m and n cannot be null, they are the sizes of the relations, they are numbers (integers).

2. `R INTERSECTION S`

• max : m ( `m<n` both relation contains same keys then we may get maximum m keys )
Correct but the reasoning is wrong. You compare tuples of the two relations, not keys.

• min: 0 ( taking m=n=null if no common keys in both relations)
Correct but the reasoning is wrong. The result can be 0 because the two relations may have no common tuples).

3. `R - S`

• max : m ( if they are disjoint then in R-S we will get all tuples of R )
Correct

• min: 0 ( if all tuples in R is also present in S)
Correct

4. `S - R`

• max : n ( as explained above )
Correct

• min: 0 ( as explained above )
Wrong, the minimum is `n - m`.

5. `R natural join S`

• max : n*m ( if no matching key constraints natural join will produce Cartesian product )
Correct

• min: m ( m < n when key constraints are taken into consideration )
Wrong, the minimum is `0`. You can easily find an example, identical with case 2 (`INTERSECTION`).

6. `R LEFT OUTER JOIN S`

• max : m ( everything from left table will be output even if no match)
Wrong, the maximum is `m * n`, the same as for natural join. Or just take `ON TRUE`.

• min: 0 ( when m=0 )
Wrong, the minimum is `m`. Example can be the same as for `NATURAL` join above (or just take `ON FALSE`) but it cannot give as a result lees than the number of tuples in `R` (the left relation in the join).

7. `R / S`

• max : m ( when n=0 )
Correct but it doesn't have to be n=0 or m=0. You can find another example.

• min: I'm not able to make a conclusion.
Minimum is `0` Consider that relational division is similar to integer division. `3 / 7` gives `0` in integer division for example. Try to convert this into relational division.

I have recompiled the above answer more lucidly and added some more relational algebra operations. Hope, it's useful :)

Consider Relations R and S where R is having m tuples and S is having n tuples. m<=n . What would be the minimum and maximum number of tuples in each of the following cases (Assume that nothing is mentioned about key constraints)

1. R union S
2. R intersection S
3. R-S
4. S-R
5. R NATURAL JOIN S
6. R Left OUTER Join S
7. R/S
8. R CROSS PRODUCT S
9. R Right OUTER Join S
10. R Full OUTER Join S

These results have been determined considering generic tables without any given candidate keys involved.

Note: if candidate keys for a given table are given, then results will be different.

1. `R UNION S`

• max : n+m

Reason : union we add all the tuples from both relations. i.e. When R and S have no common tuple.

• min: n

Reason : The minimum is `n` (the greatest of the two sizes, m and n). When all the tuples of R also exist in S.

2. `R INTERSECTION S`

• max : m ( `m<n` )

Reason : both relation contains same tuples then we may get maximum m keys

• min: 0

Reason :  if no common tuples in both relations

3. `R - S`

• max : m

Reason : if they are disjoint (if they have no element in common) then in R-S we will get all tuples of R

• min: 0

Reason : if all tuples in R is also present in S

4. `S - R`

• max : n

Reason : if they are disjoint (if they have no element in common) then in S-R we will get all tuples of S

• min: n-m

Reason : m<n there will be some tuples in S after deleting the common tuples

5. `R natural join S`

• max : n*m

Reason : if no matching key constraints, natural join will produce Cartesian product

• min: 0

Reason : Identical with case 2 (`INTERSECTION`).

6. `R LEFT OUTER JOIN S`

• max : m*n

Reason : if all rows in left table matches with all rows in right table

• min: m (including every tuple from the left table)

Reason : if no tuple matches between the two table, but still we have to include all the tuples from the left table.

The minimum is 1 when m=1 , minimum is 2 when m=2, minimum is 0 when m=0

7. `R / S`

• max : m

Reason : when n=0

• min: 0

Reason : Consider that relational division is similar to integer division. `3 / 7` gives 0 in integer division for example. Try to convert this into relational division

8. `R CROSS PRODUCT S`

• max & min : m*n

Reason : combining each row in R with each row in S.

9. `R RIGHT OUTER JOIN S`

• max : m*n

Reason : if all rows in left table matches with all rows in right table

• min: n (including every tuple from the right table)

Reason : if no tuple matches between the two table, but still we have to include all the tuples from the right table.

The minimum is 1 when n=1 , minimum is 2 when n=2, minimum is 0 when n=0

10. `R FULL OUTER JOIN S`

• max : m*n

Reason : if all rows in left table matches with all rows in right table

• Case 1→ min: m+n

Reason : if no tuple matches between the two table, but still we have to include all the tuples from the left & right table.

• Case 2 → min: max(m,n)

Reason : when every tuple in one of the table matches with tuples in other table.

elaborate explanation for min: max(m,n) for Full Outer Join:

Consider relation R with 4 tuples and S with 8 tuples.

So, min of outer join would be if there's no match. i.e m+n = 4+8 = 12 tuples.

but this is not the case to get absolute minimum.

To get min. in full outer join:

Consider, 4 out of 4 tuples in R matches with S's tuples (4 out 8 is same as R)

this time, resultant relation would have: 4(matched) + 4(unmatched) tuple = 8 tuples. (which is less than 12)