Реляционное исчисление.

В отличие от реляционной алгебры, которая указывает, как получить требуемое отношение из имеющихся отношений, реляционное исчисление указывает свойства искомого отношения без конкретизации процедуры его получения. Математической основой реляционного исчисления является исчисление предикатов – один из разделов математической логики. В теории исчисления предикатов под предикатом понимается функция, значения которой являются высказывания. Высказывание может быть истинным или ложным. Чтобы задать n-местный предикат P(x₁,…,x_n), следует указать множества D₁,…, D_n – области изменения предметных переменных x₁,…,x_n. Синтаксически задание n-местного предиката осуществляется указанием формулы логико-математического языка, содержащей n переменных. В наиболее распространённом случае такой язык содержит предметные переменные x, y, z,…, функциональные символы f, g, h,… с различным количеством аргументных мест и предикатные символы P, Q, R,… также с различным количеством аргументных мест. Из переменных и функциональных символов конструируются термы языка, содержательно интерпретируемые как имена объектов исследования. Если P есть n-местный предикатный символ, n³0, а t₁,…,t_n – термы, то P(t₁,…,t_n) есть, по определению, атомарная формула. Содержательно P(t₁,…,t_n) означает, что истинно высказывание, гласящее, что t₁,…,t_n связаны отношением P. Из атомарных формул с помощью пропозициональных связок и кванторов конструируются формулы языка. Обычный набор связок состоит из операторов сравнения, а набор кванторов включает конъюнкцию, дизъюнкцию, импликацию, отрицание, квантор “для всех”, квантор “существует”. Вхождения переменной x в формулу j называется связанным, если x входит в часть j вида $xj или "xj. Остальные вхождения называются свободными.

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

RANGE OF <переменная> IS <список>.

Здесь <переменная> – это идентификатор переменной кортежа, <список> – конструкция вида X₁[,X₂[,…,X_n]…]. Список содержит элементы, каждый из которых является либо отношением, либо выражением над отношениями. Область допустимых значений <переменной> образуется путем объединения значений всех элементов списка. Выражение реляционного исчисления, формирующего запрос на языке исчисления кортежей, упрощенно можно записать в виде:

(Y₁[,Y₂[…,Y_m]…]) [WHERE wff].

Здесь Y_i – это запись вида

{<переменная> ½<переменная>.<атрибут>} [AS <атрибут>]

Соответственно, wff – well-formed formula (правильно построенная формула) – это предикат, который записывается одним из следующих типов:

<условие>

NOT wff

<условие> AND wff

<условие> OR wff

IF <условие> THEN wff

EXISTS <переменная> (wff)

FORALL <переменная> (wff)

(wff)

Например, предположим, что имеется три отношения, О1, О2, О3,

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

RANGE OF S IS O1

(S.ПР) WHERE S.КАФ=’К1’

Создадим список преподавателей, студентов и часов, для студентов четвёртого курса.

RANGE OF P IS O2

RANGE OF V IS O3

(V) WHERE EXISTS P (V.СТУД=P.СТУД AND P.КУРС=4)

Этот же список можно сформировать следующим образом

RANGE OF P IS O2

RANGE OF V IS O3

RANGE OF VP IS (V) WHERE EXISTS P (V.СТУД=P.СТУД AND P.КУРС=4)

(VP)

В реляционном исчислении доменов используются переменные, значения которых используют переменные, значения которых берутся из доменов, а не из кортежей отношений. Исчисление доменов поддерживает дополнительную форму условий, называемую условием принадлежности. В общем виде условие принадлежности записывается в виде R(A₁:p₁, A₂:p₂,…), где A_i – атрибут отношения R, а p_i – переменная домена или литерал. Условие считается истинным тогда и только тогда, когда в отношении R имеется кортеж со значениями p_i для атрибутов A_i.

Для приведенных выше в примере первого списка выражения исчисления доменов будут иметь вид

(S) WHERE О1 (КАФ : ‘К1’)

Здесь S – переменная домена атрибута ПР, объявленная каким-либо образом, подобно оператору RANGE исчисления кортежей.

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

4. Проектирование реляционных баз данных
на основе нормализации.