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

Материал из Викиконспекты
Версия от 19:34, 4 сентября 2022; Maintenance script (обсуждение | вклад) (rollbackEdits.php mass rollback)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

Синтаксис

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

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

Примеры

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