Upper and lower bounds for the cardinalities

[mathmari]

Hey! :giggle:

Let two relations $M$ and $N$ be given with the cardinalities $m$ and $n$ respectively. Determine and justify the upper and lower bounds for the cardinalities of the following relations:
- $M\cup N$ :
- $M\times N$ :
- $M\cap N$ :
- $M\setminus N$ :
- $M\Join N$ :
- $M\ltimes N$ : I have done the following : - $M\cup N$ :

If the two relations are compatible then the cardinality is equal to $m+n$,whixh is the upper bound, and if the two relations are not combatible then the union is the empty set and so the cardinality is $0$ which is the lower bound.

- $M\times N$ :

The result is a tuple with both elements so the is the cardinality $m\cdot n$?

- $M\cap N$ :

The intersection contains tuples which are both in $M$ and $N$.Therefore if there no tuple in both then the cardinality is $0$, which is the lower bound. the upper bound is the minimum of $m$ and $n$, or not?

- $M\setminus N$ :

If $M$ and $N$ are two union-compatible relations,then their difference is a relation which contains tuples which are in $M$ but not in $N$. So the cardinality is $0$ if $M=N$ and $m$ if $M\cap N=\emptyset$.

- $M\Join N$ :

It is like a concatenation from $M$ and $N$, so is the cardinality the $m+n$ ?

- $M\ltimes N$ :

This contains all tuples from $M$ but only the lines that are also in $N$. So the cardinality is $0$ as lower bound and $n$ as upper bound, or not?
Is my attempt correct? :unsure:

 

[I like Serena]

- $M\cup N$ :

If the two relations are compatible then the cardinality is equal to $m+n$,whixh is the upper bound, and if the two relations are not combatible then the union is the empty set and so the cardinality is $0$ which is the lower bound.

What if the two relations have a couple of tuples in common? Then the cardinality is not $m+n$ is it? (Worried)

Is the union an empty set if they are not compatible? Or is the union undefined? :unsure:

- $M\times N$ :

The result is a tuple with both elements so the is the cardinality $m\cdot n$?

Yep. (Nod)

- $M\cap N$ :

The intersection contains tuples which are both in $M$ and $N$.Therefore if there no tuple in both then the cardinality is $0$, which is the lower bound. the upper bound is the minimum of $m$ and $n$, or not?

Correct. (Nod)

- $M\setminus N$ :

If $M$ and $N$ are two union-compatible relations, then their difference is a relation which contains tuples which are in $M$ but not in $N$. So the cardinality is $0$ if $M=N$ and $m$ if $M\cap N=\emptyset$.

What if $M \subset N$? That does not seem to be covered.

And what if $M\cap N\ne\varnothing$?

- $M\Join N$ :

It is like a concatenation from $M$ and $N$, so is the cardinality the $m+n$ ?

Nope. (Shake)

The natural join ($\Join$) combines the tuples on their common attribute, or leaves them out if there is no match.
It implies that the cardinality cannot be $m+n$.

- $M\ltimes N$ :

This contains all tuples from $M$ but only the lines that are also in $N$. So the cardinality is $0$ as lower bound and $n$ as upper bound, or not?

Suppose $N$ contains only 1 tuple.
And suppose $M$ contains $m$ tuples that each match the tuple in $N$ on their common attribute.
Then we get more than $n=1$ tuples, don't we? (Wondering)

 

[mathmari]

What if the two relations have a couple of tuples in common? Then the cardinality is not $m+n$ is it? (Worried)

The union is only defined when all columns are the same? :unsure:

Is the union an empty set if they are not compatible? Or is the union undefined? :unsure:

So what can we say about the lower bound? :unsure:

What if $M \subset N$? That does not seem to be covered.

And what if $M\cap N\ne\varnothing$?

Ah is the set difference also defined when $M\subset N$? What would then be the result? Would it be the empty set? :unsure:

The natural join ($\Join$) combines the tuples on their common attribute, or leaves them out if there is no match.
It implies that the cardinality cannot be $n$.

So is the maximum cardinality equal to the minimum of m and n? :unsure:

Suppose $N$ contains only 1 tuple.
And suppose $M$ contains $m$ tuples that each match the tuple in $N$ on their common attribute.
Then we get more than $n=1$ tuples, don't we? (Wondering)

Ah do we get the number of elements as in $M$? :unsure:

 

[I like Serena]

The union is only defined when all columns are the same?

Yes. So suppose all columns are the same and suppose both M and N have the same tuple.

So what can we say about the lower bound?

If the union is not defined, then the lower bound is also undefined.

