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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Sashapff переименовал страницу Связь алгебры и исчисления. Реляционная полнота исчисления кортежей в [[Связь алгебры и исчисления кортеже…)
Строка 60: Строка 60:
 
* <tex>T_3=\pi_{G_∗}(T_2)</tex>. Еще один квантор существования, снова проецируем.  
 
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.
 
* <tex>T=\pi_{G_∗}(\pi_{G_∗,S_∗,C_∗}(\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)) \bowtie C)</tex>. Можем записать как одно большое выражение в терминах реляционной алгебры.
 +
 +
== Реляционная полнота ==
 +
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
 +
 +
{{Определение
 +
|definition=
 +
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
 +
}}
 +
 +
Получаем, что исчисление кортежей реляционно полно.

Версия 03:23, 20 декабря 2021

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

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

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

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

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


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


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