Введение в системы БД (542480), страница 166
Текст из файла (страница 166)
Для примера, рассматриваемого в разделе 17.2, сформулированное выше условие соблюдено (условие выборки очень простое и относится лишь к одному из операндов), благодаря чему стало возможным применить распределительный закон для замены рассматриваемого в примере выражения его более эффективным эквивалентом. Благодаря этому закону операция выборки была выполнена раньше остальных операций. Предварительное выполнение операций выбор- 648 Часть г'. Дополнительные аспекты ки почти всегда себя оправдывает, так как приводит к существенному уменьшению количества кортежей, обрабатываемых следующей операцией, а также, возможно, к уменьшению количества кортежей на выходе этой операции. Ниже приведено несколько примеров более специфических случаев применения распределительного закона„на этот раз для операции проекции.
Во-первых, операция проекции распределяется по операциям объединения и пересечения (но не по операции вычитания). ( А 0И10М В ] ( С ) =- А ( С ) ВЕ10В В ( С ) ( А 1ИТЕЕЯЕС1 В ) ( С ) ж А ( С ) 1ВТЕЕЯЕСТ В ( С ) Здесь А и В должны иметь одинаковые типы. Во-вторых, эта операция также распределяется по операции соединения, т.е. тождество ( А,Т01И В ) ( С ) ж ( А ( АС ) ),Т01й ( В ( ВС ) ) справедливо, но только в том случае, если: ° множество АС является объединением общих атрибутов отношений А и В, плюс те атрибуты из множества С, которые имеются только в отношении А; ° множество ВС является объединением общих атрибутов отношений А и В, плюс те атрибуты из множества С, которые имеются только в отношении В.
Эти законы можно использовать для организации предварительного выполнения операций проекций, что обычно себя оправдывает по тем же причинам, что и в случае операций выборки. Коммутативность и ассоциативность Законы комчутативности и ассоциативности являются двумя еще более важными и общими правилами преобразования. Говорят, что бинарная операция О является коммутативной тогда и только тогда, когда для всех А и В истинно следующее тождество.
А О В= — ВО А Например, в обычной арифметике операции умножения и сложения являются коммутативными, а операции деления и вычитания — нет. В реляционной алгебре коммутативными являются операции объединения, пересечения и соединения, а операции вычитания и деления таковыми не являются. Например, если запрос включает соединение двух отношений, А и В, то коммутативность означает, что безразлично, какое из отношений А и В выбрано в качестве "внешнего" или "внутреннего". Следовательно, при вычислении данного объединения системе предоставлено право выбора в качестве "внешнего", например, меньшего из двух отношений (см.
раздел 17.7). Перейдем к ассоциативности. Принято считать, что бинарная операция О является ассоциативной, если для всех А, В и С истинно следующее тождество. АО(ВОС)м(АОВ)ОС Например, в обычной арифметике произведение и сложение — ассоциативные операции, а деление и вычитание — нет. В реляционной алгебре ассоциативными являются операции объединения, пересечения и соединения, а операции вычитания и деления таковыми не являются. Так, например, если в запросе используется соединение трех от- Глава 17. Оптимизация 649 ношений, А, В и С, то из законов коммутативности и ассоциативности следует, что не имеет значения, в каком порядке будет выполняться соединение отношений.
Поэтому в процессе вычисления подобного соединения системе предоставляется право выбора наиболее эффективной последовательности из всех существующих. Идемпотентность Еще одним важным обшим правилом является закон пдечлогленглносгли. Бинарную операцию О называют идемпотентной тогда и только тогда, когда для любого А выполняется следующее тождество. Можно ожидать, что применение закона идемпотентности окажется полезным в процессе преобразования выражений. В реляционной алгебре операции объединения, пересечения и соединения являются идемпотентными, а операции деления и вычитания — нет.
Вычисляемые скалярные выражения Объектом применения законов трансформации являются не только реляционные выражения. Например, выше уже упоминалось, что некоторые законы трансформации применимы и к аряфчел~ическич выражениям. Вот конкретный пример. Вследствие того, что операция умножения "*" распределяется по операции сложения "+", выражение А * В+ А * С можно трансформировать в выражение А*(В+С) Оптимизатор реляционных выражений должен знать о возможности подобных преобразований, так как ему приходится иметь дело с вычисляемыми скалярными выражениями в контексте операций ЕХТЕЕВ и ЯВИНАЕГЕЕ.
Следует отметить, что приведенный выше пример иллюстрирует несколько более общую форму распределительного закона. Выше было дано определение понятия распределяемости по отношению к унарны ч операциям, распределяемым по бинарныч операциям. Однако в данном случае обе операции, "я" и "+", являются бинарлььчи.
Говорят, что бинарная операция б распределяется по бинарной операции О, если для всех А, 8 и С истинно равенство Аб(ВОС)=(АЬВ)О(АЕС] (в приведенном выше арифметическом примере б представляет операцию "*", а О— операцию "+"). Логические выражения Перейдем к обсуждению логические выражений (иначе называемых булевыми выражениями или условиями), результатами вычисления которых могут быть только значения исглика н ложь.
Предположим, что А и  — это атрибуты двух различных отношений, тогда условие (которое может быть частью запроса) А>ВАЕВВ>3 650 Часть )г дополнительные аспекты абсолютно эквивалентно выражению А > В АВ0 В > 3 АБО А > 3 и потому может быть преобразовано в это выражение. Данная эквивалентность базируется на том основании, что операция ">" является транзнтивной.
Заметьте, что подобное преобразование весьма полезно, так как позволяет системе выполнить дополнительную операцию выборки (по А) до выполнения "больше чем"-соединения, заданно~о условием А > В. Повторим сказанное выше. Предварительное выполнение операций выборки чаще всего оправдывает себя, следовательно, будет полезной и способность системы логически выводить предварительные операции выборки (что и было реализовано в данном примере). Заиечание. Этот прием реализован в различных коммерческих продуктах, включая СУБД ОВ2 (в которой его называют транзитивным замыканием предикатов), а также СУБД!ЖОКЕЯ.
Вот еще один пример. Вследствие того, что операция ОВ распределяется по операции АБО, логическое выражение А>ВОЕ ( С =ОАЮЕ<Е ) можно преобразовать в выражение ( А > В Ой С = 0 ) АЮ ( А > В ОВ Е < Е ) Этот пример демонстрирует другой общий закон: "Любое условие может быть преобразовано в эквивалентное условие, называемое конъюнктивной нормальной формой (КНФ)". Выражение в КНФ в общем случае имеет следующий вид. С1 АЮ С2 АБО ... АВО Сл Здесь С1, С2, ..., Сл — это логические выражения (называемые конъюнктамн), в которых не используется логическая операция АВО. Преимущество КНФ состоит в том, что выражение в КНФ истинно только в том случае, если истинны все его конъюнкты.
И наоборот, выражение в КНФ лалсио, если ложь является результатом вычисления хотя бы одного конъюнкта. Так как логическая операция АЮ коммугативна (выражение А АБО В эквивалентно выражению ВАЮ А), оптимизатор может вычислять отдельные конъюнкты в любом порядке, в частности по возрастанию их сложности (начиная с самых простых). Как только будет найден конъюнкт, результатом вычисления которого является ложь, процесс вычисления выражения в КНФ можно будет прекратить. Более того, в системах с параллельной обработкой возможно параллельное вычисление каждого из конъюнктов [175ВЯ17.61).
Опять же, как только будет найден первый конъюнкт, результатом вычисления которого является значение лолсь, процесс вычисления выражения в КНФ можно будет прекратить. Из сказанного выше следует, что оптимизатор должен знать, как общие свойства, такие как распределенность, применяются не только к реляционным операциям, но н к операторам сравнения, например ">", к логическим операторам, например АБО и ОВ, к арифметическим операторам, например "4-", и т.п.
Семантические преобразования Рассмотрим следующее выражение. (ВРВО1ЕВ) (Р1) Глава 17. Оптимизация 651 Данное соединение относится к соединениям типа внеигний ключ — соответствующий потенииальный ключ. В нем внешнему ключу в переменной-отношении БР ставится в соответствие потенциальный ключ в переменной-отношении Б. Следовательно, каждый кортеж в переменной-отношении БР связан с определенным кортежем в переменной-отношении Б. Таким образом, из каждого кортежа в переменной-отношении БР в общий результат поступает только значение атрибута Р$. Другими словами, соелинение можно вообще не выполнять! Рассматриваемое выражение можно заменить следующим выражением. БР 1 Р$ Тем не менее будьте внимательны — подобное преобразование применимо только в силу семантики (смысла) конкретной ситуации. В общем случае каждый операнд в операции соединения вносит в соединение кортежи, которые не имеют дополняющих их кортежей в других операндах и, следовательно, не попадающих в общий конечный результат.
Поэтому чаще всего преобразования подобного типа будут некорректны. Однако в рассматриваемом конкретном случае каждый кортеж в переменной-отношении БР обязательно имеет соответствующий ему кортеж в переменной-отношении Б согласно установленному ограничению целостности (фактически это ограничение ссылочной целостности), которое гласит, что каждая поставка деталей должна быть связана с определенным поставщиком. Следовательно, учитывая это замечание, можно утверждать, что в данном случае рассматриваемое преобразование вполне корректно. Преобразование, которое является корректным только в силу конкретного установленного ограничения целостности, называют семантическим преобразованием [17.27], а оптимизацию, достигаемую в результате подобных преобразований, — семантической оптимизацией.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
