<<
>>

Реляционное исчисление с переменными кортежами

. Выражения реляционного исчисления с переменными кортежами записываются в следующем виде:

wm,

где t — единственная свободная переменная — кортеж, обозначающая кортеж фиксированной длины; если необходимо указать арность кортежа, то используют запись f'\ где i — арность кортежа t; 4* — некоторая формула, построенная по специальным правилам (для обозначения переменных- кортежей будем использовать прописные буквы).

Например, выражение

{//*,(/) ^2(/)},

где в качестве формулы выступает конструкция Я\(() V 7?2(0? означает, что нас интересует множество всех кортежей /, причем таких кортежей, которые принадлежат отношению Я\ или отношению Я2. Отметим, что формула (*,(0 V Я2(ф имеет смысл только тогда, когда отношения Я\ и Я2 имеют одинаковую арность (поскольку переменная-кортеж / задана как переменная фиксированной длины). Приведенное выражение {///?!(/) V /?2(0} эквивалентно операции объединения (Я\ и Я2) реляционной алгебры.

Формулы в реляционном исчислении строятся из атомов и совокупности операторов (арифметических и логических).

Атомы формул бывают трех типов:

1) /?(/), где Я — имя отношения. Этот атом означает, что / есть кортеж в отношении Я;

2) $[/] 0 !/[/], где £ и и — переменные-кортежи; 0 — арифметический оператор отношения; /,у— номера или имена интересующих нас компонентов (столбцов) в соответствующих кортежах; $[/] — обозначение /-го компонента в кортеже-переменной 5; м(/) — обозначениеу-го компонента в кортеже-переменной и.

Например, атом ($[3] ^ и[5]) означает, что третий компонент переменной £ больше или равен пятому компоненту переменной и\

3) ф] 0 а или а 0 ф], где а — константа.

Например, атом (¿[4] = 70) означает, что четвертый компонент переменной-кортежа б равен 70.

При записи формул используется понятие «свободных» и «связанных» переменных-кортежей, что определяется характером использования в формуле кванторов:

V — квантор всеобщности (общности); читается: все, всякий, каков бы ни был и т.п.

3 — квантор существования; читается: некоторые, хотя бы один, существует и т.п.

Вхождение переменной X в формуле ¥ связано, если в ¥ оно находится в подформуле, начинающейся квантором V или 3, за которым непосредственно следует переменная Хио котором говорят в данном случае, что он связывает переменную X. В остальных случаях вхождение переменной X в формулу ¥ свободно. Например, в формуле

(\/х)(Я(х, у) V (3у)№, у, £) Л 0(х, у))) V (\/х)(3гЖх, У, 2) V (3*хад) все вхождения х связаны, первое и последнее вхождения у свободны, остальные вхождения переменной у связаны, все вхождения переменной г свободны, единственное вхождение переменной г связано.

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

Формулы, а также свободные и связанные вхождения переменных- кортежей в эти формулы определяются рекурсивно следующим образом:

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

2. Если/ и/ — формулы, то:

/ л/ (утверждает, что/ и/> являются истинными),

/ V/ (утверждает, что/ или/, или обе истинны),

1/1 (утверждает, что/ не истинна) также являются формулами.

Экземпляры переменных-кортежей являются свободными или связанными в (/] л/), (/1 V/) и (1/) точно так же, как они являются свободными или связанными в/ и/ (т.е. свободны, соответственно связаны, те и только те вхождения переменных, которые происходят от свободных, соответственно связанных, вхождений переменных в / и /). Некоторое вхождение переменной может быть связанным в/, например, в то время как другое — свободным в/ и т.п.

3. Если/— формула, то (У5)(/) тоже формула. Свободные вхождения переменной 5 в формуле /теперь становятся связанными квантором (У^) в формуле (У^)(/). Формула (У.$)(/) утверждает: какое бы значение (т.е. какой бы кортеж) подходящей арности ни подставляли вместо свободных вхождений ^ в формуле f она всегда истинна.

4. Если/ — формула, то (3^)(/) также формула. Свободные вхождения переменной ^ в формуле / теперь также становятся связанным квантором (3^) в формуле (3^)(/). Формула (3^)(/) утверждает, что существует значение 5, при подстановке которого вместо всех свободных вхождений ^ в формулу/ эта формула становится истинной.

