Кафедра ИУ5 МГТУ им. Н.Э.Баумана, студенческое сообщество - Вклад [ru]

ТОРА (9) - Лекция №9 - Оптимизация запросов

2013-01-20T19:41:46Z

89.178.214.74: /* Оптимизация формул реляционной алгебры */

Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

Запрос, поступающий в СУБД, подвергается оптимизации с целью уменьшения времени его выполнения.

Шаги оптимизатора:
# строится логический план выполнения запроса (дерево логических операций);
# на основе логического плана строится физический план выполнения запроса (дерево физических операций);
# реализация этого физического плана.

=== Законы реляционной алгебры ===

==== Закон коммутативности декартова произведения отношений ====

{{Формула|f=R_1\times R_2 = R_2\times R_1}}, здесь и далее {{Формула|f=R_1}} и {{Формула|f=R_2}} - экземпляры отношений.

==== Закон ассоциативности декартова произведения ====

{{Формула|f=(R_1\times R_2)\times R_3 = R_1\times (R_2\times R_3)}}

==== Закон каскада проекций ====

Допустим, {{Формула|f=(a_1 ... a_n)\subseteq (b_1 ... b_n)}}, {{Формула|f={a_i} }}, {{Формула|f={b_i} }} - это атрибуты отношения {{Формула|f=R}}

тогда {{Формула|f=\Pi_{a_1 ... a_n}(\Pi_{b_1 ... b_n}(R)) = \Pi_{a_1 ... a_n}(R)}}

==== Закон каскада селекций ====

Допустим, {{Формула|f=F = f_1\wedge f_2}}

тогда {{Формула|f=\sigma_F(R) = \sigma_{f_1}(\sigma_{f_2}(R))}}

==== Закон перестановки проекции и селекции ====

1)

: Допустим, в условия поиска {{Формула|f=F}} входят атрибуты только из множества {{Формула|f=a_1 ... a_n}}
: тогда {{Формула|f=\Pi_{a_1 ... a_n}(\sigma_F(R)) = \sigma_F(\Pi_{a_1 ... a_n}(R))}}

2)

: Допустим, в условия поиска {{Формула|f=F}} входят атрибуты не только из множества {{Формула|f=a_1 ... a_n}}, но и из {{Формула|f=b_1 ... b_n}}
: тогда {{Формула|f=\Pi_{a_1 ... a_n}(\sigma_F(R)) = \Pi_{a_1 ... a_n}(\sigma_F(\Pi_{a_1 ... a_n, b_1 ... b_n}(R)))}}

==== Селекция декартова произведения ====

Отношение {{Формула|f=f_1}} содержит атрибуты только из отношения {{Формула|f=R_1}}

тогда {{Формула|f=\sigma_{f_1}(R_1\times R_2) = \sigma_{f_1}(R_1)\times R_2}}

:Следствие:
:пусть {{Формула|f=F = f_1 \wedge f_2}} и в {{Формула|f=f_1}} входят атрибуты {{Формула|f=R_1}}, а в {{Формула|f=f_2}} входят из {{Формула|f=R_2}},
:тогда {{Формула|f=\sigma_{F}(R_1\times R_2) = \sigma_{f_1}(R_1)\times \sigma_{f_2}(R_2)}}
::Доказательство:
::{{Формула|f=\sigma_{f_1 \wedge f_2}(R_1\times R_2) = \sigma_{f_1}(\sigma_{f_2}(R_1\times R_2)) = \sigma_{f_1}(\sigma_{f_2}(R_2\times R_1))=}}
::{{Формула|f== \sigma_{f_1}(R_1\times\sigma_{f_2}(R_2)) = \sigma_{f_1}(R_1)\times \sigma_{f_2}(R_2)}}

==== Закон перестановки селекции и объединения ====

{{Формула|f=\sigma_{F}(R_1\bigcup R_2) = \sigma_{F}(R_1)\bigcup\sigma_{F}(R_2)}}

==== Закон перестановки селекции и разности отношений ====

{{Формула|f=\sigma_{F}(R_1 - R_2) = \sigma_{F}(R_1) - \sigma_{F}(R_2)}}

==== Закон перестановки проекции и декартова произведения ====

{{Формула|f=b_1 ... b_n}} - это атрибуты отношения {{Формула|f=R_1}}

