Викиконспекты - Вклад участника [ru]

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

2021-12-29T11:13:03Z

188.123.230.124: /* Пример преобразования */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1, $\ldots$, An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим пример {{---}} группы, в которых хотя бы один студент полностью аттестован. То есть существует такой студент, что для любого курса существует оценка не меньше 60 баллов. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют такие группы, что существует хотя бы один студент, учащийся в этой группе, у которого по всем курсам существует положительная оценка. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения: <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>.
* Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений: <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>.
* Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C: <tex>T_2=T_1 \div C</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>.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-29T11:10:09Z

188.123.230.124: /* Квантор существования */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1, $\ldots$, An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим пример {{---}} группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют такие группы, что существует хотя бы один студент, учащийся в этой группе, у которого по всем курсам существует положительная оценка. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-29T11:08:47Z

188.123.230.124: /* Проекция \pi_{A_1,\ldots,A_n}(R) */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1, $\ldots$, An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим пример {{---}} группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют такие группы, что существует хотя бы один студент, учащийся в этой группе, у которого по всем курсам существует положительная оценка. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-29T11:08:10Z

188.123.230.124: /* Проекция \pi_{A_1,\ldots,A_n}(R) */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1, ..., An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим пример {{---}} группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют такие группы, что существует хотя бы один студент, учащийся в этой группе, у которого по всем курсам существует положительная оценка. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-29T11:07:52Z

188.123.230.124: /* Проекция \pi_{A_1,\ldots,A_n}(R) */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$, ...,$ An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим пример {{---}} группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют такие группы, что существует хотя бы один студент, учащийся в этой группе, у которого по всем курсам существует положительная оценка. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-29T11:07:36Z

188.123.230.124: /* Алгебра через исчисление */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$, ..., $An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим пример {{---}} группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют такие группы, что существует хотя бы один студент, учащийся в этой группе, у которого по всем курсам существует положительная оценка. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-29T11:07:01Z

188.123.230.124: /* Проекция \pi_{A_1,\ldots,A_n}(R) */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,...,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим пример {{---}} группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют такие группы, что существует хотя бы один студент, учащийся в этой группе, у которого по всем курсам существует положительная оценка. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

Исчисление кортежей

2021-12-29T11:03:46Z

188.123.230.124: /* Синтаксис */

В этом разделе будет рассмотрен один из видов [[Реляционное исчисление | реляционного исчисления]] {{---}} исчисление кортежей.

== Переменные-кортежи ==
В исчислении кортежей переменные являются кортежами. У каждой переменной-кортежа есть тип. Тип состоит из набора атрибутов и набора значений. Для каждого атрибута указан его домен {{---}} имя и тип. Такая комбинация из имен и типов атрибутов и набора значений в данной модели называется отношением. Из этого следует, что каждая кортежная переменная пробегает некоторое отношение.

=== Синтаксис ===
Для каждой переменной берем ее значение из тела соответствующего отношения. На языке исчисления кортежей объявление переменной записываем таким образом:
Переменная :: Отношение

=== Примеры ===
Можно задать переменную S, которая пробегает по всем студентам, и переменную G, которая пробегает по всем группам:
S :: Students
G :: Groups
Можно записать группы четвертого курса, то есть группы, которые имеют название M34351, M34371 или M34391:
G4 :: Groups where
Name = 'M34351' ∨
Name = 'M34371' ∨
Name = 'M34391'
Последний пример демонстрирует, что для отношения можно указать ограничивающее его условие.

== Операции с отношениями ==
=== Ограничение ===
Можно ограничить отношение, выбрав те кортежи, которые удовлетворяют требуемым условиям. Это делается с помощью ключевого слова where:
Отношения where Условие

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

=== Примеры ===
Рассмотрим примеры. Можно задать отношение {{---}} группы, имеющие название M34371:
Groups where Name = 'M34371'
Помимо способа, предложенного в предыдущей секции, можно задать группы 4 курса по-другому. Это такие группы, у которых название M34351, еще такие группы, у которых название M34371, и такие группы, у которых название M34391.
G4 :: Groups where Name = 'M34351',
Groups where Name = 'M34371',
Groups where Name = 'M34391'

== Условия ==
Разделяют три вида условий: простые, составные и условия с кванторами.
=== Простые условия ===
==== Cравнение атрибутов с константами ====
К простым условиям относится сравнение атрибутов с константами. Например, можно найти студентов с именем Иван:
S.Name = 'Иван'
Или выделить студентов с идентификатором меньше 5:
S.Id < 5

==== Cравнение атрибутов между собой ====
Также можно сравнивать атрибуты между собой, в том числе и на неравенство. Например найти студентов, имеющих идентификатор не меньше, чем идентификатор их группы:
S.Id $\geq$ G.Id

==== Cравнение атрибутов с применением формул ====
В качестве расширения можно использовать произвольные формулы ровно так же, как были устроены расширения в [[Реляционная алгебра|реляционной алгебре]]. Можно использовать любые формулы, зависящие от значений кортежных переменных. Например, можно найти студентов, у которых имя на 3 символа длиннее фамилии:
length(S.FirstName) = length(S.LastName) + 3

=== Составные условия ===
Из простых условий можно строить логические формулы с помощью стандартных логических связок «и», «или» и «не»: $\land$, $\lor$, $\lnot$.

Например, можно задать группы, которые имеют названия M34391 или M34371:
G where Name = 'M34371' ∨ Name = 'M34391'

Или студентов с именем Иван, но которые имеют фамилию не Иванов:
S where FirstName = 'Иван' ∧ LastName <> 'Иванов'

=== Условия с кванторами ===
Поверх логических формул можно навешивать кванторы всеобщности $\forall$ и существования $\exists$.

==== Синтаксис ====
В общем случае пишем сначала квантор, затем переменную, а далее в скобках условие, которое должно выполняться.
Квантор Переменная (Условие)

