Законы алгебраических преобразований. Алгоритм Ульмана оптимизации реляционных выражений

ЗАКОНЫ АЛГЕБРАИЧЕСКИХ ПРЕОБРАЗОВАНИЙ.  
АЛГОРИТМ УЛЬМАНА ОПТИМИЗАЦИИ  
РЕЛЯЦИОННЫХ ВЫРАЖЕНИЙ.

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

Рассмотрим выражение R ´ S. При реализации этого запроса в основную память загружается максимальное количество блоков отношения R, оставляя пространство для одного блока S. Осуществляется конкатенация всех блоков R с блоком S. Такая стратегия уменьшает число необходимых загрузок каждого блока S с коэффициентом, равным числу записей R, которые могут поместиться в основной памяти.

Пусть:

1. Отношения R и S имеют соответственно m и n кортежей.
2. В одном блоке помещается a и b кортежей.
3. В основной памяти могут находиться c блоков.

Тогда число доступов составляет

 для чтения R и для S. Общее число доступов:

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

1. Законы коммутативности для соединения и произведения. Здесь и далее E_i – реляционное выражение, а F_j – условие, налагаемое на реляционное выражение.

2. Закон ассоциативности для соединений и произведения.

3. Каскад проекций

 если 

4. Каскад селекций

5. Перестановка селекций и проекций

В более общем случае если условие F вовлекает атрибуты В₁, …, В_m, которых нет среди А₁, …, А_n, то

6. Перестановка селекции с декартовым произведением

а) Если в формуле F₁ используются атрибуты Е₁.

б) Если в формуле F₁ используются атрибуты Е₁, а в формуле F₂ – атрибуты Е₂.

в) Если в формуле F₁ используются атрибуты Е₁, а в формуле F₂ – атрибуты Е₁ и Е₂.

7. Перестановка селекции с объединением

Предполагается, что если имена атрибутов Е₁ отличны от имен Е₂, то формула F модифицируется в F₁ и F₂, в которых используются соответствующие имена.

8. Перестановка селекции с разностью

F модифицируется в F₁ и F₂ аналогично (7).

9. Перестановка проекции с декартовым произведением

10. Перестановка проекции с объединением.

Если имена атрибутов  Е₁ и Е₂ отличаются, то надо заменить их на А₁,…,А_n.

Используя законы алгебраических преобразований, Дж. Ульман предложил  следующий алгоритм оптимизации: исходное реляционное выражение представляется в виде бинарного дерева, узлы которого – двуместные операторы (´, È, –).

Шаг 1. Представить каждую селекцию σ_{F1 ^ … ^ Fn}(Е) в виде каскада σ_F1(…(σ_Fn(E))…) по правилу 4.

Шаг 2. Переместить каждую селекцию в дереве насколько это возможно вниз, используя законы 4-8.

Шаг 3. Переместить каждую проекцию в дереве вниз, насколько это возможно, используя законы 3, 5, 9, 10. При этом закон 3 приводит к исчезновению некоторых проекций, а закон 5 расщепляет проекцию на 2, одна из которых может перемещаться по дереву вниз. Проекция исключается, если она проецирует выражение на все атрибуты.

Шаг 4. Комбинировать каждый каскад проекций или селекций в одиночную проекцию или селекцию с последующей проекцией, используя законы 3-5.

Шаг 5. Разбиваем внутренние узлы полученного  в результате дерева на группы следующим  образом: каждый узел, представляющий двуместный оператор (´, È, –), принадлежит группе, которая образована из предков с операторами селекции или проекции и потомков данного узла с унарными операторами селекции или проекции, завершающимися в листьях. Исключением является случай, когда используется двуместный оператор ´ без последующей селекции, так как в этом случае селекция комбинируется с произведением, образуя Θ-соединение.