{{Формула|f=c_1 ... c_k}} - это атрибуты отношения {{Формула|f=R_2}}

{{Формула|f=\Pi_{b_1 ... b_n, c_1 ... c_k}(R_1\times R_2)}} = {{Формула|f=\Pi_{b_1 ... b_n}(R_1)\times \Pi_{c_1 ... c_k}(R_2)}}

==== Закон перестановки проекции и объединения ====

{{Формула|f=\Pi_{a_1 ... a_n}(R_1\bigcup R_2) = \Pi_{a_1 ... a_n}(R_1)\bigcup\Pi_{a_1 ... a_n}(R_2)}}

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

Пусть условие {{Формула|f=F = f_1 \wedge ... \wedge f_n}}

Правила:
# переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8;
# переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10;
# по возможности скомбинировать каждый каскад селекции в одиночную селекцию и каждый каскад проекции в одиночную проекцию. Тогда всё можно будет сделать за один проход.

После выполнения этих трёх правил выражение {{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}} преобразуется к виду:

{{Формула|f=\Pi_A(\sigma_F(}}{{Формула|f=\Pi_{A_1}(\sigma_{f_1}(R_1))}}{{Формула|f=\times ...\times}}{{Формула|f=\Pi_{A_n}(\sigma_{f_n}(R_n))}}{{Формула|f=))}},

здесь {{Формула|f=\Pi_{A_i}(\sigma_{f_i}(R_i))}} - ''подзапросы''. Суть в том, что сначала выполняются подзапросы, а они имеют намного меньшую размерность, чем исходная таблица, и время выполнения будет меньше, чем по исходной формуле {{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}}.

=== Логический план ===

==== Построение логического плана ====

Порядок построения:
# запрос преобразуется в формулу реляционной алгебры;
# выполняется преобразование (оптимизация) этой формулы.

Оператор <code>SELECT</code> (без агрегирования, группирования и удаления дубликатов) может быть представлен так:

{{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}}, где
:от {{Формула|f=R_1}} до {{Формула|f=R_n}} - это декартово произведение отношений (таблиц), указанных за ключевым словом <code>FROM</code>;
:{{Формула|f=\sigma_F}} - это селекция кортежей декартова произведения в соответствии с условием, указанным за ключевым словом <code>WHERE</code>;
:{{Формула|f=\Pi_A}} - это проекция селекции на множество атрибутов A, указанных за ключевым словом <code>SELECT</code>

В чём суть такой логической оптимизации? Сначала надо выполнить декартово произведение, потом селекцию, потом проекцию - всё по порядку скобок в этом выражении. Потому что если таблица имеет большой размер, то это выражение будет выполняться очень долго.

Пример: найти фамилии поставщиков, поставляющих детали с названием "винт".

{{Формула|f=\rho = (S, P, SP)}}

<syntaxhighlight lang="sql">
SELECT фамилия
FROM S, P, SP
WHERE P.название = 'винт' AND
S.номер_поставки = SP.номер_поставки AND
SP.номер_детали = P.номер_детали;
</syntaxhighlight>

{{Формула|f=\Pi_{фамилия}(\sigma_{P.н="винт" \wedge S.н-п=SP.н-п \wedge SP.н-д=P.н-д}(S\times P\times SP))}}

[[#Оптимизация формул реляционной алгебры | Полученную]] {{Формула|f=\Pi_A(\sigma_F(\Pi_{A_i}(\sigma_{f_2}(R_1))\times ...\times \Pi_{A_n}(\sigma_{f_n}(R_n))))}} можно представить в графическом виде - это и будет ''логический план выполнения запроса'':

[[Файл:9sTORAl9pic1.png|400px]]

Получается, подзапросы можно выполнять параллельно, а это тоже уменьшает время выполнения всего запроса.

Пример:

[[Файл:9sTORAl9pic2.png|link=Файл:9sTORAl9pic2.svg]]

Запрос найти значение остатков больше 1500 на счетах пользователя с кодом 3:

<syntaxhighlight lang="sql">
SELECT остаток
FROM R2
WHERE остаток > 1500 AND
номер_счёта IN(
SELECT номер_счёта
FROM R1
WHERE код_пользователя = 3
);
</syntaxhighlight>

Этот запрос преобразуется сервером в неявном виде в формулу реляционной алгебры:

{{Формула|f=\Pi_{остаток}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3 \wedge R_1.н-c=R_2.н-с})}}

