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

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

Выразим операции реляционной алгебры через операции реляционного исчисления.

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

select A1$,\ldots,$An from R

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

from R where $\theta$

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

select R.*, expr as A from R

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

R :: R1, R2

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

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

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

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

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

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

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

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

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