Реферат: Реляционное исчисление

FORALLV (p (V) )

равносильна следующей формуле WFF.

true AND p (t1) AND … ANDp (tm)

В частности, обратите внимание, что если отношение r пустое, то результатом вычисления данного выражения будет значение истина .

В качестве примера рассмотрим отношение R, содержащее те же кортежи, что и в предыдущем примере. Тогда приведённые ниже выражения будут иметь указанные значения.

FORALL V (V.A>1) : false

FORALL V (V.B>1) : true

FORALL V (V.A = 1 and V.C>2) : true

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

FORALL V (p) ≡ NOT EXISTS V (NOT p)

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

Например, утверждение (истинное)

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

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

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

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

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

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

EXISTSx (x>3)

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

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

EXISTS x (x>3) AND x<0

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

EXISTS y (y>3) AND x<0

EXISTS y (y>3) AND y<0

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

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

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

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