Relational Algebra: Showing equality using aggregate operator

405 Views Asked by At

The schemas are given here for relations $R$ and $S$:

$$R(A,B)$$ $$S(C,D,E)$$

One can see that the following equality is true:

$$\gamma_{B,sum(E)}(R\Join_{A=C}S) = \gamma_{B,sum(E)}(R\Join_{A=C} ({\gamma_{C,sum(E)}}S))$$

After changing the aggregate operator sum(..) for count(..), is the following true?:

$$\gamma_{B,count(E)}(R\Join_{A=C}S) = \gamma_{B,count(E)}(R\Join_{A=C} ({\gamma_{C,count(E)}}S))$$

I do not believe the second equality to be true. Does this mean that we can repeat aggregate operators sometimes, but not always?

1

There are 1 best solutions below

0
On BEST ANSWER

I assume that count($E$) counts the number of values and not the number of distinct values. We denote with $F'$ the set of distinct values in $F$.

In the left side of the equation, first you make a join of $R$ and $S$ on $A=C$. So, the join will have tuples of the form $(a,b,d,e)$, where $(a,b)\in R$ and $(a,d,e)\in S$ and $a\in C$. Then, you group all tuples in this relation with respect to $B$. So, a group of tuples will be $\{(a_i,b,d_i,e_i): i\in I_b\subseteq\mathbb{N}\}$. For each $b\in B'$ you'll have such a group and you count how many tuples each group has. In other words, for each $b\in B'$, you count $| I_b |$ and the final relation has tuples of the form $(a,b,d,| I_b |)$, where $b\in B'$, $a\in C'$ and $d\in D$.

On the right hand side of the equation, fist move is to group tuples in $S$ with respect to $C$. So, you can express $S$ as a union of its groups with respect to $C$. $$S=\displaystyle\bigcup_{c\in C'}\{(c,d_i,e_i): i\in I_c\subseteq\mathbb{N}\}$$

Then, for each group you count its cardinality $|I_c |$. Now, $\gamma_{C,count(E)}S$ is a new relation with tuples of the form $(c,d,| I_c |)$, where $c\in C'$ and $d\in D$. You make a join of $\gamma_{C,count(E)}S$ and $R$ on $A=C$. Then, the join will have tuples of the form $(a,b,d,| I_c |)$, where $b\in B$, $d\in D$ and $a\in C'$. Then, you group this relation with respect to $B$ and for each $b\in B'$ you count the members of its group. The result will be a relation with tuples of the form $(a,b,d,| I_b|)$, where $a\in C'$, $b\in B'$ and $d\in D$.

As you can see, the resulting relations that you get from each side of the equation are equal.