Реляционное исчисление с переменными-кортежами.

Аналогично тому, как РА использует в качестве операндов отношения, РИ кортежей строит свои выражения из кортежей.

Выражение в РИ строятся из атомов. Атомы могут быть трех типов:

1) , где – имя отношения, а – переменная-кортеж. Этот атом означает, что есть кортеж отношения .

2) , где и – переменные-кортежи, – арифметический оператор сравнения; – номера столбцов кортежей и соответственно. Этот атом означает, что -й компонент находится в отношении с -й компонентой .

3) tⁱ θС, Сθtⁱ, где и – то же, что в 2); С = . Этот атом означает, что -й компонент кортежа находится в отношении с константой С.

 

Переменная называется связанной, если этой переменной в формуле предшествует квантор или . В противном случае переменная называется свободной.

Выражение определяется рекурсивно следующим образом:

1) Каждый атом является выражением. Переменные в выражении являются свободными или связанными в зависимости от того, были ли они свободными или связанными в атоме.

2) Если φ₁ и φ₂ – выражения РИ, то φ₁ φ₂, φ₁ φ₂, φ_i – также выражения РИ. В результирующем выражении переменные будут свободными или связанными так же, как они были свободными или связанными в выражениях φ₁ и φ₂.

3) Если φ – формула, то – формула, которая утверждает, что существуют значения , при подстановке которых вместо всех свободных вхождений переменной в формулу , эта формула становится истинной. Переменная становится связанной, остальные свободны или связанны в зависимости от того, свободны они или связанны в формуле .

4) Если φ – формула, то – формула. Эта формула утверждает, что какое бы значение подходящей арности мы не подставляли вместо свободных вхождений в , формула является истинной. Лает то же, что в 3).

5) Формулы могут заключаться в скобки. Если их нет, то приоритет операций:

6) Ничто другое не является формулой.

Таким образом, формула в РИ с переменными-кортежами есть выражение вида , где – единственная свободная переменная-кортеж. А само исчисление кортежей определяется так же, как РИ только с другим О.

Пример:

РИ с переменными-кортежами в том виде, в каком его определили, позволяет представить некоторые бесконечные отношения. Например, означает все возможные не принадлежащие кортежи. Для того чтобы этого избежать вводится понятие безопасных выражений, для которых каждый компонент любого кортежа , удовлетворяющий , должен быть элементом множества .

D(φ) - множество символов, которые явно появляются в выражении φ, либо являются компонентами какого-либо кортежа отношения , упомянутого в φ. Множество является функцией отношений, которые должны подставляться вместо переменных отношения в . Т.к. – все отношения предполагаются конечными, то и множество конечно.

R_j имеет n_j компонент, – множество констант.

Выражение реляционного исчисления с переменными-кортежами называется безопасным, если выполняются условия:

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

2. Для любого подвыражения вида , входящего в выражение , каждый компонент , если t удовлетворяет .

3. Если для любого подвыражения вида , входящего в выражение , каждый компонент , то t будет удовлетворять выражению .

Условие 3 может показаться не интуитивным, но мы должны заметить, что формула эквивалентна . Последняя является безопасной, если для которого истинно и . Домены и одни и те же, следовательно, условие 3 устанавливает, что формула безопасна, когда безопасна формула .

Пример безопасного выражения:

Пусть – формула такая, что любая ее подформула вида и безопасна. Тогда безопасно каждое выражение вида

(*),

т.к. любое , удовлетворяющее (*), принадлежит , в силу чего каждый из его компонентов принадлежит . Например, такой вид имеет формула разности множеств: при .

Обобщения: безопасным является выражение:

должны быть символом, появляющемся в -ом компоненте кортежа из . Такой вид имеет проекция

.

На основании приведенных условий можно утверждать, что если – формула, в которой любая подформула вида или безопасна, то безопасно выражение вида (*), т.к. любой кортеж , удовлетворяющий этой формуле, принадлежит . Следовательно, любая компонента выражения (*).

Если φ состоит из подвыражений φ₁ и φ₂, связанных связками , и каждое φ_i может быть определено правилами 1-3, то безопасность выражения φ определяется безопасностью выражений φ₁ и φ₂.

Безопасные выражения РИ с переменными-кортежами эквивалентны РА.

Теорема: Если существует выражение РА, то существует эквивалентное ему безопасное выражение в РИ с переменными-кортежами.