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

В этом разделе будет рассмотрена связь между языками реляционная алгебра и исчисление кортежей, которой является одной из разновидностей реляционного исчисления.

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

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

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

Проекция выражается, как select необходимого набора атрибутов:

select A1, $\ldots$, An from R

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

Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:

from R where $\theta$

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

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

select R.*, expr as A from R

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

Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:

R :: R1, R2

Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции — разности отношений.

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

Разность отношений R1 и R2 — это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:

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

Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

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

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

R1.*, R2.* from R1, R2

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

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

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

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

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

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

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

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

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

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

Преобразование формулы

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

Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

Применение кванторов

Квантор существования

Квантор существования соответсвует проекции. Проецируем, исключая атрибуты, порожденные переменной.

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

Получаем в точности поведение квантора существования.

Квантор всеобщности

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

Пример преобразования

Рассмотрим пример — группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:

select G.GId where $\exists$S ($\forall$C ($\exists$P
    (G.GId = S.GId $\land$ S.SId = P.SId $\land$
      C.CId = P.CId $\land$ P.Points $\geq$ 60)))

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

• [math]T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)[/math]. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
• [math]T_1=\pi_{G_∗,S_∗,C_∗}(T_0)[/math]. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
• [math]T_2=T_1 \div C[/math]. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
• [math]T_3=\pi_{G_∗}(T_2)[/math]. Еще один квантор существования, снова проецируем.
• [math]T=\pi_{G_∗}(\pi_{G_∗,S_∗,C_∗}(\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)) \bowtie C)[/math]. Можем записать как одно большое выражение в терминах реляционной алгебры.

Реляционная полнота

Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).

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

Реляционно-полные языки — языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.

Получаем, что исчисление кортежей реляционно полно.