スカイラインオペレーター

データベースフィルター

スカイライン演算子は最適化問題の対象であり、複数の次元を持つタプルのパレート最適解を計算します。

この演算子は、Börzsönyi ら^{[1]が提案した}SQLの拡張機能で、データベースからの結果をフィルター処理して、すべての次元で他のどのポイントにも支配されていないオブジェクトのみを保持します。スカイラインという名前は、ハドソン川から見たマンハッタンの眺めに由来しており、そこでは他のどの建物にも隠れていない建物が見えます。建物は、それより背の高い建物や川に近い建物に支配されていない場合に見えます (2 次元、川までの距離が最小、高さが最大)。スカイライン演算子のもう 1 つの用途は、休暇用のホテルを選択することです。ユーザーはホテルが安くてビーチに近いことを望んでいます。ただし、ビーチに近いホテルは値段が高い場合もあります。この場合、スカイライン演算子は、価格とビーチまでの距離の両方で他のホテルより悪くないホテルのみを表示します。

形式仕様

スカイライン演算子は、他のどのタプルにも支配されていないタプルを返します。あるタプルが他のタプルを支配するとは、すべての次元において少なくとも同等であり、少なくとも1つの次元において優れている場合です。正式には、各タプルをベクトルと考えることができます。がすべての次元においてと同等であり、少なくとも1つの次元において優れている場合、は支配します（と表記します）。 ^[2] 優位性（）は、がより大きい（およびの場合）またはより小さい（およびの場合）など、任意の厳密な半順序として定義できます。 $p,q\in \mathbb {R} ^{n}$ $p$ $q$ $p\succ q$ $p$ $q$ $p\succ q\Leftrightarrow \forall i\in [n].p[i]\succeq q[i]\wedge \exists j\in [n].p[j]\succ q[j].$ $p\succ q$ $\succ :=>$ $\succeq :=\geq$ $\succ :=<$ $\succeq :=\leq$

2 つの次元を想定し、両方の次元の優位性をより大きいと定義すると、 SQL-92でスカイラインを次のように計算できます。

WITH tuples ( id , i , j ) as ( values ( 1 , 1 , 1 ), ( 1 , 2 , 1 ), ( 1 , 1 , 2 )) SELECT * FROM tuples t1 WHERE NOT EXISTS ( -- これはSELECT * FROM tuples t2によって支配されません-- WHERE t2 . i > = t1 . iかつt2 . j >= t1 . j -- すべての次元で少なくとも同等に良好であり、AND ( t2 . i > t1 . iまたはt2 . j > t1 . j ) -- 少なくとも 1 つの次元で優れているタプル);

提案された構文

SQLの拡張として、Börzsönyiら^[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 クエリには次の逆結合not existsが必要です。

SELECT ... FROM (...) q WHERE NOT EXISTS ( SELECT * FROM (...) p WHERE p . d1 [ <= | >= ] q . d1 AND ... AND p . dm [ <= | >= ] q . dm AND ( p . d1 [ < | > ] q . d1 OR ... OR p . dm [ < | > ] q . dm ))

実装

スカイライン演算子は、現在のSQL構文を使用してSQLに直接実装できますが、ディスクベースのデータベースシステムでは非常に遅くなることがわかっています。^{[1]分割統治法、インデックス、}^[1] MapReduce ^[3]およびグラフィックカード上の汎用コンピューティングを利用する他のアルゴリズムも提案されています。^[4]データストリームに対するスカイラインクエリ（つまり、連続スカイラインクエリ）は、リアルタイムの意思決定問題やデータストリーミング分析に広く普及しているため、マルチコアでの並列クエリ処理のコンテキストで研究されてきました。^[5]

参照

参考文献

^ abcd Borzsonyi, Stephan; Kossmann, Donald; Stocker, Konrad (2001). 「スカイライン演算子」. Proceedings 17th International Conference on Data Engineering . pp. 421– 430. doi :10.1109/ICDE.2001.914855. ISBN 0-7695-1001-9. S2CID 5812098。
^ Maximilian E. Schüle、Alex Kulikov、Alfons Kemper、Thomas Neumann (2020). 「インメモリデータベースシステムのためのARTful Skyline Computation」.データベースと情報システムの新しいトレンド - ADBIS 2020 Short Papers、フランス、リヨン、2020年8月25日～27日、議事録. Communications in Computer and Information Science. 第1259巻. pp. 3– 12. doi :10.1007/978-3-030-54623-6_1. ISBN 978-3-030-54622-9。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)
^ ムレスゴー、カスパー;ペダーセン、イェンス・ラウリッツ。ルー、ファ。周永琳（2014）。「MapReduce での効率的なスカイライン計算」(PDF)。手順第 17 回拡張データベース技術国際会議 (EDBT) : 37–48 .
^ Bøgh, Kenneth S; Assent, Ira; Magnani, Matteo (2013). 「効率的なGPUベースのスカイライン計算」.第9回国際新ハードウェアデータ管理ワークショップ議事録. pp. 5:1–5:6. doi :10.1145/2485278.2485283. ISBN 9781450321969. S2CID 13195757。
^ デ・マティス、ティツィアーノ;ディ・ジローラモ、サルヴァトーレ。メンカリ、ガブリエレ（2016年8月25日）。「マルチコアアーキテクチャでの継続的なスカイラインクエリ」。同時実行性と計算: 実践と経験。28 (12): 3503–3522。土井:10.1002/cpe.3866。S2CID 6562372。

このデータベースソフトウェア関連の記事はスタブです。記事を拡張することでWikipediaに貢献できます。

[borzsony2001skyline-1] Borzsonyi, Stephan; Kossmann, Donald; Stocker, Konrad (2001). 「スカイライン演算子」. Proceedings 17th International Conference on Data Engineering . pp. 421– 430. doi :10.1109/ICDE.2001.914855. ISBN 0-7695-1001-9. S2CID 5812098。

[adbis-2] Maximilian E. Schüle、Alex Kulikov、Alfons Kemper、Thomas Neumann (2020). 「インメモリデータベースシステムのためのARTful Skyline Computation」.データベースと情報システムの新しいトレンド - ADBIS 2020 Short Papers、フランス、リヨン、2020年8月25日～27日、議事録. Communications in Computer and Information Science. 第1259巻. pp. 3– 12. doi :10.1007/978-3-030-54623-6_1. ISBN 978-3-030-54622-9。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)

[3] ムレスゴー、カスパー;ペダーセン、イェンス・ラウリッツ。ルー、ファ。周永琳（2014）。「MapReduce での効率的なスカイライン計算」(PDF)。手順第 17 回拡張データベース技術国際会議 (EDBT) : 37–48 .

[4] Bøgh, Kenneth S; Assent, Ira; Magnani, Matteo (2013). 「効率的なGPUベースのスカイライン計算」.第9回国際新ハードウェアデータ管理ワークショップ議事録. pp. 5:1–5:6. doi :10.1145/2485278.2485283. ISBN 9781450321969. S2CID 13195757。

[5] デ・マティス、ティツィアーノ;ディ・ジローラモ、サルヴァトーレ。メンカリ、ガブリエレ（2016年8月25日）。「マルチコアアーキテクチャでの継続的なスカイラインクエリ」。同時実行性と計算: 実践と経験。28 (12): 3503–3522。土井:10.1002/cpe.3866。S2CID 6562372。