天際線運算

天際線運算（英語：Skyline Operator）屬於最佳化問題的範疇。用來查詢資料庫中的結果，並保證返回的每一個結果至少在某一方面不劣於其他結果。

這個運算符是SQL的一個擴充，由德國的Börzsönyi等人於2001年提出。^[1] 論文中所用的酒店示例是天際線運算的一個經典示例。當用戶希望酒店是既便宜又靠近海灘，但是靠近海灘的酒店通常又比較昂貴時，天際線運算符可以保證其查詢結果中，對於任意兩個酒店，每一個酒店都至少在與海灘的距離或者價格中，不比另一個劣。

天際線運算返回的結果是資料庫中一部分特殊的點，這些點構成了資料庫的輪廓^[2]。這也是此運算得名的原因。

擬議的語法[編輯]

Börzsönyi et al.^[1] 提供以下語句作為天際線運算的示例:

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

在d₁,...d_m 表示天際線運算所考量的維度。MIN MAX 與 DIFF 用來指定維度被考慮的方向。

實現[編輯]

天際線運算可以直接使用SQL憑藉目前SQL的結構實現，然而實踐表明其實現效率低下。^[1] 目前提出的其他算法藉助以下想法實現天際線運算：分而治之（divide and conquer）、索引（indices）^[1]、MapReduce^[3] 或圖形處理單元上的通用計算。^[4] 由於其可以在實時決策的問題和數據流的分析中廣泛運用，天際線查詢流（即連續的天際線查詢）問題正在研究之中，其研究屬於運用多核處理器實現並行Query處理（parallel query processing）的領域^[5]

參見[編輯]

參考文獻[編輯]

^ ^1.0 ^1.1 ^1.2 ^1.3 Borzsonyi, Stephan; Kossmann, Donald; Stocker, Konrad. The Skyline Operator. Proceedings 17th International Conference on Data Engineering. 2001: 421–430. doi:10.1109/ICDE.2001.914855.
^ Skyline计算研究综述--《计算机工程与应用》2008年06期. www.cnki.com.cn. [2019-06-14].
^ Mullesgaard, Kasper; Pedersen, Jens Laurits; Lu, Hua; Zhou, Yongluan. Efficient Skyline Computation in MapReduce (PDF). Proc. 17th International Conference on Extending Database Technology (EDBT). 2014: 37–48 [2019-06-14]. （原始內容存檔 (PDF)於2015-04-02）.
^ Bøgh, Kenneth S; Assent, Ira; Magnani, Matteo. Efficient GPU-based skyline computation. Proceedings of the Ninth International Workshop on Data Management on New Hardware. 2013: 5:1–5:6. doi:10.1145/2485278.2485283.
^ De Matteis, Tiziano; Di Girolamo, Salvatore; Mencagli, Gabriele. Continuous skyline queries on multicore architectures. Concurrency and Computation: Practice and Experience. 25 August 2016, 28 (12): 3503–3522. doi:10.1002/cpe.3866.

[borzsony2001skyline-1] 1.0 ^1.1 ^1.2 ^1.3 Borzsonyi, Stephan; Kossmann, Donald; Stocker, Konrad. The Skyline Operator. Proceedings 17th International Conference on Data Engineering. 2001: 421–430. doi:10.1109/ICDE.2001.914855.

[2] Skyline计算研究综述--《计算机工程与应用》2008年06期. www.cnki.com.cn. [2019-06-14].

[3] Mullesgaard, Kasper; Pedersen, Jens Laurits; Lu, Hua; Zhou, Yongluan. Efficient Skyline Computation in MapReduce (PDF). Proc. 17th International Conference on Extending Database Technology (EDBT). 2014: 37–48 [2019-06-14]. （原始內容存檔 (PDF)於2015-04-02）.

[4] Bøgh, Kenneth S; Assent, Ira; Magnani, Matteo. Efficient GPU-based skyline computation. Proceedings of the Ninth International Workshop on Data Management on New Hardware. 2013: 5:1–5:6. doi:10.1145/2485278.2485283.

[5] De Matteis, Tiziano; Di Girolamo, Salvatore; Mencagli, Gabriele. Continuous skyline queries on multicore architectures. Concurrency and Computation: Practice and Experience. 25 August 2016, 28 (12): 3503–3522. doi:10.1002/cpe.3866.

[1]

[2]

[3]

[4]

[5]