Замечание. Квантор FORALL включен в реляционное исчисление просто для удобства. Он не является необходимым, так как приведенное ниже тождество показывает, что любая формула WFF, использующая квантор FORALL, всегда может быть заменена эквивалентной формулой WFF, использующей квантор EXISTS.

FORALL V ( р ) = NOT EXISTS V ( NOT р )

(Проще говоря, выражение все значения V, удовлетворяющие формуле р - это то же самое, что и выражение нет таких значений V, которые бы не удовлетворяли формуле р .) Например, утверждение (истинное)

Для любого целого х существует целое у, такое, что у > х

равносильно утверждению

Не существует целого х, такого, что не существует целого у, такого, что у > х.

(Иначе говоря, не существует наибольщего целого числа.) Но обычно легче выразить подобное утверждение в терминах квантора FORALL, чем в терминах квантора EXISTS, с использованием двойного отрицания. Другими словами, на практике гораздо удобнее использовать оба квантора.

Еще раз о свободных и связанных переменных

Предположим, что переменная х изменяется на множестве всех целых чисел, и рассмотрим следующую формулу WFF.

EXISTS X ( X > 3 )

Связанная переменная х в этой формуле WFF является своего рода фиктивной переменной. Она служит лищь для связи внутренних параметров выражения с внещним квантором. В формуле WFF просто утверждается, что существует целое число (скажем, х), которое больще 3. Следовательно, заметьте, значение этой формулы WFF осталось бы полностью неизменным, если бы все экземпляры х были заменены экземплярами некоторой другой переменной (скажем, у). Другими словами, формула WFF EXISTS у (у > 3) семантически идентична формуле, приведенной ранее.

Теперь рассмотрим другую формулу WFF.

EXISTS X ( X > 3 ) AND X < О

Здесь имеется три ссылки на переменную х, обозначающие две различные переменные. Первые две ссылки связаны и могли бы быть заменены ссылкой на другую переменную у без изменения общего смысла формулы. Третья ссылка на переменную х не может быть безболезненно изменена. Таким образом, из двух приведенных ниже формул WFF первая эквивалентна рассмотренной формуле, а вторая - нет.

EXISTS y(y>3)ANDx<0 EXISTS у ( у > 3 ) AND у < О

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

Дополнительная терминология. Формула WFF, в которой все переменные связаны, называется закрытой формулой WFF (фактически она является высказыванием). Открытая формула WFF - это формула, которая не является закрытой, т.е. такая формула, которая содержит по крайней мере одну ссылку на свободную переменную.

Реляционные операции

Параметр <реляционная операциЯ> не совсем уместен в контексте исчисления - более подходящим вариантом был бы параметр <реляционное определение>. Однако мы будем использовать именно первый вариант для согласованности с обозначениями в главе 6. В качестве напоминания приводим следующий синтаксис.

<реляционная операциЯ>

::= <прототип кортежа> [ WHERE <логическое выражение> ]

<прототип кортежа>

:: = <выражение кортежа>

Напоминаем также, что следующие синтаксические правила теперь несколько упрощены,

Во-первых, все ссылки на переменные кортежей в параметре <прототип кортежа> должны быть свободными в пределах значения этого параметра.

Во-вторых, ссылка на переменную кортежа в предложении WHERE может быть свободной только в случае, если ссылка на эту же переменную (обязательно свободная) присутствует в соответствующем значении параметра <прототип кортежа>.

Например, следующее выражение является допустимым значением параметра <реляционная операциЯ> ( Получить номера поставщиков, находящихся в Лондоне ).

SX.SI WHERE SX.CITY = London

Здесь ссылка на переменную SX в прототипе кортежа является свободной. Ссылка на переменную SX в предложении WHERE также является свободной, поскольку ссылка на ту же переменную (обязательно свободную) имеется и в значении параметра <прототип кортежа> этого выражения.

Замечание. Далее термин прототип кортежа будет употребляться без скобок.

Приведем другой пример ( Получить имена поставщиков детали с номером Р2 ; см. обсуждение квантора существования, которое приводилось выше).

SX.SNAME WHERE EXISTS SPX ( SPX.Sl SX.Si AND

SPX.Pl = Pi { P2 ) )

Здесь все ссылки на переменную SX являются свободными, тогда как все ссылки на переменную SPX (в предложении WHERE) являются связанными, как и должно быть, поскольку на них нет ссылок в прототипе кортежа.

Интуитивно понятно, что результатом выполнения операции, заданной параметром <реляционная операциЯ>, будет отношение, содержащее все возможные значения кортежей, определяемых параметром <прототип кортежа>, для которых результат вычисления логического выражения, заданного в предложении WHERE параметром <логическое выражение>, принимает значение истина. (Если предложение WHERE опущено, это эквивалентно указанию выражения WHERE true.) Сделаем некоторые уточнения.

Прежде всего, прототип кортежа - это список разделенных запятыми элементов (возможно, заключенный в скобки), каждый элемент которого является либо ссылкой на атрибут кортежа (который может содержать предложение AS для введения нового имени атрибута), либо просто именем переменной кортежа. Тем не менее отметим следующее.

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

б) Ссылка на атрибут кортежа без предложения AS, в принципе, является сокращенным обозначением ссылки с предложением AS, в которой новое имя атрибута совпадает со старым.

Следовательно, без потери общности прототип кортежа можно рассматривать как список, состоящий из разделенных запятыми ссылок на атрибуты в виде Vi.Ai AS Bj. Обратите внимание, что ссылки Vi- и Aj-e могут повторяться, тогда как ссылки В j-e должны быть разными.

Пусть VI, V2, ..., Vm будут различными переменными кортежей, упоминаемыми в прототипе кортежа, и пусть эти переменные будут определены на отнощениях г1, г2, rm соответственно. Примем, что гГ, г2, rm - это новые отнощения, полученные после переименования атрибутов в предложении AS, и пусть г - это декартово произведение отнощений гГ, г2, rm.

Пусть отнощение г - это выборка из отнощения г, удовлетворяющая формуле WFF в предложении WHERE.

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

Конечное значение реляционной операции, заданной параметром <реля-ционное выражение>, определяется как проекция отнощения г по всем заданным атрибутам Bj.

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

7.3. Примеры

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

Существуют и другие возможности, однако для экономии времени мы ограничимся только этими двумя.