referat (Реляционное исчисление), страница 2

:: = RANGEVAR

RANGES OVER ;

Параметр может использоваться как , однако, лишь в определенном контексте, а именно:

• перед точкой и последующим уточнением в параметре ;

• сразу после квантора в параметре ;

• как операнд в параметре ;

• как параметр или как (операнд) подпараметр в параметре .

:: = .[ AS ]

Параметр может использоваться как параметр , но только в определенном контексте, а именно:

• как операнд параметра ;

• как параметр или как (операнд) подпараметр в параметре .

:: = … все обычные возможности вместе с:

| < логическое выражение с квантором>

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

• Параметр расположен непосредственно после параметра (т.е. параметр следует сразу за ключевым словом WHERE.).

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

Замечание по терминологии. В контексте реляционного исчисления (в версии исчисления доменов или исчисления кортежей) логические выражения часто называют правильно построенными формулами (well-formed formulas – WFF, что произносится как « вэфф»). Далее мы также будем часто пользоваться этой терминологией.

:: = EXISTS ()

| FORALL ()

:: = [ WHERE ]

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

:: =

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

Замечание. Прототип кортежа – термин удачный, но не стандартный.

2.2. Переменные кортежей.

Приведём несколько примеров определения переменных кортежей (выраженных в контексте базы данных поставщиков и деталей).

RANGEVAR SX RANGES OVER S;

RANGEVAR SY RANGES OVER S;

RANGEVAR SPX RANGES OVER SP;

RANGEVAR SPY RANGES OVER SP;

RANGEVAR PX RANGES OVER P;

RANGEVAR SU RANGES OVER

(SX WHERE SX.CITY=’London’)

