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

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

Исчисление кортежей при прежних обозначениях определяется шестеркой

(4.1)

и имеет выражение {x(R)|f(x)}, где f – разрешенная формула над U; х – свободная переменная.

Исчисление кортежей – формализованная система обозначений и правил для записи выражения нового правила.

Для описания операций в исчислении кортежей возможно использовать предложенный Э. Коддом язык АЛЬФА. В нем [91 используются следующие операторы: get w – получить из рабочей области w; range – область; hold – найти (первичный ключ запоминает место кортежей); put – включить; having – принадлежащий; update – обновить; insert – вставить; delete – уничтожить; up, down – (сортировка) по возрастанию, убыванию; count – считать (число записей); total – общий итог. Применяются следующие обозначения: Y, X – множество элементов данных из домена X в реляционном отношении Y; $ – существует; " – любой; È – ИЛИ; Ç – И; ù – НЕ; "х" – символ значения х.

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

Каждый пользователь обладает своей рабочей областью w (область связи между пользователем и моделью данных). В рабочую область w попадают данные, отобранные в результате поиска (рис. 4.3). Рабочая область w содержит отношения, выделенные из МД посредством оператора get. Отношение имеет форму таблицы.

После завершения работы оператора get содержимое w может обрабатываться любым способом, который допускают базовые языки программирования. Оператор get обеспечивает всегда прямой поиск (по значениям, условиям для данных) последовательно, но не по адресу. Единицей доступа в языке РИ является экземпляр логической записи (кортеж). Пользователь может определить в операторе get любую выборку доменов из одного или нескольких отношений.

На основе исчисления кортежей построен декларативный язык программирования Structured Query Language (SQL).

Рис. 4.3. Схема выполнения запроса

Пример 4.4. Иллюстрацию основных операций на языке РИ будем проводить на следующих отношениях [9]:

СТУД(CH, СФ, Балл, Курс, Группа, Кафедра),

ПРЕП(ПН, ПФ, Должность, Кафедра, Зарплата, Надбавка),

СТПР(СН, ПН, Часы),

где СТУД, ПРЕП, СТПР – отношения Студент, Преподаватель, Студент-Преподаватель; СН, СФ – номер зачетной книжки и фамилия студента соответственно; ПН, ПФ – табельный номер и фамилия преподавателя соответственно.

Вариантов описания запросов очень много, поэтому рассмотрим их основные классы.

I. Операторы поиска:

а) простой поиск – получить фамилии студентов (избыточные дублирующие значения не помещаются в рабочую область w)

get w(СТУД.СФ);

На языке SQL ему соответствует команда

SELECT СТУД.СФ FROM Студ;

Более подробно язык SQL рассмотрен в гл. 5.

б) поиск с использованием кванторов $ и " и логических операций – существуют ли фамилии студентов такие; табельный номер преподавателя – 2486

range СТПРх

get w(СТУД.СФ): х (Х.СН = СТУД.СНХ.ПН = '2486');

II. Операции обновления:

а) простое обновление – заменить название кафедры ИиУС у преподавателя с табельным номером 2486

hold w (ПРЕП.ПН, ПРЕП.Кафедра): ПРЕП.ПН = 2486 w.Кафедра = ИиУС

update w;

б) простое включение – включить (put) в отношение запись о студенте с номером зачетной книжки 857 Петрове: балл – 3, курс – 4, группа И4, кафедра ИиУС

w.CH = 857

w.CФ = Петров

w.Бал 3

w.Kyp c= 4

w.Группа = И4

w.Кафедра = ИиУС

put w(CTУД);

в) удаление – удалить данные о студентах, имеющих балл менее 3

hold w(CTУД): СТУД.Балл < 3

delete w;

д) обновление основного ключа – заменить табельный номер преподавателя с № 785 на № 127

hold w(ΠΡΕΠ): ПРЕП.ПН = 785

delete w

w.ΠΗ = 127

put w(ΠΡΕΠ).

III. Вычисляемые операции (библиотечные функции):

а) количество записей о студентах

get w(count(CTУД.CH));

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

Запрос: найти номера, фамилии и баллы студентов 4 курса группы И4 кафедры ИиУС

{X Y Z | СТУД (X Y Z 4 И4 ИиУС)}.

Запрос: получить фамилии преподавателей и количество часов

{XYP | $Z$L$M$N$Q(ΠΡΕΠ{Ζ ИиУС Μ N X Р) Ç СТПР(Q Z Υ))}.

В общем виде – это выражения

(а1 .. аn | (Çb1) ... (Çbm) (R1(c11 ... c1k))... (Rp(cp1 ... cpk ))},

где сij – некоторые значения аi, bi, появляющиеся не менее одного раза, или константы. Все переменные неявно связаны квантором существования и отображаются подчеркнутыми символьными строками. Неподчеркнутые строки являются константами. Вывод на печать помечается символом Р.(print), за которым возможно указание имени переменной (например Ρ.A).

На основе исчисления доменов М.М. Злуфф, как отмечено в [9], создал [9] визуальный декларативный язык программирования Query By Example (QBE).

В силу своей универсальности язык SQL (точнее SQL2) получил широкое распространение в современных реляционных БД и будет подробнее рассмотрен в гл. 5.

В свете сказанного закономерно возникает вопрос о сопоставлении РА и РИ в смысле полноты и замкнутости операций преобразования таблиц.

Общим для РА и РИ (рис. 4.4) является простота, независимость данных от физической организации и физических методов доступа.

Достоинством реляционной алгебры является возможность доказательства полноты системы операций. Однако операции реляционной алгебры соответствуют процедурным языкам, что характерно для разработчиков и пользователей-программистов и не очень удобно для пользователей-непрограммистов. Операция реляционного исчисления реализуется в виде декларативных языков программирования, что для пользователя предпочтительнее. Иными словами, РА дополняется РИ. В то же время доказательство полноты системы операций в реляционном исчислении затруднительно.

Доказано [4, 10, 11] однозначное соответствие групп операций реляционной алгебры и реляционного исчисления. Это одновременно является доказательством полноты и замкнутости системы операций в РИ и возможности перехода к декларативным языкам типа SQL.

Рис. 4.4. Соотношения реляционного исчисления и реляционной алгебры