Например, формула (3^)(/г(^)) означает, что отношение Я не пусто, т.е. существует некоторый кортеж 5, принадлежащий Я.

5. Формулы при необходимости заключаются в скобки. Используется следующий порядок старшинства (в перечисленном порядке): арифметические операторы сравнения; кванторы 3 и V; 1, л, V.

6. Ничто иное не является формулой.

На основании изложенного в качестве примера запишем выражение реляционного исчисления на переменных-кортежах, соответствующее операции проекции П. /2 (Я) в реляционной алгебре. Оно будет иметь вид

{/*>/(3м)(ВД л ((/[1] =!/[/,]) л ... л (ОД = м[Щ}.

Можно сократить число скобок:

{/*>/(3ИХД(И) А /[ 1 ] = ф|] л ... Л t[k] = и[|*])}.

Введем ограничения на конечность реальных отношений в БД, чтобы исключить возможность формирования выражений вида

{//>(/)},

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

С этой целью в реляционном исчислении рассматривают только так называемые «безопасные» выражения {//4*(/)}, для которых выполняется условие, что каждый компонент (элемент столбца) любого /, удовлетворяющего 4*(/), является элементом некоторого множества элементов ДЧ*).

Множество ДЧ*) определяется как функция фактических отношений, которые указываются в Ч*(/), констант, присутствующих в формуле Ч*(/), и элементов кортежей тех отношений, которые указаны в 4*(/).

Так как все отношения в БД предполагаются конечными, то и множество Д4') конечно:

ДЧ'Ма,.,} и {«2т} U ... U {¿w} U П,(Л,) U П2(Л,) U ...

... П*(Л,) U П,(Л2) U ... U ЩЛ„),

где , •••, (Л(/) л ¥(/))• Тогда по условию 1 (выполнение условий 2 и 3 задано как исходная предпосылка) выражение {/¡Л(0 л ¥(/)} является безопасным.

Заметим, что если в ¥(/) найдется хотя бы одна из подформул вида (Зм)(¥|(/)) или (V«)(¥//)), которая окажется небезопасной, то тогда и выражение {///?(/) л ¥(/)} не будет являться безопасным. Если в формуле ¥(/) вообще отсутствуют подформулы вида (Эм)(¥,(/)) или (\/м)(¥/(/)), то выражение {*//?(/) л ¥(/)} всегда является безопасным.

Например, если ¥(/) = Т/?2(/),т0 получим безопасное выражение

да/)л1д2(/)}.

Безопасным является также выражение {///?(/)}, соответствующее отношению К (точнее — переменной /?, обозначающей отношение).

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

Теорема 1. Если Е — выражение реляционной алгебры, то существует эквивалентное ему безопасное выражение в реляционном исчислении с переменными-кортежами.

Для основных операций реляционной алгебры можно указать следующие соответствующие выражения реляционного исчисления на переменных-кортежах:

1. Операции объединения (К\ и К2) соответствует выражение:

{t/R](t)vR2(t)}.

2. Операции разности № - Л2) соответствует выражение:

{,*,(') Л Тедь

Здесь рассматривается все множество кортежей / таких, что / принадлежит Я\ и не принадлежит Л2.

3. Операции декартово произведение (Я\ х Я2) соответствует выражение

{/

<< | >>
Источник: Григорьев Ю.А., Ревунков Г.И.. Банки данных. 2002

Еще по теме Реляционное исчисление с переменными кортежами:

  1. § 27 Действие давности на обязательства. – Погашение права на иск. – Начало исчисления давности. – Открытие права на иск. – Исчисление давности в срочных и бессрочных договорах, при периодическом исполнении, по обязательствам главным и зависящим. – Перерыв давности – признанием долга. – Постановления русского закона о сем предмете.
  2. ПЕРЕМЕННАЯ ПРОМЕЖУТОЧНАЯ
  3. ПЕРЕМЕННАЯ
  4. ПЕРЕМЕННАЯ ЗАВИСИМАЯ
  5. ПЕРЕМЕННАЯ НЕЗАВИСИМАЯ
  6. ПЕРЕМЕННАЯ КОНТРОЛИРУЕМАЯ
  7. Пять переменных У. Мичела.
  8. Статья 73. Исчисление сроков наказания
  9. Сопротивление переменам в нас
  10. Теория «типовых переменных» и индивидуального выбора (Т. Парсонс).