Приведение запросов со вложенными подзапросами к запросам с соединениями

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

Ниже Ri обозначает i-е отношение базы данных; Ck - k-е поле (столбец) отношения.

Предикаты, допустимые в запросах языка SQL, можно разбить на следующие четыре группы:

Простые предикаты. Это предикаты вида Ri.Ck op X, где X - константа или список констант, и op - оператор скалярного сравнения (=, !=, >, >=, <, <=) или оператор проверки вхождения во множество (IS IN, IS NOT IN).

Предикаты со вложенными подзапросами. Это предикаты вида Ri.Ck op Q, где Q - блок запроса, а op может быть таким же, как для простых предикатов. Предикат может также иметь вид Q op Ri.Ck. В этом случае оператор принадлежности ко множеству заменяется на CONTAINS или DOES NOT CONTAIN. Эти две формы симметричны. Достаточно рассматривать только одну.

Предикаты соединения. Это предикаты вида Ri.Ck op Rj.Cn, где Ri != Rj и op - оператор скалярного сравнения.

Предикаты деления. Это предикаты вида Qi op Qj, где Qi и Qj - блоки запросов, а op может быть оператором скалярного сравнения или оператором проверки вхождения в множество.

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

Каноническим представлением запроса на n отношениях называется запрос, содержащий n-1 предикат соединения и не содержащий предикатов со вложенными подзапросами. Фактически, каноническая форма - это алгебраическое представление запроса.

Ниже приводятся два примера канонических форм запросов с предикатами разного типа. Соответствующая техника существует и для других видов предикатов.

SELECT Ri.Ck FROM Ri WHERE Ri.Ch IS IN

SELECT Rj.Cm FROM Rj WHERE Ri.Cn = Rj.Cp

эквивалентно

SELECT Ri.Ck FROM Ri, Rj WHERE

Ri.Ch = Rj.Cm AND Ri.Cn = Rj.Cp

SELECT Ri.Ck FROM Ri WHERE Ri.Ch =

SELECT AVG (Rj.Cm) FROM Rj WHERE Rj.Cn = Ri.Cp

эквивалентно

SELECT Ri.Ck FROM Ri, Rt WHERE

Ri.Ch = Rt.Cm AND Ri.Cp = Rt.Cn

- Rt ( Cp, Cn ) = SELECT Rj.Cp, AVG (Rj.Cn) FROM Rj

GROUP BY Rj.Cp

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

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

Заметим, что в кратко описанном нами подходе имеются некоторые тонкие семантические некорректности. Известны исправленные методы, но они слишком сложны технически, чтобы рассматривать их на наших лекциях.

Содержание раздела