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

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

Пусть е6сть переменная-кортеж t(R), где R = (A₁A₂…A_n) имеет арность n. Тогда вместо переменной-кортежа t вводятся n новых переменных на доменах t₁, t₂, …, t_n и заданное выражение исчисления с переменными-кортежами заменяется выражением {t₁, t₂, …, t_n | j΄(t₁, t₂, …, t_n)}. Здесь j΄ представляет собой j, в которой:

Любой атом r(t) заменяется атомом r(t₁, t₂, …, t_n);

Каждое свободное вхождение t[A_i] заменено переменной t_i;

Для каждого квантора $u или "u вводится m новых переменных u₁, u₂, …, u_m, где m – арность u. Кванторы $u (или "(u)) заменяются кванторами $u₁ $u₂ … $u_m ("u₁ "u₂ … "u_m, соответственно), и в подчиненных кванторам выражениях u[A_i] заменяются на u_i и r(u) на r(u₁, u₂, …, u_m).

Теорема

Для каждого безопасного выражения с переменными-кортежами существует эквивалентное безопасное выражение с переменными на доменах.

Пример:

Даны отношения со схемами S(S#, SNAME, CITY) – поставщик,

P(P#, PNAME, PRICE) – деталь,

SP(S#, P#, QTY) – поставка.

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

a) Выражение исчисления с переменными-кортежами:

{t(SNAME) | $u(S) $v(SP) (S(u) Ù SP(v) Ù u[SNAME] = t[SNAME] Ù u[S#] = v[S#] Ù v[P#] = “P2”)}

b) Выражение исчисления с переменными на доменах:

{t(SNAME) | $u₁(S#) $u₂(SNAME) $u₃(CITY) $v₁(S#) $v₂(P#) $v₃(QTY) (S(u₁,u₂,u₃) Ù SP(v₁,v₂,v₃) Ù u₂ = t Ù u₁ = v₁ Ù v₂ = “P2”)}