# Partitioning Strategies for Parallel Computation of Flexible Skylines
## 3 Background  
We focus on numeric attributes in \(\mathbb{R}^{+}\) and generally refer to a schema \(S\) of attributes \(\{A_{1},\ldots,A_{d}\}\) over such a domain. We use the notion of tuple and relation over \(S\) in accordance with the standard relational model so that \(t[A_{i}]\) is the value of tuple \(t\) over attribute \(A_{i}\). The _skyline_[2] of a relation \(r\) is the set of non-dominated tuples in \(r\), where we say that \(t\)_dominates_\(s\), denoted \(t\prec s\), if, for every attribute \(A\in S\), \(t[A]\leq s[A]\) holds and there exists an attribute \(A^{\prime}\in S\) such that \(t[A^{\prime}]<s[A^{\prime}]\) holds, as follows:  
\[\texttt{Sky}(r)=\{t\in r\mid\
exists\in r.\ s\prec t\}. \tag{1}\]  
The score of \(t\) through _scoring function_\(f\) is the value \(f(t[A_{1}],\ldots,t[A_{d}])\in\mathbb{R}^{+}\), also indicated \(f(t)\). We conventionally assume, for both scores and attribute values, that smaller values are preferable. The skyline can be equivalently defined as the set of tuples that are top-\(1\) results for at least one monotone scoring function. \[\texttt{Sky}(r)=\{t\mid t\in r\wedge\exists f\in\texttt{MF}.\ \forall s\in r.\ s\
eq t\implies f(s)>f(t)\}, \tag{2}\]  
where MF indicates the set of all monotone functions. The notion of _flexible skyline_[3] generalizes Equations (1) and (2), as follows:  
**Definition 1**. : _For a set \(\mathcal{F}\) of monotone scoring functions, \(t\)\(\mathcal{F}\)-dominates \(s\), denoted \(t\prec_{\mathcal{F}}s\), iff \(\forall f\in\mathcal{F}.\ f(t)\leq f(s)\) and \(\exists f\in\mathcal{F}.\ f(t)<f(s)\). The non-dominated flexible skyline \(\operatorname{ND}(r;\mathcal{F})\) is the set \(\{t\in r\mid\
exists\in r.\ s\prec_{\mathcal{F}}t\}\). The potentially optimal flexible skyline \(\operatorname{PO}(r;\mathcal{F})\) is the set \(\{t\in r\mid\exists f\in\mathcal{F}.\ \forall s\in r.\ s\
eq t\implies f(s)>f(t)\}\)._We observe that ND generalizes skylines as in Equation (1) (with \(\prec_{\mathcal{F}}\) instead of \(\prec\)), while PO generalizes Equation (2) (with \(\mathcal{F}\) instead of \(\mathtt{MF}\)). The \(\mathcal{F}\)-_dominance region_\(\operatorname{DR}(t;\mathcal{F})\) is the set of all points \(\mathcal{F}\)-dominated by \(t\). As a general property, \(\operatorname{PO}(r;\mathcal{F})\subseteq\operatorname{ND}(r;\mathcal{F}) \subseteq\operatorname{Sky}(r)\). **Example 1**. : _Consider the dataset \(r\) in Figure 1a, showing locations with their distance from points of interest. The non-dominated options in \(r\) are \(\boldsymbol{a}\), \(\boldsymbol{b}\), \(\boldsymbol{h}\), \(\boldsymbol{e}\), and \(\boldsymbol{i}\): this is \(\operatorname{Sky}(r)\). Consider now the set \(\mathcal{F}\) to be the scoring functions of the form \(f(x,y)=w_{1}x+w_{2}y\), where \(w_{1}\geq w_{2}\), i.e., linearly combining distances, with more importance given to the train station (ts) than to the concert hall (ch). Under \(\mathcal{F}\), \(\boldsymbol{h}\) and \(\boldsymbol{i}\) are \(\mathcal{F}\)-dominated by \(\boldsymbol{a}\) and \(\boldsymbol{e}\), respectively, so only \(\boldsymbol{a}\), \(\boldsymbol{b}\), and \(\boldsymbol{e}\) are in \(\operatorname{ND}(r;\mathcal{F})\). The gray area in Figure 1b represents the union of \(\mathcal{F}\)-dominance regions \(\operatorname{DR}(\boldsymbol{a};\mathcal{F})\cup\operatorname{DR}(\boldsymbol {b};\mathcal{F})\cup\operatorname{DR}(\boldsymbol{e};\mathcal{F})\). The gray segment in Figure 1c represents the space of normalized weights \((w_{1},w_{2})\), i.e., in the \([0,1]\) interval and such that \(w_{1}+w_{2}=1\). The set of combinations for which \(w_{1}\geq w_{2}\) holds is in gray, while for those marked in orange \(w_{1}\geq w_{2}\) does not hold.