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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

Переменные-кортежи

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

Синтаксис

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

Переменная :: Отношение

Примеры

Можно задать переменную 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