БАЗИСНЫЕ СРЕДСТВА МАНИПУЛИРОВАНИЯ РЕЛЯЦИОННЫМИ ДАННЫМИ

Выделяют два теоретических языка обработки реляционных данных — реляционная алгебра и реляционное исчисление.

Реляционная алгебра

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

Рис. 6. Основные операции реляционной алгебры

Реляционная алгебра как теоретический язык запросов, по сравнению с реляционным исчислением, более наглядно описывает выполняемые над отношениями действия. Примером языка запросов, основанного на реляционной алгебре, является ISBL (Information System Base Language — базовый язык информационных систем). Языки запросов, построенные на основе реляционной алгебры, в современных СУБД широкого распространения не получили. Однако знакомство с ней полезно для понимания сути реляционных операций, выражаемых другими используемыми языками.

Вариант реляционной алгебры, предложенный Э.Ф. Код- дом (E.F. Codd), включает в себя следующие основные операции: объединение, разность (вычитание), пересечение, декартово (прямое) произведение (или произведение), выборка (селекция, ограничение), проекция, деление и соединение. Упрощенное графическое представление этих операций приведено на рисунке 6.

По справедливому замечанию К.Дж. Дейта (C.J. Date), реляционная алгебра Э. Кодда обладает несколькими недостатками. Во-первых, восемь перечисленных операций по охвату своих функций, с одной стороны, избыточны, так как минимально необходимый набор составляет пять операций: объединение, вычитание, произведение, проекция и выборка. Три другие операции (пересечение, соединение и деление) можно определить через пять минимально необходимых. Так, например, соединение — это проекция выборки произведения.

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

Рассмотрим перечисленные операции более подробно, сначала — операции реляционной алгебры Э. Кодда, а затем — дополнительные операции, введенные К. Дейтом. Операции реляционной алгебры Э. Кодда можно разделить на две группы:

• 1) базовые теоретико-множественные и специальные реляционные. Первая группа операций включает в себя классические операции теории множеств: объединение, разность, пересечение и произведение.
• 2) развитие обычных теоретике-множественных операций в направлении к реальным задачам манипулирования данными, в ее состав входят следующие операции: проекция, селекция, деление и соединение.

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

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

Объединением двух совместимых отношений R1 и R2 одинаковой размерности (R UNION R2) является отношение R, содержащее все элементы исходных отношений (за исключением повторений).

Пример: пусть отношением RI будет множество поставщиков из Москвы, а отношение R2 — множество поставщиков, которые поставляют деталь Р. Тогда отношение R обозначает поставщиков, находящихся в Москве, или поставщиков, выпускающих деталь Pi, либо тех и других.

R1

R2

R (R UNION R2)

Вычитание совместимых отношений RI и R2 одинаковой размерности (R MINUS R2) есть отношение, тело которого состоит из множества кортежей, принадлежащих R1, но не принадлежащих отношению R2. Для тех же отношений R и

R2 из предыдущего примера отношение R будет представлять собой множество поставщиков, находящихся в Москве, но не выпускающих деталь Р1, т. е. R = {(54, Николай, 20, Москва)}.

Заметим, что результат операции вычитания зависит от порядка следования операндов, т. е. R MINUS R2 и R2 MINUS R1 — не одно и то же.

Пересечение двух совместимых отношений R и R2 одинаковой размерности (R INTERSECT R2) порождает отношение R с телом, включающим в себя кортежи, одновременно принадлежащие обоим исходным отношениям. Для отношений R и R2 результирующее отношение R будет означать всех производителей из Москвы, выпускающих деталь Р. Тело отношения R состоит из единственного элемента (51, Сергей, 20, Москва).

Произведение отношения R степени к и отношения R2 степени к2 (R TIMES R2), которые не имеют одинаковых имен атрибутов, есть такое отношение R степени (к + к2), заголовок которого представляет сцепление заголовков отношений RI и R2, а тело — имеет кортежи, такие, что первые к элементов кортежей принадлежат множеству Л1, а последние к2 элементов — множеству /?2.При необходимости получения произведения двух отношений, имеющих одинаковые имена одного или нескольких атрибутов, применяется операция переименования RENAME, рассматриваемая далее.

Пример: пусть отношение R представляет собой множество номеров всех текущих поставщиков {51, 52, 53, 54, 55}, а отношение R2 — множество номеров всех текущих деталей {Р, Р2, РЗ, Р4, Р5, Р6}. Результатом операции Rl TIMES R2 является множество всех пар типа «поставщик—деталь», т. е. {(51, Р), (51, Р2), (51, РЗ), (51, Р4), (51, Р5), (51, Я>), (52, Р) ... (55, Р6)).

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

