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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Простые условия)
м (rollbackEdits.php mass rollback)
 
(не показано 16 промежуточных версий 3 участников)
Строка 2: Строка 2:
  
 
== Переменные-кортежи ==
 
== Переменные-кортежи ==
У каждой переменной-кортежа есть тип {{---}} набор атрибутов, для каждого из которых есть домен, а так же набор значений. Такая комбинация в данной модели называется отношением. Из этого следует, что каждая кортежная переменная пробегает некоторое отношение.
+
В исчислении кортежей переменные являются кортежами. У каждой переменной-кортежа есть тип. Тип состоит из набора атрибутов и набора значений. Для каждого атрибута указан его домен {{---}} имя и тип. Такая комбинация из имен и типов атрибутов и набора значений в данной модели называется отношением. Из этого следует, что каждая кортежная переменная пробегает некоторое отношение.
  
 
=== Синтаксис ===
 
=== Синтаксис ===
Для каждой переменной берем ее значение из тела соответствующего отношения:
+
Для каждой переменной берем ее значение из тела соответствующего отношения. На языке исчисления кортежей объявление переменной записываем таким образом:
 
  <font color = red>Переменная <font color = grey>::</font> Отношение</font>
 
  <font color = red>Переменная <font color = grey>::</font> Отношение</font>
  
 
=== Примеры ===  
 
=== Примеры ===  
Мжно задать переменная S, которая пробегает по всем студентам, и переменную G, которая пробегает по всем группам:
+
Можно задать переменную S, которая пробегает по всем студентам, и переменную G, которая пробегает по всем группам:
 
  S <font color = grey>::</font> Students
 
  S <font color = grey>::</font> Students
 
  G <font color = grey>::</font> Groups
 
  G <font color = grey>::</font> Groups
Строка 50: Строка 50:
  
 
==== Cравнение атрибутов с применением формул ====
 
==== Cравнение атрибутов с применением формул ====
В качестве расширения можно использовать произвольные формулы ровно так же, как были устроены расширения в [[Реляционная алгебра|реляционной алгебре]]. Можно использовать любые формулы, зависящие от значений кортежных переменных. Например, найти студентов, у которых имя на 3 символа длиннее фамилии:
+
В качестве расширения можно использовать произвольные формулы ровно так же, как были устроены расширения в [[Реляционная алгебра|реляционной алгебре]]. Можно использовать любые формулы, зависящие от значений кортежных переменных. Например, можно найти студентов, у которых имя на 3 символа длиннее фамилии:
 
  length<font color = grey>(</font>S<font color = grey>.</font>FirstName<font color = grey>)</font> <font color = grey>=</font> length<font color = grey>(</font>S<font color = grey>.</font>LastName<font color = grey>)</font> <font color = grey>+</font> <font color = #056967>3</font>
 
  length<font color = grey>(</font>S<font color = grey>.</font>FirstName<font color = grey>)</font> <font color = grey>=</font> length<font color = grey>(</font>S<font color = grey>.</font>LastName<font color = grey>)</font> <font color = grey>+</font> <font color = #056967>3</font>
  
 
=== Составные условия ===
 
=== Составные условия ===
Из простых условий можно строить логические формулы с помощью стандартных связок: <font color = blue>$\land$</font>, <font color = blue>$\lor$</font>, <font color = blue>$\lnot$</font>.
+
Из простых условий можно строить логические формулы с помощью стандартных логических связок «и», «или» и «не»: <font color = blue>$\land$</font>, <font color = blue>$\lor$</font>, <font color = blue>$\lnot$</font>.
  
 +
Например, можно задать группы, которые имеют названия M34391 или M34371:
 
  G <font color = blue>where</font> Name <font color = gray>=</font> <font color = green>'M34371'</font> <font color = blue>∨</font> Name <font color =  
 
  G <font color = blue>where</font> Name <font color = gray>=</font> <font color = green>'M34371'</font> <font color = blue>∨</font> Name <font color =  
 
gray>=</font> <font color = green>'M34391'</font>
 
