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

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

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

1. R(x1x2...xk), где R – k-арное отношение; хi - константа или переменная на некотором домене.

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

2. xθy, где х и у – константы или переменные на некотором домене, θ – оператор сравнения. Атом хθу указывает, что х и у представляют собой значения, при которых истинно xθy.

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

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

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

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

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

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

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

1)из истинности φ(х1, х2, ..., xk) следует, что xi принадлежит D(φ);

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

3)если ("u)(φ1(u)) является подформулой φ, то из истинности φ1(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) вводится т новых переменных на доменах u1, и2, ..., ит, где т – арность кортежа и. В области действия этой кванти-фикации выполняются замены:

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

где φ’ – это φ, в которой выполнены соответствующие замены. Например, {tï R1(t)ÚR2(t)} перепишется так:

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

92