Эквивалентность выражений реляционной алгебры и реляционного исчисления с переменными-кортежами

Безопасные выражения

Выражение вида { t | Ø r(t) } в общем случае определяет бесконечное отношение, что недопустимо. Поэтому в реляционном исчислении ограничиваются рассмотрением так называемых безопасных выражений вида { t | y(t) }, которые гарантированно дают ограниченное множество кортежей. В таких выражениях значения атрибутов кортежей t являются элементами некоторого ограниченного универсального множества – DOM(y). Здесь DOM(y) – унарное отношение, элементами которого являются символы, которые либо явно появляются в y, либо служат компонентами какого-либо кортежа в некотором отношении R, упоминаемом в y.

В книге Дж. Ульман. Основы систем баз данных / пер. с англ – М.: Финансы и статистика, 1983, стр. 103 – 104, приведено следующее определение:

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

1. Всякий раз, когда t удовлетворяет y(t), каждый компонент t есть элемент DOM(y).

2. Для любого подвыражения y вида ( $ u) (w(u)) каждый компонент u принадлежит DOM(w), если u удовлетворяет w.

3. Если для любого подвыражения y вида ( " u) (w(u)) каждый компонент u не принадлежит DOM(w), то u удовлетворяет w.

Условия 2 и 3 позволяют устанавливать истинность квалифицированной формулы ( $ u) (w(u)) или ( " u) (w(u)), рассматривая только u, составленные из принадлежащих DOM(w) символов. Например, любая формула ( $ u) (R(u) Ù …) удовлетворяет условию 2, а любая формула ( " u) (ØR(u) Ú …) – условию 3.

Хотя условие 3 может показаться не интуитивным, мы должны заметить, что формула ( " u) (w(u)) логически эквивалентна формуле Ø ( $ u) ( Ø w(u)). Последняя не является безопасной, если и только если существует некоторое u₀, для которого истинно Øw(u₀) и u₀ не принадлежит домену формулы Øw. Так как домены w и Øw одни и те же, условие 3 устанавливает, что формула ( " u) (w(u)) безопасна, когда безопасна формула Ø ( $ u) ( Ø w(u)) …»

В той же книге (стр. 104) доказана следующая теорема, которая здесь приводится без доказательства.

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

Ниже приводятся некоторые эквивалентности.

Выражение реляционной алгебры	Выражение реляционного исчисления с переменными-кортежами
Объединение: r1 È r2, r1(R), r2(R)	{x(R) | r1(x) Ú r2(x) }
Разность: r1 – r2 , r1(R), r2(R)	{x(R) | r1(x) Ù Ør2(x) }
Пересечение: r1 Ç r2, r1(R), r2(R)	{x(R) | r1(x) Ù r2(x) }
Декартово произведение: r1 ´ r2, r1(R1), r2(R2)	{x(R1R2) | $u(R1) $v(R2) (r1(u) Ù r2(v) Ù x[R1] = u{r1] Ù x[R2] = v[R2]) }
Проекция: pL(r), r(R), L Í R	{t(L) | $u(R) (r(u) Ù u[L] = t[L] }
Выбор: sF(r), r(R)	{ t(R) | r(t) Ù F’) }
Естественное соединение: r1 r2 r1(AB), r2(BC)	{ t(ABC) | $u(AB) $v(BC) (r1(u) Ù r2(v) Ù u[B] = v[B] Ù t[AB] = u[AB] Ù t[C] = v[C]) }
Деление: r1 ¸ r2, r1(AB), r2(B)	{ t(A) | "x(B) (r2(x) Ù $y(AB) (r1(y) Ù y[B] = x[B] Ù y[A] = t[A] }