Реляционное исчисление кортежей

В реляционном исчислении кортежей задача состоит в нахождении таких кортежей, для которых предикат P является истинным. Это исчисление основано на переменных кортежа. Переменными кортежа являются такие переменные, областью определения которых служит указанное отношение. Таковыми являются переменные, для которых допустимыми значениями могут быть только кортежи данного отношения. (Понятие "область определения" в данном случае относится не к используемому диапазону значений, а к домену, в котором определены эти значения.)

Формулы в реляционном исчислении имеют вид {t ï y (t)}, где t — переменная - кортеж, т.е. переменная, обозначающая кортеж некоторой фиксированной длины, а y — формула, построенная из атомов и совокупности операторов, которые определяются ниже.

Атомы формул y могут быть трех типов:

1. R(t), где R — имя отношения, а t — переменная-кортеж. Этот атом означает, что t есть кортеж в отношении R.

2. t [ i ] q s [ j ], где t и s являются переменными - кортежами, а q — арифметический оператор сравнения (=, ¹, £, ³ и т.д.). Этот атом означает, что i -й компонент t находится в отношении q с j -м компонентом s. Например, t [ 1 ] < s [ 2 ] означает, что первый компонент t меньше, чем второй компонент s.

3. t [ i ] q a и a q t [ i ], где q и t [ i ] имеют тот же смысл, что и в п. 2, а а - константа. Первый из этих атомов означает, что i -й компонент t находится в отношении q с константой а. Второй атом имеет аналогичный смысл. Например, t [ 1 ] = 3 указывает, что значение первого компонента t равно 3.

При определении операций реляционного исчисления введем понятия «свободных» и «связанных» переменных - кортежей. (Эти понятия имеют в точности тот же смысл, что и в исчислении предикатов.)

Неформально вхождение переменной в формулу является «связанным», если этой переменной предшествует квантор «для всех» " - всеобщности или «существует» $ - существования. В противном случае переменная называется «свободной».

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

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

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

2. Если y₁, и y₂ — формулы, то y₁ Ù y₂, y₁ Ú y₂ и Ø y₁ также формулы, утверждающие соответственно, что «y₁, и y₂ обе являются истинными», «y₁, или y₂, либо обе истинны» и «y₁ не истинна». Экземпляры переменных – кортежей являются свободными или связными в y₁ Ù y₂, y₁ Ú y₂ и Ø y₁ точно так же, как они являются свободными или связными в y₁ и y₂, в зависимости, где они появляются.

3. Если y - формула, то ( $ t)(y) - также формула. Вхождения переменной t, свободные в формуле y, являются связанными квантором ( $ t) в формуле ( $ t)(y). Формула ( $ t)(y) утверждает, что существует значение t, при подстановке которого вместо всех свободных вхождений t в формулу y эта формула становится истинной. Например, ( $ t)(R(t)) означает, что отношение R не пусто, т.е. существует некоторый кортеж t, принадлежащий R.

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

5. Формулы могут при необходимости заключаться в скобки. Предполагается следующий порядок старшинства: арифметические операции сравнения, кванторы $ и " и, наконец, Ø, Ù, Ú в перечисленном порядке.

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

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

{t ï R(t) Ù ( $ s) (S(s) Ù (s [ ID ] = t [ ID ] ) Ù s [ FIO ] = ‘ Иванов ’ )}

Это выражение означает, что в отношении S существует кортеж, который имеет такое же значение атрибута ID, что и значение атрибута ID в текущем кортеже t из отношения R, а атрибут FIO из кортежа s имеет значение ‘ Иванов ’.

Квантор всеобщности используется в выражениях, которые относятся ко всем экземплярам, например:

{t ï ( " t) (t [ CITY ] ¹ ‘Харьков’)}

Это выражение означает, что ни в одном кортеже отношения R значение атрибута CITY не равно ‘Харьков’.

В отношении логических операций могут применяться следующие правила эквивалентности:

1. ( $ t) (y(t)) º Ø ( " t) ( Ø (y(t)))

2. ( " t) (y(t)) º Ø ( $ t) ( Ø (y(t)))

3. ( $ t) (y₁(t) Ù (y₂(t)) º Ø ( " t) ( Ø (y₁(t)) Ú Ø (y₂(t)))

4. ( " t) (y₁(t) Ù (y₂(t)) º Ø ( $ t) ( Ø (y₁(t)) Ú Ø (y₂(t)))

Исходя из рассмотренных правил, последнюю формулу можно записать следующим образом:

{t ï Ø ( $ t) (t [ CITY ] = ‘Харьков’)}

Дата добавления: 2014-01-11