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 se$ .
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 $p r =$ null)
  1. $S_{A} := S_{A} \cup (t_{r} [A], i_{A})$ .
  2. $t_{r} := t_{r}^{''}$
  3. $i_{A} := 0$

2ndSem

Explorer

15.22

Graph View