Связь алгебры и исчисления кортежей. Реляционная полнота исчисления кортежей

Алгебра через исчисление

Выразим операции реляционной алгебры через операции реляционного исчисления.

Проекция [math]\pi_{A_1,\ldots,A_n}(R)[/math]

select A1$,\ldots,$An from R

Фильтр [math]\sigma_\theta(R)[/math]

from R where $\theta$

Дополнительный столбец [math]\varepsilon_{A=expr}(R)[/math]

select R.*, expr as A from R

Объединение [math]R_1 \cup R_2[/math]

R :: R1, R2

Разность [math]R1 \smallsetminus R2[/math]

R :: R1 where $\lnot\exists$R2 (R1 = R2)

Декартово произведение [math]R_1 \times R_2[/math]

R1.*, R2.* from R1, R2

Естественное соединение [math]R_1 \bowtie R_2[/math]

R1.*, R2.* from R1, R2 where 
                R1.Атрибуты = R2.Атрибуты

Реляционная полнота исчисления кортежей

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

Исчисление через алгебру

Определение:

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

Для того, чтобы преобразовать выражение реляционного исчисления в выражение реляционной алгебры необходимо выполнить последовательность действий:

• Построить выражения для каждой переменной;
• Взять декартово произведение;
• Отфильтровать по условию в предваренной нормальной форме;
• Применить кванторы.