Основы реляционного исчисления

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

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

Формулы реляционного исчисления могут быть описаны математически, но в последнее время принят способ описания, более близкий к языку SQL. Рассмотрим в этом виде основы реляционного исчисления с переменными-кортежами.

Переменные-кортежи определяются оператором Range. Например, оператор Range S is Student описывает переменную S, которая может принимать значение любого кортежа отношения Student.

Правильные формулы реляционного исчисления WFF (Well-Formed Formula) определяются рекурсивно и принимают значения TRUE или FALSE. Простейший вид формулы это сравнение, например, Student.Age < 20 или Student.Out > Student.In. Здесь Age, Out, In – названия полей отношения Student. Выражения, постоенные из WFF с помощью логических операций Not, And, Or также являются WFF.

Далее введем кванторы существования Exists (существует, имеется, найдется, для некоторых) и всеобщности Forall (все, всякий, любой, каждый). Выражения типа Exists S (Form) и Forall S (Form), где S - переменная-кортеж, а Form – WFF, также будем считать WFF. Эти выражения имеют смысл: “существует значение S, для которого выполняется выражение Form” и “для всех S выполняется выражение Form”.

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

Пусть, например, переменные S и T определены на отношении Student, и T имеет значение текущего кортежа. Тогда формула Exists S (S.Age < T.Age) принимает значение TRUE, если найдется кортеж S, удовлетворяющий условию, то есть значение T.Age не является минимальным.

Для формул со связанными пременными справедливы соотношения

not Exists S (Form) = Forall S (not Form);

not Forall S (Form) = Exists S (not Form).

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

Следующим понятием является целевой список (Target_list). Он определяет столбцы результата и строится из элементов вида

· S.Attr, где S – свободная переменная, Attr – атрибут отношения;

· S – все атрибуты отношения;

· New_name = S.Attr – новый преименованный атрибут.

Выражение реляционного исчисления определяется как

Target_list Where WFF

Рассмотрим, например, отношение Student (Name, Gr, Subj, Mark), содержащее данные о результатах прошедшей сессии. Будем считать, оцнка всегда присутствует и может быть как удовлетворительной, так и нет. Пусть требуется определить список групп, в которых нет неудовлетворительных оценок.

Введем переменные S и T на множестве кортежей отношения Student.

Range S, T is Student

Выражение S.Gr Where S.Mark ≠ 2 не будет определять правильный результат, поскольку даст те группы, в которых есть положительные оценки, а не те, в которых их нет.

Выражение S.Gr Where Not Exists S (S.Mark = 2) также неправильно, но по другой причине. Дело в том, что здесь два применения переменной с именем S, и они не связаны между собой. В первом случае переменная S свободная, а во втором – связанная. Поэтому, вероятно, правильнее говорить о связанном или свободном вхождении в формулу экземпляров переменных. Аналогично, в языке программирования можно использовать одну переменную для разных целей.

Правильный результат даст выражение

S.Gr Where Not Exists T (S.Gr = T.Gr and S. Mark = 2)

В каком соотношении находятся между собой реляционная алгебра и реляционное исчисление? Оказывается, что все базовые операции реляцинной алгебры можно представить выражениями реляционного исчисления, то есть реляционная алгебра “выводится” из реляционного исчисления. С другой стороны, выражениями реляционного исчисления в явном виде описываются последовательностью операций реляционной алгебры. Принято говорить, что реляционная алгебра и реляционное исчисления обладают одинаковой выразительной силой.

В качестве примеров можно назвать такие языки реляционного исчисления как ALPHA, предложенный Э.Коддом, QUEL из СУБД Ingres и, конечно, SQL. Необходимо отметить, что нет “чистых” языков реляционного исчисления. Некоторые операторы, имеющие процедурный характер, можно в лучшем случае связать с реляционной алгеброй. Впрочем, даже наиболее известный своей декларативностью язык PROLOG имеет такой процедурный оператор, как Cut, предназначенный для явного управления процессом вычислений.

Дата добавления: 2014-01-07