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

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

Реляционное исчисление основывается на исчислении предикатов, одном из разделов математической логики. Кодд предложил саму концепцию реляционного исчисления и представил «подъязык данных ALPHA», реализующий эту концепцию. Этот язык не был воплощен на практике, но оказал сильное влияние на язык QUEL, который какое-то время оказывал серьезную конкуренцию языку SQL.

Поскольку язык SQL в итоге оказался более популярным и сегодня является стандартом для работы с реляционными данными, мы не будем сильно углубляться в эту тему, а дадим лишь краткий обзор.

Начнем с небольшого сравнения реляционной алгебры и реляционного исчисления.

Предположим, что мы работаем с базой данных, содержащей отношения Студенты (Студент_Номер, Студент_Имя, Студент_Стипендия, Группа_Номер) и Группы (Группа_Номер, Группа_Наименование, Группа_Количество, Группа_Староста), и хотим узнать имена и номера студентов, являющихся старостами групп с количеством студентов в них больше 20.

Если бы для формулировки такого запроса использовалась реляционная алгебра, то мы получили бы алгебраическое выражение, которое читалось бы, например, следующим образом:

· Выполнить соединение отношений Студенты и Группы по условию Студент_Номер = Группа_Староста;

· Ограничить полученное отношение по условию Группа_Количество > 20;

· Спроецировать результат предыдущей операции на атрибут Студент_Имя, Студент_Номер.

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

Выдать Студент_Имя и Студент_Номер для студентов таких, что существует группа с таким же значением Группа_Староста и значением Группа_Количество большим 20.

Во второй формулировке мы указали лишь характеристики результирующего отношения, но ничего не сказали о способе его формирования. В этом случае система должна сама решить, какие операции и в каком порядке нужно выполнить над отношениями Студенты и Группы. Из приведенного примера виден более «процедурный» характер реляционной алгебры и «декларативный» характер реляционного исчисления. Повторим, это отличие внешнее, и существуют правила преобразования выражений друг в друга.

Базисными понятиями исчисления являются понятие переменной с определенной для нее областью допустимых значений и понятие правильно построенной формулы (Well-Formed Formula, WFF), опирающейся на переменные, предикаты и кванторы.

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

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

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

RANGE СОТРУДНИК IS СОТРУДНИКИ

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

Правильно построенные формулы служат для выражения условий, накладываемых на кортежные переменные. Основой WFF являются простые сравнения (comparison), представляющие собой операции сравнения скалярных значений (значений атрибутов переменных или явно заданных констант). Например, конструкция «Студент.Студент_Номер = 140» является простым сравнением. По определению, простое сравнение является WFF, а WFF, заключенная в круглые скобки, является простым сравнением.

Более сложные варианты WFF строятся с помощью логических связок NOT, AND, OR и IF... THEN. Так, если form - WFF, а comp - простое сравнение, то NOT form, comp AND form, comp OR form и IF comp THEN form являются WFF.

Наконец, допускается построение WFF с помощью кванторов. Если form - это WFF, в которой участвует переменная var, то конструкции EXISTS var (form) и FORALL var (form) представляют wff.

Переменные, входящие в WFF, могут быть свободными или связанными. Все переменные, входящие в WFF, при построении которой не использовались кванторы, являются свободными. Фактически, это означает, что если для какого-то набора значений свободных кортежных переменных при вычислении WFF получено значение true, то эти значения кортежных переменных могут входить в результирующее отношение. Если же имя переменной использовано сразу после квантора при построении WFF вида EXISTS var (form) или FORALL var (form), то в этой WFF и во всех WFF, построенных с ее участием, var - это связанная переменная. Это означает, что такая переменная не видна за пределами минимальной WFF, связавшей эту переменную. При вычислении значения такой WFF используется не одно значение связанной переменной, а вся ее область определения.

Пусть Студент1 и Студент2 - две кортежные переменные, определенные на отношении Студенты. Тогда, WFF EXISTS Студент2 (Студент1.Студент_Стипендия > Студент2.Студент_Стипе-ндия) для текущего кортежа переменной Студент1 принимает значение true в том и только в том случае, если во всем отношении Студенты найдется кортеж (связанный с переменной Студент2) такой, что значение его атрибута Студент_Стипендия удовлетворяет внутреннему условию сравнения.

WFF FORALL Студент2 (Студент1.Студент_Стипендия > Студент2.Студент_Стипендия) для текущего кортежа переменной Студент1 принимает значение true в том и только в том случае, если для всех кортежей отношения Студенты (связанных с переменной Студент2) значения атрибута Студент_Стипендия удовлетворяют условию сравнения.

Итак, WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена столбцов результирующего отношения. Этот компонент называется целевым списком (target_list).

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

var.attr, где var - имя свободной переменной соответствующей WFF, а attr - имя атрибута отношения, на котором определена переменная var;

var, что эквивалентно наличию подсписка var.attr1, var.attr2,..., var.attrn, где attr1, attr2,..., attrn включает имена всех атрибутов определяющего отношения;

new_name = var.attr; new_name - новое имя соответствующего атрибута результирующего отношения.

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

Выражением реляционного исчисления кортежей называется конструкция вида target_list WHERE wff. Значением выражения является отношение, тело которого определяется WFF, а набор атрибутов и их имена - целевым списком.

В исчислении доменов областью определения переменных являются не отношения, а домены. Применительно к базе данных Студенты-Группы можно говорить, например, о доменных переменных Имя (значения - допустимые имена) или Номер_Группы (значения - допустимые номера групп).

Основным формальным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяющих выражать так называемые условия членства. Если R - это n-арное отношение с атрибутами a1, a2,..., an, то условие членства имеет вид

R (ai1:vi1, ai2:vi2,..., aim:vim) (m <= n),

где vij - это либо литерально задаваемая константа, либо имя кортежной переменной. Условие членства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения указанных атрибутов. Если vij - константа, то на атрибут aij задается жесткое условие, не зависящее от текущих значений доменных переменных; если же vij - имя доменной переменной, то условие членства может принимать разные значения при разных значениях этой переменной.

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

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