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

Идемпотентность

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

А О А = А

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

Вычисляемые скалярные выражения

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

А * В + А * С

можно трансформировать в выражение

А * ( В + С )

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

Следует отметить, что приведенный выше пример иллюстрирует несколько более общую форму распределительного закона. Выше было дано определение понятия рас-пределяемости по отношению к унарным операциям, распределяемым по бинарным операциям. Однако в данном случае обе операции, * и + , являются бинарны.ми. Говорят, что бинарная операция 5 распределяется по бинарной операции О, если для всех А, В и С истинно равенство

Ад(ВОС) = (АдВ)0(АдС)

(в приведенном выше арифметическом примере 5 представляет операцию * , а О - операцию + ).

Логические выражения

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

А > В AND В > 3

абсолютно эквивалентно выражению А > В AND В > 3 AND А > 3

и потому может быть преобразовано в это выражение.

Данная эквивалентность базируется на том основании, что операция > является транзитивной. Заметьте, что подобное преобразование весьма полезно, так как позволяет системе выполнить дополнительную операцию выборки (по А) до выполнения больше чем -соединения, заданного условием А > В. Повторим сказанное выше. Предварительное выполнение операций выборки чаще всего оправдывает себя, следовательно, будет полезной и способность системы логически выводить предварительные операции выборки (что и было реализовано в данном примере).

Замечание. Этот прием реализован в различных коммерческих продуктах, включая СУБД DB2 (в которой его называют транзитивным замыканием предикатов), а также СУБД INGRES.

Вот еще один пример. Вследствие того, что операция OR распределяется по операции AND, логическое выражение

А > В OR ( С = D AND Е < F )

можно преобразовать в выражение

(A>BORC = D)AND(A>BORE<F)

Этот пример демонстрирует другой общий закон: Любое условие может быть преобразовано в эквивалентное условие, называемое конъюнктивной нормальной формой (КНФ) . Выражение в КНФ в общем случае имеет следующий вид.

С1 AND С2 AND ... AND Cn

Здесь Cl, С2,Cn - это логические выражения (называемые конъюнктами), в которых не используется логическая операция AND. Преимущество КНФ состоит в том, что выражение в КНФ истинно только в том случае, если истинны все его конъюнкты. И наоборот, выражение в КНФ ложно, если ложь является результатом вычисления хотя бы одного конъюнкта. Так как логическая операция AND коммутативна (выражение А AND В эквивалентно выражению BAND А), оптимизатор может вычислять отдельные конъюнкты в любом порядке, в частности по возрастанию их сложности (начиная с самых простых). Как только будет найден конъюнкт, результатом вычисления которого является ложь, процесс вычисления выражения в КНФ можно будет прекратить. Более того, в системах с параллельной обработкой возможно параллельное вычисление каждого из конъюнктов [17.58]-[ 17.61]. Опять же, как только будет найден первый конъюнкт, результатом вычисления которого является значение ложь, процесс вычисления выражения в КНФ можно будет прекратить.

Из сказанного выше следует, что оптимизатор должен знать, как общие свойства, такие как распределенность, применяются не только к реляционным операциям, но и к операторам сравнения, например > , к логическим операторам, например AND и OR, к арифметическим операторам, например + , и т.п.

Семантические преобразования

Рассмотрим следующее выражение. ( SP JOIN S ) { PI }

Данное соединение относится к соединениям типа внешний ключ - соответствующий потенциальный ключ. В нем внешнему ключу в переменной-отношении SP ставится в соответствие потенциальный ключ в переменной-отношении S. Следовательно, каждый кортеж в переменной-отношении SP связан с определенным кортежем в переменной-отношении S. Таким образом, из каждого кортежа в переменной-отношении SP в общий результат поступает только значение атрибута Р. Другими словами, соединение можно вообще не выполнять! Рассматриваемое выражение можно заменить следующим выражением.

SP { Р }

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

Преобразование, которое является корректным только в силу конкретного установленного Офаничения целостности, называют семантическим преобразованием [17.27], а оптимизацию, достигаемую в результате подобных преобразований, - семантической оптимизацией. Семантическую оптимизацию можно определить как процесс преобразования одного запроса в другой, качественно отличный запрос, который, тем не менее, дает результат, идентичный результату исходного запроса, благодаря тому, что обрабатываемые данные удовлетворяют определенному офаничению целостности.

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

Определить всех поставщиков только красных детачей, которые (поставщики) находятся в там же городе, где хранится хотя бы одна поставляемая ими деташ

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

Определить всех поставщиков из Лондона, поставляющих только красные детали.

Замечание. Насколько известно автору, лишь немногие современные коммерческие продукты в должной мере используют идею семантической оптимизации. Однако, в принципе, семантическая оптимизация способна обеспечивать значительное улучшение производительности (весьма вероятно, намного превышающее то, которое в настоящее время может быть достигнуто с помощью любых традиционных приемов оптимизации). Более подробно идея семантической оптимизации изложена в [17.16], [17.28]-[ 17.30] и особенно - в [17.27].