# 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  
In this section, we propose a semantic correspondence between SPARQL algebra operators and the PACT transformations implemented in the Apache Flink DataSet API. We use the formalization of PACT transformations presented in the previous section to provide an intuitive and correct mapping of the semantics elements of SPARQL queries. It is important to remember that in this formalization a record is an unordered list of \(n\) key-value pairs. However, as described in Section 2.1, an RDF dataset is a set of triples which is composed of three elements \(<s,p,o>\). Hence, for this particular case, a record will be understood as an unordered list of three key-value pairs. Besides, we assume that each field of a record \(r\) can be accessed using indexes 0, 1, and 2. Likewise, we assume that RDF triple pattern are triples \([s,p,o]\) where \(s,p,o\) can be variables or values. Finally, the result of the application of each PACT transformation is intended to be a solution mapping, i.e., sets of key-value pairs with RDF variables as keys that will be represented as records with \(n\) key-value pairs. Following, we present the definition of our encoding of SPARQL queries as PACT transformations. First, we define the encoding of the graph pattern evaluation as follows:  
**Definition 16** (**Graph Pattern PACT Encoding**). : _Let \(P\) be a graph pattern and \(\mathcal{D}\) be an RDF dataset, the PACT encoding of the evaluation of \(P\) over \(\mathcal{D}\), denoted by \(||P||^{\mathcal{D}}\), is defined recursively as follows:_  
1. _If_ \(P\) _is a triple pattern_ \([s,p,o]\) _then:_ \[||P||^{\mathcal{D}}=\text{ map}(filter(\mathcal{D},\,\mathsf{f_{1}}),\,\mathsf{f_{2}})\] _where function_ \(\mathsf{f_{1}}\) _is defined as follows:_ \[\mathsf{f_{1}}(r)=\mathsf{eval}(s,r[0])\,\wedge\,\mathsf{eval}(p,r[ 1])\wedge\,\mathsf{eval}(o,r[2])\] \[\mathsf{eval}(a,b)=\left\{ \begin{array}{ll}\mathsf{true}&\quad \quad\mathsf{if}\,\,\,a\in Var\\ a=b&\quad\quad\mathsf{otherwise}\end{array} \right.\] _and function_ \(\mathsf{f_{2}}\) _is defined as follows:_ \[\mathsf{f_{2}}(r)=\left\{ \begin{array}{ll}[s:r[0],\,\,p:r[1],\,o:r[2]\,\,]& \quad\mathsf{if}\,\,\,s,p,o\,\in\,Var\\ [s:r[0],\,\,p:r[1]\,\,]&\quad\mathsf{if}\,\,\,s,p\in Var\,\wedge\,o\
ot\in\, Var\\ [s:r[0],\,\,o:r[2]\,\,]&\quad\mathsf{if}\,\,\,s,\in Var\,\wedge\,p\
ot\in\, Var\\ [p:r[1],\,\,o:r[2]\,\,]&\quad\mathsf{if}\,\,\,p,o\in Var\,\wedge\,s\
ot\in\, Var\\ [s:r[0]]&\quad\mathsf{if}\,\,\,s\in Var\,\wedge\,p,o\
ot\in\,Var\\ [p:r[1]\,\,]&\quad\mathsf{if}\,\,\,p\in Var\,\wedge\,s,o\
ot\in\,Var\\ [0:r[2]\,\,]&\quad\mathsf{if}\,\,\,o\in Var\,\wedge\,s,p\
ot\in\,Var\\ [\,]&\quad\mathsf{otherwise}\end{array} \right.\] _2. If_ \(P\) _is_ \((P_{1}\,\,\mathsf{AND}\,\,P_{2})\) _then:_ \[||P||^{\mathcal{D}}=\text{ match}(||P_{1}||^{\mathcal{D}},\,\,||P_{2}||^{ \mathcal{D}},\,\mathsf{f},\,K,\,K)\] _where_ \(K=vars(P_{1})\capvars(P_{2})\) _and function_ \(\mathsf{f}\) _is defined as follows:_ \[f(r_{1},r_{2})=\,r_{1}\cup r_{2}\] _3. If_ \(P\) _is_ \((P_{1}\,\,\mathsf{OPT}\,\,P_{2})\) _then:_ \[||P||^{\mathcal{D}}=\text{ untor}(||P_{1}||^{\mathcal{D}},\,||P_{2}||^{ \mathcal{D}})\] _5. If_ \(P\) _is_ \((P^{\prime}\,\,\mathsf{FILTER}\,\,R)\) _then:_ \[||P||^{\mathcal{D}}=\text{ filter}(||P^{\prime}||^{\mathcal{D}},\,\mathsf{f})\] _where function_ \(\mathsf{f}\) _is defined as follows:_ \[\mathsf{f}(t)=\text{ exp}(R,t)\] \[\mathsf{exp}(R,t)=\left\{\begin{array}{ll}t[x]\,\,\mathsf{op}\,\,c& \quad\mathsf{if}\,\,\,c1\\ t[x]\,\,\mathsf{op}\,\,t[y]&\quad\mathsf{if}\  
_where \(R\) is a boolean expression and_  
\[c1=R\;\texttt{is}\;(x\;\texttt{op}\;c)\;for\;x\in Var,\;\texttt{op} \in\{=,\
eq,<,\leq,>,\geq\}\] \[c2=R\;\texttt{is}\;(x\;\texttt{op}\;y)\;for\;x,y\in Var,\; \texttt{op}\in\{=,\
eq,<,\leq,>,\geq\}\] \[c3=R\;\texttt{is}\;(R_{1}\;\texttt{op}\;R_{2})\;for\;\texttt{op} \in\{\wedge,\vee\}\]  
In this way, the graph pattern PACT evaluation is encoded according to the recursive definition of a graph pattern \(P\).