7.3. Выводы

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

Традиционно определяют восемь реляционных операторов, объединенных в две группы.

Теоретико-множественные операторы: объединение, пересечение, вычитание, декартово произведение.

Специальные реляционные операторы: выборка, проекция, соединение, деление.

Для выполнения некоторых реляционных операторов требуется, чтобы отношения были совместимы по типу.

Не все операторы реляционной алгебры являются независимыми - некоторые из них выражаются через другие реляционные операторы. Операторы соединения, пересечения и деления можно выразить через другие реляционные операторы, т.е. эти операторы не являются примитивными. Оставшиеся реляционные операторы (объединение, вычитание, декартово произведение, выборка, проекция) являются примитивными операторами - их нельзя выразить друг через друга.

Имеется несколько типов запросов, которые нельзя выразить средствами реляционной алгебры. (К ним относятся запросы, требующие дать в ответе список атрибутов, удовлетворяющих определенным условиям, построение транзитивного замыкания отношений, построение кросс-таблиц. Для получения ответов на подобные запросы приходится использовать процедурные расширения реляционных языков)

Лекция 8. Реляционное исчисление.

1. Элементы реляционного исчисления.

2. Реляционное вычисление кортежей.

3. Реляционное вычисление доменов.

8.1. Элементы реляционного исчисления

В отличие от реляционной алгебры (процедурный подход), реляционное исчисление реализует декларативный (описательный) подход к выполнению операций над данными, поскольку оно лишь описывает свойства желаемого результата в виде логической формулы.

Основная идея состоит в том, чтобы любую операцию над отношениями описать в виде правильной формулы. СУБД, основанные на реляционном исчислении, автоматически распознают эти формулы и выполняют требуемые преобразования над данными. Достоинством такого подхода является то, что он позволяет построить непроцедурные языки манипулирования данными.

Базисными понятиями реляционного исчисления являются:

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

- понятие правильно построенной формулы, опирающейся на переменные, предикаты и кванторы.

Аналитические выражения записывают в одной из следующих форм:

а) { t | Y (t) } - читается так: “множество переменных t таких, что истинна формула Y “

б) { t1, t2, ... tk | Y ‘ ( t1, t2, ... tk ) }

где t - переменная - кортеж,

t1,...tk - переменные на доменах,

k - ранг отношения,

Y - формула, построенная из атомов.

В зависимости от того, что является областью определения переменной, различают исчисление кортежей и исчисление доменов. В первом случае (а)) в качестве значений переменных используются кортежи, во втором (б)) - домены.

8.2. Реляционное исчисление кортежей

Атомы формул Y могут быть трех типов:

1. R(S) - означает, что S - это кортеж в отношении R

2. s[i] @ u[j] - означает, что i-ая компонента S и j-ая компонента U связаны оператором сравнения (< > =). Например: s[1] < u[3] справедливо для кортежей s = (1, 6, 6, 6) и u = (2, 2, 5, 2)

3. s[i] @ const или const @ s[i], - аналогичная п.2 связь с константой. Например, s[3] = “СИДОРОВ”

Формулы составляются из атомов по следующим правилам:

1. Каждый атом - это формула

2. Если Y 1иY 2- формулы, тоY 1 Щ Y 2, Y 1 Ъ Y 2, Ш Y 1- тоже формулы.

3. Если Y- формула, то($ s) (Y ) - тоже формула, которая утверждает, что существует такое значение переменной S, при которомYистинна.

4. Если Y - формула, то (" s) (Y )- тоже формула, которая утверждает, что при подстановке любого значения переменнойSв формулуYона остается истинной.

5. Порядок старшинства операций в формулах: операторы сравнения (< > = и т.п.), $ , " , Ш ,Щ ,Ъ

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

При использовании кортежных переменных можно ссылаться на отдельный атрибут этой переменной, например: если S = (5, Иванов, 500, 3) - это кортеж отношения СОТРУДНИКИ (номер, имя, оклад, отдел), то S[3] = 500 - это значение третьего атрибута данного кортежа (оклад). На практике в языках, основанных на реляционном исчислении, часто вместо номера атрибута используют его имя, например, вместо S[3] пишут S.Оклад, что более наглядно.

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

Если же имя переменной Х использовано сразу после квантора $ Х или " Х, то она считается связанной переменной, которая не видна за пределами формулы, описанной в кванторе. При вычислении значения такой формулы используется не одно значение связанной переменной, а вся ее область определения. Например, пусть Х и Y - две кортежные переменные, определенные на отношении СОТРУДНИКИ. Тогда, формула

$ Y (Х.Оклад > Y.Оклад)

для текущего значения Х истинна в том и только в том случае, если во всем отношении СОТРУДНИКИ найдется кортеж Y такой, что значение его атрибута Оклад удовлетворяет заданному условию сравнения.

Чтобы описать, какие атрибуты кортежа должны входить в результирующее отношение, используют целевой список, который может состоять из следующих элементов:

1. Х.А где Х - имя свободной переменной, а А - имя атрибута отношения

2. Х, то есть имена всех атрибутов отношения

3. N = X.A, где N - новое имя атрибута результирующего отношения (когда используются несколько переменных с одинаковой областью определения)

В реальных языках БД вместо математических обозначений кванторов и логических связок используют, как правило, словесные обозначения:

$	EXISTS	Ш	NOT
"	FORALL	Щ	AND
|	WHERE	Ъ	OR

Таким образом, аналитическое выражение реляционного исчисления кортежей можно записать в виде:

ЦелевойСписок WHERE Формула.

Значением выражения является отношение, тело которого определяется формулой, а набор атрибутов и их имена - целевым списком. На основе рассмотренного исчисления построен язык SQL.

8.3. Реляционное исчисление доменов

В этом исчислении переменные являются доменами. Например, в базе данных СОТРУДНИКИ-ОТДЕЛЫ можно говорить о доменных переменных ИМЯ (значения - допустимые имена) или НОМЕР (значения - допустимые номера сотрудников). Основным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяющих выражать так называемые условия членства.

Если R - это отношение с атрибутами a₁, a₂, ..., a_n, то условие членства имеет вид

R (a_i1: v_i1, a_i2: v_i2,..., a_im: v_im) (m <= n), где v_ij - это либо константа, либо имя доменной переменной. Условие членства истинно в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения указанных атрибутов.

Во всем остальном формулы и выражения этих двух видов реляционного исчисления похожи. Реляционное исчисление доменов является основой для большинства языков запросов, основанных на использовании форм, в частности, для популярного табличного языка запросов к БД Query-by-Example ("запрос по образцу").