==== Примеры ====
Можно задать группы, в которых есть хотя бы один Иван, то есть для группы существует такой студент, которого зовут Иван и при этом он учится в данной группе:
G where $\exists$S (S.FirstName = 'Иван' ∧ S.GId = G.GId)

Также можно задать группы, в которых нет Иванов. Другими словами, для любого студента, если его зовут Иван, то номер его группы не совпадает с рассматриваемым:
G where $\forall$S (S.FirstName = 'Иван' ∨ S.GId <> G.GId)

Отметим, что про каждую переменную известно, из какого она отношения, поэтому при подстановке в квантор рассматриваются только значения переменных из соответствующих отношений. Например, когда в первом примере пишем $\exists$S, это означает, что существует кортеж в отношении Students, для которого выполняется дальнейшее условие.

== Примеры ==
Самый простой пример {{---}} можно задавать переменные, как уже было ранее показано:
S :: Students; G :: Groups; C :: Courses; P :: Point;
G4 :: Groups where Name = 'M34351' ∨
Name = 'M34371' ∨ Name = 'M34391'

Рассмотрим более сложный пример, в котором используются составные условия и условия с кванторами. Полностью аттестованная группа {{---}} группа такая, что у каждого студента по каждому курсу есть оценка хотя бы 60 баллов. На языке исчисления кортежей полностью это выглядит ровно так же, как и звучит:
select G.GId from G where $\forall$S ($\forall$C ($\exists$P
(S.SId = P.SId $\land$ C.CId = P.CId $\land$ P.Points ≥ 60)))
Видим, что запрос получился довольно лаконичным, в то время как в [[Реляционная алгебра|реляционной алгебре]] для такого же запроса потребовалось бы целых 2 больших деления.

Второй особенностью [[Реляционное исчисление|реляционного исчисления]] является то, что можно выбирать сразу из нескольких отношений, просто перечислив их в секции from через запятую. Мотивация состоит в том, что в секции select можно указывать только атрибуты тех отношений, из которых выбираем. В данном примере хотим указать и имя студента, и название его группы, поэтому нужно выбрать и студентов, и группы, так как в противном случае будет неоткуда достать соответсвующий кусочек информации. В таком случае еще необходимо добавить условие, что номер рассматриваемой группы и номер группы студента совпадают:
select S.FirstName, S.LastName, G.Name
from S, G
where S.GId = G.GId

Исчисление кортежей

2021-12-29T11:01:50Z

188.123.230.124: /* Переменные-кортежи */

В этом разделе будет рассмотрен один из видов [[Реляционное исчисление | реляционного исчисления]] {{---}} исчисление кортежей.

== Переменные-кортежи ==
В исчислении кортежей переменные являются кортежами. У каждой переменной-кортежа есть тип. Тип состоит из набора атрибутов и набора значений. Для каждого атрибута указан его домен {{---}} имя и тип. Такая комбинация из имен и типов атрибутов и набора значений в данной модели называется отношением. Из этого следует, что каждая кортежная переменная пробегает некоторое отношение.

=== Синтаксис ===
Для каждой переменной берем ее значение из тела соответствующего отношения:
Переменная :: Отношение

=== Примеры ===
Можно задать переменную S, которая пробегает по всем студентам, и переменную G, которая пробегает по всем группам:
S :: Students
G :: Groups
Можно записать группы четвертого курса, то есть группы, которые имеют название M34351, M34371 или M34391:
G4 :: Groups where
Name = 'M34351' ∨
Name = 'M34371' ∨
Name = 'M34391'
Последний пример демонстрирует, что для отношения можно указать ограничивающее его условие.

== Операции с отношениями ==
=== Ограничение ===
Можно ограничить отношение, выбрав те кортежи, которые удовлетворяют требуемым условиям. Это делается с помощью ключевого слова where:
Отношения where Условие

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

=== Примеры ===
Рассмотрим примеры. Можно задать отношение {{---}} группы, имеющие название M34371:
Groups where Name = 'M34371'
Помимо способа, предложенного в предыдущей секции, можно задать группы 4 курса по-другому. Это такие группы, у которых название M34351, еще такие группы, у которых название M34371, и такие группы, у которых название M34391.
G4 :: Groups where Name = 'M34351',
Groups where Name = 'M34371',
Groups where Name = 'M34391'

== Условия ==
Разделяют три вида условий: простые, составные и условия с кванторами.
=== Простые условия ===
==== Cравнение атрибутов с константами ====
К простым условиям относится сравнение атрибутов с константами. Например, можно найти студентов с именем Иван:
S.Name = 'Иван'
Или выделить студентов с идентификатором меньше 5:
S.Id < 5

==== Cравнение атрибутов между собой ====
Также можно сравнивать атрибуты между собой, в том числе и на неравенство. Например найти студентов, имеющих идентификатор не меньше, чем идентификатор их группы:
S.Id $\geq$ G.Id

==== Cравнение атрибутов с применением формул ====
В качестве расширения можно использовать произвольные формулы ровно так же, как были устроены расширения в [[Реляционная алгебра|реляционной алгебре]]. Можно использовать любые формулы, зависящие от значений кортежных переменных. Например, можно найти студентов, у которых имя на 3 символа длиннее фамилии:
length(S.FirstName) = length(S.LastName) + 3

=== Составные условия ===
Из простых условий можно строить логические формулы с помощью стандартных логических связок «и», «или» и «не»: $\land$, $\lor$, $\lnot$.

Например, можно задать группы, которые имеют названия M34391 или M34371:
G where Name = 'M34371' ∨ Name = 'M34391'

Или студентов с именем Иван, но которые имеют фамилию не Иванов:
S where FirstName = 'Иван' ∧ LastName <> 'Иванов'

=== Условия с кванторами ===
Поверх логических формул можно навешивать кванторы всеобщности $\forall$ и существования $\exists$.

