Let $M$ and $N$ be relations.
I want to calculate the lower and upper bound of $M\Join N$ and $M\ltimes N$.
$$$$
I have done the following :
- As for $M\Join N$ :
If $M$ and $N$ contain have common columns and same rows at these columns, then the natural join consider these rows and take all combinations, right?
Is this like cartesian product?
- As for $M\ltimes N$ :
The result contains the tuples of $M$ that have at least a common column with $N$, right?
If all tuples of $M$ have common columns with $N$ then the upper bound is $m$.
If no tuple of $M$ has common columns with $N$ then the lower bound is $0$.
Is that correct?
For the natural join you are right. The upper bound is $|M| \times |N|$ (in case all the tuples join), and the lower bound is $0$ (in case no tuple join).
For the left join you have to take into account that a left join returns the natural join between M and N, together all those tuples from M that do not join any tuple from N.
Hence, the upper bound is $max(|M|, |M| \times |N|)$ (it will be $|M|$, for instance, if no tuple from M joins N), and the lower bound is $|M|$ (in case no tuple from M joins N).