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

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

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

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

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

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

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

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

где прописными буквами записаны ключевые слова языка, <переменная > - идентификатор переменной кортежа (области значений), а <список> - последовательность одного или более элементов, разделенных запятыми, т.е. конструкции вида Х₁[, X₂[…,X_n]…].

Конструкция RANGE указывает идентификатор переменной и область ее допустимых значений. Список элементов Х₁[, X₂[…,X_n]…] содержит элементы, каждый из которых является либо отношением, либо выражением над отношением. Все элементы списка должны быть совместимы по типу, т.е. соответствующие элементам отношения должны иметь идентичные заголовки. Область допустимых значений <переменной> образуется путем объединения значений всех элементов списка. Так, запись вида RANGE OF T IS X1,X2 означает, что область определения переменной Т включает в себя все значения из отношения, которое является объединением отношений Х1 и Х2.

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

RANGE OF D IS R9;

RANGE OF DC IS R10;

RANGE OF SD IS (R12) WHERE R12.Материал = ‘Сталь-ст1’;

Переменные D, DC в первых двух примерах определены соответственно на отношениях R9 и R10. Переменная SD может принимать значения из множества кортежей отношения R12, где материал совпадает с материалом Сталь-ст1.

Запись выражения, формирующего запрос на языке исчисления кортежей с помощью формы Бэкуса-Наура, упрощенно можно представить следующим образом:

<выражение> ::= (y₁[,y₂[…,y_m]…]) [ WHERE wff ]

y_i ::= {<переменная> | <переменная>, <атрибут> } [AS <атрибут>] wff ::= <условие>| NOT wff |

<условие> AND wff | <условие> OR wff |

IF <условие> THEN wff | EXISTS <переменная> (wff) |

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

Общий смысл записи выражения состоит в перечислении атрибутов результирующего (целевого) отношения, атрибуты которого должны удовлетворять условию истинности формулы wff (well formulated formula – правильно построенная формула). Список атрибутов целевого отношения, или целевой список, в терминах реляционной алгебры по существу определяет операцию проекции, а формула wff – селекцию кортежей.

В паре <переменная>, <атрибут> первая составляющая служит для указания переменной кортежа (определенной конструкцией RANGE), а вторая – для определения атрибута отношения, на котором изменяется переменная кортежа. Необязательная часть AS <атрибут> используется для переименования целевого отношения. Если она отсутствует, то имя атрибута целевого отношения наследуется от соответствующего имени атрибута исходного отношения.

Употребление в качестве элемента целевого отношения Т равносильно перечислению в списке всех соответствующих атрибутов, т.е. Т.А₁, Т.А₂,…, ТА_n, где А₁, А₂,…, А_n – атрибуты отношения, сопоставляемого с переменной Т.

Пример 2. Варианты записи пары <переменная>.<атрибут>.

SD.[Шифр детали]

DC.[Цех] AS Цех_изготовитель

В приведенном определении wff <условие> представляет собой либо формулу wff, заключенную в скобки, либо простое сравнение вида

<операнд1>  <операнд2>,

где в качестве любого операнда выступает переменная или скалярная константа, а символ  обозначает операцию сравнения =, , >, , ,  и т.д.

Ключевые слова NOT, AND, OR обозначают логические операции соответственно: Не, И, ИЛИ. Ключевые слова IF и THEN позволяют задать условие. Ключевые слова EXISTS и FORALL называются кванторами. Первый из них – квантор существования, а второй – квантор всеобщности.

Формула wff вида: EXISTS x (f) означает: «Существует по крайней мере одно такое значение переменной х, что вычисление формулы f дает значение истина».

Выражение вида: FORALL x (f) интерпретируется как высказывание: «Для всех значений переменной х вычисление формулы f дает значение истина».

В общем случае переменные кортежей в формулах могут быть свободными или связанными. В формулах EXISTS x(f) и FORALL x(f) переменные кортежей х всегда являются связанными.

Пример 3. Запись выражения.

Приведем запись выражения, соответствующего запросу: «Получить названия цехов, где производится деталь «Гайка М1».

D.[Цех] WHERE EXISTS R9 (D.[Название детали]=’Гайка М1’ )

Вариант реляционного исчисления, основанного на доменах (исчисление доменов), предложен Лакроиксом и Пиротте (Lacroix and Pirotte), которые также разработали на его основе соответствующий язык ILL. Другими языками, основанными на исчислении доменов, являются: FQL, DEDUCE, QBE. По утверждению Дейта, язык QBE включает элементы исчисления кортежей и исчисления доменов, но более близок ко второму. Он не является реляционно полным, так как не поддерживает операцию отрицания квантора существования (NOT EXISTS).

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

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

R(A₁:₁, A₂:₂,…),

где A_i – атрибут отношения R, а _i – переменная домена или литерал. Проверяемое условие истинно, если и только если существует кортеж в отношении R, имеющий атрибуты А, равные заданным в выражении соответствующим значениям .

Например, выражение R12 ([Шифр детали] : ‘003412’, Материал :’Сталь-ст1’) истинно, если в отношении R12 существует хотя бы один кортеж со значением ‘003412’ атрибута Шифр детали и значением ‘Сталь-ст1’ атрибута Материал. Аналогично, выражение R12 ([Шифр детали] : SHD, Материал : M) истинно, если в отношении R12 существует кортеж, в котором значение атрибута [Шифр детали] эквивалентно текущему значению переменной домена SHD, а значение атрибута Материал эквивалентно текущему значению переменной домена М.

В следующих примерах будем подразумевать существование (объявленное каким-либо образом, подобно оператору RANGE исчисления кортежей) следующих переменных доменов: SHD (домен атрибута Шифр детали), HD (домен атрибута Название детали), M (домен атрибута Материал).

Пример 4. Выражения исчисления доменов.

(SHD) WHERE R12 ([Шифр детали] : SHD)

(SHD) WHERE R12 ([Шифр детали] : SHD, Материал : ‘Сталь-ст1’)

Первое выражение означает множество всех шифров деталей отношения R12, второе – множество шифров деталей, изготовленных из материала “Сталь-ст1”.