Теперь оптимизируем:

{{Формула|f==^4\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3}(R_1\times R_2)))=^6}}

{{Формула|f==\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\sigma_{R_1.к-п=3}(R_1)\times\sigma_{R_2.о>1500}(R_2)=^{5, 2} }}

{{Формула|f==\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\Pi_{остаток, R_1.н-с, R_2.н-с}(\sigma_{R_1.к-п=3}(R_1)\times\sigma_{R_2.о>1500}(R_2))=^9}}

{{Формула|f==\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(}}{{Формула|f=\Pi_{R_1.н-с}(\sigma_{R_1.к-п=3}(R_1))}}{{Формула|f=\times}}{{Формула|f=\Pi_{R_2.н-с, остаток}(\sigma_{R_2.о>1500}(R_2))}}{{Формула|f=))}}

Полученное выражение - результат оптимизации. Можно построить логический план выполнения запроса.

[[Файл:9sTORAl9pic3.png|400px]]

{{Forward|l=ТОРА (9) - Лекция №10 - Логический и физический план запроса}}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №9 - Оптимизация запросов

2013-01-20T19:40:04Z

89.178.214.74: /* Оптимизация формул реляционной алгебры */

Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

Запрос, поступающий в СУБД, подвергается оптимизации с целью уменьшения времени его выполнения.

Шаги оптимизатора:
# строится логический план выполнения запроса (дерево логических операций);
# на основе логического плана строится физический план выполнения запроса (дерево физических операций);
# реализация этого физического плана.

=== Законы реляционной алгебры ===

==== Закон коммутативности декартова произведения отношений ====

{{Формула|f=R_1\times R_2 = R_2\times R_1}}, здесь и далее {{Формула|f=R_1}} и {{Формула|f=R_2}} - экземпляры отношений.

==== Закон ассоциативности декартова произведения ====

{{Формула|f=(R_1\times R_2)\times R_3 = R_1\times (R_2\times R_3)}}

==== Закон каскада проекций ====

Допустим, {{Формула|f=(a_1 ... a_n)\subseteq (b_1 ... b_n)}}, {{Формула|f={a_i} }}, {{Формула|f={b_i} }} - это атрибуты отношения {{Формула|f=R}}

тогда {{Формула|f=\Pi_{a_1 ... a_n}(\Pi_{b_1 ... b_n}(R)) = \Pi_{a_1 ... a_n}(R)}}

==== Закон каскада селекций ====

Допустим, {{Формула|f=F = f_1\wedge f_2}}

тогда {{Формула|f=\sigma_F(R) = \sigma_{f_1}(\sigma_{f_2}(R))}}

==== Закон перестановки проекции и селекции ====

1)

: Допустим, в условия поиска {{Формула|f=F}} входят атрибуты только из множества {{Формула|f=a_1 ... a_n}}
: тогда {{Формула|f=\Pi_{a_1 ... a_n}(\sigma_F(R)) = \sigma_F(\Pi_{a_1 ... a_n}(R))}}

2)

: Допустим, в условия поиска {{Формула|f=F}} входят атрибуты не только из множества {{Формула|f=a_1 ... a_n}}, но и из {{Формула|f=b_1 ... b_n}}
: тогда {{Формула|f=\Pi_{a_1 ... a_n}(\sigma_F(R)) = \Pi_{a_1 ... a_n}(\sigma_F(\Pi_{a_1 ... a_n, b_1 ... b_n}(R)))}}

==== Селекция декартова произведения ====

Отношение {{Формула|f=f_1}} содержит атрибуты только из отношения {{Формула|f=R_1}}

тогда {{Формула|f=\sigma_{f_1}(R_1\times R_2) = \sigma_{f_1}(R_1)\times R_2}}