gray>=</font> <font color = green>'M34391'</font>
  
 +
Или студентов с именем Иван, но которые имеют фамилию не Иванов:
 
  S <font color = blue>where</font> FirstName <font color = gray>=</font> <font color = green>'Иван'</font> <font color = blue>∧</font> LastName <font color = gray><></font> <font color = green>'Иванов'</font>
 
  S <font color = blue>where</font> FirstName <font color = gray>=</font> <font color = green>'Иван'</font> <font color = blue>∧</font> LastName <font color = gray><></font> <font color = green>'Иванов'</font>
  
 
=== Условия с кванторами ===
 
=== Условия с кванторами ===
Поверх логических формул можно навешивать кванторы:
+
Поверх логических формул можно навешивать кванторы всеобщности <font color = blue>$\forall$</font> и существования <font color = blue>$\exists$</font>.
* Всеобщности <font color = blue>$\forall$</font>;
 
* Существования <font color = blue>$\exists$</font>.
 
  
 
==== Синтаксис ====
 
==== Синтаксис ====
 +
В общем случае пишем сначала квантор, затем переменную, а далее в скобках условие, которое должно выполняться.
 
  <font color = red>Квантор Переменная <font color = grey>(</font>Условие<font color = grey>)</font></font>
 
  <font color = red>Квантор Переменная <font color = grey>(</font>Условие<font color = grey>)</font></font>
  
 
==== Примеры ====
 
==== Примеры ====
 +
Можно задать группы, в которых есть хотя бы один Иван, то есть для группы существует такой студент, которого зовут Иван и при этом он учится в данной группе:
 
  G <font color = blue>where</font> <font color = blue>$\exists$</font>S <font color = gray>(</font>S<font color = gray>.</font>FirstName <font color = gray>=</font> <font color = green>'Иван'</font> <font color = blue>∧</font> S<font color = gray>.</font>GId <font color = gray>=</font> G<font color = gray>.</font>GId<font color = gray>)</font>
 
  G <font color = blue>where</font> <font color = blue>$\exists$</font>S <font color = gray>(</font>S<font color = gray>.</font>FirstName <font color = gray>=</font> <font color = green>'Иван'</font> <font color = blue>∧</font> S<font color = gray>.</font>GId <font color = gray>=</font> G<font color = gray>.</font>GId<font color = gray>)</font>
  
 +
Также можно задать группы, в которых нет Иванов. Другими словами, для любого студента, если его зовут Иван, то номер его группы не совпадает с рассматриваемым:
 
  G <font color = blue>where</font> <font color = blue>$\forall$</font>S <font color = gray>(</font>S<font color = gray>.</font>FirstName <font color = gray>=</font> <font color = green>'Иван'</font> <font color = blue>∨</font> S<font color = gray>.</font>GId <font color = gray><></font> G<font color = gray>.</font>GId<font color = gray>)</font>
 
  G <font color = blue>where</font> <font color = blue>$\forall$</font>S <font color = gray>(</font>S<font color = gray>.</font>FirstName <font color = gray>=</font> <font color = green>'Иван'</font> <font color = blue>∨</font> S<font color = gray>.</font>GId <font color = gray><></font> G<font color = gray>.</font>GId<font color = gray>)</font>
  
Про каждую переменную известно, из какого она отношения, поэтому при подстановке в квантор рассматриваются только значения переменных из соответствующих отношений.
+
Отметим, что про каждую переменную известно, из какого она отношения, поэтому при подстановке в квантор рассматриваются только значения переменных из соответствующих отношений. Например, когда в первом примере пишем <font color = blue>$\exists$</font>S, это означает, что существует кортеж в отношении Students, для которого выполняется дальнейшее условие.
  
 
== Примеры ==
 
== Примеры ==
Переменные:
+
Самый простой пример {{---}} можно задавать переменные, как уже было ранее показано:
 
  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

Текущая версия на 19:34, 4 сентября 2022

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

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

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

Синтаксис

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

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

Примеры

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