Главная » SQL, Базы данных » Свободные и связанные переменные области значений

0

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

Пусть v — переменная области значений, а р и q — правильно построенные формулы.

Тогда имеем следующее.

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

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

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

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

■     Единственная ссылка на переменную V в значении параметра <range  attribute ref> V. А является свободной в пределах этого параметра <range a t tribu te ref>.

■  Если ссылка на переменную V является свободной в некотором выражении ехр,

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

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

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

FORALL V ( V.A > 1 )                                           : FALSE FORALL V ( V.B > 1 )                                            : TRUE FORALL V ( V.A = 1 AND V.C > 2 ) : TRUE

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

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

Неформально говоря, выражение "все значения V удовлетворяют формуле р" есть не что иное, как и выражение "нет таких значений V, которые бы не удовлетворяли формуле р". Например, (истинное) утверждение "Для любого целого х существует целое у, такое, что у > х" равносильно утверждению "Не существует целого х, такого, что не существует целого у, такого, что у > х" (иначе говоря, не существует наибольшего целого числа). Однако одни утверждения проще выразить в терминах квантора FORALL, а другие — в терминах квантора EXISTS; вернее, если один из кванторов недоступен, то иногда возникает необходимость  использовать двойное отрицание (как показано в предыдущем примере).  Поэтому  с точки зрения практики желательно, чтобы поддерживались оба квантора.

Дополнительные сведения о свободных и связанных переменных

Предположим, что переменная х принимает значения из множества всех целых чисел,

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

EXISTS х  (  х >  3. )

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

EXISTS  у   (у  >   3)

семантически идентична формуле, приведенной ранее.

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

EXISTS   х   (   х  >   3   )   AND  x  <   О

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

EXISTS  У  (  У  >  3   )  AND х

<  О EXISTS   у   (   у  >   3   ) AND  у  <   О

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

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

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

Параметр <relation op inv> не совсем уместен в контексте исчисления —  более подходящим вариантом был бы параметр <relation def>. Однако мы будем использовать именно первый вариант для согласованности с обозначениями в главе 7. В качестве напоминания приведем его синтаксис.

<relation  op inv>

::=   <proto  tuple>  [  WHERE  <bool  exp>  ]

<proto   tuple>

::=   .. .   определение   см.   в   тексте  данной главы

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

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

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

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

<relation op inv> ("Определить номера поставщиков, находящихся в Лондоне").

SX.S#  WHERE  SX.CITY  =   ‘London’

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

<proto  tuple> этого выражения.

Приведем другой пример ("Получить имена поставщиков детали с номером Р2"; см.

обсуждение квантора существования EXISTS в подразделе "Кванторы" этого раздела).

SX.SNAME WHERE EXISTS SPX ( SPX.S# = SX.S# AND SPX.P# = P# (‘P2′) )

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

Интуитивно  ясно,  что  результатом  выполнения  операции,  заданной  параметром

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

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

а)

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

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

300     Часть II. Реляционная модель

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

■     Пусть V1, V2, …, Vm — различные переменные области значений, присутствую щие в кортеже-прототипе, областями значений которых являются, соответственно, отношения rl, r2, …, rm. Допустим, что r 1′, r2′, . . . , rm’ — это новые отно шения, полученные после переименования атрибутов в конструкции AS, a r’ — это декартово произведение отношений r 1′,   r2′,   …,   rm’.

■     Пусть отношение r — это сокращение отношения r’, удовлетворяющее правиль но построенной формуле в конструкции WHERE.

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

■     Конечное значение реляционной операции, заданной параметром <relation op inv>, определяется как проекция отношения r по всем заданным атрибутам Bj.

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии