Главная » SQL, Базы данных » ПРЕОБРАЗОВАНИЕ ВЫРАЖЕНИЙ

0

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

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

Операции сокращения и проекции

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

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

(   A WHERE pi   )  WHERE  p2 эквивалентно следующему выражению: A  WHERE  pi   AND  p2

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

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

( А  {  ас11  }  )   {  ас12  } эквивалентно следующему выражению: А  {  ас12  }

Здесь ас11иас12 — разделенные запятыми списки имен атрибутов.

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

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

(   А   {   acl  }    )  WHERE  p эквивалентно следующему выражению: (  A WHERE  р  )    {   acl  }

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

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

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

f  (  A  O  B  )  ≡  f  (  A  )  O  f  (  B  )

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

SQRT   (  А  *  В  )   ≡  SQRT   (  А  )   *  SQRT   (  В  )

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

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

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

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

4 Определение термина "простое условие сокращения" приведено в подразделе "Операция ограни-чения" раздела

7.4 главы 7.

( A UNION В ) { acl } ≡ А { ac1 } UNION В { acl }

( A INTERSECT В ) { acl } ≡ А { acl } INTERSECT В { acl }

Здесь A и B должны иметь одинаковые типы.

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

( A JOIN В ) { acl } ( А { acl1 } ) JOIN ( В { ас12 } )

Здесь acll — объединение атрибутов соединения и тех атрибутов acl, которые присутствуют только в Л, а ас12 — объединение атрибутов соединения и тех атрибутов acl, которые присутствуют только в в.

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

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

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

А  О  В ≡ В  О  А

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

А   О   (   В   О   С   )    ≡    (   А   О   В   )   О   С

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

Идемпотентность и поглощение

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

А  О  А  ≡  А  ‘

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

Операции объединения и пересечения подчиняются также приведенным ниже полезным правилам поглощения.

A UNION ( A INTERSECT В ) ≡ А

A INTERSECT ( A UNION В ) ≡ А

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

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

А   *   В   +   А   *   С

можно преобразовать в следующее выражение:

А   *    (   В   +   С   )

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

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

A  6  (  B O C  )  ≡  (  A  6  B  )  O  (  A  5  C  )

(В приведенном выше арифметическом примере 5 можно рассматривать как "*", а о —

как"+".)

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

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

А  >   В  AND   В   >   3

безусловно, эквивалентно выражению

А   >   В   AND   В   >   3   AND   А   >   3

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

Данная эквивалентность основана на том, что операция ">" является  транзитивной.

Отметим, что подобное преобразование весьма полезно, поскольку позволяет  системе выполнить дополнительную операцию сокращения (по А) до выполнения операции по

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

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

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

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

можно преобразовать в следующее выражение:

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

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

Cl   AND   C2   AND   …   AND   Cn

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

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

Семантические преобразования Рассмотрим следующее выражение. (   SP   JOIN   S   )    {   Р#   }

Данное  соединение  относится  к  соединениям  типа  "внешний   ключ—соответствующий потенциальный ключ". В нем внешнему ключу в переменной отношения SP ставится в соответствие потенциальный ключ в  переменной отношения S. Поэтому каждый кортеж в переменной отношения SP соединяется с определенным кортежем в переменной отношения S. Таким образом, из каждого кортежа в переменной отношения SP в общий результат поступает значение атрибута р#. Другими словами, соединение

можно вообще не выполнять! Рассматриваемое выражение можно заменить следующим выражением.

SP   {   Р#   }

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

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

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

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

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

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

Примечание. Насколько известно автору, семантическая оптимизация в должной мере используется лишь в немногих современных коммерческих продуктах. Но, в  принципе, семантическая оптимизация способна обеспечивать значительное  повышение производительности (весьма вероятно, намного превышающее то, которое в настоящее время может быть достигнуто с помощью любых традиционных приемов оптимизации). Более подробно идея семантической оптимизации изложена в [18.13], [18.26]—[18.28] и особенно — в [18.25].

Заключительные замечания

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии