Operador de Skyline

El operador skyline es objeto de un problema de optimización y calcula el óptimo de Pareto en tuplas con múltiples dimensiones.

Este operador es una extensión de SQL propuesta por Börzsönyi et al. ^{[ 1 ]} para filtrar los resultados de una base de datos y conservar solo aquellos objetos que no estén dominados por ningún otro punto en todas las dimensiones. El nombre skyline proviene de la vista de Manhattan desde el río Hudson , donde se pueden ver los edificios que no están ocultos por ningún otro. Un edificio es visible si no está dominado por un edificio más alto o más cercano al río (dos dimensiones, distancia al río minimizada, altura maximizada). Otra aplicación del operador skyline consiste en seleccionar un hotel para unas vacaciones. El usuario desea que el hotel sea económico y esté cerca de la playa. Sin embargo, los hoteles cercanos a la playa también pueden ser caros. En este caso, el operador skyline solo presentaría aquellos hoteles que no sean peores que cualquier otro hotel en cuanto a precio y distancia a la playa.

El operador skyline devuelve tuplas que no están dominadas por ninguna otra tupla. Una tupla domina a otra si es al menos igual de buena en todas las dimensiones y mejor en al menos una dimensión. Formalmente, podemos pensar en cada tupla como un vector${\displaystyle p,q\in \mathbb {R} ^{n}}$.${\displaystyle p}$domina${\displaystyle q}$(escrito:${\displaystyle p\succ q}$) si${\displaystyle p}$es al menos tan bueno como${\displaystyle q}$en todas las dimensiones, y superior en al menos una: ^{[ 2 ]}$${\displaystyle p\succ q\Leftrightarrow \forall i\in [n].p[i]\succeq q[i]\wedge \exists j\in [n].p[j]\succ q[j].}$$ Dominio (${\displaystyle p\succ q}$) se puede definir como cualquier orden parcial estricto , por ejemplo mayor (con${\displaystyle \succ$ :=>} y${\displaystyle \succeq$ :=\geq } ) o menos (con${\displaystyle \succ$ :=<} y${\displaystyle \succeq$ :=\leq } ).

Suponiendo dos dimensiones y definiendo el dominio en ambas dimensiones como mayor, podemos calcular el horizonte en SQL-92 de la siguiente manera:

WITH tuples ( id , i , j ) as ( values ​​( 1 , 1 , 1 ), ( 1 , 2 , 1 ), ( 1 , 1 , 2 )) SELECT * FROM tuples t1 WHERE NOT EXISTS ( -- que no está dominada por SELECT * FROM tuples t2 -- una tupla que es WHERE t2 . i >= t1 . i and t2 . j >= t1 . j -- al menos tan buena en todas las dimensiones AND ( t2 . i > t1 . i or t2 . j > t1 . j ) -- y mejor en al menos una dimensión );

Como extensión de SQL, Börzsönyi et al. ^{[ 1 ]} propusieron la siguiente sintaxis para el operador skyline:

SELECCIONAR ... DE ... DONDE ... AGRUPAR POR ... QUE TENGA ... SKYLINE DE [ DISTINTO ] d1 [ MÍN | MÁX | DIFERENCIA ], ..., dm [ MÍN | MÁX | DIFERENCIA ] ORDENAR POR ...

donde d ₁ , ... d _m denotan las dimensiones del horizonte y MIN, MAX y DIFF especifican si el valor en esa dimensión debe minimizarse, maximizarse o simplemente ser diferente.

Sin una extensión SQL, la consulta SQL requiere un antijoin con not exists:

SELECCIONAR ... DE (...) q DONDE NO EXISTE ( SELECCIONAR * DE (...) p DONDE p . d1 [ <= | >= ] q . d1 Y ... Y p . dm [ <= | >= ] q . dm Y ( p . d1 [ < | > ] q . d1 O ... O p . dm [ < | > ] q . dm ))

El operador skyline se puede implementar directamente en SQL utilizando construcciones SQL actuales, pero se ha demostrado que esto es muy lento en sistemas de bases de datos basados ​​en disco. ^{[ 1 ]} Se han propuesto otros algoritmos que utilizan divide y vencerás, índices, ^{[ 1 ]} MapReduce ^{[ 3 ]} y computación de propósito general en tarjetas gráficas . ^{[ 4 ]} Las consultas skyline en flujos de datos (es decir, consultas skyline continuas) se han estudiado en el contexto del procesamiento de consultas paralelas en multinúcleos, debido a su amplia difusión en problemas de toma de decisiones en tiempo real y análisis de flujos de datos. ^{[ 5 ]}

Exasol cuenta con una implementación nativa. ^{[ 6 ]}

• eficiencia de Pareto
• Optimización multiobjetivo
• Envoltura convexa
• Búsqueda del vecino más cercano
• Algoritmo de selección