(SX WHERE EXISTS SPX (SPX.S# = SX.S# AND

SPX.P# SPX = P# (‘P1’) ) );

Переменная кортежа SU из последнего примера определена на объединении множества кортежей поставщиков детали с номером ‘P1’. Обратите внимание, что в определении переменной кортежа SU используются переменные кортежей SX и SPX. Также обратите внимание на то, что в подобных определениях переменных, построенных на объединении отношений, объединяемые отношения, безусловно, должны быть совместимы по типу.

Замечание. Переменные кортежей не являются переменными в обычном смысле (как в языках программирования); они являются переменными в логическом смысле.

2.3. Свободные и связанные переменные кортежей.

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

Пусть V – переменная кортежа. Тогда имеем следующее.

• Ссылки на переменную V в формулах WFF типа NOT p свободны или связаны в пределах этой формулы в зависимости от того, свободны ли они в формуле p.Ссылки на переменную V в формулах WFF типа (p AND q) и (p OR q) свободны или связаны в зависимости от того, свободны ли они в формулах p и q.

• Ссылки на переменную V, которые свободны в формуле WFF p, связаны в формулах WFF типа EXISTS V(p) и FORALL V(p). Другие ссылки на переменные кортежей в формуле p будут свободны или связаны в формулах WFF типа EXISTS V(p) и FORALL V(p) в соответствии с тем, свободны ли они в формуле p.

Для полноты необходимо добавить следующие замечания.

• Единственная ссылка на переменную V в значении параметра является свободной в пределах этого параметра .

• Единственная ссылка на переменную V в значении параметра V.A является свободной в пределах этого параметра .

• Если ссылка на переменную V является свободной в некотором выражении exp, то эта ссылка будет также свободной в любом выражении exp’, непосредственно содержащем выражение exp как подвыражение, если только в выражении exp’ не вводится квантор, связывающий переменную V.

Приведём несколько примеров формул WFF, содержащих переменные

кортежей.

• Простые сравнения

SX.S# = S# (‘S1’)

SX.S# = SPX.S#

SPX.P# ≠ PX.P#

Здесь все ссылки на переменные SX, PX и SPX являются свободными.

• Логические выражения из простых сравнений

PX.WEIGHT < WEIGHT (15.5) OR PX.CITY = ‘Rome’

NOT (SX.CITY = ‘London’)

SX.S# = SPX.S# AND SPX.P# ≠ PX.P#

PX.COLOR = COLOR (‘Red’) OR PX.CITY = ‘London’

Здесь также все ссылки на переменные SX,PX и SPX являются свободными.

• Формулы WFF с кванторами

EXISTS SPX (SPX.S# = SX.S# AND SPX.P# = P# (‘P2’) )

FORALL PX (PX.COLOR = COLOR (‘Red’) )

В этих примерах ссылки на переменные SPX и PX являются связанными, а ссылка на переменную SX является свободной. Подробнее данные примеры объясняются ниже.

2.4. Кванторы.

Существуют два квантора: EXISTS и FORALL. Квантор EXISTS является квантором существования, а FORALL─ квантором всеобщности. По сути, если выражение p ─ формула WFF, в которой переменная V свободна, то выражения

EXISTS V (p)

и

FORALL V (p)

также являются допустимыми формулами WFF, но переменная V в них обеих будет связанной. Первая формула означает следующее: «Существует по крайней мере одно значение переменной V, такое, что вычисление формулы p даёт для него значение истина ». Вторая формула означает следующее: «Для всех значений переменной V вычисление формулы p даёт значение истина ». Предположим, например, что переменная V изменяется на множестве «Члены сената США в 1999 году», и предположим также, что выражение p ─ следующая формула WFF: «V ─ женщина» (разумеется, здесь не пытаемся использовать формальный синтаксис). Тогда выражение EXISTS V(p) будет допустимой формулой WFF, имеющей значение истина (true); выражение FORALL V(p) также будет допустимой формулой WFF, но вычисление его значения будет давать значение ложь (false).

Теперь рассмотрим квантор существования EXISTS более внимательно. Ещё раз обратимся к примеру из предыдущего раздела.

EXISTS SPX (SPX.S# = SX.S# AND SPX.P# = P# (‘P2’) )

Из приведённых ранее рассуждений следует, что эта формула WFF может быть прочитана следующим образом.

В текущем значении отношения SP существует кортеж (скажем, SPX), такой, для которого значение атрибута S# в этом кортеже равно значению атрибута SX.S# (какое бы оно ни было), а значение атрибута P# в кортеже SPX равно ‘P2’.

Каждая ссылка на переменную SPX в этом примере является связанной. Единственная ссылка на переменную SX свободна.

Формально квантор существования EXISTS определяется как повторение операции OR (ИЛИ). Другими словами, если r ─ это отношение с кортежами t1, t2, … , tm, V ─ это переменная кортежа, изменяющаяся на данном отношении, и p(V) ─ это формула WFF, в которой переменная V используется как свободная переменная, то формула WFF вида

EXISTS V (p (V))

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

false OR p (t1) OR … OR p (tm)

В частности, обратите внимание, что если отношение R пустое (т.е. m=0), то результатом вычисления данного выражения будет значение ложь.

Рассмотрим в качестве примера отношение r, содержащее следующие кортежи.

(1, 2, 3)

(1, 2, 4)

(1, 3, 4)

Для простоты предположим, что три атрибута, идущие по порядку слева направо, имеют имена A, B и C соответственно и каждый из этих атрибутов имеет тип INTEGER. Тогда приведённые ниже выражения будут иметь указанные значения.

EXISTS V (V.C>1) : true

EXISTS V (V.B>3) : false

EXISTS V (V.A>1 OR V.C = 4) : true

Теперь рассмотрим квантор общности FORALL, для чего вернёмся к соответствующему примеру из предыдущего раздела.

FORALL PX (PX.COLOR = COLOR (‘Red’) )

Эта формула WFF может быть прочитана следующим образом.

В текущем значении отношения P для всех кортежей (скажем, PX) значение их атрибута COLOR равно ‘Red’.

Обе ссылки на переменную PX в этом примере связаны.

Подобно тому, как квантор EXISTS был определён как повторение операции OR, квантор существования FORALL определяется как повторяющаяся операция AND (И). Другими словами, если обозначения r, V и p(V) имеют тот же смысл, что и в приведённом выше определении квантора EXISTS, то формула WFF вида

FORALL V (p (V) )

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

true AND p (t1) AND … AND p (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.

EXISTS x (x>3)

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

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