Связь алгебры и исчисления кортежей. Реляционная полнота исчисления кортежей
Содержание
- 1 Алгебра через исчисление
- 1.1 Проекция [math]\pi_{A_1,\ldots,A_n}(R)[/math]
- 1.2 Фильтр [math]\sigma_\theta(R)[/math]
- 1.3 Дополнительный столбец [math]\varepsilon_{A=expr}(R)[/math]
- 1.4 Объединение [math]R_1 \cup R_2[/math]
- 1.5 Разность [math]R1 \smallsetminus R2[/math]
- 1.6 Декартово произведение [math]R_1 \times R_2[/math]
- 1.7 Естественное соединение [math]R_1 \bowtie R_2[/math]
- 1.8 Реляционная полнота исчисления кортежей
- 2 Исчисление через алгебру
Алгебра через исчисление
Выразим операции реляционной алгебры через операции реляционного исчисления.
Проекция
select A1$,\ldots,$An from R
Фильтр
from R where $\theta$
Дополнительный столбец
select R.*, expr as A from R
Объединение
R :: R1, R2
Разность
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Декартово произведение
R1.*, R2.* from R1, R2
Естественное соединение
R1.*, R2.* from R1, R2 where R1.Атрибуты = R2.Атрибуты
Реляционная полнота исчисления кортежей
Набор перечисленных операций составляет базис операций реляционной алгебры. Все операции этого набора можно эмулировать в терминах реляционного исчисления. Из этого следует, что выразительна мощность реляционного исчисления не меньше выразительной мощности реляционной алгебры.
Исчисление через алгебру
Определение: |
Предваренная нормальная форма — форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие. |
Для того, чтобы преобразовать выражение реляционного исчисления в выражение реляционной алгебры необходимо выполнить последовательность действий:
- Построить выражения для каждой переменной;
- Взять декартово произведение;
- Отфильтровать по условию в предваренной нормальной форме;
- Применить кванторы.
Применение кванторов
Рассмотрим подробнее, как применять кванторы.
Квантор существования
Квантор существования соответсвует проекции. Проецируем, исключая атрибуты, порожденные переменной.
- Если существует хотя бы одно значение кортежной переменной, удовлетворяющее условию, то проекция окажется не пустой.
- Если такого значения не окажется, то проекция окажется пустой.
Получаем в точности поведение квантора существования.
Квантор всеобщности
Квантор всеобщности соответсвует делению. Делим на все столбцы, порожденные переменной.
Пример преобразования
select G.GId where $\exists$</font>S ($\forall$C ($\exists$P (G.GId = S.GId $\land$ S.SId = P.SId $\land$ C.CId = P.CId $\land$ P.Points $\geq$ 60)))