==== Синтаксис ====
В общем случае пишем сначала квантор, затем переменную, а далее в скобках условие, которое должно выполняться.
Квантор Переменная (Условие)

==== Примеры ====
Можно задать группы, в которых есть хотя бы один Иван, то есть для группы существует такой студент, которого зовут Иван и при этом он учится в данной группе:
G where $\exists$S (S.FirstName = 'Иван' ∧ S.GId = G.GId)

Также можно задать группы, в которых нет Иванов. Другими словами, для любого студента, если его зовут Иван, то номер его группы не совпадает с рассматриваемым:
G where $\forall$S (S.FirstName = 'Иван' ∨ S.GId <> G.GId)

Отметим, что про каждую переменную известно, из какого она отношения, поэтому при подстановке в квантор рассматриваются только значения переменных из соответствующих отношений. Например, когда в первом примере пишем $\exists$S, это означает, что существует кортеж в отношении Students, для которого выполняется дальнейшее условие.

== Примеры ==
Самый простой пример {{---}} можно задавать переменные, как уже было ранее показано:
S :: Students; G :: Groups; C :: Courses; P :: Point;
G4 :: Groups where Name = 'M34351' ∨
Name = 'M34371' ∨ Name = 'M34391'

Рассмотрим более сложный пример, в котором используются составные условия и условия с кванторами. Полностью аттестованная группа {{---}} группа такая, что у каждого студента по каждому курсу есть оценка хотя бы 60 баллов. На языке исчисления кортежей полностью это выглядит ровно так же, как и звучит:
select G.GId from G where $\forall$S ($\forall$C ($\exists$P
(S.SId = P.SId $\land$ C.CId = P.CId $\land$ P.Points ≥ 60)))
Видим, что запрос получился довольно лаконичным, в то время как в [[Реляционная алгебра|реляционной алгебре]] для такого же запроса потребовалось бы целых 2 больших деления.

Второй особенностью [[Реляционное исчисление|реляционного исчисления]] является то, что можно выбирать сразу из нескольких отношений, просто перечислив их в секции from через запятую. Мотивация состоит в том, что в секции select можно указывать только атрибуты тех отношений, из которых выбираем. В данном примере хотим указать и имя студента, и название его группы, поэтому нужно выбрать и студентов, и группы, так как в противном случае будет неоткуда достать соответсвующий кусочек информации. В таком случае еще необходимо добавить условие, что номер рассматриваемой группы и номер группы студента совпадают:
select S.FirstName, S.LastName, G.Name
from S, G
where S.GId = G.GId

Исчисление кортежей

2021-12-28T19:33:44Z

188.123.230.124: /* Примеры */

В этом разделе будет рассмотрен один из видов [[Реляционное исчисление | реляционного исчисления]] {{---}} исчисление кортежей.

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

=== Синтаксис ===
Для каждой переменной берем ее значение из тела соответствующего отношения:
Переменная :: Отношение

=== Примеры ===
Можно задать переменную S, которая пробегает по всем студентам, и переменную G, которая пробегает по всем группам:
S :: Students
G :: Groups
Можно записать группы четвертого курса, то есть группы, которые имеют название M34351, M34371 или M34391:
G4 :: Groups where
Name = 'M34351' ∨
Name = 'M34371' ∨
Name = 'M34391'
Последний пример демонстрирует, что для отношения можно указать ограничивающее его условие.

== Операции с отношениями ==
=== Ограничение ===
Можно ограничить отношение, выбрав те кортежи, которые удовлетворяют требуемым условиям. Это делается с помощью ключевого слова where:
Отношения where Условие

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

=== Примеры ===
Рассмотрим примеры. Можно задать отношение {{---}} группы, имеющие название M34371:
Groups where Name = 'M34371'
Помимо способа, предложенного в предыдущей секции, можно задать группы 4 курса по-другому. Это такие группы, у которых название M34351, еще такие группы, у которых название M34371, и такие группы, у которых название M34391.
G4 :: Groups where Name = 'M34351',
Groups where Name = 'M34371',
Groups where Name = 'M34391'

== Условия ==
Разделяют три вида условий: простые, составные и условия с кванторами.
=== Простые условия ===
==== Cравнение атрибутов с константами ====
К простым условиям относится сравнение атрибутов с константами. Например, можно найти студентов с именем Иван:
S.Name = 'Иван'
Или выделить студентов с идентификатором меньше 5:
S.Id < 5

==== Cравнение атрибутов между собой ====
Также можно сравнивать атрибуты между собой, в том числе и на неравенство. Например найти студентов, имеющих идентификатор не меньше, чем идентификатор их группы:
S.Id $\geq$ G.Id

==== Cравнение атрибутов с применением формул ====
В качестве расширения можно использовать произвольные формулы ровно так же, как были устроены расширения в [[Реляционная алгебра|реляционной алгебре]]. Можно использовать любые формулы, зависящие от значений кортежных переменных. Например, можно найти студентов, у которых имя на 3 символа длиннее фамилии:
length(S.FirstName) = length(S.LastName) + 3

=== Составные условия ===
Из простых условий можно строить логические формулы с помощью стандартных логических связок «и», «или» и «не»: $\land$, $\lor$, $\lnot$.

Например, можно задать группы, которые имеют названия M34391 или M34371:
G where Name = 'M34371' ∨ Name = 'M34391'

Или студентов с именем Иван, но которые имеют фамилию не Иванов:
S where FirstName = 'Иван' ∧ LastName <> 'Иванов'

=== Условия с кванторами ===
Поверх логических формул можно навешивать кванторы всеобщности $\forall$ и существования $\exists$.

==== Синтаксис ====
В общем случае пишем сначала квантор, затем переменную, а далее в скобках условие, которое должно выполняться.
Квантор Переменная (Условие)

