# SPARQL2 Flink: Evaluation of SPARQL Queries on Apache Flink
## 3 Mapping SPARQL Queries to an Apache Flink Program
### Formalization of Apache Flink Transformations
: _Let \(\mathcal{T}^{\prime}\subseteq\mathcal{T}\) be a dataset and given a function \(f\) ranging over \(\mathcal{T}^{\prime}\) to boolean values, i.e., \(f:\mathcal{T}^{\prime}\rightarrow\{\mathsf{true},\mathsf{false}\}\), we define a filter transformation as follows:_  
\[filter(\mathcal{T}^{\prime},f)=\{r\mid f(r)=\mathsf{true}\}\]  
The filter transformation evaluates predicate \(f\) with every record of a dataset \(\mathcal{T}^{\prime}\) and it selects only those records with which \(f\) returns true. **Definition 11** (**Project Transformation**). : _Let \(\mathcal{T}^{\prime}\subseteq\mathcal{T}\) be a dataset and given a set of keys \(K=\{k^{\prime}_{1},\ldots,k^{\prime}_{m}\}\), we define a project transformation as follows:_  
\[project(\mathcal{T}^{\prime},K)=\{r^{\prime}\mid\exists_{r\in\mathcal{T}^{ \prime}}.\,r^{\prime}=r(K)\}\]  
While filter transformation allows selecting some specific records according to some criteria, which are expressed in the semantics of a function \(f\), the project transformation enables us to obtain some specific fields from the records of a dataset \(\mathcal{T}^{\prime}\). For this purpose, we apply a record projection operation--to each record in \(\mathcal{T}^{\prime}\) with respect to a set of keys \(K\). It is worth highlighting that the result of a project transformation is a multi-set due to several records having the same values in the keys of set \(K\). Previous PACT transformations take as a parameter a dataset \(\mathcal{T}^{\prime}\) and produce as a result a new dataset according to specific semantics. Nevertheless, a lot of data sources are available, and it is necessary to process and combine multiple datasets eventually. In consequence, some PACT transformations are taking two or more datasets as parameters [14]. Following, we present a formal interpretation of the essential multi-datasets transformations, including matching, grouping, and union. **Definition 12** (**Match Transformation**). : _Let \(\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\mathcal{T}\) be datasets, given a function \(f\) ranging over \(\mathcal{T}_{1}\) and \(\mathcal{T}_{2}\), i.e., \(f:\mathcal{T}_{1}\times\mathcal{T}_{2}\rightarrow\mathcal{T}\) and given sets of keys \(K_{1}\) and \(K_{2}\), we define a match transformation as follows:_  
\[match(\mathcal{T}_{1},\mathcal{T}_{2},f,K_{1},K_{2})=\{r\mid\exists_{r_{1} \in\mathcal{T}_{1},\,r_{2}\in\mathcal{T}_{2}}.\,f(r_{1},r_{2})=r\wedge r_{1}[K _{1}]\equiv r_{2}[K_{2}]\}\]  
Thus, match transformation takes each pair of records \((r_{1},r_{2})\) built from datasets \(\mathcal{T}_{1}\) and \(\mathcal{T}_{2}\), and applies user function \(f\) with those pairs for which the values in \(r_{1}\) with respect to keys in \(K_{1}\) coincide with the values in \(r_{2}\) with respect to keys in \(K_{2}\). For this purpose, it checks this correspondence through a record value projection. Intuitively, the match transformation enables us to group and process pairs of records related to some specific criterion. In some cases, it is necessary to match and process a record in a dataset even if a corresponding record does not exist in the other dataset. The outer match transformation extends the match transformation to enable such a matching. Outer match transformation is defined as follows:  
**Definition 13** (**Outer Match Transformation**). : _Let \(\mathcal{T}_{1},\mathcal{T}_{2}\subseteq\mathcal{T}\) be datasets, given a function \(f\) ranging over \(\mathcal{T}_{1}\) and \(\mathcal{T}_{2}\), i.e., \(f:\mathcal{T}_{1}\times\mathcal{T}_{2}\rightarrow\mathcal{T}\) and given sets of keys \(K_{1}\) and \(K_{2}\), we define a outer match transformation as follows:_  
\[ \begin{split} outerMatch(\mathcal{T}_{1},\mathcal{T}_{2},f,K_{1},K_{2})&=\\ match(\mathcal{T}_{1},\mathcal{T}_{2},f,K_{1},K_{2})& \ \cup\{r\ |\ \exists_{r_{1}\in\mathcal{T}_{1}}\cdot\
eg(\exists_{r_{2}\in\mathcal{T}_{2}}.\ r_{1}[K_{1}]\equiv r_{2}[K_{2}])\ \wedge f(r_{1},[\ ])=r\}\end{split}