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

Деревья соединений

При соединении двух отношений следует определить порядок их перечисления в тексте оператора. Существует соглашение: в качестве левого аргумента выбирается отношение с меньшим прогнозируемым размером.

Ранее рассмотренные алгоритмы (однопроходные, циклические, на основе индексирования) демонстрируют более высокие показатели производительности в случае, если меньшее по размеру отношение является левым аргументом оператора соединения. Однопроходной алгоритм и соединение методом вложенных циклов трактуют меньший операнд как опорное отношение, просматриваемое во внешнем цикле. Соединение на основе индексирования имеет смысл выбирать только тогда, когда одно из отношений достаточно мало, а другое снабжено индексом для общих атрибутов.

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

Если соединению подлежат два отношения, имеются всего две альтернативы, связанные с тем, какой из операторов должен быть размещён слева. Если же количество отношений, подлежащих соединению, более двух, то количество вариантов соединения резко возрастает.

Например, для отношений R, S, T и U, сохраняя порядок следования, можно выделить:

- линейное левостороннее соединение (((R S) T) U);

- линейное правостороннее соединение (R (S (T U)));

- кустовое соединение ((R S) (T U)).

Для кустового соединения в этом случае возможны ещё два других способа группировки: ((R (S T)) U) и (R ((S T) U)).

Поскольку порядок перечисления операндов, как мы уже отметили, имеет немаловажное значение, каждому из пяти деревьев в данном случае соответствует 4!=24 (количество перестановок из n элементов) вариантов соединения.

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

Бинарное дерево называется левосторонним, если все его правые дочерние вершины являются листьями.

Бинарное дерево называется правосторонним, если все его левые дочерние вершины являются листьями.

Кустовое соединение образуется ветвящимися бинарными деревьями (сбалансированными или несбалансированными).

Мы ограничим наше внимание рассмотрением только таких вариантов группировки операндов, которые описываются левосторонними деревьями, по следующим причинам:

1) количество возможных левосторонних деревьев с заданным числом вершин и свободным порядком их именования, относительно велико, но оно несоизмеримо мало в сравнении с количеством всех возможных вариантов деревьев, что позволяет сузить существенным образом пространство поиска;

2) модель левосторонних деревьев адекватна требованиям общеупотребительных алгоритмов соединения (однопроходных и соединения вложенным циклом), их эффективность повышается, если порядок группировки операндов описывается левосторонним деревом соединения.

Листья в лево- и правостороннем дереве соединения могут быть промежуточными вершинами, представляющие операторы, отличные от оператора соединения.

Например, можно рассматривать как левостороннее дерево с одним оператором соединения.

Считается, что с увеличением числа аргументов n-арного оператора соединения количество левосторонних деревьев возрастает гораздо медленнее, нежели количество всех возможных деревьев соединения. Для n отношений существует только одна топологическая форма левостороннего дерева, представляющая семейство из n! деревьев, соответствующих различным способам связывания вершин с отношениями, что справедливо и для правосторонних деревьев.

Количество топологических фор деревьев соединения n отношений подчиняется следующему рекурентному соотношению:

Поясним второе соотношение: количество листьев i в левом поддереве относительно корневой вершины может быть от 1 до n-1 . Эти листья допускают размещение любым из способов, реализующих формы деревьев с i листьями. Оставшиеся (n-i) листьев правого поддерева можно упорядочить одним из T(n-i) способов.

Вычислим несколько первых значений этого рекурентного соотношения:

Общее количество поддеревьев с учётом перемещения отношений внутри выражения соединения составит .

Например, для нашего случая всего деревьев будет , из них левосторонних, ещё – правосторонних, остальные – ветвящиеся деревья. Как видно, левосторонних деревьев существенно меньше.

Рассмотрим второй из упомянутых доводов в пользу применения левосторонних деревьев соединения, декларирующий их способность к формированию оптимальных планов запросов. Отметим также сопутствующие эффекты:

1) если однопроходной алгоритм соединения применяется к опорному отношению, расположенному слева в дереве соединения, объём памяти в каждый момент времени, как правило, меньше, чем при применении правостороннего или ветвящегося дерева соединения;

2) при соединении методом вложенных циклов, когда в цикле обрабатывается дерево левого отношения-операнда, удаётся избежать необходимости многократного конструирования промежуточного отношения.

Например,

Пусть (((R S) T) U) – левостороннее дерево соединения, R – опорное отношение, тогда

1. Для вычисления (R S) кортежи R загружаются в буферы оперативной памяти и сохраняются до завершения операции, (R S) тоже держится в оперативной памяти. Общее число буферов для этой части вычислений B(R)+B(R S).

2. Для соединения (R S) T) , буферы для хранения R уже не нужны и могут быть использованы повторно для хранения части результата (R S) T).

3. Для соединения (((R S) T) U) отпадает потребность в буферах, содержащих промежуточные данные (R S) и они могут использоваться для хранения блоков итогового отношения.

Таким образом, однопроходной алгоритм соединения, применяемый к выражению, которому соответствует левостороннее дерево, требует пространства оперативной памяти достаточного для единовременного хранения не более двух промежуточных отношений.

Теперь рассмотрим правостороннее соединение (R (S (T U))). В этом случае порядок действий будет следующим:

1. В оперативную память загружается отношение R, т.к. в качестве опорного всегда выбирается левый аргумент.

2. Формируется в качестве тестируемого (S (T U). Для этого загружается в оперативную память S.

3. Формируется в качестве тестируемого (T U). Для этого загружается в оперативную память T.

Таким образом, в буферах оперативной памяти должны находиться кортежи R, S и T, т.е. правостороннее соединение требует для дерева с n листьями нахождения в памяти блоков данных n-1 отношения-операнда.