Traditionally, skyline and ranking queries have been treated separately as alternative ways of discovering interesting data in potentially large datasets. While ranking queries adopt a speci c scoring function to rank tuples, skyline queries return the set of non-dominated tuples and are independent of attribute scales and scoring functions. Ranking queries are thus less general, but cheaper to compute and widely used. In this paper, we integrate these two approaches under the unifying framework of restricted skylines by applying the notion of dominance to a set of scoring functions of interest.
When simultaneously optimizing di erent criteria (e.g., the di erent attributes
in a dataset), a problem known as multi-objective optimization, three approaches
are prevalent [4]: (
Restricted skyline (R-skyline) queries, introduced in [2], consider arbitrary families of scoring functions (induced, e.g., by constraints on the weights), thus allowing greater exibility than skylines and ranking queries. The linchpin of Rskylines is the novel concept of F -dominance: t F -dominates s when t is always better than or equal to s according to all the scoring functions in the family F (and strictly better for at least one scoring function in F ).
In this paper, we present a synthesis of the results in [2], where we introduced two R-skyline operators: nd, characterizing the set of non-F -dominated tuples; po, referring to the tuples that are potentially optimal, i.e., best according to some function in F . R-skylines capture in a single framework all the practically relevant approaches to multi-objective optimization, traditionally dealt with separately, and enable the study of other scenarios of practical interest. For example, decision makers may encounter objectives in which the model parameters are characterized by complex preferences, perhaps coming from preference elicitation from a crowd (see, e.g., [3] and references therein for strategies for collecting preferences between tuples). 2
We consider a relational schema R(A1; : : : ; Ad), with d 1, where, w.l.o.g., each attribute value ranges in [0; 1]; we refer to an instance r over R.
The skyline of r, denoted Sky(r), is equivalently de ned (i) as the set of all
non-dominated tuples (Eq. (
tg
Sky(r) = ft 2 r j 9f 2 M: 8s 2 r: s 6= t ! f (t) < f (s)g where s t means \s dominates t", and M is the set of monotone scoring functions. While the former view is typically adopted for skylines, the latter is commonly applied to \top-k" queries (here with k = 1), i.e., those queries whose goal is to return the k best tuples according to a given scoring function.
We now introduce R-skylines, whose behavior is similar to Sky, but applied to a limited set of monotone scoring functions F M. To this end, we say that t F -dominates s, s 6= t, denoted by t F s, i 8f 2 F : f (t) f (s). Example 1. Consider the tuples t = h0:5; 0:5i, s = h0; 1i, the monotone scoring functions f1(x; y) = x + y and f2(x; y) = x + 2y, and the set F = ff1; f2g. We have t F s, since f1(t) = f1(s) = 1 and f2(t) = 1:5 < f2(s) = 2. However, t 6 M s, since M includes f3(x; y) = 2x + y, for which f3(t) = 1:5 > f3(s) = 1.
The non-dominated restricted skyline of r wrt. F , denoted by nd(r; F ), is de ned as the set of non-F -dominated tuples:
F tg:
Here, as a convention, we consider lower values to be better than higher ones.
(
The potentially optimal restricted skyline of r wrt. F , denoted by po(r; F ), returns the tuples that are best (top 1) according to some scoring function in F .
po(r; F ) = ft 2 r j 9f 2 F : 8s 2 r: s 6= t ! f (t) < f (s)g:
The right-hand side of Eq. (
The following containment relationships between R-skylines and Sky hold: po(r; F ) nd(r; F )
Sky(r): po(r; M) = nd(r; M) = Sky(r): DR(t; F ) = fs 2 [0; 1]d j t
F sg:
The F -dominance region DR(t; F ) of a tuple t under F is the set of all points
in [0; 1]d that are F -dominated by t:
Such a region grows larger for smaller sets: DR(t; F1)
DR(t; F2), if F1
(
F2. ( )=(
) ( )=( ) (a) Tuples from Example 2 in [0; 1]d, d = 2. F-dominance regions in gray.
(b) Region of normalized weights such that w1 w2 (in gray).
Example 2. Let F be the set of linear scoring functions f (x; y) = w1x+w2y with w1 w2 and let r consist of t1 = h0:3; 0:6i, t2 = h0:4; 0:45i, t3 = h0:5; 0:2i, t4 = h0:6; 0:15i (Figure 1a). We have po(r; F ) = ft1; t3g nd(r; F ) = ft1; t2; t3g Sky(r) = r. Indeed, no tuple in r dominates any other tuple in r, and so Sky(r) = r. However, t3 F t4, since f (t3) f (t4) holds for any f 2 F , as w1(0:5 0:6) w2(0:15 0:2) always holds when w1 w2. Therefore t4 2= nd(r; F ). Figure 1a shows in gray the region of [0; 1]d whose points (including tuple t4) are F -dominated by some tuple in r, i.e., [t2rDR(t; F ); Figure 1b shows in gray the region of normalized weights such that w1 w2.
Finally, with linear scoring functions, as is well known [7], top-1 tuples can only lie in the boundary of the convex hull of the F -dominated region, thus t2 2= po(r; F ), since there is no function f 2 F for which both f (t2) < f (t1) and f (t2) < f (t3), as there are no w1; w2 such that w1(0:4 0:3) < w2(0:6 0:45), w1(0:4 0:5) < w2(0:2 0:45), and w1 w2 all hold. 3
A practically relevant case to consider is that of the weighted Lp norms, de ned as follows, where W = (w1; : : : ; wd) 2 W is a normalized weight vector, i.e., W [0; 1]d and, for each W = (w1; : : : ; wd) 2 W, we have Pid=1 wi = 1: LpW (t) =
d X wit[Ai]p i=1 !1=p ; p 2 N: We therefore turn our attention to the case in which the set of monotone scoring functions coincides with the family Lp of weighted Lp norms:
Lp = fLpW j W 2 Wg; p 2 N.
The behaviors of nd and po are very di erent under Lp.
Theorem 1. For every value of p and every r, nd(r; Lp) = Sky(r). Thus, any Lp family is \powerful enough" to reveal all skyline points with nd. However, this does not hold for po, as indicated in the following theorems. Theorem 2. Let p < p0, with p; p0 2 N. Then, for every r, po(r; Lp) po(r; Lp0 ).
Theorem 3. For each p 2 N, there exists r such that po(r; Lp) Sky(r).
The results of Theorems 1, 2 and 3 suggest that, by imposing some constraints on the weights, one can use any Lp family to smoothly move from the skyline (no constraints) to top-1 queries (a single weight vector satis es the constraints).
Checking F -dominance for Lp norms with linear constraints on the weights can be done in PTIME. Let LpC indicate the set Lp with linear constraints C = fC1; : : : ; Ccg on weights, where Cj = Pd i=1 ajiwi kj (for j 2 f1; : : : ; cg).
Theorem 4 (F -dominance test). t LpC s i the following linear programming problem in the unknowns W = (w1; : : : ; wd) has a non-negative solution: (8) (9) (10) minimize subject to
Pd i=1 wi(s[Ai]p
t[Ai]p) wi 2 [0; 1] Pd
i=1 wi = 1 Pd i=1 ajiwi kj
Computing nd(r; F ) using Theorem 4 is likely to be time-consuming, since a di erent linear programming (LP) problem needs to be solved for each F dominance test. An alternative approach is to explicitly compute the F -dominance regions of tuples, and then discard those tuples that belong to at least one of such regions. The advantage of this approach is that the computation of the F -dominance region of a tuple t can be performed just once, thus independently of how many F -dominance tests involve t.
In order to compute DR(t; LpC), we observe that the subset of W that satis es
C, denoted W(C), is a convex polytope contained in the unit (d 1)-simplex.
Theorem 5 (F -dominance region). Let W (
d
X wi(`)t[Ai]p;
i=1
` 2 f1; : : : ; qg:
Example 3. Let d = 2, p = 1, and consider tuples t1 = h0:3; 0:6i, t3 = h0:5; 0:2i,
t4 = h0:6; 0:15i from Example 2. For C = fw1 w2g and considering that
w1 + w2 = 1 and 0 w1; w2 1, the vertices of W(C) are W (
s[A1] + s[A2] 0:3; s[A1] + s[A2] 0:7g: 0:9g: (11) (12) (13) Tuple t4 satis es (12) and thus t3
L1C t4. For tuple t1, the system becomes: Here, t4 does not satisfy (13) and therefore t1 6 L1C t4.
As Example 3, Figure 1a and Inequalities (11) suggest, the \shape" of DR(t; LpC) (modulo cropping in the [0; 1]d hypercube) is independent of t, since the left-hand sides are the same and the right-hand sides are, for any given t, a constant. The only signi cant overhead introduced by this approach is the enumeration of the vertices of W(C). However, this has to be done just once for all tuples.
For any set F , po(r; F ) can be computed from nd(r; F ) by retaining only the tuples that are not F -dominated by any \virtual" tuple obtained by combining other tuples in nd(r; F ). When F = LpC, this is done by solving an LP problem. Theorem 6 (po test). Let nd(r; LpC) = ft1; t2; : : : ; t ; tg. Then, t 2 po(r; LpC) i there is no convex combination s of t1; : : : ; t such that s LpC t, i.e., i the following linear system in the unknowns = ( 1; : : : ; ) is unsatis able: Pid=1 wi(`)(Pj=1 j tj [Ai]p)
i=1 wi(`)t[Ai]p Pd ` 2 f1; : : : ; qg (14) Pj=1 j = 1: j 2 [0; 1] j 2 f1; : : : ; g
Input: relation r, constraints C, family F = LpC. Output: nd(r; F).
1. let ND := ;; let W (
Besides the LpC family, Theorems 4, 5, and 6 also hold for any set F whose functions are weighted sums of monotone functions of single attributes and monotonic transforms thereof. 4
We considered several algorithmic opportunities for the computation of nd. { Appropriately sorting the dataset beforehand produces a topological sort with respect to the F -dominance relation. With that, if tuple t precedes tuple s in the sorted relation, then s 6 F t. { The F -dominance test can be executed by either i) solving an LP problem as in Theorem 4 or ii) checking whether t 2 DR(s; F ) as in Theorem 5 through vertex enumeration of the polytope W(C). { We can either i) rst compute Sky and then remove F -dominated tuples (two phases), or ii) integrate dominance and F -dominance tests (one phase).
The best choice is to use sorting, vertex enumeration and a single phase. The corresponding pseudocode is shown in Algorithm 1, called SVE1F. The main idea is to scan the tuples sortedly and to populate a current window ND of nonF -dominated tuples. No tuple will ever be removed from ND, as no tuple can be F -dominated by a tuple found later in the sorted relation. The vertices of the polytope W(C) are computed just once (line 1). Algorithm 1 interleaves dominance and F -dominance tests, thus performing, for each new tuple s, a single pass over ND. Every candidate F -dominated tuple s (line 3) is compared against every candidate F -dominant tuple t (line 6) to decide whether s should be added to ND. The F -dominance test of line 6 is done via Theorem 5 and, thus, it is useful to precompute the left-hand sides of Inequality (11) already at line 4.
For the computation of po(r; F ), we start from the tuples in nd(r; F ) and, by Theorem 6, we discard any tuple t that is F -dominated by a convex combination of tuples in nd(r; F ) n ftg. However, directly checking F -dominance via (14) may be prohibitively time consuming when = jnd(r; F )j 1 is large. We therefore try, in Algorithm 2 (POND, i.e. po via nd), to reduce as early as possible the set of candidate potentially optimal tuples (PO) by adopting the following heuristics: i) we start with a convex combination of only ~ = 2 tuples (line 2), which will give rise to smaller, faster-to-solve systems (14) for testing F -dominance; as long
Input: relation r, constraints C, family F = LpC. Output: po(r; F). 1. let PO := nd(r; F) // via SVE1F 2. let ~ := 2; let lastRound := false 3. while(:lastRound) 4. if ~ jPOj 1 then lastRound := true 5. for each t in PO in reverse order // candidate F-dominated tuple 6. if 9s: s F t; s is convex comb. of the rst min(~; jPOj 1) tuples in POnftg then let PO:=POnftg 7. let ~ := ~ 2 8. return PO as ~ < jPOj 1, this condition is only su cient for pruning, but not necessary; after each round, we double ~ (line 7); ii) we sortedly enumerate candidate F dominated tuples from PO in reverse order (line 5), as the worst tuples wrt. the ordering are the most likely to be F -dominated; iii) using linear system (14), we check the existence of a convex combination of the rst ~ tuples in PO (line 6), as they are the best wrt. the ordering and thus more likely to F -dominate other tuples. In the last round (enabled by line 4) all the remaining tuples are checked against a convex combination of all the other tuples still in po, which is now a necessary and su cient condition for pruning, as in Theorem 6.
In [2], e ciency and e ectiveness of the proposed algorithms have been measured on both real and synthetic scenarios with varying i) data distribution, ii) dataset size, iii) number of dimensions, and iv) number of constraints. With default settings (anticorrelated data, N = 100K tuples, d = 6 dimensions, F = L1C family with jCj = 3 constraints), our algorithms incur sub-second execution times. Such times increase as N increases, d increases and jCj decreases.
Both nd and po reduce the size of the result wrt. Sky (Fig. 2a). For default values, their e ectiveness is remarkable (9.8% of the Sky points are in nd and only 1% in po). Somewhat surprisingly, computing nd via SVE1F may require much less time than computing Sky, because F -dominance tests, albeit more costly than dominance tests, are more e ective in pruning redundant tuples. /) ( ⨯ ○ ⨯ ⨯ ○ ○ ⨯○ ⨯○ ⨯ ○ | | | | | | ( ) ( ) ( ) ( ) ( ) ( ) (a) jndj=jSkyj and jpoj=jSkyj cardinality (b) Precision and recall of top-k queries wrt. Sky, ratios as dataset size N varies. nd, and po. Centroid of the W(C) as weight vector;
N = 100K tuples in the dataset.
Fig. 2: R-skylines vs. skyline and ranking queries (anticorrelated data with d = 6, F = L1C, jCj = 3).
Let Tk(r; f ) indicate the set of top-k tuples in relation r wrt. a scoring function f . The precision of Tk(r; f ) wrt. a set S is de ned as pre(S) = jS \ Tk(r; f )j=k, whereas the recall is rec(S) = jS \ Tk(r; f )j=jSj. Figure 2b shows precision and recall when f is the most representative weighted sum in F (i.e., f 's weight vector is the centroid of W(C)). Recall grows with k, while precision decreases. With standard parameter values, when k = jSj (and thus precision and recall are equal), rec(nd) is 50%, while rec(po) is 38%. Retrieving the entire nd with a top-k query may however require to scan almost the entire dataset. As expected, top-k queries incur a small fraction of the execution time of SVE1F (below 7%). 5
In this paper, we have presented a framework aiming to unify skyline and ranking queries. We have done so by introducing two R-skyline operators implementing the notions of non-dominated (nd) and potentially optimal (po) tuples with respect to a set of scoring functions F . The greater exibility of these operators captures not only standard skyline and top-1 queries, but also constraints on the weights in the scoring functions, which are highly relevant in practice.
It is well known that choosing the \right" weights for a scoring function is a di cult task for users, since it is usually hard to predict the e ects on ranking of changing one or more parameters. Replacing precise values with constraints on weights, as R-skylines do, is therefore a viable way to alleviate the problem.
We have shown that both nd and po are very e ective in focusing on tuples of interest, even in very large datasets. In practical cases, computing nd requires no more than a few seconds. For the more complex problem of computing po, we have developed heuristics to reduce the number of LP problems to be solved.
Natural extensions of this framework include the notions of top-k query and k-skyband, with k > 1 [6].