==== Примеры ====
Можно задать группы, в которых есть хотя бы один Иван, то есть для группы существует такой студент, которого зовут Иван и при этом он учится в данной группе:
G where $\exists$S (S.FirstName = 'Иван' ∧ S.GId = G.GId)

Также можно задать группы, в которых нет Иванов. Другими словами, для любого студента, если его зовут Иван, то номер его группы не совпадает с рассматриваемым:
G where $\forall$S (S.FirstName = 'Иван' ∨ S.GId <> G.GId)

Отметим, что про каждую переменную известно, из какого она отношения, поэтому при подстановке в квантор рассматриваются только значения переменных из соответствующих отношений. Например, когда в первом примере пишем $\exists$S, это означает, что существует кортеж в отношении Students, для которого выполняется дальнейшее условие.

== Примеры ==
Самый простой пример {{---}} можно задавать переменные, как уже было ранее показано:
S :: Students; G :: Groups; C :: Courses; P :: Point;
G4 :: Groups where Name = 'M34351' ∨
Name = 'M34371' ∨ Name = 'M34391'

Рассмотрим более сложный пример, в котором используются составные условия и условия с кванторами. Полностью аттестованная группа {{---}} группа такая, что у каждого студента по каждому курсу есть оценка хотя бы 60 баллов. На языке исчисления кортежей полностью это выглядит ровно так же, как и звучит:
select G.GId from G where $\forall$S ($\forall$C ($\exists$P
(S.SId = P.SId $\land$ C.CId = P.CId $\land$ P.Points ≥ 60)))
Видим, что запрос получился довольно лаконичным, в то время как в [[Реляционная алгебра|реляционной алгебре]] для такого же запроса потребовалось бы целых 2 больших деления.

Второй особенностью [[Реляционное исчисление|реляционного исчисления]] является то, что можно выбирать сразу из нескольких отношений, просто перечислив их в секции from через запятую. Мотивация состоит в том, что в секции select можно указывать только атрибуты тех отношений, из которых выбираем. В данном примере хотим указать и имя студента, и название его группы, поэтому нужно выбрать и студентов, и группы, так как в противном случае будет неоткуда достать соответсвующий кусочек информации. В таком случае еще необходимо добавить условие, что номер рассматриваемой группы и номер группы студента совпадают:
select S.FirstName, S.LastName, G.Name
from S, G
where S.GId = G.GId

Реляционное исчисление

2021-12-27T16:50:14Z

188.123.230.124: /* Структура запросов */

В этом разделе будет рассмотрен подход к формированию запросов, основанный на описании данных, которые необходимо получить.

== Реляционное исчисление ==

{{Определение
|definition=
'''Реляционное исчисление''' {{---}} декларативный язык для работы с отношениями, описывающий какими свойствами должен обладать требуемый результат.
}}
В отличие от [[Реляционная алгебра | реляционной алгебры]] не описываем, как будет получен результат.

Выделяют две разновидности реляционного исчисления:
* Исчисление кортежей {{---}} переменные принимают значения кортежа целиком;
* Исчисление доменов {{---}} каждая переменная принимает одно атомарное значение из какого-то домена.

== Структура запросов ==
Запросы в обоих видах исчислений устроены одинаково: сначала определяем переменные, с которыми будем работать, а затем определяем атрибуты результата из наборов переменных и свойства, которым они должны удовлетворять. Для реализации описанного поведения в реляционном исчисление используется стандартная конструкция select-from-where, как и в [[Реляционная алгебра|реляционной алгебре]]. В секции select указываются интересующие атрибуты, в секции from указываются переменные, из которых берутся соответствующие атрибуты, а в секции where ограничивающие условия. С точки зрения синтаксиса запрос выглядит так:
Определения переменных
select СписокАтрибутов
from Переменные
where Условие

== Отличия от реляционной алгебры ==
Рассмотрим разницу между [[Реляционная алгебра | реляционной алгеброй]] и реляционным исчислением на примере: получить идентификаторы студентов, обучающихся в группе M34371.

Запрос в реляционной алгебре состоит из естественного соединения студентов с номерами групп, затем фильтрации по номеру группы и получения идентификаторов студентов:
<tex>\pi_{SId}(\sigma_{Name=M34371}(Students \bowtie Groups))</tex>. По шагам описали, что необходимо сделать.

Соответсвующий запрос в терминах исчисления кортежей (S {{---}} Students, G {{---}} Groups):
select S.SId from S
where $\exists$G (S.GId = G.GId ∧ G.Name = 'M34371')
То есть, не указываем, как конкретно собираемся исполнять запрос, а описали, какие студенты нас интересуют.

Реляционное исчисление

2021-12-27T16:44:04Z

188.123.230.124: /* Структура запросов */

В этом разделе будет рассмотрен подход к формированию запросов, основанный на описании данных, которые необходимо получить.

== Реляционное исчисление ==

{{Определение
|definition=
'''Реляционное исчисление''' {{---}} декларативный язык для работы с отношениями, описывающий какими свойствами должен обладать требуемый результат.
}}
В отличие от [[Реляционная алгебра | реляционной алгебры]] не описываем, как будет получен результат.

Выделяют две разновидности реляционного исчисления:
* Исчисление кортежей {{---}} переменные принимают значения кортежа целиком;
* Исчисление доменов {{---}} каждая переменная принимает одно атомарное значение из какого-то домена.

== Структура запросов ==
Запросы в обоих видах исчислений устроены одинаково: сначала определяем переменные, с которыми будем работать, а затем атрибуты результата из наборов переменных и свойств, которым они должны удовлетворять.
Определения переменных
select СписокАтрибутов
from Переменные
where Условие

== Отличия от реляционной алгебры ==
Рассмотрим разницу между [[Реляционная алгебра | реляционной алгеброй]] и реляционным исчислением на примере: получить идентификаторы студентов, обучающихся в группе M34371.

