# SPARQL2 Flink: Evaluation of SPARQL Queries on Apache Flink
## 3 Mapping SPARQL Queries to an Apache Flink Program
### Correspondence between SPARQL Algebra Operators and Apache Flink Transformations
More precisely, we have that:  
* If \(P\) is a triple pattern, then records of dataset \(\mathcal{D}\) are filtered (by means of function f1) to obtain only the records that are compatible with respect to the variables and values in \([s,p,o]\). Then, the filtered records are mapped (by means function f2) to obtain solution mappings that relate each variable to each possible value. * If \(P\) is a join (left join) (it uses the SPARQL operators AND (OPT)), then a _match_ (_outermatch_) transformation is performed between the recursive evaluation of subgraphs \(P_{1}\) and \(P_{2}\) with respect to a set \(K\) conformed by the variables in \(P_{1}\) and \(P_{2}\). * If \(P\) is a union graph pattern, then there is a union transformation between the recursive evaluation of subgraphs \(P_{1}\) and \(P_{2}\). * Finally, if \(P\) is a filter graph pattern, then a \(filter\) transformation is performed over the recursive evaluation of subgraph \(P^{\prime}\) where the user function \(f\) is built according to the structure of the filter expression \(R\). Additionally to the graph pattern evaluation, we present an encoding of the evaluation of SELECT and DISTINCT SELECT queries as well as the ORDER-BY and LIMIT modifiers. The selection encoding is defined as follows:  
**Definition 17** (**Selection PACT Encoding**). : _Let \(\mathcal{D}\) be an RDF dataset, \(P\) be a graph pattern, \(K\) be a finite set of variables, and \(Q=\langle P,K\rangle\) be a selection query over \(\mathcal{D}\), the PACT Encoding of the evaluation of \(Q\) over \(\mathcal{D}\) is defined as follows:_  
\[||Q||^{\mathcal{D}}=\;project(||P||^{\mathcal{D}},K)\]  
Correspondingly, the selection query is encoded as a project transformation over the evaluation of the graph pattern \(P\) associated with the query with respect to a set of keys \(K\) conformed by the variables in the SELECT part of the query. We make a subtle variation in defining the distinct selection as follows:  
**Definition 18** (**Distinct Selection PACT Encoding**). : _Let \(\mathcal{D}\) be an RDF dataset, \(P\) be a graph pattern, \(K\) be a finite set of variables, and \(Q^{*}=\langle P,K\rangle\) be a distinct selection query over \(\mathcal{D}\), the PACT Encoding of the evaluation of \(Q^{*}\) over \(\mathcal{D}\) is defined as follows:_  
\[||Q^{*}||^{\mathcal{D}}=reduce(project(||P||^{\mathcal{D}},\;K),\;\texttt{f}, \;K)\]  
_where function f is defined as follows:_  
\[f(r_{1},r_{2})=\,r_{1}\cup r_{2}\]0  
The definition of the distinct selection PACT encoding is similar to the general selection query encoding. The main difference corresponds to a reduction step (_reduce_ transformation) in which, the duplicate records, i.e., records with the same value in the keys of set \(K\) (the distinct keys) are reduced to only one occurrence by means of the function f that takes as a parameter a set of records for which the value in the keys in \(K\) is the same and returns the first of them (actually, it could return any of them). The encoding of the evaluation of a order-by query is defined as follows:  
**Definition 19** (Order By PACT Encoding). : _Let \(\mathcal{D}\) be an RDF dataset, \(P\) be a graph pattern, \(k\) be a variable, and \(Q^{*}=\langle P,k,flag\rangle\) be an order by query over \(\mathcal{D}\), the PACT Encoding of the evaluation of \(Q^{*}\) over \(\mathcal{D}\) is defined as follows:_  
\[f(r_{1},r_{2})=\,r_{1}\cup r_{2}\]1  
_where function order is defined as follows:_  
\[f(r_{1},r_{2})=\,r_{1}\cup r_{2}\]2  
_where \(M=\{t_{1},\ldots,t_{n}\}\) and \(M^{\prime}=\{t^{\prime}_{1},\ldots,t^{\prime}_{n}\}\) is a permutation of \(M\) such that \(t^{\prime}_{i}[k]\leq t^{\prime}_{i+1}[k]\) if \(flag=\mathtt{ASC}\) or \(t^{\prime}_{i}[k]\geq t^{\prime}_{i+1}[k]\) if \(flag=\mathtt{DESC}\), for each \(i\in\{1,\ldots,n-1\}\)._  
Thereby, the graph pattern associated with the query is first evaluated according to the encoding of its precise semantics. Then, the resulting solution mapping is ordered by means of a function order.