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

== Алгебра через исчисление ==
Выразим операции реляционной алгебры через операции реляционного исчисления.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
 <font color = blue>select</font> A1<font color = gray>$,\ldots,$</font>An <font color = blue>from</font> R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
 <font color = blue>from</font> R <font color = blue>where</font> <font color = red>$\theta$</font>

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
 <font color = blue>select</font> R<font color = grey>.*,</font> expr <font color = blue>as</font> A <font color = blue>from</font> R

=== Объединение <tex>R_1 \cup R_2</tex> ===
 R <font color = grey>::</font> R1<font color = grey>,</font> R2

=== Разность <tex>R1 \smallsetminus R2</tex> ===
 R <font color = grey>::</font> R1 <font color = blue>where $\lnot\exists$</font>R2 <font color = grey>(</font>R1 <font color = grey>=</font> R2<font color = grey>)</font>

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
 R1<font color = grey>.*,</font> R2<font color = grey>.*</font> <font color = blue>from</font> R1<font color = grey>,</font> R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
 R1<font color = grey>.*,</font> R2<font color = grey>.*</font> <font color = blue>from</font> R1<font color = grey>,</font> R2 <font color = blue>where</font> 
                 R1<font color = grey>.</font><font color = red>Атрибуты</font> <font color = grey>=</font> R2<font color = grey>.</font><font color = red>Атрибуты</font>

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

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

== Исчисление через алгебру ==
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие. 
}}

Для того, чтобы преобразовать выражение реляционного исчисления в выражение реляционной алгебры необходимо выполнить последовательность действий:
* Построить выражения для каждой переменной;
* Взять декартово произведение;
* Отфильтровать по условию в предваренной нормальной форме;
* Применить кванторы.

=== Применение кванторов ===
Рассмотрим подробнее, как применять кванторы.
==== Квантор существования ====
Квантор существования соответсвует проекции. Проецируем, исключая атрибуты, порожденные переменной. 
* Если существует хотя бы одно значение кортежной переменной, удовлетворяющее условию, то проекция окажется не пустой. 
* Если такого значения не окажется, то проекция окажется пустой. 
Получаем в точности поведение квантора существования. 

==== Квантор всеобщности ====
Квантор всеобщности соответсвует делению. Делим на все столбцы, порожденные переменной. В каждом кортеже несколько столбцов, делим на всех оптом.

=== Пример преобразования ===
 <font color = blue>select</font> G<font color = grey>.</font>GId <font color = blue>where $\exists$</font>S <font color = grey>(</font><font color = blue>$\forall$</font>C <font color = grey>(</font><font color = blue>$\exists$</font>P
     <font color = grey>(</font>G<font color = grey>.</font>GId <font color = grey>=</font> S<font color = grey>.</font>GId <font color = blue>$\land$</font> S<font color = grey>.</font>SId <font color = grey>=</font> P<font color = grey>.</font>SId <font color = blue>$\land$</font>
       C<font color = grey>.</font>CId <font color = grey>=</font> P<font color = grey>.</font>CId <font color = blue>$\land$</font> P<font color = grey>.</font>Points <font color = blue>$\geq$</font> <font color = #056967>60</font><font color = grey>)))</font>
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <tex>T_3=\pi_{G_∗}(T_2)</tex>. Еще один квантор существования, снова проецируем. 
* <tex>T=\pi_{G_∗}(\pi_{G_∗,S_∗,C_∗}(\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)) \bowtie C)</tex>. Можем записать как одно большое выражение в терминах реляционной алгебры.