15.22

Suppose you have to compute $_{A} γ_{s u m (C)} (r)$ as well as $_{A, B} γ_{s u m (C)} (r)$ . Describe how to compute these together using a single sorting of $r$ .

First we sort relation $r$ on $(A, B)$ . That is if two tuples $t_{1}, t_{2} \in r$ have different $A$ values, then we use their values for attribute $A$ to sort them. If they have the same $A$ value, we use their values for attribute $B$ to sort them.

Then we perform the following:

$p r :=$ address of first tuple of $r$
Let $S_{A}$ be an empty set. At the end of this algorithm it will contain the result of $_{A} γ_{s u m (C)} (r)$ .
Let $S_{A B}$ be an empty set. At the end of this algorithm it will contain the result of $_{A, B} γ_{s u m (C)} (r)$ .
$t_{r} :=$ tuple to which $p r$ points
$i_{A} := 0$ .
while ( $p r \neq$ null)
1. $t_{r}^{'} :=$ tuple to which $p r$ points
2. $i_{A B} := t_{r}^{'} [C]$ .
3. Set $p r$ to point to the next tuple of $r$ .
4. $d o n e := f a l s e$ .
5. while (not $d o n e$ and $p r \neq$ null)
  1. $t_r’’ := $ tuple to which $p r$ points.
  2. If ( $t_{r}^{″} [A, B] = t_{r}^{'} [A, B]$ )
    1. $i_{A B} := i_{A B} + t_{r}^{″} [C]$
    2. Set $p r$ to point to the next tuple of $r$ .
  3. Else
    1. $d o n e := t r u e$
6. $S_{A B} := S_{A B} \cup (t_{r}^{'} [A], t_{r}^{'} [B], i_{A B})$
7. $i_{A} := i_{A} + i_{A B}$
8. If ( $t_{r}^{″} [A] \neq t_{r} [A]$ OR $pr = $ null)
  1. $S_{A} := S_{A} \cup (t_{r} [A], i_{A})$ .
  2. $t_{r} := t_{r}^{″}$
  3. $i_{A} := 0$