:Следствие:
:пусть {{Формула|f=F = f_1 \wedge f_2}} и в {{Формула|f=f_1}} входят атрибуты {{Формула|f=R_1}}, а в {{Формула|f=f_2}} входят из {{Формула|f=R_2}},
:тогда {{Формула|f=\sigma_{F}(R_1\times R_2) = \sigma_{f_1}(R_1)\times \sigma_{f_2}(R_2)}}
::Доказательство:
::{{Формула|f=\sigma_{f_1 \wedge f_2}(R_1\times R_2) = \sigma_{f_1}(\sigma_{f_2}(R_1\times R_2)) = \sigma_{f_1}(\sigma_{f_2}(R_2\times R_1))=}}
::{{Формула|f== \sigma_{f_1}(R_1\times\sigma_{f_2}(R_2)) = \sigma_{f_1}(R_1)\times \sigma_{f_2}(R_2)}}

==== Закон перестановки селекции и объединения ====

{{Формула|f=\sigma_{F}(R_1\bigcup R_2) = \sigma_{F}(R_1)\bigcup\sigma_{F}(R_2)}}

==== Закон перестановки селекции и разности отношений ====

{{Формула|f=\sigma_{F}(R_1 - R_2) = \sigma_{F}(R_1) - \sigma_{F}(R_2)}}

==== Закон перестановки проекции и декартова произведения ====

{{Формула|f=b_1 ... b_n}} - это атрибуты отношения {{Формула|f=R_1}}

{{Формула|f=c_1 ... c_k}} - это атрибуты отношения {{Формула|f=R_2}}

{{Формула|f=\Pi_{b_1 ... b_n, c_1 ... c_k}(R_1\times R_2)}} = {{Формула|f=\Pi_{b_1 ... b_n}(R_1)\times \Pi_{c_1 ... c_k}(R_2)}}

==== Закон перестановки проекции и объединения ====

{{Формула|f=\Pi_{a_1 ... a_n}(R_1\bigcup R_2) = \Pi_{a_1 ... a_n}(R_1)\bigcup\Pi_{a_1 ... a_n}(R_2)}}

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

Пусть условие {{Формула|f=F = f_1 \wedge ... \wedge f_n}}

Правила:
# переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8;
# переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10;
# по возможности скомбинировать каждый каскад селекции в одиночную селекцию и каждый каскад проекции в одиночную проекцию. Тогда всё можно будет сделать за один проход.

После выполнения этих трёх правил выражение {{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}} преобразуется к виду:

{{Формула|f=\Pi_A(\sigma_F(}}{{Формула|f=\Pi_{A_1}(\sigma_{f_1}(R_1))}}{{Формула|f=\times ...\times}}{{Формула|f=\Pi_{A_n}(\sigma_{f_n}(R_n))}}{{Формула|f=))}},

здесь {{Формула|f=\Pi_{A_1}(\sigma_{f_1}(R_1))}}, {{Формула|f=\Pi_{A_n}(\sigma_{f_n}(R_n))}} и прочие - ''подзапросы''. Суть в том, что сначала выполняются подзапросы, а они имеют намного меньшую размерность, чем исходная таблица, и время выполнения будет меньше, чем по исходной формуле {{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}}.

=== Логический план ===

==== Построение логического плана ====

Порядок построения:
# запрос преобразуется в формулу реляционной алгебры;
# выполняется преобразование (оптимизация) этой формулы.

Оператор <code>SELECT</code> (без агрегирования, группирования и удаления дубликатов) может быть представлен так:

{{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}}, где
:от {{Формула|f=R_1}} до {{Формула|f=R_n}} - это декартово произведение отношений (таблиц), указанных за ключевым словом <code>FROM</code>;
:{{Формула|f=\sigma_F}} - это селекция кортежей декартова произведения в соответствии с условием, указанным за ключевым словом <code>WHERE</code>;
:{{Формула|f=\Pi_A}} - это проекция селекции на множество атрибутов A, указанных за ключевым словом <code>SELECT</code>

В чём суть такой логической оптимизации? Сначала надо выполнить декартово произведение, потом селекцию, потом проекцию - всё по порядку скобок в этом выражении. Потому что если таблица имеет большой размер, то это выражение будет выполняться очень долго.

Пример: найти фамилии поставщиков, поставляющих детали с названием "винт".

{{Формула|f=\rho = (S, P, SP)}}

<syntaxhighlight lang="sql">
SELECT фамилия
FROM S, P, SP
WHERE P.название = 'винт' AND
S.номер_поставки = SP.номер_поставки AND
SP.номер_детали = P.номер_детали;
</syntaxhighlight>

{{Формула|f=\Pi_{фамилия}(\sigma_{P.н="винт" \wedge S.н-п=SP.н-п \wedge SP.н-д=P.н-д}(S\times P\times SP))}}

