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

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

Атомы формул могут быть двух типов [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 представляют собой значения, при которых истинно x

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

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) строится следующим образом:

Содержание Назад Вперед

Главная сайта