# Query Rewriting for Incremental Continuous Query Evaluation in HIFUN
## 4 Methods  
### Incremental Computation in HIFUN  
In this section, we show how we can use HIFUN language to incrementally evaluate continuous queries. An important common feature of real-life applications is that the input data continuously grow and old data remain intact. As such, for the rest of this paper we assume that the dataset being processed can only increase in size between \(t\) and \(t^{\prime}\). In such a scenario, the idea of incrementally evaluating a continuous query is to use the results of an already performed computation on the old data, and evaluate the query only on the data appended between \(t\) and \(t^{\prime}\); eventually new and previous results should be merged. As we saw earlier, in an HIFUN query \(Q=(g,m,op)\), the domain of the definition of an answer coincides with the range of the grouping function. Consider, for instance, the query \(Q=(b,q,sum)\) of our running example, asking for the totals by branch. The domain of the answer is the set of all branches and this set is also the range of \(b\). We call this set the key of the query. Now, in a continuous query, the key might change over time. Indeed, in the case of totals by branch, new branches might start operation between \(t\) and \(t^{\prime}\), whereas branches operating at time \(t\) might cease to operate between \(t\) and \(t^{\prime}\). Figure 3 illustrates our incremental approach for continuous queries--the same query asked two times. We perceive the problem of incremental evaluation as follows: let \(ans\) be the answer of continuous query \(Q\) at time \(t\), on dataset \(D\); let \(ans^{\prime}\) be the answer of \(Q\) at time \(t^{\prime}\) on dataset \(D^{\prime}\), where \(D^{\prime}=D+\Delta D\); and let \(incr\) be the answer of \(Q\) at time \(t^{\prime}\) on dataset \(\Delta D\). Moreover, let \(K\) be the key of \(Q\) at time \(t\) and let \(k^{\prime}\) be the key of \(Q\) at time \(t^{\prime}\). Our algorithm for computing \(ans^{\prime}\) supports both distributive and non-distributive operations. Without loss of generality, we present in the sequel four cases of distributive operations and a non-distributive one:  
* **op= sum:**\(ans^{\prime}(i)=ans(i)+incr(i)\) if i is in \(K\cap K^{\prime}\); \(ans(i)\) if i is in \(K\setminus K^{\prime}\); \(incr(i)\) if i is in \(K^{\prime}\setminus K\);
* **op= min:**\(ans^{\prime}(i)=min(ans(i),incr(i))\) if i is in \(K\cap K^{\prime}\); \(ans(i)\) if i is in \(K\setminus K^{\prime}\); \(incr(i)\) if i is in \(K^{\prime}\setminus K\);
* **op= max:**\(ans^{\prime}(i)=max(ans(i),incr(i))\) if i is in \(K\cap K^{\prime}\); \(ans(i)\) if i is in \(K\setminus K^{\prime}\); \(incr(i)\) if i is in \(K^{\prime}\setminus K\);
* **op= count:**\(ans^{\prime}(i)=ans(i)+incr(i)\) if i is in \(K\cap K^{\prime}\); \(ans(i)\) if i is in \(K\setminus K^{\prime}\); \(incr(i)\) if i is in \(K^{\prime}\setminus K\);  
The non-distributive aggregate operation of the average can be computed by applying a combination of distributive aggregate operations. More specifically, the answer \(ans^{\prime}\) of query \(Q\) at time \(t^{\prime}\) is computed as follows:  
* **op= avg:*
* \(ans^{\prime}(i)=ans(i)\) if i is in \(K\setminus K^{\prime}\);
* \(ans^{\prime}(i)=incr(i)\) if i is in \(K^{\prime}\setminus K\);
* \(ans^{\prime}(i)=\frac{ans_{op=sum(i)+incr_{op=sum(i)}}}{ans_{op=count(i)+incr_{op= sum(i)}}}\) if i is in \(K\cap K^{\prime}\);
Distributive aggregate operations are those whose computation can be distributed and be recombined using the distributed aggregates. All operations \(min\), \(max\), \(sum\) and \(count\) are distributive. This means that if the data are distributed into \(n\) sets, and we apply the aforementioned distributive operation to each one of them (resulting in \(n\) aggregate values), the total aggregate operation can be computed for all data by applying the aggregate operation for each subset and then combining the results. For example: \(sum(1,2,3,4,5)=sum(sum(1,2),sum(3,4,5))\).