[[#Оптимизация формул реляционной алгебры | Полученную]] {{Формула|f=\Pi_A(\sigma_F(\Pi_{A_i}(\sigma_{f_2}(R_1))\times ...\times \Pi_{A_n}(\sigma_{f_n}(R_n))))}} можно представить в графическом виде - это и будет ''логический план выполнения запроса'':

[[Файл:9sTORAl9pic1.png|400px]]

Получается, подзапросы можно выполнять параллельно, а это тоже уменьшает время выполнения всего запроса.

Пример:

[[Файл:9sTORAl9pic2.png|link=Файл:9sTORAl9pic2.svg]]

Запрос найти значение остатков больше 1500 на счетах пользователя с кодом 3:

<syntaxhighlight lang="sql">
SELECT остаток
FROM R2
WHERE остаток > 1500 AND
номер_счёта IN(
SELECT номер_счёта
FROM R1
WHERE код_пользователя = 3
);
</syntaxhighlight>

Этот запрос преобразуется сервером в неявном виде в формулу реляционной алгебры:

{{Формула|f=\Pi_{остаток}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3 \wedge R_1.н-c=R_2.н-с})}}

Теперь оптимизируем:

{{Формула|f==^4\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3}(R_1\times R_2)))=^6}}

{{Формула|f==\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\sigma_{R_1.к-п=3}(R_1)\times\sigma_{R_2.о>1500}(R_2)=^{5, 2} }}

{{Формула|f==\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\Pi_{остаток, R_1.н-с, R_2.н-с}(\sigma_{R_1.к-п=3}(R_1)\times\sigma_{R_2.о>1500}(R_2))=^9}}

{{Формула|f==\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(}}{{Формула|f=\Pi_{R_1.н-с}(\sigma_{R_1.к-п=3}(R_1))}}{{Формула|f=\times}}{{Формула|f=\Pi_{R_2.н-с, остаток}(\sigma_{R_2.о>1500}(R_2))}}{{Формула|f=))}}

Полученное выражение - результат оптимизации. Можно построить логический план выполнения запроса.

[[Файл:9sTORAl9pic3.png|400px]]

{{Forward|l=ТОРА (9) - Лекция №10 - Логический и физический план запроса}}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]

ТОРА (9) - Лекция №9 - Оптимизация запросов

2013-01-20T19:39:20Z

89.178.214.74: /* Оптимизация формул реляционной алгебры */

Оригинал всего раздела, посвящённого оптимизации SQL-запросов, от самого [[Григорьев Ю.А. | Григорьева]] можно загрузить [http://yadi.sk/d/VjjMs6ww1HH2D здесь].
__TOC__
== Оптимизация SQL-запросов ==

Запрос, поступающий в СУБД, подвергается оптимизации с целью уменьшения времени его выполнения.

Шаги оптимизатора:
# строится логический план выполнения запроса (дерево логических операций);
# на основе логического плана строится физический план выполнения запроса (дерево физических операций);
# реализация этого физического плана.

=== Законы реляционной алгебры ===

==== Закон коммутативности декартова произведения отношений ====

{{Формула|f=R_1\times R_2 = R_2\times R_1}}, здесь и далее {{Формула|f=R_1}} и {{Формула|f=R_2}} - экземпляры отношений.

==== Закон ассоциативности декартова произведения ====

{{Формула|f=(R_1\times R_2)\times R_3 = R_1\times (R_2\times R_3)}}

==== Закон каскада проекций ====

Допустим, {{Формула|f=(a_1 ... a_n)\subseteq (b_1 ... b_n)}}, {{Формула|f={a_i} }}, {{Формула|f={b_i} }} - это атрибуты отношения {{Формула|f=R}}

тогда {{Формула|f=\Pi_{a_1 ... a_n}(\Pi_{b_1 ... b_n}(R)) = \Pi_{a_1 ... a_n}(R)}}

==== Закон каскада селекций ====

Допустим, {{Формула|f=F = f_1\wedge f_2}}

тогда {{Формула|f=\sigma_F(R) = \sigma_{f_1}(\sigma_{f_2}(R))}}

==== Закон перестановки проекции и селекции ====

1)

