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

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

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

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

Синтаксис

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

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

Примеры

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