Стадия 2. Выполнение операций UNION, EXCEPT, INTERSECT

     Если  в операторе SELECT присутствовали ключевые слова UNION, EXCEPT и INTERSECT, то таблицы, полученные в результате выполнения 1-й стадии, объединяются, вычитаются или пересекаются.

     Стадия 3. Упорядочение результата

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

     Как на самом деле выполняется оператор SELECT

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

     На  самом деле в РСУБД имеется  оптимизатор, функцией которого является нахождение такого оптимального алгоритма выполнения запроса, который гарантирует получение правильного результата.

     Схематично  работу оптимизатора можно представить  в виде последовательности нескольких шагов:

     Шаг 1 (Синтаксический анализ). Поступивший  запрос подвергается синтаксическому  анализу. На этом шаге определяется, правильно ли вообще (с точки зрения синтаксиса SQL) сформулирован запрос. В ходе синтаксического анализа вырабатывается некоторое внутренне представление запроса, используемое на последующих шагах.

     Шаг 2 (Преобразование в каноническую форму). Запрос во внутреннем представлении подвергается преобразованию в некоторую каноническую форму. При преобразовании к канонической форме используются как синтаксические, так и семантические преобразования. Синтаксические преобразования (например, приведения логических выражений к конъюнктивной или дизъюнктивной нормальной форме, замена выражений "x AND NOT x" на "FALSE", и т.п.) позволяют получить новое внутренне представление запроса, синтаксически эквивалентное исходному, но стандартное в некотором смысле. Семантические преобразования используют дополнительные знания, которыми владеет система, например, ограничения целостности. В результате семантических преобразований получается запрос, синтаксически не эквивалентный исходному, но дающий тот же самый результат.

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

     Шаг 4. (Выполнение плана запроса). На этом шаге план, выбранный на предыдущем шаге, передается на реальное выполнение.

     Во  многом качество конкретной СУБД определяется качеством ее оптимизатора. Хороший  оптимизатор может повысить скорость выполнения запроса на несколько порядков. Качество оптимизатора определяется тем, какие методы преобразований он может использовать, какой статистической и иной информацией о таблицах он располагает, какие методы для оценки стоимости выполнения плана он знает.

     Реализация реляционной алгебры средствами оператора SELECT (Реляционная полнота SQL)

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

     Оператор декартового  произведения

     Реляционная алгебра:

     Оператор SQL:

     SELECT A.Поле1, A.Поле2, …, B.Поле1, B.Поле2, …

     FROM A, B;

     или

     SELECT A.Поле1, A.Поле2, …, B.Поле1, B.Поле2, …

     FROM A CROSS JOIN B;

     Оператор проекции

     Реляционная алгебра:

     Оператор SQL:

     SELECT DISTINCT X, Y, …, Z

     FROM A;

     Оператор выборки

     Реляционная алгебра: ,

     Оператор SQL:

     SELECT *

     FROM A

     WHERE c;

     Оператор объединения

     Реляционная алгебра:

     Оператор SQL:

     SELECT *

     FROM A

     UNION

     SELECT *

     FROM B;

     Оператор вычитания

     Реляционная алгебра:

     Оператор SQL:

     SELECT *

     FROM A

     EXCEPT

     SELECT *

     FROM B

     Реляционный оператор переименования RENAME выражается при помощи ключевого слова AS в списке отбираемых полей оператора SELECT. Таким образом, язык SQL является реляционно-полным.

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

     Оператор соединения

     Реляционная алгебра:

     Оператор SQL:

     SELECT A.Поле1, A.Поле2, …, B.Поле1, B.Поле2, …

     FROM A, B

     WHERE c;

     или

     SELECT A.Поле1, A.Поле2, …, B.Поле1, B.Поле2, …

     FROM A CROSS JOIN B

     WHERE c;

     Оператор пересечения

     Реляционная алгебра:

     Оператор SQL:

     SELECT *

     FROM A

     INTERSECT

     SELECT *

     FROM B;

     Оператор деления

     Реляционная алгебра:

     Оператор SQL:

     SELECT DISTINCT A.X

     FROM A

     WHERE NOT EXIST

     (SELECT *

     FROM B

     WHERE NOT EXIST

     (SELECT *

     FROM A A1

     WHERE

       A1.X = A.X AND

       A1.Y = B.Y));

     Пусть отношение A содержит данные о поставках  деталей, отношение B содержит список всех деталей, которые могут поставляться. Атрибут X является номером поставщика, атрибут Y является номером детали.

     Разделить отношение A на отношение B означает в  данном примере "отобрать номера поставщиков, которые поставляют все детали".

     Преобразуем текст выражения:

     "Отобрать  номера поставщиков, которые поставляют  все детали" эквивалентно

     "Отобрать  те номера поставщиков из таблицы  A, для которых не существует непоставляемых деталей в таблице B" эквивалентно

     "Отобрать те номера поставщиков из таблицы A, для которых не существует тех номеров деталей из таблицы B, которые не поставляются этим поставщиком" эквивалентно

     "Отобрать  те номера поставщиков из таблицы  A, для которых не существует  тех номеров деталей из таблицы  B, для которых не существует записей о поставках в таблице A для этого поставщика и этой детали".

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

 

      Заключение

 

     Фактически  стандартным языком доступа к  базам данных в настоящее время  стал язык SQL (Structured Query Language).

     Язык SQL оперирует терминами, несколько отличающимися от терминов реляционной теории, например, вместо "отношений" используются "таблицы", вместо "кортежей" - "строки", вместо "атрибутов" - "колонки" или "столбцы".

     Стандарт  языка SQL, хотя и основан на реляционной  теории, но во многих местах отходит он нее.

     Основу  языка SQL составляют операторы, условно  разбитые не несколько групп по выполняемым функциям:

     Операторы DDL (Data Definition Language) - операторы определения  объектов базы данных.

     Операторы DML (Data Manipulation Language) - операторы манипулирования данными.

     Операторы защиты и управления данными, и др.

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

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

 

      Глоссарий