Skyline operator

The skyline operator is the subject of an optimization problem and computes the Pareto optimum on tuples with multiple dimensions.

This operator is an extension to SQL proposed by Börzsönyi et al. ^[1] to filter results from a database to keep only those objects that are not worse in multiple dimensions than any other. The name skyline comes from the view on Manhattan from the Hudson River, where those buildings can be seen that are not hidden by any other. A building is visible if it is not dominated by a building that is taller or closer to the river (two dimensions, distance to the river minimized, height maximized). Another application of the skyline operator involves selecting a hotel for a holiday. The user wants the hotel to be both cheap and close to the beach. However, hotels that are close to the beach may also be expensive. In this case, the skyline operator would only present those hotels that are not worse than any other hotel in both price and distance to the beach.

Formal specification

The skyline operator returns tuples that are not dominated by any other tuple. A tuple dominates another if it is at least as good in all dimensions and better in at least one dimension. Formally, we can think of each tuple as a vector ${\displaystyle p,q\in \mathbb {R} ^{n}}$. ${\displaystyle p}$ dominates ${\displaystyle q}$ (written: ${\displaystyle p\succ q}$) if ${\displaystyle p}$ is at least as good as ${\displaystyle q}$ in every dimension, and superior in at least one: ^[2]

$${\displaystyle p\succ q\Leftrightarrow \forall i\in [n].p[i]\succeq q[i]\wedge \exists j\in [n].p[j]\succ q[j].}$$

Dominance (${\displaystyle p\succ q}$) can be defined as any strict partial ordering, for example greater (with ${\displaystyle \succ$ :=>} and ${\displaystyle \succeq$ :=\geq }) or less (with ${\displaystyle \succ$ :=<} and ${\displaystyle \succeq$ :=\leq }).

Assuming two dimensions and defining dominance in both dimensions as greater, we can compute the skyline in SQL-92 as follows:

WITHtuples(id,i,j)as(values(1,1,1),(1,2,1),(1,1,2))SELECT*FROMtuplest1WHERENOTEXISTS(-- which is not dominated bySELECT*FROMtuplest2-- a tuple that isWHEREt2.i>=t1.iandt2.j>=t1.j-- at least as good in all dimensionsAND(t2.i>t1.iort2.j>t1.j)-- and better in at least one dimension);

Proposed syntax

As an extension to SQL, Börzsönyi et al. ^[1] proposed the following syntax for the skyline operator:

SELECT...FROM...WHERE...GROUPBY...HAVING...SKYLINEOF[DISTINCT]d1[MIN|MAX|DIFF],...,dm[MIN|MAX|DIFF]ORDERBY...

where d₁, ... d_m denote the dimensions of the skyline and MIN, MAX and DIFF specify whether the value in that dimension should be minimised, maximised or simply be different.

Without an SQL extension, the SQL query requires an antijoin with not exists:

SELECT...FROM(...)qWHERENOTEXISTS(SELECT*FROM(...)pWHEREp.d1[<=|>=]q.d1AND...ANDp.dm[<=|>=]q.dmAND(p.d1[<|>]q.d1OR...ORp.dm[<|>]q.dm))

Implementation

The skyline operator can be implemented directly in SQL using current SQL constructs, but this has been shown to be very slow in disk-based database systems. ^[1] Other algorithms have been proposed that make use of divide and conquer, indices, ^[1] MapReduce ^[3] and general-purpose computing on graphics cards. ^[4] Skyline queries on data streams (i.e. continuous skyline queries) have been studied in the context of parallel query processing on multicores, owing to their wide diffusion in real-time decision making problems and data streaming analytics. ^[5]

See also

• Pareto efficiency
• Multi-objective optimization
• Convex hull
• Nearest neighbor search
• Selection algorithm

References

1. Borzsonyi, Stephan; Kossmann, Donald; Stocker, Konrad (2001). "The Skyline operator". Proceedings 17th International Conference on Data Engineering. pp. 421–430. doi:10.1109/ICDE.2001.914855. ISBN   0-7695-1001-9. S2CID   5812098.
2. Maximilian E. Schüle, Alex Kulikov, Alfons Kemper, Thomas Neumann (2020). "ARTful Skyline Computation for In-Memory Database Systems". New Trends in Databases and Information Systems - ADBIS 2020 Short Papers, Lyon, France, August 25-27, 2020, Proceedings. pp. 3–12. doi:10.1007/978-3-030-54623-6_1. ISBN   978-3-030-54622-9.
3. Mullesgaard, Kasper; Pedersen, Jens Laurits; Lu, Hua; Zhou, Yongluan (2014). "Efficient Skyline Computation in MapReduce" (PDF). Proc. 17th International Conference on Extending Database Technology (EDBT): 37–48.
4. Bøgh, Kenneth S; Assent, Ira; Magnani, Matteo (2013). "Efficient GPU-based skyline computation". Proceedings of the Ninth International Workshop on Data Management on New Hardware. pp. 5:1–5:6. doi:10.1145/2485278.2485283. ISBN   9781450321969. S2CID   13195757.
5. De Matteis, Tiziano; Di Girolamo, Salvatore; Mencagli, Gabriele (25 August 2016). "Continuous skyline queries on multicore architectures". Concurrency and Computation: Practice and Experience. 28 (12): 3503–3522. doi:10.1002/cpe.3866. S2CID   6562372.