Исчисление кортежей и его реляционная полнота

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

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

Каждая переменная-кортеж имеет тип.

Тип кортежа

• Имена и типы атрибутов;
• Набор значений.

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

Синтаксис

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

Примеры

S :: Students
G :: Groups
G4 :: Groups where
    Name = 'M34351' ∨
    Name = 'M34371' ∨
    Name = 'M34391'

Последний пример демонстрирует, что для отношения можно указать ограничивающее его условие.

Операции с отношениями

Ограничение

Можно ограничить отношение, выбрав те кортежи, которые удовлетворяют требуемым условиям.

Отношения where Условие

Объединение

Для объединения используется синтаксис перечисления необходимых отношений через запятую.

Отношение1, Отношение2

Примеры

Groups where Name = 'M34371'

G4 :: Groups where Name = 'M34351',
        Groups where Name = 'M34371',
        Groups where Name = 'M34391'

Условия

Простые условия

Сравнение атрибутов с константами:

S.Name = 'Иван'

S.Id < 5

Сравнение атрибутов между собой (в том числе и на неравенство):

S.Id $\geq$ G.Id

Сравнение с применением формул:

length(S.FirstName) = length(S.LastName) + 3

Можно использовать любые формулы, зависящие от значений кортежных переменных.

Составные условия

Из простых условий можно строить логические формулы с помощью стандартных связок: $\land$, $\lor$, $\lnot$.

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)

Про каждую переменную известно, из какого она отношения, поэтому при подстановке в квантор рассматриваются только значения переменных из соответствующих отношений.

Примеры

Переменные:

S :: Students; G :: Groups; C :: Courses; P :: Point;
G4 :: Groups where Name = 'M34351' ∨
    Name = 'M34371' ∨ Name = 'M34391'

Полностью аттестованные группы:

select G.GId from G where ∀S (∀C (∃P
    (S.SId = P.SId ∧ C.CId = P.CId ∧ P.Points ≥ 60)))

Несколько отношений:

select S.FirstName, S.LastName, G.Name
from S, G
where S.GId = G.GId