Левостороннее дерево соединений

Рис. 1.9. Левостороннее дерево соединений.

В данном варианте в каждом соединении правым аргументом является исходная таблица. Этот порядок соединения имеет следующие преимущества:

· число переборов вариантов соединений меньше, чем для кустового дерева (для левостороннего дерева оно равно n!, где n – число соединяемых таблиц);

· для этого типа дерева достаточно просто организовать каналы обработки.

Канал обработки – это возможность передачи результатов выполнения одной операции на вход другой операции через оперативную память (без промежуточного запоминания на диске).

Рассмотрим операции соединений 1 и 2 на рис. 1.9: (R S) T. Схема выполнения этих операций показана на рис. 1.10.

Рис. 1.10. Организация каналов обработки.

В канале только левый аргумент может быть опорным (т.е. храниться в оперативной памяти). Правый аргумент соединения называется тестируемым и может располагаться на диске. Если таблица подзапроса R и результат соединения (см. рис. 1.10) умещаются в оперативной памяти, то использование каналов позволяет организовать однопроходной алгоритм соединения таблиц (исходные таблицы R₁, S₁, T₁ читаются с диска один раз).

Можно отметить следующий недостаток рассмотренного порядка соединения таблиц: выбирается квазиоптимальный план, так как перебирается ограниченное число вариантов (n!), поскольку правый аргумент – это всегда исходная таблица.

Поиск по сайту: