Skyline operator

The Skyline operator is the subject of an optimization problem, used in a query to filter results from a database to keep only those objects that are not worse than any other.

This operator is an extension to SQL proposed by Börzsönyi et al.[1] A classic example of 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.

Proposed syntax

To give an example in SQL: Börzsönyi et al.[1] proposed the following syntax for the Skyline operator:

SELECT ... FROM ... WHERE ...
GROUP BY ... HAVING ...
SKYLINE OF [DISTINCT] d1 [MIN | MAX | DIFF],
                 ..., dm [MIN | MAX | DIFF]
ORDER BY ...

where d1, ... dm 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.

Implementation

The Skyline operator can be implemented directly in SQL using current SQL constructs, however this has been shown to be very slow.[1] Other algorithms have been proposed that make use of divide and conquer, indices,[1] MapReduce[2] and general-purpose computing on graphics cards.[3] 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.[4]

gollark: No, I also do.
gollark: Wrong.
gollark: On IRC.
gollark: Also, mondecitronne.com's cert expired.
gollark: ngircd spontaneously segfaulted, "fun".

See also

References
  1. Borzsonyi, Stephan; Kossmann, Donald; Stocker, Konrad (2001). "The Skyline Operator". Proceedings 17th International Conference on Data Engineering: 421–430. doi:10.1109/ICDE.2001.914855.
  2. 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.
  3. 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: 5:1–5:6. doi:10.1145/2485278.2485283.
  4. De Matteis, Tiziano; Di Girolamo, Salvatore; Mencagli, Gabriele (25 August 2016). "Continuous skyline queries on multicore architectures" (PDF). Concurrency and Computation: Practice and Experience. 28 (12): 3503–3522. doi:10.1002/cpe.3866.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.