'Maximum number that can be returned by 2 Natural Joins

Given relations A(a,b,c), B(e,f), C(d,g,h), where A has 800 tuples, B 200 and c 500. In worst case gives the expression A * B * C ( with * natural join) :

a) 800 tuples

b) 200 tuples

c) 500 tuples

d) 800*200*500 tuples

e) 800+200+500 tuples

f) Nothing from the above.

My guess was 800+200+500 since there isnt any common attribute ? And what if there was a common attribute ?

sqldatabasecomputer-sciencerelational-algebra


Solution 1:[1]

A natural join on tables that have no rows in common is in fact a cross join as you so rightly suppose. You'll get A * B * C = 800 * 200 * 500 = 80,000,000 rows.

Once the tables have columns in common a filter takes place. Depending on whether there are matches and how many, you get anything from 0 to 80,000,000 rows. Examples:

  • If all tables have one column in common and its value is the same in every row in every table, you end up with all combinations again.
  • If all tables have one column in common and its value is 'A' in all rows in table A, 'B' in all rows in table 'B' and 'C' in all rows in table C, you end up with no matches, i.e. zero rows.

After all, this all is dull theory, because nobody in their right mind would ever use a natural join :-)

Solution 2:[2]

I think that you mean cross join rather than natural join, since you stated that the three tables have no column in common.

In that case, you would get a cartesian product of the three tables, that is all possible combinations of rows from the tables: this gives you 800 * 200 * 500 rows in the resultset.

On the other hand, if there are 1-1 relationships across the tables (that is, 0 or 1 row in each table can be found in the other tables), and you are combining the tables with inner joins, then then you would get a subset of rows that do exist in the three tables: that's at most 200 rows (and possibly 0 rows, if no tuple can be matched across the three tables). This is not, however, what your question seems to refer to.

If you are dealing with other types of relations (one-to-many, many-to-many, ...), then there is no generic answer. It does depend on the relationships and data.

Solution 3:[3]

Relation A contain 800 different tuple, relation B contain 200 different tuple, relation C contain 500 different tuple. In natural join it'll return the records where the 200 different values of B matches with the values of A and C so, max no of tuples will be 200

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 GMB
Solution 3 Harsh Soni

Related Questions