Запрос в реляционной алгебре состоит из естественного соединения студентов с номерами групп, затем фильтрации по номеру группы и получения идентификаторов студентов:
<tex>\pi_{SId}(\sigma_{Name=M34371}(Students \bowtie Groups))</tex>. По шагам описали, что необходимо сделать.

Соответсвующий запрос в терминах исчисления кортежей (S {{---}} Students, G {{---}} Groups):
select S.SId from S
where $\exists$G (S.GId = G.GId ∧ G.Name = 'M34371')
То есть, не указываем, как конкретно собираемся исполнять запрос, а описали, какие студенты нас интересуют.

Реляционное исчисление

2021-12-27T00:44:48Z

188.123.230.124: /* Структура запросов */

В этом разделе будет рассмотрен подход к формированию запросов, основанный на описании данных, которые необходимо получить.

== Реляционное исчисление ==

{{Определение
|definition=
'''Реляционное исчисление''' {{---}} декларативный язык для работы с отношениями, описывающий какими свойствами должен обладать требуемый результат.
}}
В отличие от [[Реляционная алгебра | реляционной алгебры]] не описываем, как будет получен результат.

Выделяют две разновидности реляционного исчисления:
* Исчисление кортежей {{---}} переменные принимают значения кортежа целиком;
* Исчисление доменов {{---}} каждая переменная принимает одно атомарное значение из какого-то домена.

== Структура запросов ==

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

=== Синтаксис ===
Определения переменных
select СписокАтрибутов
from Переменные
where Условие

== Отличия от реляционной алгебры ==
Рассмотрим разницу между [[Реляционная алгебра | реляционной алгеброй]] и реляционным исчислением на примере: получить идентификаторы студентов, обучающихся в группе M34371.

Запрос в реляционной алгебре состоит из естественного соединения студентов с номерами групп, затем фильтрации по номеру группы и получения идентификаторов студентов:
<tex>\pi_{SId}(\sigma_{Name=M34371}(Students \bowtie Groups))</tex>. По шагам описали, что необходимо сделать.

Соответсвующий запрос в терминах исчисления кортежей (S {{---}} Students, G {{---}} Groups):
select S.SId from S
where $\exists$G (S.GId = G.GId ∧ G.Name = 'M34371')
То есть, не указываем, как конкретно собираемся исполнять запрос, а описали, какие студенты нас интересуют.

Реляционное исчисление

2021-12-27T00:44:25Z

188.123.230.124: /* Структура запросов */

В этом разделе будет рассмотрен подход к формированию запросов, основанный на описании данных, которые необходимо получить.

== Реляционное исчисление ==

{{Определение
|definition=
'''Реляционное исчисление''' {{---}} декларативный язык для работы с отношениями, описывающий какими свойствами должен обладать требуемый результат.
}}
В отличие от [[Реляционная алгебра | реляционной алгебры]] не описываем, как будет получен результат.

Выделяют две разновидности реляционного исчисления:
* Исчисление кортежей {{---}} переменные принимают значения кортежа целиком;
* Исчисление доменов {{---}} каждая переменная принимает одно атомарное значение из какого-то домена.

== Структура запросов ==

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

=== Синтаксис ===
Определения переменных
select СписокАтрибутов
from Переменные
where Условие

== Отличия от реляционной алгебры ==
Рассмотрим разницу между [[Реляционная алгебра | реляционной алгеброй]] и реляционным исчислением на примере: получить идентификаторы студентов, обучающихся в группе M34371.

Запрос в реляционной алгебре состоит из естественного соединения студентов с номерами групп, затем фильтрации по номеру группы и получения идентификаторов студентов:
<tex>\pi_{SId}(\sigma_{Name=M34371}(Students \bowtie Groups))</tex>. По шагам описали, что необходимо сделать.

Соответсвующий запрос в терминах исчисления кортежей (S {{---}} Students, G {{---}} Groups):
select S.SId from S
where $\exists$G (S.GId = G.GId ∧ G.Name = 'M34371')
То есть, не указываем, как конкретно собираемся исполнять запрос, а описали, какие студенты нас интересуют.

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

2021-12-27T00:43:17Z

188.123.230.124: /* Пример преобразования */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим пример {{---}} группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют такие группы, что существует хотя бы один студент, учащийся в этой группе, у которого по всем курсам существует положительная оценка. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:42:49Z

188.123.230.124: /* Пример преобразования */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют такие группы, что существует хотя бы один студент, учащийся в этой группе, у которого по всем курсам существует положительная оценка. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:40:56Z

188.123.230.124: /* Пример преобразования */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим группы, в которых хотя бы один студент полностью аттестован. На языке исчислений запрос будет выглядеть так:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:30:42Z

188.123.230.124: /* Преобразование формулы */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальными операциями, поэтому рассмотрим применение подробнее.

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

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

=== Пример преобразования ===
Рассмотрим такой запрос:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:28:51Z

188.123.230.124: /* Применение кванторов */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальной операцией, поэтому рассмотрим его подробнее.

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

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

=== Пример преобразования ===
Рассмотрим такой запрос:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:28:06Z

188.123.230.124: /* Исчисление через алгебру */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу к языку реляционной алгебры. Для этого сначала нам потребуется определить понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальной операцией, поэтому рассмотрим его подробнее.

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

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

=== Пример преобразования ===
Рассмотрим такой запрос:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:27:17Z

188.123.230.124: /* Исчисление через алгебру */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу. Далее нам потребуется понятие предваренной нормальной формы:
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
=== Преобразование формулы ===
* Изначально формула состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальной операцией, поэтому рассмотрим его подробнее.

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

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

=== Пример преобразования ===
Рассмотрим такой запрос:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:25:26Z

188.123.230.124: /* Исчисление через алгебру */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу. Изначально она состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не является тривиальной операцией, поэтому рассмотрим его подробнее.

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

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

