Skyline-Operator

Der Skyline-Operator ist Gegenstand eines Optimierungsproblems und berechnet das Pareto-Optimum auf Tupeln mit mehreren Dimensionen.

Dieser Operator ist eine von Börzsönyi et al. vorgeschlagene Erweiterung von SQL, um Ergebnisse aus einer Datenbank so zu filtern, dass nur solche Tupel erhalten bleiben, die in mehreren Dimensionen nicht schlechter sind als andere. Der Name Skyline stammt von der Ansicht auf Manhattan vom Hudson River aus, wo jene Gebäude zu sehen sind, die von keinem anderen verdeckt werden. Ein Gebäude ist sichtbar, wenn es nicht von einem Gebäude dominiert wird, das höher oder näher am Fluss steht (zwei Dimensionen, Abstand zum Fluss minimiert, Höhe maximiert). Eine weitere Anwendung des Skyline-Operators ist die Auswahl eines Hotels für einen Urlaub. Man möchte ein günstiges Hotel in Strandnähe. Hotels in Strandnähe können jedoch auch teuer sein. In diesem Fall würde der Skyline-Operator nur die Hotels anzeigen, die sowohl beim Preis als auch bei der Entfernung zum Strand nicht schlechter sind als alle anderen Hotels.

Formale Beschreibung

Der Skyline-Operator gibt Tupel zurück, die von keinem anderen Tupel dominiert werden. Ein Tupel dominiert ein anderes, wenn es in allen Dimensionen mindestens gleich gut und in mindestens einer Dimension besser ist. Formal kann man sich jedes Tupel als einen Vektor $p,q\in \mathbb {R} ^{n}$ vorstellen. $p$ dominiert $q$ (geschrieben: $p\succ q$), wenn $p$ in jeder Dimension mindestens so gut wie $q$ und in mindestens einer überlegen ist: $$p\succ q\Leftrightarrow \forall i\in [n].p[i]\succeq q[i]\wedge \exists j\in [n].p[j]\succ q[j].$$ Die Dominanz ($p\succ q$) kann als eine beliebige strikte Ordnung definiert werden, zum Beispiel größer (mit $\succ :=>$ und $\succeq :=\geq$) oder kleiner (mit $\succ :=<$ und $\succeq :=\leq$).

Geht man von zwei Dimensionen aus und definiert die Dominanz in beiden Dimensionen als größer, kann man die Skyline in SQL-92 wie folgt berechnen:

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             -- Wo kein Tupel existiert,
  WHERE t2.i >= t1.i and t2.j >= t1.j -- das in allen Dimensionen gleich gut
    AND (t2.i > t1.i or t2.j > t1.j)  -- und in einer Dimension besser ist.
);

Vorgeschlagene Syntax

Als Erweiterung von SQL haben Börzsönyi et al. die folgende Syntax für den Skyline-Operator vorgeschlagen:

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

dabei sind d₁, ... d_m die Dimensionen der Skyline und MIN, MAX und DIFF geben an, ob der jeweilige Wert minimiert, maximiert wird oder schlicht abweichen soll.

Ohne SQL-Erweiterung ist ein Anti-Join mittels not exists notwendig:

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 ))

Implementierung

Der Skyline-Operator kann ohne Erweiterung in SQL ausgedrückt werden, allerdings gibt einige spezifische Implementierungen. Zum Beispiel gibt es Implementierungen mittels MapReduce oder CUDA. Skyline-Abfragen auf Datenströmen (d. h. kontinuierliche Skyline-Abfragen) wurden im Zusammenhang mit der parallelen Abfrageverarbeitung auf Mehrkernprozessoren untersucht, da sie in Datenstromanalysen und Echtzeitsystemen weit verbreitet sind.