Реляционное исчисление доменов

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

Атомы формул могут быть двух типов [11, 17].

1. R(x1x2…xk),

где R - k-арное отношение; xi - константа или переменная на некотором домене.

Атом R(x1x2…xk)

указывает, что значения тех xi, которые являются переменными, должны быть выбраны так, чтобы (x1x2…xk) было кортежем отношения R.

2. x

y, где x и y – константы или переменные на некотором домене, ? –оператор сравнения.

Атом x

y указывает, что x и y представляют собой значения, при которых истинно xy.

Формулы в реляционном исчислении с переменными на доменах также используют логические связки ?, ?, ¬ и кванторы (

x), (x), где x – переменная на домене. Аналогично используются понятия свободных и связанных переменных.

Реляционное исчисление с переменными на доменах имеет вид

{x1x2…xk | ?(x1 , x2 ,…, xk)},

где ? – формула, обладающая тем свойством, что только ее свободные переменные на доменах являются различными переменными x1 , x2 ,…, xk. Например, выражение

{x1x2 | R1(x1x2) ?(

y)(¬R2(x1y) ?¬R2(x2y))}

имеет место для бинарных отношений R1

и R2 и означает множество кортежей в R1, таких, что ни один из их компонентов не является первым компонентом какого-либо кортежа отношения R2.

С целью учета ограничения – конечности реальных отношений – аналогично вводятся безопасные выражения.

Реляционное исчисление с переменными на доменах называется безопасным, если выполняются следующие условия:

1)    из истинности ?(x1 , x2 ,…, xk) следует, что xi принадлежит –D(?);

2)    если (

u)(?1(u)) является подформулой ?, то из истинности ?1(u), следует, что u принадлежит D(?);

3)    если (

u)(?1(u)) является подформулой ?, то из истинности ?1(u), следует, что u не принадлежит D(?).

Выражение исчисления с переменными на доменах, эквивалентное заданному выражению исчисления с переменными-кортежами {t| ?(t) строится следующим образом:

1)    если t является кортежем арности k, то вводится k новых переменных на доменах t1, t2, …, tk;

2)    атомы R(t) заменяются атомами R(t1, t2, …, tk);

3)    каждое свободное вхождение t[i] заменяется на ti;

4)    для каждого квантора (u) или (u) вводится m новых переменных на доменах u1, u2, …, um,

где m – арность кортежа u. В области действия этой квантификации выполняются замены:

R(u) на R(u1u2…um),

u[i] заменяется на ui,

(u) на (u1)(u1)…(um),

(u) на (u1)(u1)…(um);

5) выполняется построение выражения

{t1t2…tk | ?'(t1, t2, …, tk)},

где ?' – это ?, в которой выполнены соответствующие замены.

Например, {t| R1(t) ?R2(t)} перепишется так:

В реляционном исчислении с переменными на доменах существуют следующие две теоремы.

Теорема 4.2. Для каждого безопасного выражения реляционного исчисления с переменными-кортежами существует эквивалентное безопасное выражение реляционного исчисления с переменными на доменах [17].

Теорема 4.3. Для каждого безопасного выражения реляционного исчисления с переменными на доменах существует эквивалентное ему выражение реляционной алгебры [17].

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


Содержание раздела

---

---