=== Пример преобразования ===
Рассмотрим такой запрос:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:24:33Z

188.123.230.124: /* Разность R1 \smallsetminus R2 */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие кортежи из R1, что не существует кортежа из R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу. Изначально она состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не тривиальная операция, поэтому рассматрим ее подробнее.

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

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

=== Пример преобразования ===
Рассмотрим такой запрос:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:23:54Z

188.123.230.124: /* Исчисление через алгебру */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие из R1, что не существует R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу. Изначально она состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
* После того, как выражение приведено в предваренную нормальную форму, в глобальном условии оказалось множество переменных. Построим выражения для каждой переменной.
* Для каждой переменной определен диапазон, из которого она берет значения, поэтому далее можно построить соответсвующее декартово произведение. Другими словами, берем все переменные и строим потенциально огромное декартово произведение.
* Теперь это декартово произведение необходимо отфильтровать по глобальному условию из предваренной нормальной формы. Для каждого кортежа из декартово произведения зафиксированы все значения, поэтому для каждого из них можно проверить, истинно оно или нет.
* После того, как проверили глобальное условие, то есть сделали фильтр по нему, необходимо применить кванторы.
Применение кванторов не тривиальная операция, поэтому рассматрим ее подробнее.

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

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

=== Пример преобразования ===
Рассмотрим такой запрос:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:20:42Z

188.123.230.124: /* Исчисление через алгебру */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие из R1, что не существует R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

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

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

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

=== Пример преобразования ===
Рассмотрим такой запрос:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-27T00:20:17Z

188.123.230.124: /* Исчисление через алгебру */

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие из R1, что не существует R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

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

Рассмотрим, как можно преобразовать формулу. Изначально она состоит из каких-то атомарных вещей, которые можно вычислить, для каждой из них сравнить два значения, а далее идут логические связки и кванторы. Поэтому первым действием приводим выражение в предваренную нормальную форму.
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}

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

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

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

=== Пример преобразования ===
Рассмотрим такой запрос:
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

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

2021-12-26T23:49:34Z

188.123.230.124:

В этом разделе будет рассмотрена связь между языками [[Реляционная алгебра|реляционная алгебра]] и [[Исчисление кортежей|исчисление кортежей]], которой является одной из разновидностей [[Реляционное исчисление|реляционного исчисления]].
== Алгебра через исчисление ==
Для того, чтобы показать связь между языками, сначала выразим операции реляционной алгебры через операции реляционного исчисления. Начнем с простых операций алгебры, далее перейдем к более сложным.
=== Проекция <tex>\pi_{A_1,\ldots,A_n}(R)</tex> ===
Проекция выражается, как select необходимого набора атрибутов:
select A1$,\ldots,$An from R

=== Фильтр <tex>\sigma_\theta(R)</tex> ===
Чтобы сделать фильтрацию необходимо добавить в запрос в секцию where соответствующее условие:
from R where $\theta$

=== Дополнительный столбец <tex>\varepsilon_{A=expr}(R)</tex> ===
Для того, чтобы добавить дополнительный столбец, необходимо обозначить соответсвующее выражение в секции select в явном виде:
select R.*, expr as A from R

=== Объединение <tex>R_1 \cup R_2</tex> ===
Для объединения отношений используется стандартный синтаксис перечисления их через запятую при объявлении переменной:
R :: R1, R2
Отметим, что для того, чтобы сделать объединение, отношения должны быть совместимыми, то есть должны иметь одинаковый набор атрибутов. Аналогично будет для следующей операции {{---}} разности отношений.

=== Разность <tex>R1 \smallsetminus R2</tex> ===
Разность отношений R1 и R2 {{---}} это такие из R1, что не существует R2, с которым оно совпадает. Соответственно запрос в исчислении кортежей выражается так:
R :: R1 where $\lnot\exists$R2 (R1 = R2)
Под записью R1 = R2 в секции условия имеется в виду равенство для всех соответствующих атрибутов.

=== Декартово произведение <tex>R_1 \times R_2</tex> ===
Для того, чтобы выразить декартово произведения, тоже используется синтаксис с запятой, но уже в секции from:
R1.*, R2.* from R1, R2

=== Естественное соединение <tex>R_1 \bowtie R_2</tex> ===
Естественное соединение выражается как декартово произведение, но с дополнительным условием, что соответсвующие атрибуты равны:
R1.*, R2.* from R1, R2 where
R1.Атрибуты = R2.Атрибуты

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

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

== Исчисление через алгебру ==
{{Определение
|definition=
'''Предваренная нормальная форма''' {{---}} форма, при которой в начале выражения записаны все кванторы, а затем глобальное условие.
}}
Преобразовать выражение реляционного исчисления в выражение реляционной алгебры происходит в несколько этапов.
=== Преобразование ===
* Построить выражения для каждой переменной;
* Взять декартово произведение;
* Отфильтровать по условию в предваренной нормальной форме;
* Применить кванторы.

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

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

=== Пример преобразования ===
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)))
Выражению соответствуют группы, в которых есть хотя бы один студент, аттестованный по всем дисциплинам. Для удобства выражение уже записано в предваренной нормальной форме. Преобразуем:
* <tex>T_0=\sigma_{P.Points\geq60}((G \bowtie S \times C) \bowtie P)</tex>. Для простоты равенства соответствующих атрибутов уже неявно записаны как естественные соединения.
* <tex>T_1=\pi_{G_∗,S_∗,C_∗}(T_0)</tex>. Самый внутренний квантор существования, поэтому проецируем на оставшиеся атрибуты соответствующих отношений.
* <tex>T_2=T_1 \div C</tex>. Следующий квантор всеобщности, поэтому делим на все атрибуты, принадлежащие отношению C.
* <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>. Можем записать как одно большое выражение в терминах реляционной алгебры.

