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

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

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

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

Проекция [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]. Можем записать как одно большое выражение в терминах реляционной алгебры.

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

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

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

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

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