Реляционное исчисление доменов
В реляционном исчислении с переменными на доменах используются те же операторы, что и в реляционном исчислении с переменными-кортежами.
Атомы формул могут быть двух типов [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) строится следующим образом: