Исчисление кортежей — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры)
(Примеры)
Строка 80: Строка 80:
  
 
== Примеры ==
 
== Примеры ==
Переменные:
+
Самый простой пример {{---}} можно задавать переменные, как уже было ранее показано:
 
  S <font color = grey>::</font> Students<font color = grey>;</font> G <font color = grey>::</font> Groups<font color = grey>;</font> C <font color = grey>::</font> Courses<font color = grey>;</font> P <font color = grey>::</font> Point<font color = grey>;</font>
 
  S <font color = grey>::</font> Students<font color = grey>;</font> G <font color = grey>::</font> Groups<font color = grey>;</font> C <font color = grey>::</font> Courses<font color = grey>;</font> P <font color = grey>::</font> Point<font color = grey>;</font>
 
  G4 <font color = grey>::</font> Groups <font color = blue>where</font> Name <font color = grey>=</font> <font color = green>'M34351'</font> <font color = blue>∨</font>
 
  G4 <font color = grey>::</font> Groups <font color = blue>where</font> Name <font color = grey>=</font> <font color = green>'M34351'</font> <font color = blue>∨</font>
 
     Name <font color = grey>=</font> <font color = green>'M34371'</font> <font color = blue>∨</font> Name <font color = grey>=</font> <font color = green>'M34391'</font>
 
     Name <font color = grey>=</font> <font color = green>'M34371'</font> <font color = blue>∨</font> Name <font color = grey>=</font> <font color = green>'M34391'</font>
  
Полностью аттестованные группы:
+
Рассмотрим более сложный пример, в котором используются составные условия и условия с кванторами. Полностью аттестованная группа {{---}} группа такая, что у каждого студента по каждому курсу есть оценка хотя бы 60 баллов. На языке исчисления кортежей полностью это выглядит ровно так же, как и звучит:
 
  <font color = blue>select</font> G<font color = grey>.</font>GId <font color = blue>from</font> G <font color = blue>where</font> <font color = blue>$\forall$</font>S <font color = grey>(</font><font color = blue>$\forall$</font>C <font color = grey>(</font><font color = blue>$\exists$</font>P
 
  <font color = blue>select</font> G<font color = grey>.</font>GId <font color = blue>from</font> G <font color = blue>where</font> <font color = blue>$\forall$</font>S <font color = grey>(</font><font color = blue>$\forall$</font>C <font color = grey>(</font><font color = blue>$\exists$</font>P
 
     <font color = grey>(</font>S<font color = grey>.</font>SId <font color = grey>=</font> P<font color = grey>.</font>SId <font color = blue>$\land$</font> C<font color = grey>.</font>CId <font color = grey>=</font> P<font color = grey>.</font>CId <font color = blue>$\land$</font> P<font color = grey>.</font>Points <font color = blue>≥</font> 60<font color = grey>)))</font>
 
     <font color = grey>(</font>S<font color = grey>.</font>SId <font color = grey>=</font> P<font color = grey>.</font>SId <font color = blue>$\land$</font> C<font color = grey>.</font>CId <font color = grey>=</font> P<font color = grey>.</font>CId <font color = blue>$\land$</font> P<font color = grey>.</font>Points <font color = blue>≥</font> 60<font color = grey>)))</font>
 +
Видим, что запрос получился довольно лаконичным, в то время как в [[Реляционная алгебра|реляционной алгебре]] для такого же запроса потребовалось бы целых 2 больших деления.
  
Несколько отношений:
+
Второй особенностью [[Реляционное исчисление|реляционного исчисления]] является то, что можно выбирать сразу из нескольких отношений, просто перечислив их в секции from через запятую. Мотивация состоит в том, что в секции select можно указывать только атрибуты тех отношений, из которых выбираем. В следующем примере хотим указать и имя студента, и название его группы, поэтому нужно выбрать и студентов, и группы, так как в противном случае будет неоткуда достать соответсвующий кусочек информации. В таком случае еще необходимо добавить условие, что номер рассматриваемой группы и номер группы студента совпадают.
 
  <font color = blue>select</font> S<font color = grey>.</font>FirstName<font color = grey>,</font> S<font color = grey>.</font>LastName<font color = grey>,</font> G<font color = grey>.</font>Name
 
  <font color = blue>select</font> S<font color = grey>.</font>FirstName<font color = grey>,</font> S<font color = grey>.</font>LastName<font color = grey>,</font> G<font color = grey>.</font>Name
 
  <font color = blue>from</font> S<font color = grey>,</font> G
 
  <font color = blue>from</font> S<font color = grey>,</font> G
 
  <font color = blue>where</font> S<font color = grey>.</font>GId <font color = grey>=</font> G<font color = grey>.</font>GId
 
  <font color = blue>where</font> S<font color = grey>.</font>GId <font color = grey>=</font> G<font color = grey>.</font>GId

Версия 01:55, 27 декабря 2021

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

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

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

Синтаксис

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

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

Примеры

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