Реструктуризация запроса

На последней стадии запрос преобразуется таким образом, чтобы обеспечить наиболее эффективное его выполнение.

Опираясь не правила преобразования операций, оптимизатор получает возможность преобразовать некоторое выражение реляционной алгебры к некоторому эквивалентному ему выражению, обработка которого будет заведомо более эффективной. Данные правила будем использовать для реструктуризации дерева реляционной алгебры, построенного в процессе декомпозиции запроса. Для представления формул этих правил воспользуемся тремя отношениями R, S и T, причем в отношении R определен набор атрибутов , а в отношении S – набор атрибутов . Обозначения p, q и t будут использоваться для обозначения предикатов, а обозначения - для представления выборки атрибутов.

1.Операция выборки с конъюнктивным предикатом может быть преобразована в последовательность операций выборки по элементам конъюнкции и наоборот.

.

Этот метод преобразования называют каскадной выборкой. Например:

.

2.Правило коммутативности операции выборки.

.

Например:

.

3.В последовательности операций проекций необходима только последняя из этих операций.

.

Например:

.

4.Правила коммутативности операций выборки и проекции.

Если предикат p включает только атрибуты, входящие в список проекции, то операции выборки и проекции будут обладать свойством коммутативности.

, где .

Например:

.

5.Правило коммутативности операции q - соединения и декартового произведения.

.

Операции соединения по эквивалентности и натурального соединения можно считать особыми случаями операции q - соединения, поэтому приведенное правило справедливо и для этих двух операций. Например:

.

Здесь следует отметить, что эти правила справедливы, если не учитывается порядок столбцов.

6.Правило коммутативности операций выборки и q-соединения или декартового произведения.

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

.

В альтернативном случае, когда предикат операции выборки представляет собой конъюнкцию предикатов вида pÙq, где предикат p включает только атрибуты отношения R, а предикат q включает атрибуты только отношения S, операции выборки и q-соединения будут обладать следующим вариантом коммутативности:

.

Например:

.

7.Правило коммутативности операций проекции и q - соединения или декартового произведения.

Если список атрибутов операции проекции имеет вид , где в первый подсписок входят атрибуты только отношения R, а во второй атрибуты – только отношения S, то в том случае, когда условие соединения содержит только атрибуты из L, операция проекции и q - соединения будут обладать следующим вариантом свойства коммутативности:

.

Если условие соединения содержит дополнительные атрибуты, не входящие в отношение L, например, атрибуты , где первый список содержит только отношение R, а второй – только отношение S, то дополнительно придется выполнить выверяющую операцию проекции:

.

Например:

.

Вариант с использованием второго варианта правила:

.

8.Правило коммутативности операций объединения и пересечения, но не вычитания множеств.

RÈS=SÈR,

RÇS=SÇR.

9.Правило коммутативности операции выборки и операций над множествами (объединение, пересечение и вычитание).

.

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

.

11.Правило ассоциативности операции q - соединения (и декартового произведения).

Операции декартового произведения и естественного соединения всегда ассоциативны:

.

Если условие соединения q включает атрибуты только из отношений S и T, то операция q - соединения обладает следующим свойством ассоциативности:

.

12.Правило ассоциативности операции объединения и пересечения (но не операции разности множеств).

.

Определить студентов группы «АП-71», сдававших экзамен по «Базам данных» после 12.01.2003

Select Student.Nzach, Student.FIOS From Student, Predmet, Vedom Where Student.Sgroup = “АП-71” And Student.Sgroup = Vedom.Sgroup And Predmet.Predm = “ Базы данных” And Predmet.CodePredm = Vedom.CodePredm And Vedom.DateEkzam > #12.01.03

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

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

1. Применяем правило 1, позволяющее преобразовать операцию выборки по конъюнкции условий в последовательность операций выборки по отдельным условиям, входящим в конъюнкцию. Применяем правило 2 и 6, позволяющие переупорядочить последовательность операций выборки и декартового произведения.

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

.

Применим это правило во всех подходящих случаях.

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

4. Правила 4 и 7, позволяющие переместить операции проекции так, чтобы они выполнялись до операций соединения по эквивалентности, а также создать новые полезные операции проекции.

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

Таким образом, можно сформулировать правила для оптимизации запросов следующим образом:

1. Выполнение операций выборки на самых ранних этапах. Выполнение операций выборки сокращает кардинальность отношения и сокращает время последующих операций обработки запроса. Следовательно, целесообразно начинать оптимизацию с использования правила 1 для формирования каскадной последовательности операций выборки, после чего следует применять правила 2, 4, 6 и 9. Цель этих действий состоит в том, чтобы переместить операцию выборки в дереве как можно ниже. Дополнительно полезно сохранить вместе все предикаты, касающиеся одного и того же отношения.

2. Объединение в одну операцию соединения операции декартового произведения и следующей за ней операции выборки, предикат которой представляет условие соединения. Здесь необходимо воспользоваться формулой:

.

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

.

В этом случае можно воспользоваться правилами 11 и 12, задающими ассоциативные свойства операций тета – соединения (а также объединения и пересечения). Цель состоит в переупорядочивании операций таким образом, чтобы первым выполнялось соединение, в результате которого будет получено меньшее по размеру отношение. Это позволит выполнить второе соединение с меньшим по размеру исходным отношением.

4. Как можно более раннее выполнение операций проекции. Операция проекции уменьшает кардинальность отношения, что приводит к сокращению объемов данных, подлежащих дальнейшей обработке. Следовательно, целесообразно сначала использовать правило 3 для построения исходной последовательности проекций, после чего применять к ним правила 4, 5 и 10, задающие свойства коммутативности операций проекции с бинарными отношениями. Целью данной процедуры является перемещение операций проекции вниз по дереву (насколько это возможно). Дополнительно рекомендуется объединять операции проекции, выполняемые над одним отношением.

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