3

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

0

2 Answers 2

4

Yes, your answers are mostly right, except a few mistakes:

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.

0
1

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)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.