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

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

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

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

• S (поставщики);

• Р (детали);

• SP (поставки).

Первичными ключами этих таблиц являются соответственно: П# (код поставщи­ка), Д# (код детали) и составной ключ (П#, Д#). Содержимое таблиц приведено на рис. 3.7. Для удобства изложения предположим, что в рассматриваемых языках зап­росов нет ограничений на употребление символов русского алфавита в именах атри­бутов. Каждое из полей П# и Д# таблицы SP в отдельности является внешним клю­чом по отношению к таблице S и Р соответственно.

Предположим, что имена доменов (множеств допустимых значений) совпадают с именами атрибутов. Исключение составляют атрибуты Город_П (город, в котором находится поставщик) и Город_Д (город, в котором выпускается деталь), которые имеют общий домен: множество названий городов. Имя этого домена может быть, например, просто Город. Характеристики доменов как типов данных следующие: Д# — строка символов длиной 5, Имя — строка символов длиной 20, Статус — цифровое дли­ной 5, Город — строка символов длиной 15, Д# — строка символов длиной 6, Тип — строка символов длиной 6, Вес — цифровое длиной 5, Количество — цифровое длиной 5.

S

П#	Имя	Статус	Город_П
S1	Сергей		Москва
S2	Иван		Киев
S3	Борис		Киев
S4	Николай		Москва
S5	Андрей		Минск

Р

Д#	Название	Тип	Вес	Город_Д.
Р1	гайка	каленый		Москва
Р2	болт	мягкий		Киев
РЗ	винт	твердый		Ростов
Р4	винт	каленый		Москва
Р5	палец	твердый		Киев
Р6	шпилька	каленый		Москва

SP

П#	Д#	Количество
S1	P1
S1	P2
S1	P3
S1	P4
S1	P5
S1	P6
S2	P1
S2	P2
S3	P2
S4 /	P2
S4	P4
S4	P5

Рис. 3.7. Таблицы поставщиков, деталей и поставок

Пусть запрос выглядит следующим образом: " Получить номера и города поставщиков, выпускающих деталь Р2 ".

Словесно алгебраическая версия этого запроса описывается так:

• образовать естественное соединение отношений S и SP по атрибуту П#;

• выбрать из результата этого соединения кортежи с деталью Р2 (в поле Д# должна быть строка Р2);

• спроецировать результат предыдущей операции на атрибуты П# и Город_П. Этот же запрос в терминах реляционного исчисления можно сформулировать примерно так: " Получить атрибуты П# и Город_П для таких поставщиков, для которых существует поставка в отношении SP с тем же значением атрибута П# и со значением Р " атрибута Д# ".

Результатом выполнения запроса будет отношение R вида:

П#	ГородП
S1	Москва
S2	Киев
S3	Киев
S4	Москва

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

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

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

• выбрать из отношения SP кортежи, относящиеся к детали Р2;

• выполнить естественное соединение отношения S и отношения, полученного на предыдущем шаге;

• спроецировать текущее отношение на атрибуты П# и Город_П.

Экономия памяти при реализации этого алгоритма в сравнении с первоначальным вариантом достигается за счет снижения размерности участвующих в операциях временных таблиц, необходимых для хранения промежуточных результатов. Если в предыдущем случае размерность временной таблицы была 12*6 (12 строк на 6 коло­нок), то в последнем случае — 4*6.

Математической основой реляционного исчисления является исчисление предикатов — один из разделов математической логики. Понятие реляционного исчисления как языка работы с базами данных впервые предложено Коддом. Им же был разработан язык ALPHA — прототип программно реализованного языка QUEL, который некоторое время конкурировал с языком SQL.

Существует два варианта исчислений: исчисление кортежей и исчисление доменов. В первом случае для описания отношений используются переменные, допустимыми значениями которых являются кортежи отношения, а во втором случае — элементы домена.

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

Описательную часть исчисления можно представить в виде:

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

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

x1[,x2[,..., xi]...].

Вся конструкция RANGE указывает идентификатор переменной и область ее допустимых значений. Список элементов x1[,x2[,..., xi]...] содержит элементы, каждый. из которых является либо отношением, либо выражением над отношением (порядок записи выражений описывается далее). Все элементы списка должны быть совместимыпо типу, т. е. соответствующие элементам отношения должны иметь идентичные заголовки. Область допустимых значений < переменной > образуется путем объединения значений всех элементов списка. Так, запись вида RANGE OF Т IS X1, Х2 означает, что область определения переменной Т включает в себя все значения, из отношения, которое является объединением отношений X1 и Х2.

Пример 1. Варианты описаний.