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

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

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

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

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

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

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

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

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

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

а) { 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 ("запрос по образцу").

Лекция 9. Язык SQL. Часть 1.