Ah is the set difference also defined when $M\subset N$? What would then be the result? Would it be the empty set?

Yep. (Nod)

So is the maximum cardinality equal to the minimum of m and n?

Yes. (Nod)

Ah do we get the number of elements as in $M$?

In this example we would yes.
And generally $m$ is an upper bound.

 

[mathmari]

Yes. So suppose all columns are the same and suppose both M and N have the same tuple.

So it must be $m=n$ and this is also the cardinality of the union, or not? :unsure:

If the union is not defined, then the lower bound is also undefined.

Ahh ok :unsure:

In this example we would yes.
And generally $m$ is an upper bound.

Ok! And what about the lower bound? Do we get the lower bound if no column of $M$ matches to $N$ ? :unsure:

 

[I like Serena]

So it must be $m=n$ and this is also the cardinality of the union, or not?

Erm... what was the question again? :unsure:

Ok! And what about the lower bound? Do we get the lower bound if no column of $M$ matches to $N$ ?

Erm... what was the question again? :unsure:

 

[mathmari]

When we say $M$ has cardinality $m$ we don't mean that $M$ is a relation of $m$-tuples, do we? :unsure:

 

[I like Serena]

When we say $M$ has cardinality $m$ we don't mean that $M$ is a relation of $m$-tuples, do we?

The cardinality of a set is the number of elements in the set.
If that number is infinite, some extra rules apply, but in our case I believe we are just talking about finite sets.
The cardinality of the relationship $M$ is the number of tuples in $M$, which is regardless of how many members are in any particular tuple.

So no, the cardinality of $M$ does not depend on the number of members in any particular tuple. (Shake)

 

[mathmari]

Do we have tosuppose that $M$ and $N$ are compatible?

- $M\cup N$ :
So that the union is defined we have to suppose that $m=n$, or not?
The union contains all tuples of $M$ and all tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m+n=2m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
That means a lower bound is $m$ and an upper bound is $2m$. Is that correct? :unsure: - $M\times N$ :
The cartesian product contains all possible combinations of the tuples of $M$ with the tuples of $N$.
So we get $m\cdot n$ elements, which is an uppoer bound.
Is that also the lower bound? :unsure: - $M\cap N$ :
So that the intersection is defined we have to suppose that $m=n$, or not?
The intersection contains all tuples of $M$ that are also tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $0$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
That means a lower bound is $0$ and an upper bound is $m$. Is that correct? :unsure: - $M\setminus N$ :
So that the difference is defined we have to suppose that $m=n$, or not?
The difference contains all tuples of $M$ that are not tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $0$ elements.
That means a lower bound is $0$ and an upper bound is $m$. Is that correct? :unsure: About $M\Join N$ and $M\ltimes N$ I don't have an idea yet... :unsure:

 

[I like Serena]

Do we have tosuppose that $M$ and $N$ are compatible?

- $M\cup N$ :
So that the union is defined we have to suppose that $m=n$, or not?

No. (Shake)
Instead we have to suppose that the $M$ and $N$ have the same columns.
Let's assume each of them has tuples with $k$ members.
Then that is independent of how many tuples each of them has, which is $m$ respectively $n$.

The union contains all tuples of $M$ and all tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m+n=2m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
That means a lower bound is $m$ and an upper bound is $2m$. Is that correct?

Why would we have $m+n=2m$ elements if all are different? Shouldn't it just be $m+n$? :unsure:

If all tuples in $M$ and $N$ are the same, we reach indeed a lower bound.
And if one of them has a couple more tuples, then the union will have a couple more tuples.

- $M\times N$ :
The cartesian product contains all possible combinations of the tuples of $M$ with the tuples of $N$.
So we get $m\cdot n$ elements, which is an uppoer bound.
Is that also the lower bound?

Yep. (Nod)

- $M\cap N$ :
So that the intersection is defined we have to suppose that $m=n$, or not?
The intersection contains all tuples of $M$ that are also tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $0$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
That means a lower bound is $0$ and an upper bound is $m$. Is that correct?

No. Instead we have to suppose that each of them has $k$-tuples with matching columns.

- $M\setminus N$ :
So that the difference is defined we have to suppose that $m=n$, or not?
The difference contains all tuples of $M$ that are not tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $0$ elements.
That means a lower bound is $0$ and an upper bound is $m$. Is that correct?

Again no. To be defined we merely need that both $M$ and $N$ have $k$-tuples with matching columns.

About $M\Join N$ and $M\ltimes N$ I don't have an idea yet...

Ok. Let's consider them when we have addressed the others then.

 

