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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Исчисление через алгебру)
Строка 38: Строка 38:
 
* Отфильтровать по условию в предваренной нормальной форме;
 
* Отфильтровать по условию в предваренной нормальной форме;
 
* Применить кванторы.
 
* Применить кванторы.
 +
 +
=== Применение кванторов ===
 +
Рассмотрим подробнее, как применять кванторы.
 +
==== Квантор существования ====
 +
Квантор существования соответсвует проекции. Проецируем, исключая атрибуты, порожденные переменной.
 +
* Если существует хотя бы одно значение кортежной переменной, удовлетворяющее условию, то проекция окажется не пустой.
 +
* Если такого значения не окажется, то проекция окажется пустой.
 +
Получаем в точности поведение квантора существования.
 +
 +
==== Квантор всеобщности ====
 +
Квантор всеобщности соответсвует делению. Делим на все столбцы, порожденные переменной.
 +
 +
=== Пример преобразования ===
 +
<font color = blue>select</font> G.GId <font color = blue>where $\exists$</font>S (<font color = blue>$\forall$</font>C (<font color = blue>$\exists$</font>P
 +
    (G.GId = S.GId <font color = blue>$\land$</font> S.SId = P.SId <font color = blue>$\land$</font>
 +
      C.CId = P.CId <font color = blue>$\land$</font> P.Points <font color = blue>$\geq$</font> 60)))

Версия 02:44, 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)))
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Связь_алгебры_и_исчисления_кортежей._Реляционная_полнота_исчисления_кортежей&oldid=81609»