15.22

Suppose you have to compute \(_A\gamma_{sum(C)}(r)\) as well as \(_{A,B}\gamma_{sum(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:

  1. \(pr :=\) address of first tuple of \(r\)
  2. Let \(S_A\) be an empty set. At the end of this algorithm it will contain the result of \(_A\gamma_{sum(C)}(r)\).
  3. Let \(S_{AB}\) be an empty set. At the end of this algorithm it will contain the result of \(_{A,B}\gamma_{sum(C)}(r)\).
  4. \(t_r :=\) tuple to which \(pr\) points
  5. \(i_A := 0\).
  6. while (\(pr \neq\) null)
    1. \(t_r' :=\) tuple to which \(pr\) points
    2. \(i_{AB} := t_r'[C]\).
    3. Set \(pr\) to point to the next tuple of \(r\).
    4. \(done := false\).
    5. while (not \(done\) and \(pr \neq\) null)
      1. $t_r’’ := $ tuple to which \(pr\) points.
      2. If (\(t_r''[{A, B}] = t_r'[{A, B}]\) )
        1. \(i_{AB} := i_{AB} + t_r''[C]\)
        2. Set \(pr\) to point to the next tuple of \(r\).
      3. Else
        1. \(done := true\)
    6. \(S_{AB} := S_{AB} \cup (t_r'[A], t_r'[B], i_{AB})\)
    7. \(i_A := i_A + i_{AB}\)
    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\)