[mathmari]

Instead we have to suppose that the $M$ and $N$ have the same columns.
Let's assume each of them has tuples with $k$ members.
Then that is independent of how many tuples each of them has, which is $m$ respectively $n$.

Ah yes. I confused the number of elements with the number of columns.

Why would we have $m+n=2m$ elements if all are different? Shouldn't it just be $m+n$? :unsure:

If all tuples in $M$ and $N$ are the same, we reach indeed a lower bound.
And if one of them has a couple more tuples, then the union will have a couple more tuples.

The union contains all tuples of $M$ and all tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m+n$ elements, which is the upper bound.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements, which is the lower bound.
So let $C$ be the carcinality of the union, then we have that $\min \{m,n\}\leq C\leq m+n$, or how do we write the left side? Or cannot we not write that in that form? :unsure:

No. Instead we have to suppose that each of them has $k$-tuples with matching columns.

The intersection contains all tuples of $M$ that are also tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $0$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
So let $C$ be the carcinality of the intersection, then we have that $0\leq C\leq \min \{m,n\}$, or how do we write the right side? Or cannot we not write that in that form? :unsure:

Again no. To be defined we merely need that both $M$ and $N$ have $k$-tuples with matching columns.

The difference contains all tuples of $M$ that are not tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $0$ elements.
So let $C$ be the carcinality of the difference, then we have that $0\leq C\leq m$. Or cannot we not write that in that form? :unsure:

 

[I like Serena]

The union contains all tuples of $M$ and all tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m+n$ elements, which is the upper bound.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements, which is the lower bound.
So let $C$ be the carcinality of the union, then we have that $\min \{m,n\}\leq C\leq m+n$, or how do we write the left side? Or cannot we not write that in that form?

We can say that the lower bound is $\max \{m,n\}$ and that the upper bound is $m+n$.

The intersection contains all tuples of $M$ that are also tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $0$ elements.
If all tuples of $M$ are the same as in $N$ then we have $m=n$ elements.
So let $C$ be the carcinality of the intersection, then we have that $0\leq C\leq \min \{m,n\}$, or how do we write the right side? Or cannot we not write that in that form?

That is quite correct. (Nod)

The difference contains all tuples of $M$ that are not tuples of $N$.
If all tuples of $M$ are different from the tuples of $N$ then we have $m$ elements.
If all tuples of $M$ are the same as in $N$ then we have $0$ elements.
So let $C$ be the carcinality of the difference, then we have that $0\leq C\leq m$. Or cannot we not write that in that form?

That seems fine to me. It shows both the lower and upper bound as requested. (Nod)

 

[mathmari]

We can say that the lower bound is $\max \{m,n\}$ and that the upper bound is $m+n$.

We take the max because either all tuples are the same or the one has some more elements than the other one? :unsure:

 

[I like Serena]

We take the max because either all tuples are the same or the one has some more elements than the other one?

The union contains at least the $m$ tuples of $M$.
And it also contains at least the $n$ tuples of $N$.
That is $\max(m,n)$.
It happens if all tuples of the one are included in the other or vice versa, giving us a lower bound.

 

[mathmari]

The union contains at least the $m$ tuples of $M$.
And it also contains at least the $n$ tuples of $N$.
That is $\max(m,n)$.
It happens if all tuples of the one are included in the other or vice versa, giving us a lower bound.

Ahh ok! :geek:

 

[mathmari]

As for $M\Join N$ :
The natural union of $ M $ and $ N $ consists of all combinations of the tuples of the two relations, but only those tuples are listed which have the same values in each column of the two relations.
The Cartesian product is thus formed from which only those tuples are selected whose column values are the same for columns of the same name in the two relations. These columns with the same name are only included once in the result.

Upper bound: $ m \cdot n $ (if there is no connecting column, i.e. if we have a Cartesian product)
Lower bound: $ 0 $ (if there are connecting columns but they have no common values)

Let $ C $ be the cardinality of the natural join, then we have that $ 0 \leq C \leq m \cdot n $.

As for $M\ltimes N$ :
The result contains all tuples from $ M $ in unchanged form that have a link partner in $ N $.

Upper bound: $m$ (if all the tuples of $ M $ are the same as the tuples of $ N $)
Lower bound: $0$ (if there is no tuple in $ M $ that is also in $ N $)

Let $ C $ be the cardinality of the semi join, then we have that $0\leq K\leq m$.
Is everything correct? :unsure:

 

[I like Serena]

Is everything correct?

All correct. (Sun)

 

[mathmari]

All correct. (Sun)

Great! Thank you!