天际线运算：修订间差异
删除的内容 添加的内容
Peter Yeung（留言 | 贡献） 小 使用HotCat已移除Category:数据库算法; 已添加Category:数据库理论 |
|||
| 第7行： | 第7行： | ||
== 拟议的语法 == |
== 拟议的语法 == |
||
Börzsönyi et al.<ref name="borzsony2001skyline">{{Cite journal|title=The Skyline Operator|last=Borzsonyi|first=Stephan|last2=Kossmann|first2=Donald|date=2001|journal=Proceedings 17th International Conference on Data Engineering|doi=10.1109/ICDE.2001.914855|pages=421–430|last3=Stocker|first3=Konrad}}</ref> 提供以下语句作为天际线运算的示例:< |
Börzsönyi et al.<ref name="borzsony2001skyline">{{Cite journal|title=The Skyline Operator|last=Borzsonyi|first=Stephan|last2=Kossmann|first2=Donald|date=2001|journal=Proceedings 17th International Conference on Data Engineering|doi=10.1109/ICDE.2001.914855|pages=421–430|last3=Stocker|first3=Konrad}}</ref> 提供以下语句作为天际线运算的示例:<syntaxhighlight lang="sql"> |
||
SELECT ... FROM ... WHERE ... |
SELECT ... FROM ... WHERE ... |
||
GROUP BY ... HAVING ... |
GROUP BY ... HAVING ... |
||
| 第13行： | 第13行： | ||
..., dm [MIN | MAX | DIFF] |
..., dm [MIN | MAX | DIFF] |
||
ORDER BY ... |
ORDER BY ... |
||
</ |
</syntaxhighlight>在d<sub>1</sub>,...d<sub>m</sub> 表示天际线运算所考量的维度。MIN MAX 与 DIFF 用来指定维度被考虑的方向。 |
||
== 实现 == |
== 实现 == |
||
2020年7月7日 (二) 04:18的版本
 | 此條目翻譯品質不佳。 (2019年6月15日) |
天际线运算（英語：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 ...
在d1,...dm 表示天际线运算所考量的维度。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.
- ^ 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.