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

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

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

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

• パレート効率
• 多目的最適化
• 凸包
• 最近傍探索
• 選択アルゴリズム