 | Эта статья требует дополнительных ссылок для проверки . ( январь 2021 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
 | Эта статья требует внимания специалиста-математика . ( Март 2011 г. ) |
Соединение с вложенным циклом - это простой алгоритм, который объединяет два набора с помощью двух вложенных циклов . [1] Операции соединения важны для управления базой данных .
Алгоритм [ править ]
Два отношения и соединяются следующим образом:
алгоритм nested_loop_join предназначен для каждого кортежа r в R do для каждого кортежа s в S do, если r и s удовлетворяют условию соединения, то вывести кортеж < r , s >
Этот алгоритм будет включать n r * b s + b r передач блоков и n r + b r поисков, где b r и b s - количество блоков в отношениях R и S соответственно, а n r - количество кортежей в отношении R .
Алгоритм работает в операциях ввода-вывода, где и - количество кортежей, содержащихся в и, соответственно, и может быть легко обобщен для соединения любого количества отношений ...
Блок вложенного цикла алгоритм соединение [2] является обобщением простых вложенных циклов алгоритма , который использует дополнительную память , чтобы уменьшить количество раз , что отношение сканирования. Он загружает большие фрагменты отношения R в основную память. Для каждого фрагмента он сканирует S и оценивает условие соединения для всех пар кортежей, находящихся в настоящее время в памяти. Это сокращает количество сканирований S до одного для каждого фрагмента.
Вариант соединения индекса [ править ]
Если внутреннее отношение имеет индекс для атрибутов, используемых в соединении, тогда наивное гнездовое соединение цикла может быть заменено индексным соединением.
Алгоритм index_join является для каждого кортежа г в R сделать для каждого кортежа ев в S в индексе LookUp сделать выход кортеж < г , с >
Временная сложность для этого варианта улучшается с O ( M * N ) до O ( M * log N ).
См. Также [ править ]
Ссылки [ править ]
 | Эта статья по информатике незавершена . Вы можете помочь Википедии, расширив ее . |
