Кванторы, свободные и связанные переменные

При построении WFF допускается использование кванторов существования (EXISTS) и всеобщности (FORALL). Еслиform– это WFF, в которой участвует переменнаяvar, то конструкцииEXISTS var (form)иFORALL var (form)представляют собой WFF. По определению, формулаEXISTS var (form)принимает значениеtrueв том и только в том случае, если в области определения переменнойvarнайдется хотя бы одно значение (кортеж), для которого WFFformпринимает значениеtrue. ФормулаFORALL var (form)принимает значениеtrue, если для всех значений переменнойvarиз ее области определения WFFformпринимает значениеtrue.

Переменные, входящие в WFF, могут быть свободными или связанными. По определению, все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значениеtrue, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной использовано сразу после квантора при построении WFF видаEXISTS var (form)илиFORALL var (form), то в этой WFF и во всех WFF, построенных с ее участием,varявляетсясвязанной переменной. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной переменной, а вся область ее определения.

Пусть здесь и далее в этом разделе СЛУ1иСЛУ2представляют собой две кортежные переменные, определенные на отношенииСЛУЖАЩИЕ. Тогда WFF

EXISTS СЛУ2 (СЛУ1.СЛУ_ЗАРП > СЛУ2.СЛУ_ЗАРП)

для текущего кортежа переменной СЛУ1принимает значениеtrueв том и только в том случае, если во всем отношенииСЛУЖАЩИЕнайдется такой кортеж (ассоциированный с переменнойСЛУ2), чтобы значение его атрибутаСЛУ_ЗАРПудовлетворяло внутреннему условию сравнения. Легко видеть, что эта формула принимает значениеtrueтолько для тех значений кортежной переменнойСЛУ1, которые соответствуют служащим, не получающим минимальную зарплату. Соответствующее множество кортежей показано нарис. 6.2a(для тела отношенияСЛУЖАЩИЕизрис. 6.1).

Рис. 6.2.Примеры правильно построенных формул с кванторами

Правильно построенная формула

FORALL СЛУ2 (СЛУ1.СЛУ_ЗАРП СЛУ2.СЛУ_ЗАРП)

для текущего кортежа переменнойСЛУ1принимает значениеtrueв том и только в том случае, если для всех кортежей отношенияСЛУЖАЩИЕ(связанных с переменнойСЛУ2) значения атрибутаСЛУ_ЗАРПудовлетворяют условию сравнения. Снова легко видеть, что формула принимает значениеtrueтолько для тех значений кортежной переменнойСЛУ1, которые соответствуют служащим, получающим максимальную зарплату²⁷⁾. Соответствующее множество кортежей показано нарис. 6.2b.

Очевидно, что показанные на рис. 6.2отношения соответствуют условиям обеих формул. Но как в данном случае можно реализовать систему, которая по заданной формуле производит правильный результат? Наиболее очевидный способ интерпретации обеих обсуждавшихся выше формул следующий. В некотором порядке просматривать область определения свободной кортежной переменнойСЛУ1. Для каждого очередного кортежа из области определенияСЛУ1просматривать область определения связанной переменнойСЛУ2до тех пор, пока не будет установлено истинностное значение формулы для данного кортежаСЛУ1(в случае наличия квантора существования процесс просмотра дляСЛУ2можно остановить после нахождения первого кортежа, для которого значением подформулы, находящейся под знаком квантора, станетtrue; при наличии квантора всеобщности необходимо просмотреть всю область определенияСЛУ2). Заметим, что здесь мы снова получаем два цикла, как и при интерпретации WFF с двумя свободными

27 Упражнение для читателей. Почему в первой формуле (с EXISTS) использовано условие СЛУ1.СЛУ_ЗАР > СЛУ2.СЛУ_ЗАРП, а второй формуле (с FORALL) – СЛУ1.СЛУ_ЗАР СЛУ2.СЛУ_ЗАРП?

переменными. Но в данном случае во внешнем цикле обязательно просматривается область определения свободной переменной.

На самом деле, правильнее говорить не о свободных и связанных переменных, а о свободных и связанных вхождениях переменных. Если переменная varявляется связанной в WFFform, то во всех WFF, включающихform, внеformможет использоваться вхождение того же имени переменнойvar, которое может быть свободным или связанным, но в любом случае не имеет никакого отношения к вхождению переменнойvarв WFFform. Вот пример:

EXISTS СЛУ2 (СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ

AND СЛУ1.СЛУ_НОМЕР = СЛУ2.СЛУ_НОМЕР)

AND FORALL СЛУ2 (IF СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ

THEN СЛУ1.СЛУ_ЗАРП = СЛУ2.СЛУ_ЗАРП)

Эта формула принимает значение trueтолько для тех значений переменнойСЛУ1, которые соответствуют служащим, участвующим в проектах с более чем одним участником, причем все участники проекта получают одну и ту же зарплату. Здесь мы имеем два связанных вхождения переменнойСЛУ2с совершенно разным смыслом. Грубо говоря, для текущего значения переменнойСЛУ1переменнаяСЛУ2два раза «пробежит» свою область определения – первый раз при вычислении части формулы с квантором существования, а второй при вычислении части с квантором всеобщности. Кстати, к тому же результату приведет формула с одним квантором всеобщности вида:

FORALL СЛУ2 (IF (СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ AND

СЛУ1.СЛУ_НОМЕР СЛУ2.СЛУ_НОМЕР)

THEN СЛУ1.СЛУ_ЗАРП = СЛУ2.СЛУ_ЗАРП)

Легко заметить, что кванторы можно трактовать как булевские функции (функции, принимающие значения trueилиfalse) над множеством значений связанной кортежной переменной. С тем же успехом можно ввести в реляционное исчисление числовые функции над множествами, такие, какMIN(минимальное значение),MAX(максимальное значение),AVG(среднее значение) и т. д.

В этом случае можно было бы написать, например, WFF

СЛУ1.СЛУ_ЗАРП > MIN СЛУ2.СЛУ_ЗАРП (СЛУ1.ПРО_НОМ = СЛУ2.ПРО_НОМ)

в области истинности которой содержатся все кортежи отношения СЛУЖАЩИЕ, соответствующие тем служащим, которые получают заработную плату, превышающую минимальную зарплату служащих, участвующих в том же проекте. Понятно, что для получения результирующего отношения можно интерпретировать формулу таким же образом, как в обсуждавшемся выше случае наличия кванторов.