зультатов выполнения, оптимизатор должен суметь оценить размер этих результатов и использовать полученные значения при вычислении формул стоимости. К сожалению, размеры промежуточных наборов данных сильно зависит от конкретных значений хранимых данных, поэтому точная оценка стоимости может оказаться достаточно сложной проблемой. В [17.3], [17.4] обсуждаются некоторые подходы к решению этой проблемы и приводятся ссылки на другие направления исследований.

17.4. Преобразование выражений

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

Конечно, читатель должен понимать, что в результате применения к какому-либо выражению одного правила преобразования может быть получено выражение, к которому применимо другое правило преобразования. Например, среди исходных запросов нечасто встречаются запросы, сформулированные с использованием двух последовательно выполняемых операций проекции (речь об этом пойдет ниже; см. второе правило из подраздела об операциях выборки и проекции). Однако при преобразовании запросов подобные выражения достаточно часто возникают как результат применения других правил преобразования. (В этом смысле очень важным случаем является обработка представлений. Например, рассмотрим запрос Выбрать все названия городов в представлении V , где представление V определено как проекция переменной-отношения поставщиков по атрибутам Sl и CITY.) Иначе говоря, начиная с исходного выражения, оптимизатор будет шаг за шагом применять различные правила преобразования до тех пор, пока не будет получено выражение, которое согласно встроенным в оптимизатор эвристическим правилам будет считаться оптимальным для рассматриваемого запроса.

Выборки и проекции

Начнем с правил преобразования, которые включают только операции выборки и проекции.

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

( А WHERE <выборка1> ) WHERE <вы6орка2>

эквивалентно выражению

А WHERE <выборка1> AND <выборка2>

2. В последовательности операций проекций для одного и того же отношения можно игнорировать все проекции, кроме последней. Таким образом, выражение

( А { <проекция1> } ) { <проекция2> }

эквивалентно выражению

А { <проекция2> }

Конечно, чтобы исходное выражение имело смысл, каждый атрибут, присутствующий в проекции <проекция2>, обязательно должен присутствовать и в проекции <проекция1>.

3. Операцию выборки из результата операции проекции можно преобразовать в операцию проекции для результата операции выборки. Например, выражение

{ А { <проекция> } ) WHERE <выборка>

эквивалентно выражению

( А WHERE <выборка> ) { <проекция> }

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

Распределительный закон

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

f(AOB)=f(A)Of(B)

Например, в обычной арифметике операция SQRT (извлечение квадратного корня) распределяется по операции умножения, так как для всех Аи В выполняется приведенное ниже тождество.

SQRT ( А * В ) SQRT { А ) * SQRT ( В )

Следовательно, выполняя преобразование выражений, оптимизатор арифметических выражений всегда может заменить одну часть этого равенства другой. В качестве обратного примера можно привести утверждение, что операция SQRT не распределяется по операции сложения, так как в большинстве случаев квадратный корень из суммы А + В не равен сумме квадратных корней из А и В.

в реляционной алгебре операция выборки распределяется по операциям объединения, пересечения и вычитания. Она также распределяется по операции соединения, но лишь тогда и только тогда, когда условие операции выборки состоит (в самом сложном случае) из двух отдельных условий, соединенных операцией AND - по одному условию выборки для каждого операнда операции соединения. Для примера, рассматриваемого в разделе 17.2, сформулированное выше условие соблюдено (условие выборки очень простое и относится лишь к одному из операндов), благодаря чему стало возможным применить распределительный закон для замены рассматриваемого в примере выражения его более эффективным эквивалентом. Благодаря этому закону операция выборки была выполнена раньше остальных операций. Предварительное выполнение операций выбор-

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

Ниже приведено несколько примеров более специфических случаев применения распределительного закона, на этот раз для операции проекции. Во-первых, операция проекции распределяется по операциям объединения и пересечения (но не по операции вычитания).

( А UNION В){С}=А{С) UNION В { С }

( А INTERSECT В){С)=А{С} INTERSECT В { С }

Здесь Aw В должны иметь одинаковые типы. Во-вторых, эта операция также распределяется по операции соединения, т.е. тождество

( А JOIN В){С} = [А{АС}) JOIN ( В { ВС } )

справедливо, но только в том случае, если:

множество АС является объединением общих атрибутов отношений А и В, плюс те атрибуты из множества С, которые имеются только в отношении А;

множество ВС является объединением общих атрибутов отношений А и В, плюс те атрибуты из множества С, которые имеются только в отношении В.

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

Коммутативность и ассоциативность

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

А О В = В О А

Например, в обычной арифметике операции умножения и сложения являются коммутативными, а операции деления и вычитания - нет. В реляционной алгебре коммутативными являются операции объединения, пересечения и соединения, а операции вычитания и деления таковыми не являются. Например, если запрос включает соединение двух отношений, А и В, то коммутативность означает, что безразлично, какое из отношений А и В выбрано в качестве внешнего или внутреннего . Следовательно, при вычислении данного объединения системе предоставлено право выбора в качестве внешнего , например, меньшего из двух отношений (см. раздел 17.7).

Перейдем к ассоциативности. Принято считать, что бинарная операция О является ассоциативной, если для всех А, В и С истинно следующее тождество.

АО(ВОС) = (АОВ)ОС

Например, в обычной арифметике произведение и сложение - ассоциативные операции, а деление и вычитание - нет. В реляционной алгебре ассоциативными являются операции объединения, пересечения и соединения, а операции вычитания и деления таковыми не являются. Так, например, если в запросе используется соединение трех от-