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