Оператор Skyline

Фильтр базы данных

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

Этот оператор является расширением SQL, предложенным Börzsönyi et al. ^[1] для фильтрации результатов из базы данных с целью сохранения только тех объектов, которые не хуже по нескольким измерениям, чем любые другие. Название skyline происходит от вида на Манхэттен с реки Гудзон , где видны те здания, которые не скрыты никакими другими. Здание видно, если оно не загорожено зданием, которое выше или ближе к реке (два измерения, расстояние до реки минимизировано, высота максимизирована). Другое применение оператора skyline включает выбор отеля для отпуска. Пользователь хочет, чтобы отель был и дешевым, и близко к пляжу. Однако отели, которые находятся близко к пляжу, также могут быть дорогими. В этом случае оператор skyline будет представлять только те отели, которые не хуже любого другого отеля как по цене, так и по расстоянию до пляжа.

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

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

Предположив два измерения и определив доминирование в обоих измерениях как большее, мы можем вычислить линию горизонта в 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 ) -- и лучше по крайней мере в одном измерении );                                       

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

В качестве расширения SQL Бёржёньи и др. ^[1] предложили следующий синтаксис для оператора skyline:

ВЫБРАТЬ ... ИЗ ... ГДЕ ... ГРУППИРОВАТЬ ПО ... ИМЕЮЩИМ ... ЛИНИЮ ГОРИЗОНТАЛЬНОГО ИЗОБРАЖЕНИЯ [ ОТЛИЧАЕТСЯ ] d1 [ МИН | МАКС | РАЗНИЦА ], ..., dm [ МИН | МАКС | РАЗНИЦА ] УПОРЯДОЧИТЬ ПО ...                          

где d ₁ , ... d _m обозначают размеры линии горизонта, а MIN, MAX и DIFF указывают, должно ли значение в этом измерении быть минимизировано, максимизировано или просто отличаться.

Без расширения SQL запрос SQL требует антисоединения с not exists:

ВЫБЕРИТЕ ... ИЗ (...) q ГДЕ НЕ СУЩЕСТВУЕТ ( ВЫБЕРИТЕ * ИЗ (...) p ГДЕ p . d1 [ <= | >= ] q . d1 И ... И p . dm [ <= | >= ] q . dm И ( p . d1 [ < | > ] q . d1 ИЛИ ... ИЛИ p . dm [ < | > ] q . dm ))                                           

Выполнение

Оператор skyline может быть реализован непосредственно в SQL с использованием текущих конструкций SQL, но было показано, что это очень медленно в дисковых системах баз данных. ^[1] Были предложены другие алгоритмы, которые используют разделяй и властвуй, индексы, ^[1] MapReduce ^[3] и вычисления общего назначения на графических картах . ^[4] Запросы skyline к потокам данных (т. е. непрерывные запросы skyline) были изучены в контексте параллельной обработки запросов на многоядерных процессорах из-за их широкого распространения в задачах принятия решений в реальном времени и потоковой аналитике данных. ^[5]

Смотрите также

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

Ссылки

1. Боржоный, Стефан; Коссманн, Дональд; Стокер, Конрад (2001). "Оператор Skyline". Труды 17-й Международной конференции по инжинирингу данных . С. 421–430. doi :10.1109/ICDE.2001.914855. ISBN 0-7695-1001-9. S2CID  5812098.
2. Максимилиан Э. Шюле, Алекс Куликов, Альфонс Кемпер , Томас Нойман (2020). "ARTful Skyline Computation for In-Memory Database Systems". Новые тенденции в базах данных и информационных системах - ADBIS 2020 Short Papers, Лион, Франция, 25-27 августа 2020 г., Труды . Коммуникации в области компьютерных и информационных наук. Том 1259. стр. 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. Бёг, Кеннет С.; Ассен, Ира; Маньяни, Маттео (2013). «Эффективное вычисление линии горизонта на основе графического процессора». Труды Девятого международного семинара по управлению данными на новом оборудовании . С. 5:1–5:6. doi :10.1145/2485278.2485283. ISBN 9781450321969. S2CID  13195757.
5. Де Маттеис, Тициано; Ди Джироламо, Сальваторе; Менкальи, Габриэле (25 августа 2016 г.). «Непрерывные запросы горизонта на многоядерных архитектурах». Параллелизм и вычисления: практика и опыт . 28 (12): 3503–3522. дои : 10.1002/cpe.3866. S2CID  6562372.