Рубрики

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

Рассмотрим соединение (алгебру отношений) между отношениями r (R) и s (S) с использованием метода вложенных циклов. Существует 3 буфера, каждый из которых имеет размер, равный размеру дискового блока, из которых один буфер зарезервирован для промежуточных результатов. Предполагая, что размер (r (R)) (A), отношение r (R) находится во внешнем цикле.
(B) отношение s (S) находится во внешнем цикле.
(C) коэффициент выбора соединения между r (R) и s (S) составляет более 0,5.

(D) коэффициент выбора соединения между r (R) и s (S) составляет менее 0,5.

Ответ: (А)
Объяснение: Соединение с вложенным циклом является одним из методов реализации базы данных в памяти. Объединение вложенных циклов — это алгоритм, который объединяет два набора с использованием двух вложенных циклов.

В соответствии с вложенным соединением, учитывая отношения R и S

Для каждого кортежа R в R сделать
Для каждого кортежа в S сделать
Если r и s удовлетворяют условию соединения
Затем выведите кортеж <r, s>

Оценка стоимости для вышеуказанного цикла:
— b (R) и b (S) количество блоков в R и в S
— Каждый блок внешнего отношения читается один раз
— Внутреннее отношение читается один раз для каждого блока внешнего отношения.

Суммирование: IO = b (R) + n (R) * b (S) всего операций ввода-вывода

Предположим, что | R |> | S | то есть b (R) = 10, n (R) = 100, n (S) = 30 и b (s) = 3
Теперь, если R является внешним соотношением, то IO = 10 + 100 * 3 = 340
если S — внешнее отношение, то IO = 3 + 30 * 10 = 303

Как можно заметить, тот общий IO меньше, если значение внешней переменной меньше, и поскольку уже задано, что | R | <| S |. Поэтому отношение r (R) должно быть во внешнем цикле, чтобы иметь меньше количество обращений к диску.
Ссылки:

  1. https://www.informatik.huberlin.de/de/forschung/gebiete/wbi/teaching/archive/sose05/dbs2/slides/09_joins.pdf
  2. https://en.wikipedia.org/wiki/Nested_loop_join

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

0.00 (0%) 0 votes