Can someone explain me how the cartesian product works in relational algebra

jonathan picture jonathan · Oct 10, 2011 · Viewed 14.4k times · Source

here it says

Selection and cross product

Cross product is the costliest operator to evaluate. If the input relations have N and M rows, the result will contain NM rows. Therefore it is very important to do our best to decrease the size of both operands before applying the cross product operator.

suppose that we have 2 relations

first relation is called Student and has 3 attributes, thus

    student
  |a |b   |c |
  ------------
  |__|___|___|
  |__|___|___|
  |__|___|___|

second relation is university and again with 3 attributes

   university
  |e |f   |g |
  ------------
  |__|___|___|
  |__|___|___|
  |__|___|___|

we have 3 rows for each relation, so after applying the cross product operation we will get a relation which has 3*3 = 9 rows

now, I don't understand, why 9 and not 3?

won't the final relation be

 final relation
 |a |b   |c |d |e   |f |g |
 --------------------------
 |__|___|___|__|____|__|__|
 |__|___|___|__|____|__|__|
 |__|___|___|__|____|__|__|

doesn't this have 3 rows again?

Thanks

Answer

Erwin Smout picture Erwin Smout · Oct 11, 2011

If the rows in Student are row1, row2 and row3, and the rows in University are row4, row5 and row6, then the cartesian product will contain

row1row4, row1row5, row1row6, row2row4, row2row5, row2row6, row3row4, row3row5, row3row6

Each possible combination of rows. That's how it is defined. Nothing more to it.

Except for your remark "Therefore it is very important to do our best to decrease the size of both operands before applying the cross product operator.". It is important to realise that there do exist optimizers which are able to "rewrite" certain algebra operations. It is certainly not the case that the onus is always on the query writer to determine the "most appropriate way of combining restrictions with other operations". In fact, "moving restrictions to the inside as far as possible" is one of the things industrial optimizers are actually very good at.