2. Оптимизация формулы реляционной алгебры

При оптимизации формулы используются следующие правила:

1. Если условие F является конъюнкцией нескольких условий ( ), то переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8.

2. Переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10.

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

В результате использования правил 1–3 формула реляционной алгебры (5.1), соответствующая исходному запросу, преобразуется в следующую формулу:

, (5.2)

Q₁

Q_n

…

где

– условие, сформулированное в исходном запросе SELECT;

f – условие соединения подзапросов {Q_i}.

Подчеркнутые в приведённой выше формуле отношения Q₁, …, Q_n имеют меньшую размерность, чем исходные отношения R₁, …, R_n , и потому запрос по формуле (5.2) выполняется быстрее, чем по формуле (5.1).

По формуле (5.2) можно построить логический план, представленный на Рис. 1 .1.

Рис. 1.1. Логический план выполнения запроса, соответствующий формуле (5.2)

3. Иллюстрация логической оптимизации

1. Выполнение запроса по формуле π _A(σ_F(R₁× R₂ × … × R_n)), до оптимизации, иллюстрируется рисунком (Рис. 1 .2).

Рис. 1.2. Выполнение запроса по формуле (5.1).

2. Выполнение запроса по формуле

, после оптимизации, иллюстрируется рисунком (Рис. 1 .3).

Рис. 1.3. Выполнение запроса после оптимизации по формуле (5.2).

В случае отсутствия оптимизации запроса вначале нужно определить декартово произведение исходных таблиц R₁, …, R_n , затем выполнить селекцию σ_F и взять проекцию π_A. Если таблицы R₁, …, R_n имеют большую размерность, то время выполнения запроса будет достаточно большим. Поэтому запрос по формуле (5.2) выполняется быстрее, так как отношения Q₁, …, Q_n имеют меньшую размерность, чем исходные отношения R₁, …, R_{n .}

Примечание. Если исходные таблицы R₁, …, R_n размещаются на разных серверах или на одном суперкомпьютере, то подзапросы Q₁, …, Q_n могут выполняться параллельно.

3. Пример построения логического плана

1. Оптимизация запроса

Предположим, что на сервер СУБД поступает запрос SELECT. На сервере хранятся две таблицы, участвующие в запросе (Рис. 1 .4).

Рис. 1.4. Исходные таблицы на сервере СУБД.

Предположим, что клиент, связанный с сервером СУБД, выдал следующий запрос: "Найти значения остатков, большие 1500, на счетах пользователя с кодом 3". Соответствующий запрос SELECT имеет следующий вид:

SELECT остаток

FROM R2

WHERE остаток > 1500 AND номер_счета IN

(SELECT номер_счета

FROM R1

WHERE код_пользователя = 3);

Этот оператор SELECT преобразуется в формулу реляционной алгебры (см. п. 1.2.1):

Эта формула подвергается оптимизации. Оптимизатор вначале строит логический план выполнения запроса, используя законы реляционной алгебры (см. пункты 1.1.2 и 1.2.2, номера законов показаны над равенствами):

Последняя формула – результат оптимизации, здесь подчёркнуты подзапросы. По этой формуле оптимизатор строит логический план выполнения запроса (Рис. 1 .5).

Рис. 1.5. Логический план выполнения запроса в графическом виде.