: Допустим, в условия поиска {{Формула|f=F}} входят атрибуты только из множества {{Формула|f=a_1 ... a_n}}
: тогда {{Формула|f=\Pi_{a_1 ... a_n}(\sigma_F(R)) = \sigma_F(\Pi_{a_1 ... a_n}(R))}}

2)

: Допустим, в условия поиска {{Формула|f=F}} входят атрибуты не только из множества {{Формула|f=a_1 ... a_n}}, но и из {{Формула|f=b_1 ... b_n}}
: тогда {{Формула|f=\Pi_{a_1 ... a_n}(\sigma_F(R)) = \Pi_{a_1 ... a_n}(\sigma_F(\Pi_{a_1 ... a_n, b_1 ... b_n}(R)))}}

==== Селекция декартова произведения ====

Отношение {{Формула|f=f_1}} содержит атрибуты только из отношения {{Формула|f=R_1}}

тогда {{Формула|f=\sigma_{f_1}(R_1\times R_2) = \sigma_{f_1}(R_1)\times R_2}}

:Следствие:
:пусть {{Формула|f=F = f_1 \wedge f_2}} и в {{Формула|f=f_1}} входят атрибуты {{Формула|f=R_1}}, а в {{Формула|f=f_2}} входят из {{Формула|f=R_2}},
:тогда {{Формула|f=\sigma_{F}(R_1\times R_2) = \sigma_{f_1}(R_1)\times \sigma_{f_2}(R_2)}}
::Доказательство:
::{{Формула|f=\sigma_{f_1 \wedge f_2}(R_1\times R_2) = \sigma_{f_1}(\sigma_{f_2}(R_1\times R_2)) = \sigma_{f_1}(\sigma_{f_2}(R_2\times R_1))=}}
::{{Формула|f== \sigma_{f_1}(R_1\times\sigma_{f_2}(R_2)) = \sigma_{f_1}(R_1)\times \sigma_{f_2}(R_2)}}

==== Закон перестановки селекции и объединения ====

{{Формула|f=\sigma_{F}(R_1\bigcup R_2) = \sigma_{F}(R_1)\bigcup\sigma_{F}(R_2)}}

==== Закон перестановки селекции и разности отношений ====

{{Формула|f=\sigma_{F}(R_1 - R_2) = \sigma_{F}(R_1) - \sigma_{F}(R_2)}}

==== Закон перестановки проекции и декартова произведения ====

{{Формула|f=b_1 ... b_n}} - это атрибуты отношения {{Формула|f=R_1}}

{{Формула|f=c_1 ... c_k}} - это атрибуты отношения {{Формула|f=R_2}}

{{Формула|f=\Pi_{b_1 ... b_n, c_1 ... c_k}(R_1\times R_2)}} = {{Формула|f=\Pi_{b_1 ... b_n}(R_1)\times \Pi_{c_1 ... c_k}(R_2)}}

==== Закон перестановки проекции и объединения ====

{{Формула|f=\Pi_{a_1 ... a_n}(R_1\bigcup R_2) = \Pi_{a_1 ... a_n}(R_1)\bigcup\Pi_{a_1 ... a_n}(R_2)}}

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

Пусть условие {{Формула|f=F = f_1 \wedge ... \wedge f_n}}

Правила:
# переместить каждую селекцию внутрь декартова произведения, используя законы 1, 4, 6, 7, 8;
# переместить каждую проекцию внутрь декартова произведения, используя законы 1, 3, 5, 9, 10;
# по возможности скомбинировать каждый каскад селекции в одиночную селекцию и каждый каскад проекции в одиночную проекцию. Тогда всё можно будет сделать за один проход.

После выполнения этих трёх правил выражение {{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}} преобразуется к виду:

{{Формула|f=\Pi_A(\sigma_F(}}{{Формула|f=\Pi_{A_1}(\sigma_{f_1}(R_1))}}{{Формула|f=\times ...\times}}{{Формула|f=\Pi_{A_n}(\sigma_{f_n}(R_n))}}{{Формула|f=))}},

здесь {{Формула|f=\Pi_{A_i}(\sigma_{f_2}(R_1))}}, {{Формула|f=\Pi_{A_n}(\sigma_{f_n}(R_n))}} и прочие - ''подзапросы''. Суть в том, что сначала выполняются подзапросы, а они имеют намного меньшую размерность, чем исходная таблица, и время выполнения будет меньше, чем по исходной формуле {{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}}.

