Оператор Скайлайн

Оператор линии горизонта является предметом задачи оптимизации и вычисляет оптимум Парето для кортежей с несколькими измерениями.

Этот оператор является расширением SQL, предложенным Бёржёни и др. фильтровать результаты из базы данных, чтобы сохранять только те объекты, которые по нескольким измерениям не хуже любых других. Название skyline происходит от вида на Манхэттен со стороны реки Гудзон , где можно увидеть те здания, которые не скрыты никем другим. Здание видно, если над ним не доминирует здание, которое выше или ближе к реке (два измерения, минимальное расстояние до реки, максимальная высота). Еще одно приложение оператора скайлайн предполагает выбор отеля для отдыха. Пользователь хочет, чтобы отель был одновременно дешевым и близким к пляжу. Однако отели, расположенные рядом с пляжем, также могут быть дорогими. В этом случае оператор скайлайн будет представлять только те отели, которые не хуже любого другого отеля как по цене, так и по удаленности от пляжа.

Формальная спецификация

Оператор skyline возвращает кортежи, над которыми не доминирует какой-либо другой кортеж. Кортеж доминирует над другим, если он хотя бы так же хорош во всех измерениях и лучше хотя бы в одном измерении. Формально мы можем рассматривать каждый кортеж как вектор. $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$).

Предполагая наличие двух измерений и определяя доминирование в обоих измерениях как большее, мы можем вычислить линию горизонта в 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 (                    -- which is not dominated by
  SELECT * FROM tuples t2             -- a tuple that is
  WHERE t2.i >= t1.i and t2.j >= t1.j -- at least as good in all dimensions
    AND (t2.i > t1.i or t2.j > t1.j)  -- and better in at least one dimension
);

Предлагаемый синтаксис

В качестве расширения SQL Бёржёни и др. предложил следующий синтаксис для оператора линии горизонта:

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

Выполнение

Оператор skyline можно реализовать непосредственно в SQL, используя текущие конструкции SQL, но было показано, что в дисковых системах баз данных это происходит очень медленно. Были предложены и другие алгоритмы, использующие принцип «разделяй и властвуй», индексы, MapReduce и вычисления общего назначения на видеокартах . Запросы Skyline к потокам данных (т.е. непрерывные запросы Skyline) изучались в контексте параллельной обработки запросов на многоядерных процессорах из-за их широкого распространения в задачах принятия решений в реальном времени и аналитике потоков данных.

См. также

• Парето-эффективность
• Многокритериальная оптимизация
• Выпуклая оболочка
• Поиск ближайшего соседа
• Алгоритм выбора