Обзор статьи "Continuing our discussion of redundancy in SQL"

Уважаемые читатели!

Я надеюсь, что вы, так же как и я, получаете удовольствие от чтения произведений Криса Дейта. Мы предлагаем вашему вниманию пересказ второй части его заметки по поводу избыточностей языка SQL, опубликованной в июньском номере журнал Database Programming and Design. Краткое изложение первой части можно найти в этом же разделе нашего сервера.
Замечание по поводу терминологии: Дейт в этой заметке использует некоторый смешанный набор терминов. Он говорит об отношениях (relation), но при этом использует термины "строка" (row) и "столбец" (column). Для единообразия в своем изложении вместо термина "отношение" я использую термин "таблица".

С уважением, Сергей Кузнецов

DataBase Programming & Design OnLine, June 1998

Continuing our discussion of redundancy in SQL
Greevous Bodily Harm (Part 2 of 2)

C.J. Date
(http://www.dbpd.com/9806date.htm)

Кристофер Дейт является независимым автором, лектором, исследователем и консультантом, специализирующимся в области систем реляционных баз данных. Корресподенцию ему можно послать по почте по адресу: Database Programming & Design, 411 Borel Ave., Ste. 100, San Mateo, CA 94402.

Как и в первой части заметки, для примеров используется известная база данных "поставщики и детали":

S ( S#, SNAME, STATUS, CITY )
    PRIMARY KEY ( S# )

P ( P#, PNAME, COLOR, WEIGHT, CITY )
    PRIMARY KEY ( P# )

SP ( S#, P#, QTY )
     PRIMARY KEY ( S#, P# )
     FOREIGN KEY ( S#) REFERENCES S
     FOREIGN KEY ( P#) REFERENCES P

HAVING без GROUP BY (I)

Хорошо известным (и малопонятным) фактом является то, что запросы на языке SQL могут включать раздел HAVING без соответствующего раздела GROUP BY. Рассмотрим, например, следующий запрос:

Q8: Выдать общий объем поставок для всех деталей, если и только если минимальный объем поставки каждой детали больше 50. На языке SQL возможна следующая формулировка:

SELECT SUM(SP.QTY) AS TQY
FROM   SP
HAVING MIN(SP.QTY) > 50 ;

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

Пояснение: Поскольку раздел GROUP BY отсутствует, то раздел HAVING применяется к "сгруппированной" версии SP, содержащей ровно одну группу. Если условие раздела HAVING вычисляется в true для этой группы (а так оно и есть для базы данных наших примеров), то раздел SELECT возвращает требуемую сумму значений. Если же при вычислении условия HAVING было бы получено false, то группа была бы отвергнута и окончательный результат был бы пустым. (Более точно, результатом была бы таблица с одним столбцом, не содержащая ни одной строки.)

Можно ли сформулировать запрос без использования HAVING? Очевидная попытка (с использованием "преобразования Типа 2") дала бы следующий результат:

SELECT DISTINCT SUM(SP.QTY) AS TQY
FROM   SP
WHERE  (SELECT MIN(SP.QTY) FROM SP) > 50 ;

Но, к сожалению, эта формулировка не является логически эквивалентной предыдущей. Чтобы убедиться в этом, предположим, что минимальный объем поставки должен быть больше 500. Тогда при выполнении запроса в первой формулировке будет произведена таблица с одним столбцом и без единой строки. В отличие от этого, при выполнении запроса без раздела HAVING результирующая таблица будет состоять из одного столбца и одной строки (содержащей неопределенное значение), поскольку условие раздела WHERE вычисляется в false для каждой строки SP, и поэтому раздел SELECT будет вычисляться для пустой таблицы.

Замечание: неопределенное значение с строке результата появляется в результате некорректной спецификации SQL, в соответствии с которой значение SUM для пустого множества есть NULL (а должно было бы быть нулевым).

Но формулировка, эквивалентная исходной и не включающая HAVING, все-таки существует. Она немного более хитрая:

SELECT DISTINCT ( SELECT SUM(SP.QTY) FROM SP) AS TQY
FROM   SP
WHERE  (SELECT MIN(SP.QTY) FROM SP) > 50 ;

При выполнении запроса в этой формулировке, если (внешние) разделы FROM и WHERE совместно производят пустую таблицу, то таким будет и результат всего запроса. Причина состоит в том, что единственный элемент, указанный в разделе SELECT является не ссылкой на агрегатную функцию SUM, а скалярным выражением, содержащим такую ссылку. Мощность окончательного результата (т.е. число строк в результирующей таблице) не зависит от вида этого скалярного выражения; можно было бы заменить (SELECT SUM ...) на SP.P#, на SP.QTY или даже на литерал. Более детально, происходит следующее:

Предположим, что условие раздела WHERE вычисляется в false для каждой строки SP.
Тогда разделы FROM и WHERE совместно производят пустую таблицу (без строк).
Подзапрос в разделе SELECT, конечно, возвращает значение 3100. (Более точно, он вырабатывает таблицу с одним столбцом и одной строкой, содержащей численное значение, но SQL извлекает это значение из таблицы. Здесь для нас это обстоятельство не слишком важно, но в SQL вообще оно вызывает проблемы.)
Итак, обсуждаемая формулировка запроса логически эквивалентна следующей:
```
SELECT 3100 AS TQY
FROM   empty ;
```
(empty именует пустую таблицу.) Очевидно, что результатом такого запроса является таблица с одним столбцом TQY и без строк.

Теперь мы можем сформулировать еще одно правило преобразования: Пусть имеется таблица R{A,B}, и agg1 и agg2 - агрегатные функции, применимые к R.A и R.B соответственно. Тогда выражение

SELECT agg1(R.A) AS C
FROM   R
HAVING agg2(R.B) comp scalar ;

может быть логически преобразовано в эквивалентное выражение

SELECT DISTINCT ( SELECT agg1(R.A) FROM R ) AS C
FROM   R
WHERE ( SELECT agg2(R.B) FROM R ) comp scalar ;

(Здесь comp - некоторый скалярный оператор сравнения, а scalar - некоторое скалярное выражение.)

Будем называть такие преобразования "преобразованиями Типа 3". Читателям рекомендуется самостоятельно разобрать случай, когда формулировка с HAVING включает раздел WHERE.

HAVING без GROUP BY (II)

Имеется еще одно обстоятельство, связанное с запросами, которые содержат раздел HAVING и не содержат раздел GROUP BY. В языке SQL в связи с этим имеется логическая ошибка (еще одна!). Рассмотрим следующий запрос:

SELECT SUM(SP.QTY) AS TQY
FROM   SP
HAVING 0 = 0

Предположим, что в данный момент SP не содержит ни одной строки. Тогда логично считать, что "сгруппированная" версия SP, к которой применяются разделы SELECT и HAVING, не содержит ни одной группы и что корректным результатом будет таблица с одним столбцом и без единой строки. Однако SQL производит результат с одним столбцом и одной строкой (содержащей неопределенное значение). Считается, что "сгруппированная" версия SP содержит в точности одну группу (пустую); условие HAVING (тривиально) вычисляется в true для этой группы, и поэтому раздел SELECT тоже вычисляется для такой группы (вместо того, чтобы применяться к сгруппированной таблице, не содержащей ни одной группы).

Упражнение для читателей: Ниже приведена "эквивалентная" формулировка запроса без раздела HAVING, полученная применением преобразования Типа 3. Можно ли повергнуть эту формулировку подобной критике? Если нет, то вторая формулировка, конечно, более предпочтительна.

SELECT DISTINCT ( SELECT SUM(SP.QTY) FROM SP ) AS TQY
FROM   SP
WHERE 0 = 0 ;

В завершение раздела следует заметить, что в любом случае запросы с HAVING и без GROUP BY не очень "осмысленны".

Переменные с областью значений (range variables)

Замечание С.Кузнецова по поводу русскоязычной терминологии: На английском языке словосочетание "range variable" лаконично и правильно отражает суть понятия. К сожалению, до сих пор мне не удалось найти столь же лаконичный русский эквивалент, хотя было много попыток. Когда-то я пытался ввести в оборот термин "ранжированная переменная", но мне справедливо указали на отсутствие явного смысла в этом словосочетании. Если кто-нибудь знает, как лучше обозначать рассматривамое понятие на русском языке, дайте мне знать, пожалуйста.

Рассмотрим следующий запрос:

Q9: Выдать все пары номеров поставщиков, располагающихся в одном и том же городе

На языке SQL возможна следующая формулировка этого запроса:

SELECT FIRST.S# AS SX, SECOND.S# AS SY
FROM   S AS FIRST, S AS SECOND
WHERE  FIRST.CITY = SECOND.CITY

FIRST и SECOND являются примерами того, что в SQL называется корреляционными именами. Однако заметим, что SQL ничего не говорит о том, что именно именуют эти имена! В отличие от этого, в реляционном исчислении такие имена определяются для ссылок на переменные с областью значения, и далее будет использоваться этот термин.

Переменная с областью значений - это переменная, определенная на некоторой конкретной таблице; значениями переменной являются строки этой таблицы. Если областью значений переменной r является таблица R, то в каждый момент времени значением выражения "r" является некоторая строка R. В SQL переменные с областью значений вводятся посредством спецификации AS в разделе FROM (не нужно путать эту спецификацию со спецификацией AS в разделе SELECT, которая позволяет назначить имя столбцу результирующей таблицы).

Покажем, что, подобно разделам GROUP BY и HAVING, переменные с областью значений являются логически избыточными в языке SQL (несмотря на то, что они активно использовались в предыдущих примерах). Для иллюстрации сначала приведем формулировку запроса Q9 без использования переменных с областью значений:

SELECT SX, SY
FROM   ( SELECT S.S# AS SX, S.CITY FROM S) AS POINTLESS1 )
       NATURAL JOIN
       ( SELECT S.S# AS SY, S.CITY FROM S) AS POINTLESS2 )

Замечание С.Кузнецова: Напомним, что здесь используется SQL-92, в котором допустимы и такие "алгебраические" формулировки.

Как видно, в этой формулировке на самом деле определяются две переменных с областью значений - POINTLESS1 и POINTLESS2, но логически они не требуются, поскольку отсутствуют ссылки на эти переменные. Они введены исключительно для того, чтобы удовлетворить синтаксические требования языка SQL.

В качестве второго примера используем запрос Q1 из первой части заметки:

Q1: Для каждой поставляемой детали выдать номер детали, максимальный и минимальный объем поставки этой детали.

Вот формулировка этого запроса без использования переменных с областью значений (равно как и разделов GROUP BY и HAVING):

SELECT DISTINCT PZ AS P#,
                ( SELECT MAX(SP.QTY)
                   FROM  SP
                   WHERE SP.P# = PZ ) AS MXQ,
                ( SELECT MIN(SP.QTY)
                   FROM  SP
                   WHERE SP.P# = PZ ) AS MNQ
  FROM ( SELECT SP.P# AS PZ FROM SP ) AS POINTLESS ;

Как и в предыдущем примере, в этой формулировке вводится переменная с областью значений POINTLESS, но логически она не требуется, поскольку на эту переменную отсутствуют ссылки.

В завершение раздела заметим, что переменные с областью значений должны быть необязательными в SQL, поскольку

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

Обсуждение

В заметке сделана попытка показать, что запросы с разделами GROUP BY и HAVING (GBH-запросы) и переменные с областью значений являются избыточными в языке SQL. Интересно заметить, что эти аспекты SQL относятся к числу тех, которые наиболее трудно изучаются, понимаются и правильно применяются. Если говорить конкретно о GBH-запросах, то кажется, что альтернативные формулировки часто бывают более предпочтительными. Рассмотрим еще раз запрос Q4 из первой части заметки.

Q4: Выдать номер каждой детали, поставляемой более чем одним поставщиком.

Вот формулировки этого запроса с GBH и без GBH:

SELECT    SP.P#
FROM      SP
GROUP BY  SP.P#
HAVING    COUNT(*) > 1 ;

SELECT    DISTINCT SP.P#
FROM      SP
WHERE     ( SELECT COUNT(*) FROM SP AS SPX
                            WHERE SPX.P# = SP.P# ) > 1 ;

По мнению Дейта,

Вариант без GBH по крайней мере логически понятнее и проще чем вариант с GBH, поскольку в нем не используются дополнительные языковые конструкции (разделы GROUP BY и HAVING)
Из исходной формулировки проблемы не видно, что именно группирование требуется для выражения запроса на SQL (и оно действительно не требуется)
Далеко не очевидно, что нужен раздел HAVING, а не раздел WHERE

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

Конечно, нельзя отрицать, что вариант формулировки с GBH более короткий. Но если единственным преимуществом формулировок с GBH является краткость, то было бы лучше определять такие формулировки как сокращенную запись. Тогда, вероятно, не проявлялись бы отмеченные в заметке аномалии и реализация была бы проще. Замечание: следует упомянуть, что реляционный аналог разделов GROUP BY и HAVING языка SQL оператор SUMMARIZE определяется как сокращенная запись.

Наконец, необходимо отметить, что язык SQL содержит много других избыточностей (например, оператор EXISTS абсолютно избыточен). В результате большинство тривиальных запросов может быть выражено на языке SQL массой различных способов. Даже такой простой запрос как "Выдать имена поставщиков, которые поставляют деталь P2" можно выразить по меньшей мере восемью разными на вид способами. (И это при том условии, что используются только возможности SQL-86! Если применять новые возможности SQL-92, число допустимых формулировок значительно увеличится.)

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

Конечно, эта критика не была бы справедливой, если бы все формулировки выполнялись одинаково хорошо, но эта возможность сомнительна. (Сомнительно, чтобы оптимизатор запросов смог работать настолько хорошо.) Конечно, избыточности усложняют реализацию SQL. И особенно странно, что люди, ответственные за разработку языка SQL, большей частью являются представителями компаний-поставщиков СУБД, которые должны обеспечивать реализацию языка.

В заключение заметим, что проблемы избыточности устранить непросто. Если в язык когда-либо была внедрена некоторая возможность, ее никогда уже нельзя удалить, иначе перестанут работать существующие программы. Вот почему так важно иметь правильный язык с самого начала. И в этом основная сложность разработки языка.

Литература: