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

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

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

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

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

FORALL х (х < 100) -

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

FORALL х (х < 5)

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

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

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

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

FORALL х (х < 100)

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

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

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

FORALL х (х < 5)

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

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

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

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

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

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

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

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

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