Материал: Базы данных и их безопасность. Плотников Д.Г

Имеется два квантора, обычно встречающихся в логике, EXISTS (существует) и FORALL (для всех). FORALL—это квантор общности. В логике предикат с навешенным квантором общности

FORALL х (предикат-зависящий-от-х)

принимает значение истина тогда и только тогда, когда «пре- дикат-зависящий-от-х» принимает значение истина для всех значений переменной х. Например, если х снова обозначает любое целое число в диапазоне от 1 до 10, то предикат

FORALL х (х < 100)

принимает значение истина в то время, как предикат

FORALL х (х < 5)

принимает значение ложь.

В принципе, FORALL — это то, что нужно для формулировки рассматриваемого запроса. Нам хотелось бы сказать примерно следующее: «Выдать фамилии поставщиков таких, что ДЛЯ ВСЕХ (FORALL) деталей СУЩЕСТВУЕТ (EXISTS) запись в таблице SP, указывающая, что данный поставщик поставляет эту деталь». К сожалению, в языке SQL квантор FORALL непосредственно не поддерживается. Однако включающий FORALL предикат всегда может быть преобразован в эквивалентный предикат, содержащий вместо него квантор существования EXISTS, при помощи следующего тождества:

FORALL х (р) = NOT (EXISTS х (NOT (р))).

Здесь «р» — это любой предикат, который зависит от переменной х. Например, предположим еще раз, что х обозначает любое целое число в диапазоне от 1 до 10. Тогда предикат

276

FORALL x (x < 100)

(значение которого, конечно, истина) эквивалентен следующему предикату:

NOT (EXISTS х (NOT (х < 100)))

(«не существует такого х, для которого бы не имело места, что х меньше 100», т. е. «не существует х такого, что х>= 100»). Аналогичным образом, предикат

FORALL х (х < 5)

(который имеет значение ложь) эквивалентен предикату

NOT (EXISTS х (NOT (х < 5)))

(«не существует такого х, для которого было бы несправедливо, что х<5», т. е. «не существует такого х, что х> =5»).

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

FORALL х (EXISTS у (у> х)),

значение которого — истина, эквивалентен следующему:

NOT (EXISTS (NOT (EXISTS у (у > х))))

(«не существует такого действительного х, для которого не существует такого действительного у, что у больше х»).

Вернемся теперь к рассматриваемой задаче. Можно преобразовать выражение «поставщики такие, что ДЛЯ ВСЕХ деталей СУЩЕСТВУЕТ запись в таблице SP, указывающая, что данный поставщик поставляет эту деталь» в эквивалентное выражение «поставщики такие, что НЕ СУЩЕСТВУЕТ детали

277

такой, что НЕ СУЩЕСТВУЕТ записи в таблице SP, указывающей, что данный поставщик поставляет эту деталь». Следовательно, формулировка запроса в языке SQL такова:

SELECT ФАМИЛИЯ

FROM S

WHERE NOT EXISTS (SELECT * FROM P

WHERE NOT EXISTS (SELECT * FROM SP WHERE

НОМЕР_ПОСТАВЩИКА = S.НОМЕР_ПОСТАВЩИКА AND НОМЕР_ДЕТАЛИ = Р.НОМЕР_ДЕТАЛИ));

Результат:

ФАМИЛИЯ

Смит

Данный запрос можно перефразировать: «Выдать фамилии поставщиков таких, что не существует детали, которую они бы не поставляли». Вообще говоря, наиболее легкий способ, позволяющий справляться со сложными запросами, подобными только что рассмотренному, состоит, вероятно, в том, чтобы сначала записывать их в «пceвдoSQL» форме с использованием квантора FORALL, а затем более или менее механически трансформировать такую запись в реальный SQL, используя взамен NOT EXISTS.

Запрос, использующий not exists

Выдать номера поставщиков, которые поставляют, по крайней мере, все те детали, которые поставляет поставщик S2.

Один из способов справиться с этой сложной задачей состоит в том, чтобы разбить ее на множество более простых

278

запросов и заниматься ими последовательно. Так, можно сначала определить множество номеров деталей, которые поставляются поставщиком S2:

SELECT НОМЕР_ДЕТАЛИ

FROM SP

WHERE НОМЕР_ПОСТАВЩИКА = ’S2’;

Результат:

НОМЕР_ДЕТАЛИ

P1

P2

Используя предложения CREATE TABLE и INSERT, которые будут обсуждаться в части 8.4, можно сохранить этот результат в некоторой таблице в базе данных, например, в таблице ВРЕМЕННАЯ. Далее можно перейти к определению множества номеров поставщиков, которые поставляют все детали, перечисленные в таблице ВРЕМЕННАЯ:

SELECT DISTINCT НОМЕР_ПОСТАВЩИКА FROM SP SPX

WHERE NOT EXISTS (SELECT *

FROM ВРЕМЕННАЯ

WHERE NOT EXISTS (SELECT * FROM SP SPY

WHERE

SPY.НОМЕР_ПОСТАВЩИКА =

SPX.НОМЕР_ПОСТ АВЩИКА

AND SPY.НОМЕР_ДЕТАЛИ = ВРЕМЕННАЯ.НОМЕР_ДЕТАЛИ));

279

Результат:

НОМЕР_ПОСТАВЩИКА

S1

S2

(Заметим, однако, что этот запрос отличается от запроса выше необходимостью использовать, по крайней мере, один псевдоним, поскольку мы выделяем значения столбца НОМЕР_ПОСТАВЩИКА из таблицы SP, а не значения столбца ФАМИЛИЯ из таблицы S. По этой причине необходимо иметь возможность одновременно делать две различные ссылки на таблицу SP.)

Теперь таблица ВРЕМЕННАЯ может быть уничтожена. Идея о том, чтобы справляться со сложными запросами таким пошаговым образом для легкости понимания, часто оказывается полезной. Однако можно также выразить рассматриваемый полный запрос в виде единственного предложения SELECT, полностью исключая при этом необходимость в таблице ВРЕМЕННАЯ:

SELECT DISTINCT НОМЕР_ПОСТАВЩИКА FROM SP SPX

WHERE NOT EXISTS (SELECT * FROM SP SPY

WHERE НОМЕР_ПОСТАВЩИКА = ’S2’ AND NOT EXISTS

(SELECT * FROM SP SPZ WHERE

SPZ.НОМЕР_ПОСТАВЩИКА = SPX.НОМЕР_ПОСТАВЩИКА AND SPZ.НОМЕР_ДЕТАЛИ =

SPY.НОМЕР_ДЕТАЛИ));

280