# Query Rewriting for Incremental Continuous Query Evaluation in HIFUN
## 4 Methods
### System Implementation
#### 4.2.2 Continuous HIFUN Queries Using MapReduce  
The abstract definition of a query evaluation is implemented on the physical level using the MapReduce programming model exploiting Spark Streaming. Spark Streaming is a stream processing framework based on the concept of discretized streams and provides the DStream API, which accepts sequences of data which arrive over time. The API implements the micro-batch stream processing approach with periodic checking of internal state at each batch interval. Internally, each DStream is represented as a sequence of data structure called resilient distributed datasets (RDDs) which keeps the data in memory as they arrive in each batch interval. Generic Evaluation Schema to MapReduce. In this section, we elaborate on the generic query evaluation schema, described in Section 3, by presenting details of its implementation in the physical layer when Spark Streaming and the MapReduce programming model are sed:  
1. _Query Input Preparation_. A set of attributes which are included in grouping and measuring part of Q is used to extract the information from the initial unstructured dataset. A map function is used that applies the given attributes to each record of the initial DStream and returns a new DStream which contains the information useful for the next evaluation steps. 2. _Grouping Partition Construction_. In this step, a map function constructs the grouping partition as follows. The mapper receives the tuples created from the previous step and extracts the key-value pairs. The result is a new PairDStream in which the key K is the value of the grouping attribute of each data item or the value of the grouping attributes if the domain of \(ans_{Q}\) is the Cartesian product of two or more grouping attributes. The value V is the value of the measuring attribute of each data item. 3. _Grouping Partition Reduction_. In this step a reduce function is used to merge the values of each key using a query operation \(op\), and a new DStream is created as the query answer of the current micro-batch. Rewritings to MapReduce As already described, a set \(Q\) can be rewritten according to certain rewriting rules. In this subsection, we give a detailed description how the evaluation mechanism leverages these rules. Common Grouping and Measuring Rewriting RuleIn this case of rewriting, \(n\) different operations are applied to the common grouping and measuring attributes. In the _Query Input Preparation_ step the information is extracted from the initial unstructured dataset  
Figure 4: State maintenance. using the common grouping and measuring attributes, which appear in the query set \(Q\). A map function is used to apply the given common attributes to each record of the initial DStream and returns a new DStream containing the values of the common grouping and measuring attributes for each record. This is useful for the following evaluation steps. As a next evaluation step, a map function constructs the grouping partition as follows. The mapper receives the tuples created from the previous step and emits key-value pairs \(<K,V>\), where \(K\) is the value of the common grouping attribute for each tuple and value \(V\) is synthetic and carries a list of measuring attribute values. The measuring value of each tuple is used and repeated \(n\) times to create a list of \(n\) values assigned to the key \(K\). The length \(n\) of the list depends on the number of the operations which appear in the query set \(Q\). As a final evaluation step, the reduction of the grouping partition is needed. A reduce function merges the \(n\) values for each key, using the \(n\) operations included in the rewritten set, and produces the query answer in the form of key-value pairs \(<K_{q},V_{k}>\), where \(K_{q}\) is the key of the query, and \(V_{k}\) its synthetic value containing the reduced value for each operation applicable to the measuring attribute. The answer of the _Common Grouping and Measuring Rewriting Rule_ is completed when a set of \(<K_{q},V_{k}>\) is created.