Выборка (R WHERE f) отношения R по формуле / представляет собой новое отношение с таким же заголовком и телом, состоящим из таких кортежей отношения R, которые удовлетворяют истинности логического выражения, заданного формулой / Для записи формулы используются операнды — имена атрибутов (или номера столбцов), константы, логические операции (AND — И, OR — ИЛИ, NOT — НЕ), операции сравнения и скобки.

Примеры:

Р WHERE Вес < 14

SP WHERE П# = "SI" AND Д# = "Р"

Проекция отношения А на атрибуты X, Y, ..., Z (А[Х, Y, ..., Z]), где множество {X, Y, ..., Z} является подмножеством полного списка атрибутов заголовка отношения А, представляет собой отношение с заголовком X, Y, ..., Z и телом, содержащим кортежи отношения А, за исключением повторяющихся кортежей. Повторение одинаковых атрибутов в списке X, Y, ..., Z запрещается.

Операция проекции допускает следующие дополнительные варианты записи:

• — отсутствие списка атрибутов подразумевает указание всех атрибутов (операция тождественной проекции);
• — выражение вида R[ ] означает пустую проекцию, результатом которой является пустое множество;
• — операция проекции может применяться к произвольному отношению, в том числе и к результату выборки.

Пример:

Проекция /ЧТип, Город Д]

(S WHERE Город П = "Киев")

Результатом деления отношения RI с атрибутами А и В на отношение R2 с атрибутом В (R DIVIDE BY R2), где А и В простые или составные атрибуты, причем атрибут В — общий атрибут, определенный на одном и том же домене (множестве доменов составного атрибута), является отношением R с заголовком А и телом, состоящим из кортежей /'таких, что в отношении R1 имеются кортежи (г, s), причем множество значений s включает множество значений атрибута В отношения R2.

Пример:

R1

R2

R DIVIDEBY R2

Соединение C^R 1, R2) отношений RX и /?2 по условию, заданному формулой f представляет собой отношение R, которое можно получить путем декартова произведения отношений RI и R2 с последующим применением к результату операции выборки по формуле / Правила записи формулы / такие же, как и для операции селекции.

Важными с практической точки зрения частными случаями соединения являются эквисоединение и естественное соединение.

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

Операция естественного соединения (join) применяется к двум отношениям, имеющим общий атрибут. Этот атрибут в отношении имеет одно и то же имя и определен на одном и том же домене.

Результатом операции естественного соединения является отношение R, которое представляет собой проекцию эквисоединения отношений R1 и R2 по общему атрибуту на объединенную совокупность атрибутов обоих отношений.

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

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

Реляционное исчисление происходит от части символьной логики, которая называется исчислением предикатов.

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

Если предикат содержит переменную (например, «х является студентом этой группы»), то у этой переменной должна быть соответствующая область определения (при подстановке одних значений из ее области определения суждение может быть истинным, а при подстановке других — ложным).

Если Р — предикат, то множество всех значений переменной х, при которых Р становится истинным: {х Р(х)}.

Предикаты могут соединяться с помощью логических операторов: д (AND), v (OR) и ~ (NOT) (при этом образуются составные предикаты). Реляционное исчисление существует в двух формах:

1. Реляционное исчисление кортежей (Кодд).

Задача реляционного исчисления кортежей — нахождение таких кортежей, для которых предикат является истинным.

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

Предикат Р называется формулой (в математической логике - правильно построенной формулой (WFF - well formed formula)).

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

• — квантор существования (3 — «существует») означает, что в отношении есть хотя бы один кортеж, для которого формула истинна;
• — квантор общности (V — «для всех») означает, что формула будет истинна только для всех кортежей отношения.

Переменные кортежа называются свободными, если они не квалифицируются кванторами 3 и V, иначе они называются связанными переменными.

В реляционном исчислении не каждая последовательность формул является допустимой (т. е. не двусмысленной и не бессмысленной). Правила построения WFF:

• — если Р является я-арной формулой (предикатом с п аргументами), a t_v t₂, ..., t_n — это константы или переменные, то выражение P(t_v t₂, ..., t_n) — правильно построенная формула;
• — если и t₂ — константы или переменные из одного домена, а 0 представляет собой один из операторов сравнения