== Реляционная полнота ==
Любое выражение в терминах реляционной алгебры можно преобразовать в выражение в терминах реляционного исчисления. Также любое выражение реляционного исчисления можно преобразовать в обратную сторону к выражению реляционной алгебры. Таким образом, выразительные мощности исчисления и алгебры равны (алгебра рассматривается без агрегации).
{{Определение
|definition=
'''Реляционно-полные языки''' {{---}} языки, выразительная мощность которых не меньше выразительной мощности реляционной алгебры.
}}
Получаем, что исчисление кортежей реляционно полно.

Исчисление кортежей

2021-12-26T22:56:23Z

188.123.230.124: /* Примеры */

В этом разделе будет рассмотрен один из видов [[Реляционное исчисление | реляционного исчисления]] {{---}} исчисление кортежей.

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

=== Синтаксис ===
Для каждой переменной берем ее значение из тела соответствующего отношения:
Переменная :: Отношение

=== Примеры ===
Мжно задать переменная S, которая пробегает по всем студентам, и переменную G, которая пробегает по всем группам:
S :: Students
G :: Groups
Можно записать группы четвертого курса, то есть группы, которые имеют название M34351, M34371 или M34391:
G4 :: Groups where
Name = 'M34351' ∨
Name = 'M34371' ∨
Name = 'M34391'
Последний пример демонстрирует, что для отношения можно указать ограничивающее его условие.

== Операции с отношениями ==
=== Ограничение ===
Можно ограничить отношение, выбрав те кортежи, которые удовлетворяют требуемым условиям. Это делается с помощью ключевого слова where:
Отношения where Условие

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

=== Примеры ===
Рассмотрим примеры. Можно задать отношение {{---}} группы, имеющие название M34371:
Groups where Name = 'M34371'
Помимо способа, предложенного в предыдущей секции, можно задать группы 4 курса по-другому. Это такие группы, у которых название M34351, еще такие группы, у которых название M34371, и такие группы, у которых название M34391.
G4 :: Groups where Name = 'M34351',
Groups where Name = 'M34371',
Groups where Name = 'M34391'

== Условия ==
Разделяют три вида условий: простые, составные и условия с кванторами.
=== Простые условия ===
==== Cравнение атрибутов с константами ====
К простым условиям относится сравнение атрибутов с константами. Например, можно найти студентов с именем Иван:
S.Name = 'Иван'
Или выделить студентов с идентификатором меньше 5:
S.Id < 5

==== Cравнение атрибутов между собой ====
Также можно сравнивать атрибуты между собой, в том числе и на неравенство. Например найти студентов, имеющих идентификатор не меньше, чем идентификатор их группы:
S.Id $\geq$ G.Id

==== Cравнение атрибутов с применением формул ====
В качестве расширения можно использовать произвольные формулы ровно так же, как были устроены расширения в [[Реляционная алгебра|реляционной алгебре]]. Можно использовать любые формулы, зависящие от значений кортежных переменных. Например, можно найти студентов, у которых имя на 3 символа длиннее фамилии:
length(S.FirstName) = length(S.LastName) + 3

=== Составные условия ===
Из простых условий можно строить логические формулы с помощью стандартных логических связок «и», «или» и «не»: $\land$, $\lor$, $\lnot$.

Например, можно задать группы, которые имеют названия M34391 или M34371:
G where Name = 'M34371' ∨ Name = 'M34391'

Или студентов с именем Иван, но которые имеют фамилию не Иванов:
S where FirstName = 'Иван' ∧ LastName <> 'Иванов'

=== Условия с кванторами ===
Поверх логических формул можно навешивать кванторы всеобщности $\forall$ и существования $\exists$.

==== Синтаксис ====
В общем случае пишем сначала квантор, затем переменную, а далее в скобках условие, которое должно выполняться.
Квантор Переменная (Условие)

==== Примеры ====
Можно задать группы, в которых есть хотя бы один Иван, то есть для группы существует такой студент, которого зовут Иван и при этом он учится в данной группе:
G where $\exists$S (S.FirstName = 'Иван' ∧ S.GId = G.GId)

Также можно задать группы, в которых нет Иванов. Другими словами, для любого студента, если его зовут Иван, то номер его группы не совпадает с рассматриваемым:
G where $\forall$S (S.FirstName = 'Иван' ∨ S.GId <> G.GId)

Отметим, что про каждую переменную известно, из какого она отношения, поэтому при подстановке в квантор рассматриваются только значения переменных из соответствующих отношений. Например, когда в первом примере пишем $\exists$S, это означает, что существует кортеж в отношении Students, для которого выполняется дальнейшее условие.

== Примеры ==
Самый простой пример {{---}} можно задавать переменные, как уже было ранее показано:
S :: Students; G :: Groups; C :: Courses; P :: Point;
G4 :: Groups where Name = 'M34351' ∨
Name = 'M34371' ∨ Name = 'M34391'

Рассмотрим более сложный пример, в котором используются составные условия и условия с кванторами. Полностью аттестованная группа {{---}} группа такая, что у каждого студента по каждому курсу есть оценка хотя бы 60 баллов. На языке исчисления кортежей полностью это выглядит ровно так же, как и звучит:
select G.GId from G where $\forall$S ($\forall$C ($\exists$P
(S.SId = P.SId $\land$ C.CId = P.CId $\land$ P.Points ≥ 60)))
Видим, что запрос получился довольно лаконичным, в то время как в [[Реляционная алгебра|реляционной алгебре]] для такого же запроса потребовалось бы целых 2 больших деления.

Второй особенностью [[Реляционное исчисление|реляционного исчисления]] является то, что можно выбирать сразу из нескольких отношений, просто перечислив их в секции from через запятую. Мотивация состоит в том, что в секции select можно указывать только атрибуты тех отношений, из которых выбираем. В данном примере хотим указать и имя студента, и название его группы, поэтому нужно выбрать и студентов, и группы, так как в противном случае будет неоткуда достать соответсвующий кусочек информации. В таком случае еще необходимо добавить условие, что номер рассматриваемой группы и номер группы студента совпадают:
select S.FirstName, S.LastName, G.Name
from S, G
where S.GId = G.GId

