1632
правки
Изменения
м
Выразим Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
Преобразовать выражение реляционного исчисления в выражение реляционной алгебры происходит в несколько этапов.=== Преобразование формулы ===* Построить Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму. * После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной;.* Взять Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение;. Другими словами, берем все переменные и строим потенциально огромное декартово произведение. * Отфильтровать Теперь это декартово произведение необходимо отфильтровать по глобальному условию в из предваренной нормальной форме;формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет. * Применить После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы. Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.
Рассмотрим подробнее, как применять кванторы.
rollbackEdits.php mass rollback
В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов: <font color = blue>select</font> A1<font color = gray>, $,\ldots$,$</font>An <font color = blue>from</font> R
=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
<font color = blue>from</font> R <font color = blue>where</font> <font color = red>$\theta$</font>
=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
<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> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
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>
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.
=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
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=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Применение кванторов ===
==== Квантор существования ====
Квантор существования соответсвует соответствует проекции. Проецируем, исключая атрибуты, порожденные переменной.
* Если существует хотя бы одно значение кортежной переменной, удовлетворяющее условию, то проекция окажется не пустой.
* Если такого значения не окажется, то проекция окажется пустой.
Получаем в точности поведение квантора существования.
==== Квантор всеобщности ====
Квантор всеобщности соответсвует соответствует делению. Делим на все столбцы, порожденные переменной. В каждом кортеже несколько столбцов, делим на всех оптом.
=== Пример преобразования ===
Рассмотрим пример {{---}} группы, в которых хотя бы один студент полностью аттестован. То есть существует такой студент, что для любого курса существует оценка не меньше 60 баллов. На языке исчислений запрос будет выглядеть так:
<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>. Самый внутренний * Следующий квантор существованиявсеобщности, поэтому проецируем делим на оставшиеся все атрибуты соответствующих отношений.* , принадлежащие отношению C: <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.
== Реляционная полнота ==