• (<, <=, >, >=, =, ~=), то выражение t_x 0 /₂ — правильно построенная формула;
• - если выражения F и F2 — формулы, то их конъюнкция (логическое «И») обозначается как F л F2, дизъюнкция (логическое «ИЛИ») — FI v F2, а отрицание — -FI;
• - если выражение F является формулой со свободной переменной X, то выражения 3F(X) и /F(X) — также являются формулами;
• - все результирующие значения должны входить в область определения формулы (обычно область определения задается как RANGE OF переменная кортежа IS имя отноше- ния1 (выражение_исчисления_кортежей1), имя_отношения2 (выражение_исчисления_кортежей2), ... (замечание: все отношения при этом должны иметь идентичные заголовки)).

Например, есть два отношения STUDENT(STUD_ ID, NAME, CITY, GROUP ID) — данные о студенте и GROUP(GROUP ID, NAME, CITY) - данные о группе:

• - RANGE OF N IS STUDENT, {N | N.STUD_ID > 1000} - получить значения всех кортежей (N — переменная кортежа, содержит текущий кортеж определенный на отношении STUDENT в текущее время), значение атрибута STUDID у которых больше 1000;
• - RANGE OF N IS STUDENT, RANGE OF GIS GROUP, {N.NAME, N.CITY | 3G (G.GROUPJD = N.GROUP_IDG. NAME = «012345»)} — получить имя студента и город (значения NAME и CITY отношения STUDENT), если есть хотя бы один кортеж отношения GROUP, в котором значение атрибута GROUP_ID равно значению GROUP ID в текущем кортеже N и номер группы GROUP = «012345»;
• - RANGE OF N IS STUDENT, RANGE OF GIS GROUP, {N.NAME | VG (G.CITY ~= N.CITY)} - получить имена студентов, город проживания которых не совпадает с расположением ни одной группы (что эквивалентно {N.NAME | -3G (G.CITY = N.CITY)}).

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

2. Реляционное исчисление доменов (Лакруа и Пиро).

В реляционном исчислении доменов используются переменные, значения которых берутся из доменов (а не из кортежей отношений). Если P{a_x:d_v a₂:d₂, a_n:d') — предикат с

переменными домена d_v d₂, ..., d_n (определенными на атрибутах д, а₂, ..., а_п соответственно), то множество переменных домена, для которых предикат истинен:

{flfp d₂, ..., d_n | P{a_vd_v o₂.d₂, ..., ci_n.d_и)}.

Задача реляционного исчисления доменов — проверить условие принадлежности, т. е. определить, принадлежат ли значения указанному отношению (например, выражение R(x x, }>:<•%») считается истинным тогда и только тогда, когда в отношении R имеется кортеж со значениями гх (переменная домена — содержит текущее значение атрибута) и «^(литерал - константа) в его атрибутах х и у соответственно.

Например, есть отношение STUDENT(STUD ID, NAME, RATING) — данные о студенте:

{N | 3R (STUDENT(NAME:N, RATING:R) л R > 7.8)} - получить значения всех студентов с рейтингом больше 7,8 (проверка, существует ли кортеж с атрибутами NAME (переменная N) и RATING (переменная R) в отношении STUDENT, причем значение атрибута RATING в этом кортеже > 7,8).

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

Связь реляционного исчисления и реляционной алгебры

Существует алгоритм («алгоритм редукции Кодда»), с помощью которого выражение реляционного исчисления (кортежей) можно преобразовать в семантически эквивалентное выражение реляционной алгебры (т. е. реляционная алгебра и реляционное исчисление эквивалентны - каждому выражению в реляционной алгебре соответствует эквивалентное выражение в исчислении и наоборот).

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

Реляционно-полный язык — язык, по своим возможностям не уступающий реляционному исчислению или реляционной алгебре (т. е. реализующий операции, эквивалентные основным операциям реляционной алгебры). Желательно, чтобы в таком языке была и вычислительная полнота (наличие большинства вычислимых функций (+, —, * и т. п.)).

• Ш ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
• 1. Дайте определение реляционной алгебры.
• 2. Дайте определение совместимости структур отношений.
• 3. Перечислите операции реляционной алгебры.
• 4. Дайте определение реляционного исчисления.
• 5. Назовите формы реляционного исчисления.
• 6. Опишите реляционное отношение кортежей.
• 7. Опишите реляционное отношение доменов.
• 8. Укажите значение квантора существования и всеобщности.
• 9. В чем связь между реляционной алгеброй и реляционным исчислением?
• 10. Почему реляционная алгебра и реляционное исчисление называются логически эквивалентными языками?