Исчисление кортежей

2021-12-26T22:55:35Z

188.123.230.124: /* Примеры */

В этом разделе будет рассмотрен один из видов [[Реляционное исчисление | реляционного исчисления]] {{---}} исчисление кортежей.

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

=== Синтаксис ===
Для каждой переменной берем ее значение из тела соответствующего отношения:
Переменная :: Отношение

=== Примеры ===
Мжно задать переменная S, которая пробегает по всем студентам, и переменную G, которая пробегает по всем группам:
S :: Students
G :: Groups
Можно записать группы четвертого курса, то есть группы, которые имеют название M34351, M34371 или M34391:
G4 :: Groups where
Name = 'M34351' ∨
Name = 'M34371' ∨
Name = 'M34391'
Последний пример демонстрирует, что для отношения можно указать ограничивающее его условие.

== Операции с отношениями ==
=== Ограничение ===
Можно ограничить отношение, выбрав те кортежи, которые удовлетворяют требуемым условиям. Это делается с помощью ключевого слова where:
Отношения where Условие

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

=== Примеры ===
Рассмотрим примеры. Можно задать отношение {{---}} группы, имеющие название M34371:
Groups where Name = 'M34371'
Помимо способа, предложенного в предыдущей секции, можно задать группы 4 курса по-другому. Это такие группы, у которых название M34351, еще такие группы, у которых название M34371, и такие группы, у которых название M34391.
G4 :: Groups where Name = 'M34351',
Groups where Name = 'M34371',
Groups where Name = 'M34391'

== Условия ==
Разделяют три вида условий: простые, составные и условия с кванторами.
=== Простые условия ===
==== Cравнение атрибутов с константами ====
К простым условиям относится сравнение атрибутов с константами. Например, можно найти студентов с именем Иван:
S.Name = 'Иван'
Или выделить студентов с идентификатором меньше 5:
S.Id < 5

==== Cравнение атрибутов между собой ====
Также можно сравнивать атрибуты между собой, в том числе и на неравенство. Например найти студентов, имеющих идентификатор не меньше, чем идентификатор их группы:
S.Id $\geq$ G.Id

==== Cравнение атрибутов с применением формул ====
В качестве расширения можно использовать произвольные формулы ровно так же, как были устроены расширения в [[Реляционная алгебра|реляционной алгебре]]. Можно использовать любые формулы, зависящие от значений кортежных переменных. Например, можно найти студентов, у которых имя на 3 символа длиннее фамилии:
length(S.FirstName) = length(S.LastName) + 3

=== Составные условия ===
Из простых условий можно строить логические формулы с помощью стандартных логических связок «и», «или» и «не»: $\land$, $\lor$, $\lnot$.

Например, можно задать группы, которые имеют названия M34391 или M34371:
G where Name = 'M34371' ∨ Name = 'M34391'

Или студентов с именем Иван, но которые имеют фамилию не Иванов:
S where FirstName = 'Иван' ∧ LastName <> 'Иванов'

=== Условия с кванторами ===
Поверх логических формул можно навешивать кванторы всеобщности $\forall$ и существования $\exists$.

==== Синтаксис ====
В общем случае пишем сначала квантор, затем переменную, а далее в скобках условие, которое должно выполняться.
Квантор Переменная (Условие)

==== Примеры ====
Можно задать группы, в которых есть хотя бы один Иван, то есть для группы существует такой студент, которого зовут Иван и при этом он учится в данной группе:
G where $\exists$S (S.FirstName = 'Иван' ∧ S.GId = G.GId)

Также можно задать группы, в которых нет Иванов. Другими словами, для любого студента, если его зовут Иван, то номер его группы не совпадает с рассматриваемым:
G where $\forall$S (S.FirstName = 'Иван' ∨ S.GId <> G.GId)

Отметим, что про каждую переменную известно, из какого она отношения, поэтому при подстановке в квантор рассматриваются только значения переменных из соответствующих отношений. Например, когда в первом примере пишем $\exists$S, это означает, что существует кортеж в отношении Students, для которого выполняется дальнейшее условие.

== Примеры ==
Самый простой пример {{---}} можно задавать переменные, как уже было ранее показано:
S :: Students; G :: Groups; C :: Courses; P :: Point;
G4 :: Groups where Name = 'M34351' ∨
Name = 'M34371' ∨ Name = 'M34391'

Рассмотрим более сложный пример, в котором используются составные условия и условия с кванторами. Полностью аттестованная группа {{---}} группа такая, что у каждого студента по каждому курсу есть оценка хотя бы 60 баллов. На языке исчисления кортежей полностью это выглядит ровно так же, как и звучит:
select G.GId from G where $\forall$S ($\forall$C ($\exists$P
(S.SId = P.SId $\land$ C.CId = P.CId $\land$ P.Points ≥ 60)))
Видим, что запрос получился довольно лаконичным, в то время как в [[Реляционная алгебра|реляционной алгебре]] для такого же запроса потребовалось бы целых 2 больших деления.

Второй особенностью [[Реляционное исчисление|реляционного исчисления]] является то, что можно выбирать сразу из нескольких отношений, просто перечислив их в секции from через запятую. Мотивация состоит в том, что в секции select можно указывать только атрибуты тех отношений, из которых выбираем. В следующем примере хотим указать и имя студента, и название его группы, поэтому нужно выбрать и студентов, и группы, так как в противном случае будет неоткуда достать соответсвующий кусочек информации. В таком случае еще необходимо добавить условие, что номер рассматриваемой группы и номер группы студента совпадают.
select S.FirstName, S.LastName, G.Name
from S, G
where S.GId = G.GId