Иллюстрация свойств алгоритмов соединения. При выполнении соединения между более чем двумя отношениями и более чем двумя атрибутами алгоритмы двоичного соединения, такие как хеш-соединение , работают над двумя отношениями одновременно и объединяют их по всем атрибутам в условии соединения; Оптимальные алгоритмы в худшем случае, такие как обобщенное соединение, работают с одним атрибутом одновременно, но объединяют все отношения по этому атрибуту. [1]
Алгоритм оптимального соединения для наихудшего случая — это алгоритм вычисления реляционных соединений со средой выполнения, ограниченной выходным размером соединения в наихудшем случае . Традиционные алгоритмы двоичного соединения, такие как хеш-соединение, оперируют двумя отношениями одновременно; соединения между более чем двумя отношениями реализуются путем многократного применения бинарных соединений. Алгоритмы оптимального соединения в худшем случае асимптотически быстрее, чем любой алгоритм соединения, основанный на таких итерированных двоичных соединениях.
Первый алгоритм оптимального соединения для наихудшего случая, generic join , был опубликован в 2012 году. [2] Алгоритмы оптимального соединения для наихудшего случая были реализованы в коммерческих системах баз данных, включая систему LogicBlox . [3] [4] Оптимальные соединения для наихудшего случая были применены для построения оптимального алгоритма электронного сопоставления для наихудшего случая . [5]
Рекомендации
Примечания
^ Ван, Ису Реми; Уиллси, Макс; Сучу, Дэн (27 января 2023 г.). «Бесплатное соединение: объединение оптимальных и традиционных соединений для наихудшего случая». arXiv : 2301.10841 [cs.DB].
^ Нго, Хунг К.; Порат, Эли; Ре, Кристофер; Рудра, Атри (08 марта 2012 г.). «Алгоритмы оптимального соединения наихудшего случая». arXiv : 1203.1952 [cs.DB].
^ Вельдхуизен, Тодд Л. (20 декабря 2013 г.). «Чехарда Triejoin: алгоритм оптимального соединения для наихудшего случая». arXiv : 1210.0481 [cs.DB].
^ Фрайтаг, Майкл; Бэндл, Максимилиан; Шмидт, Тобиас; Кемпер, Альфонс; Нойманн, Томас (01 июля 2020 г.). «Принятие оптимальных объединений для наихудшего случая в системах реляционных баз данных». Труды Фонда VLDB . 13 (12): 1891–1904. дои : 10.14778/3407790.3407797. ISSN 2150-8097. S2CID 221115321.
^ Чжан, Ихонг; Ван, Ису Реми; Уиллси, Макс; Тэтлок, Закари (12 января 2022 г.). «Реляционное электронное сопоставление». Труды ACM по языкам программирования . 6 (ПОПЛ): 35:1–35:22. дои : 10.1145/3498696 . S2CID 236924583.
Источники
Нго, Хунг К.; Порат, Эли; Ре, Кристофер; Рудра, Атри (13 марта 2018 г.). «Алгоритмы оптимального соединения наихудшего случая». Журнал АКМ . 65 (3): 16:1–16:40. arXiv : 1203.1952 . дои : 10.1145/3180143. ISSN 0004-5411.
Нго, Хунг К; Ре, Кристофер; Рудра, Атри (28 февраля 2014 г.). «Перекос наносит ответный удар: новые разработки в теории алгоритмов соединения». Запись ACM SIGMOD . 42 (4): 5–16. дои : 10.1145/2590989.2590991. ISSN 0163-5808. S2CID 6384477.
Внешние ссылки
Нежное (-вроде) введение в оптимальные соединения для наихудшего случая