=== Логический план ===

==== Построение логического плана ====

Порядок построения:
# запрос преобразуется в формулу реляционной алгебры;
# выполняется преобразование (оптимизация) этой формулы.

Оператор <code>SELECT</code> (без агрегирования, группирования и удаления дубликатов) может быть представлен так:

{{Формула|f=\Pi_A(\sigma_F(R_1\times ...\times R_n))}}, где
:от {{Формула|f=R_1}} до {{Формула|f=R_n}} - это декартово произведение отношений (таблиц), указанных за ключевым словом <code>FROM</code>;
:{{Формула|f=\sigma_F}} - это селекция кортежей декартова произведения в соответствии с условием, указанным за ключевым словом <code>WHERE</code>;
:{{Формула|f=\Pi_A}} - это проекция селекции на множество атрибутов A, указанных за ключевым словом <code>SELECT</code>

В чём суть такой логической оптимизации? Сначала надо выполнить декартово произведение, потом селекцию, потом проекцию - всё по порядку скобок в этом выражении. Потому что если таблица имеет большой размер, то это выражение будет выполняться очень долго.

Пример: найти фамилии поставщиков, поставляющих детали с названием "винт".

{{Формула|f=\rho = (S, P, SP)}}

<syntaxhighlight lang="sql">
SELECT фамилия
FROM S, P, SP
WHERE P.название = 'винт' AND
S.номер_поставки = SP.номер_поставки AND
SP.номер_детали = P.номер_детали;
</syntaxhighlight>

{{Формула|f=\Pi_{фамилия}(\sigma_{P.н="винт" \wedge S.н-п=SP.н-п \wedge SP.н-д=P.н-д}(S\times P\times SP))}}

[[#Оптимизация формул реляционной алгебры | Полученную]] {{Формула|f=\Pi_A(\sigma_F(\Pi_{A_i}(\sigma_{f_2}(R_1))\times ...\times \Pi_{A_n}(\sigma_{f_n}(R_n))))}} можно представить в графическом виде - это и будет ''логический план выполнения запроса'':

[[Файл:9sTORAl9pic1.png|400px]]

Получается, подзапросы можно выполнять параллельно, а это тоже уменьшает время выполнения всего запроса.

Пример:

[[Файл:9sTORAl9pic2.png|link=Файл:9sTORAl9pic2.svg]]

Запрос найти значение остатков больше 1500 на счетах пользователя с кодом 3:

<syntaxhighlight lang="sql">
SELECT остаток
FROM R2
WHERE остаток > 1500 AND
номер_счёта IN(
SELECT номер_счёта
FROM R1
WHERE код_пользователя = 3
);
</syntaxhighlight>

Этот запрос преобразуется сервером в неявном виде в формулу реляционной алгебры:

{{Формула|f=\Pi_{остаток}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3 \wedge R_1.н-c=R_2.н-с})}}

Теперь оптимизируем:

{{Формула|f==^4\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\sigma_{R_2.о>1500 \wedge R_1.к-п=3}(R_1\times R_2)))=^6}}

{{Формула|f==\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\sigma_{R_1.к-п=3}(R_1)\times\sigma_{R_2.о>1500}(R_2)=^{5, 2} }}

{{Формула|f==\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(\Pi_{остаток, R_1.н-с, R_2.н-с}(\sigma_{R_1.к-п=3}(R_1)\times\sigma_{R_2.о>1500}(R_2))=^9}}

{{Формула|f==\Pi_{остаток}(\sigma_{R_1.н-c=R_2.н-с}(}}{{Формула|f=\Pi_{R_1.н-с}(\sigma_{R_1.к-п=3}(R_1))}}{{Формула|f=\times}}{{Формула|f=\Pi_{R_2.н-с, остаток}(\sigma_{R_2.о>1500}(R_2))}}{{Формула|f=))}}

Полученное выражение - результат оптимизации. Можно построить логический план выполнения запроса.

[[Файл:9sTORAl9pic3.png|400px]]

{{Forward|l=ТОРА (9) - Лекция №10 - Логический и физический план запроса}}

[[Категория:Теоретические основы реляционной алгебры (9 семестр)]]
[[Категория:Конспекты лекций и семинаров]]