# SPARQL2 Flink: Evaluation of SPARQL Queries on Apache Flink
## 3 Mapping SPARQL Queries to an Apache Flink Program
### Formalization of Apache Flink Transformations  
In this section, we propose a formal interpretation of the PACT transformations implemented in the Apache Flink DataSet API. That interpretation will be used to establish a correspondence with the SPARQL Algebra operators. This correspondence is necessary before establishing an encoding to translate SPARQL queries to Flink programs in order to exploit the capabilities of Apache Flink for RDF data processing. In order to define the PACT transformations, we need to define some auxiliary notions. First, we define the _record projection_, that builds a new record, which is made up of the key-value pairs associated with some specific keys. Second, we define the _record value projection_ that allows obtaining the values associated with some specific keys. Next, we define the _single dataset partition_ that creates groups of records where the values associated with some keys are the same. Finally, we define the _multiple dataset partition_ as a generalization of the single dataset partition. The _single dataset_ and the _multiple dataset_ partitions are crucial to establish the definition of the _reduce_ and the _cogroup_ transformations due to the fact that they apply some specific user functions over groups of records. Record projection is defined as follows:  
**Definition 4** (**Record Projection**): _Let \(r=[k_{1}:v_{1},\ldots,k_{n}:v_{n}]\in\mathcal{T}^{\prime}\) be a record and \(\{i_{1},\ldots,i_{m}\}\subseteq\mathit{keys}(r)\) be a set of keys, we define the projection of \(r\) over \(\{i_{1},\ldots,i_{m}\}\) (denoted as \(r(i_{1},\ldots,i_{m})\)) as follows:_  
\[r(i_{1},\ldots,i_{m})=\{(i^{\prime},v)\mid(i^{\prime},v)\in r\wedge i^{\prime} \in\{i_{1},\ldots,i_{m}\}\}\]  
In this way, by means of a record projection, a new record is obtained only with the key-value pairs associated to some key in the set \(I=\{i_{1},\ldots,i_{m}\}\). Record value projection is defined as follows:  
**Definition 5** (**Record Value Projection**): _Let \(r=[k_{1}:v_{1},\ldots,k_{n}:v_{n}]\in\mathcal{T}^{\prime}\) be a record and \([i_{1},\ldots,i_{m}]\) be a tuple of keys such that \(\{i_{1},\ldots,i_{m}\}\subseteq\mathit{keys}(r)\), we define the value projection of \(r\) over \([i_{1},\ldots,i_{m}]\) (denoted as \(r[i_{1},\ldots,i_{m}]\)) as follows:_  
\[r[i_{1},\ldots,i_{m}]=\ [v_{1},v_{2},\ldots,v_{m}]\]_where \(\forall_{j\in\{1,\dots,m\}}.\ (i_{j}:v_{j})\in r\)._  
It is worth specifying that the record value projection takes a record and produces a tuple of values. In this way, in this operation, the key order in the tuple \([i_{1},\dots,i_{m}]\) is considered for the result construction. Likewise, the result of the record value projection could contain repeated elements. Let \(r_{1}\) and \(r_{2}\) be tuples of values, we say that \(r_{1}\) and \(r_{2}\) are equivalent (\(r_{1}\equiv r_{2}\)) if both \(r_{1}\) and \(r_{2}\) contain exactly the same elements. The notion of single dataset partition as follows:  
Definition 6 (Single Dataset Partition): Let \(\mathcal{T}^{\prime}\subseteq\mathcal{T}\) be a dataset and given a non-emtpy set of keys \(K\), we define a _single dataset partition_ of \(\mathcal{T}\) over keys \(K\) as:  
\[partition(\mathcal{T}^{\prime},K)=\{\mathcal{T}_{1},\mathcal{T}_{2},\dots, \mathcal{T}_{m}\}\]  
where \(\{\mathcal{T}_{1},\mathcal{T}_{2},\dots,\mathcal{T}_{m}\}\) is a set partition of \(\mathcal{T}^{\prime}\) such that:  
\[\forall_{r^{\prime},r^{\prime\prime}\in\mathcal{T}^{\prime}}.\ r^{\prime}(K) \equiv r^{\prime\prime}(K)\leftrightarrow\exists_{i}.\ r^{\prime}\in \mathcal{T}_{i}\wedge r^{\prime\prime}\in\mathcal{T}_{i}\]  
Intuitively, the single dataset partition creates groups of records where the values associated to some keys (set \(K\)) are the same. Analogous to the single dataset partition, we define the multiple dataset partition below. It is possible to realize that the multiple dataset partition is a generalization of the single dataset partition.