V. Решение задач реляционной алгебры
Реляционная алгебра как теоретический язык запросов по сравнению с реляционным исчислением более наглядно описывает выполняемые над отношениями действия.
Примером языка запросов, основанного на реляционной алгебре, является ISBL (Information System Base Language — базовый язык информационных систем). Языки запросов, построенные на основе реляционной алгебры, в современных СУБД широкого распространения не получили. Однако знакомство с ней полезно для понимания сути реляционных операций, выражаемых другими используемыми языками.
Вариант реляционной алгебры, предложенный Коддом, включает в себя следующие основные операции: объединение, разность (вычитание), пересечение, декартово (прямое) произведение (или произведение), выборка (селекция, ограничение), проекция, деление и соединение. Упрощенное графическое представление этих операций приведено на рис. 9.1.
Рисунок 9.1. Основные операции реляционной алгебры
Операции реляционной алгебры Кодда можно разделить на две группы: базовые теоретико-множественные и специальные реляционные. Первая группа операций включает в себя классические операции теории множеств: объединение, разность, пересечение и произведение. Вторая группа представляет собой развитие обычных теоретико-множественных операций в направлении к реальным задачам манипулирования данными, в ее состав входят следующие операции: проекция, селекция, деление и соединение.
Операции реляционной алгебры могут выполняться над одним отношением (например, проекция) или над двумя отношениями (например, объединение). В первом случае операция называется унарной, а во втором — бинарной. При выполнении бинарной операции участвующие в операциях отношения должны быть совместимы по структуре.
Объединением двух совместимых отношений R1 и R2 одинаковой размерности (R1 UNION R2) является отношение R, содержащее все элементы исходных отношений (с исключением повторений).
Пример 1.Объединение отношений.
Пусть отношение обозначает R1 множество поставщиков из Лондона, а отношение R2 — множество поставщиков, которые поставляют деталь Р1. Тогда отношение R обозначает поставщиков, находящихся в Лондоне, или поставщиков, выпускающих деталь Р1, либо тех и других.
R1
| п# | Имя | Статус | Город_П |
| S1 | Сергей | Москва | |
| S4 | Николай | Москва |
R2
| п# | Имя | Статус | Город_Л |
| S1 | Сергей | Москва | |
| S2 | Иван | Киев |
R(R1 UNION R2)
| п# | Имя | Статус | Город_П |
| S1 | Сергей | Москва | |
| S2 | Иван | Киев | |
| S4 | Николай | Москва |
Вычитаниесовместимых отношений R1 и R2 одинаковой размерности (R1 MINUS R2) есть отношение, тело которого состоит из множества кортежей, принадлежащих R1, но не принадлежащих отношению R2. Для тех же отношений R1 и R2 из предыдущего примера отношение R будет представлять собой множество поставщиков, находящихся в Лондоне, но не выпускающих деталь Р1, то есть R={(S4, Николай, 20, Москва)}.
Заметим, что результат операции вычитания зависит от порядка следования операндов, то есть R1 MINUS R2 и R2 MINUS R1 — не одно и то же.
Пересечение двух совместимых отношений R1 и R2 одинаковой размерности (R1 INTERSECT R2) порождает отношение R с телом, включающим в себя кортежи, одновременно принадлежащие обоим исходным отношениям. Для отношений R1 и R2 результирующее отношение R будет означать всех производителей из Лондона, выпускающих деталь Р1. Тело отношения R состоит из единственного элемента (S1, Сергей, 20, Москва).
Произведение отношения R1 степени к1 и отношения R2 степени к2 (Rl TIMES R2), которые не имеют одинаковых имен атрибутов, есть такое отношение R степени (к1+к2), заголовок которого представляет сцепление заголовков отношений R1 и R2, а тело имеет кортежи такие, что первые к1 элементов кортежей принадлежат множеству R1, а последние к2 элементов — множеству R2. При необходимости получить произведение двух отношений, имеющих одинаковые имена одного или нескольких атрибутов, применяется операция переименования RENAME, рассматриваемая далее.
Пример 2.Произведение отношений.
Пусть отношение R1 представляет собой множество номеров всех текущих поставщиков {SI, S2, S3, S4, S5}, а отношение R2 — множество номеров всех текущих деталей {Р1, Р2, РЗ, Р4, Р5, Р6}. Результатом операции R1 TIMES R2 является множество всех пар типа «поставщик — деталь», то есть {(S1.P1), (S1.P2), (S1.P3), (S1.P4), (S1.P5), (S1.P6), (S2.P1).......................................... (S5.P6)}.
Заметим, что в теории множеств результатом операции прямого произведения является множество, каждый элемент которого является парой элементов, первый из которых принадлежит R1, а второй — принадлежит R2. Поэтому кортежами декартова произведения бинарных отношений будут кортежи вида: ((а, б), (в, г)), где кортеж (а, б) принадлежит отношению R1, а кортеж (в, г) — принадлежит отношению R2. В реляционной алгебре применяется расширенный вариант прямого произведения, при котором элементы кортежей двух исходных отношений сливаются, что при записи кортежей результирующего отношения означает удаление лишних скобок, то есть (а, б, в, г).
Выборка (R WHERE f) отношения R по формуле f представляет собой новое отношение с таким же заголовком и телом, состоящим из таких кортежей отношения R, которые удовлетворяют истинности логического выражения, заданного формулой f. Для записи формулы используются операнды — имена атрибутов (или номера столбцов), константы, логические операции (AND — И, OR — ИЛИ, NOT — HE), операции сравнения и скобки.
Примеры 3.Выборки. Р WHERE Вес < 14
| Д# | Название | Тип | Вес | ГородЛ |
| Р1 | гайка | каленый | Москва | |
| Р5 | палец | твердый | Киев |
SP WHERE П# = "SI" AND Д# = "Р1"
| П# | Д# | Количество |
| S1 | Р1 |
Проекция отношения А на атрибуты X, Y,..., Z (А [X, Y,..., Z]), где множество {X, Y,..., ZJ является подмножеством полного списка атрибутов заголовка отношения А, представляет собой отношение с заголовком X, Y,..., Z и телом, содержащим кортежи отношения А, за исключением повторяющихся кортежей. Повторение одинаковых атрибутов в списке X, Y,..., Z запрещается.
Операция проекции допускает следующие дополнительные варианты записи:
• отсутствие списка атрибутов подразумевает указание всех атрибутов (операция тождественной проекции);
• выражение вида R[ ] означает пустую проекцию, результатом которой является пустое множество;
• операция проекции может применяться к произвольному отношению, в том числе и к результату выборки.
Примеры 4.Проекции.
Р [Тип, Город_Д] (S WHERE Город_П="Киев") [П#]
| Тип | Город_Д |
| каленый | Москва |
| мягкий | Киев |
| твердый | Ростов |
| твердый | Киев |
| П# | Город_П |
| S2 | Киев |
| S3 | Киев |
Результатом деления отношения R1 с атрибутами А и В на отношение R2 с атрибутом В (R1 DIVIDEBY R2), где А и В простые или составные атрибуты, причем атрибут В — общий атрибут, определенный на одном и том же домене (множестве доменов составного атрибута), является отношение R с заголовком А и телом, состоящим из кортежей r таких, что в отношении R1 имеются кортежи (r, s), причем множество значений s включает множество значений атрибута В отношения R2.
return false">ссылка скрытаПример 5.Деление отношения.
Пусть R1 — проекция SP [П#, Д#], a R2 — отношение с заголовком Д# и телом {Р2, Р4}, тогда результатом деления R1 на R2 будет отношение R с заголовком П# и телом {S1, S4}.
| R222 | |
| Д# | |
| P2 | |
| P4 |
| R1 DIVIDEBY R2 | |
| П# | |
| S1 | |
| S4 |
| R1 | |
| П# | Д# |
| S1 | P1 |
| S1 | P2 |
| S1 | P3 |
| S1 | P4 |
| S1 | P5 |
| S1 | P6 |
| S2 | P1 |
| S2 | P2 |
| S3 | P2 |
| S4 | P2 |
| S4 | P4 |
| S4 | P5 |
Соединение Cf(R1, R2) отношений R1 и R2 по условию, заданному формулой f, представляет собой отношение R, которое можно получить путем Декартова произведения отношений R1 и R2 с последующим применением к результату операции выборки по формуле f. Правила записи формулы f такие же, как и для операции селекции.
Другими словами, соединением отношения R1 по атрибуту А с отношением R2 по атрибуту В (отношения не имеют общих имен атрибутов) является результат выполнения операции вида:
(R1 TIMES R2) WHERE АQ В,
где Q—логическое выражение над атрибутами, определенными на одном (нескольких — для составного атрибута) домене. Соединение Cf(R1, R2), где формула f имеет произвольный вид (в отличие от частных случаев, рассматриваемых далее), называют также Q-соединением.
Важными с практической точки зрения частными случаями соединения являются эквисоединение и естественное соединение.
Операция эквисоединения характеризуется тем, что формула задает равенство операндов. Приведенный выше пример демонстрирует частный случай операции эквисоединения по одному столбцу. Иногда эквисоединение двух отношений выполняется по таким столбцам, атрибуты которых в обоих отношениях имеют соответственно одинаковые имена и домены. В этом случае говорят об эквисоединении по общему атрибуту.
Операция естественного соединения (операция JOIN) применяется к двум отношениям, имеющим общий атрибут (простой или составной). Этот атрибут в отношениях имеет одно и то же имя (совокупность имен) и определен на одном и том же домене (доменах).
Результатом операции естественного соединения является отношение R, которое представляет собой проекцию эквисоединения отношений R1 и R2 по общему атрибуту на объединенную совокупность атрибутов обоих отношений.
Пример 6.Q-соединение.
Необходимо найти соединение отношений S и Р по атрибутам Город_П и Город_Д соответственно, причем кортежи результирующего отношения должны удовлетворять отношению «больше» (в смысле лексикографического порядка— по алфавиту).
(S TIMES P) WHERE Город_П > Город_Д
Пример 7.Эквисоединение.
| п- # | Имя | Статус | Город_П | Д# | Название | Тип | Вес | Городе |
| S2 | Иван | Киев | Р1 | гайка | каленый | Москва | ||
| S2 | Иван | Киев | Р4 | винт | каленый | Москва | ||
| S2 | Иван | Киев | Р6 | шпилька | каленый | Москва | ||
| S3 | Борис | Киев | Р1 | гайка | каленый | Москва | ||
| S3 | Борис | Киев | Р4 | винт | каленый | Москва | ||
| S3 | Борис | Киев | Р6 | шпилька | каленый | Москва |
Пусть необходимо найти естественное соединение отношений S и Р по общему атрибуту, характеризующему город (в отношении S — это Город_П, а в отношении Р — Город_Д). Поскольку условие операции требует одинаковости имен атрибутов, по которым выполняется соединение, то применяется операция RENAME переименования атрибутов.
(S RENAME Город_П AS Город) JOIN (P RENAME Город_Д AS Город)
| П# | Имя | Статус | Город | Д# | Название | Тип | Вес | |
| S1 | Сергей | Москва | Р1 | гайка | каленый | |||
| S1 | Сергей | Москва | Р4 | винт | каленый | 14, | ||
| S1 | Сергей | Москва | Р6 | шпилька | каленый | |||
| S2 | Иван | Киев | Р2 | болт | мягкий | |||
| S2 | Иван | Киев | Р5 | палец | твердый | |||
| S3 | Борис | Киев | Р2 | болт | мягкий | |||
| S3 | Борис | Киев | Р5 | палец | твердый | |||
| Николай | Москва | Р1 | гайка | каленый | ||||
| S4 | Николай | Москва | Р4 | винт | каленый | |||
| S4 | Николай | Москва | Р6 | шпилька | каленый |
Вопросы для самоконтроля.
1. Что представляет собой реляционная алгебра?
2. Назовите операции реляционной алгебры, предложенной Коддом.
3. Над каким количеством отношений могут выполняться операции реляционной алгебры?
4. Приведите графическую интерпретацию для операций пересечения и произведения.
5. Приведите пример для операции выборки.
6. Охарактеризуйте общий и частные случаи операции соединения.
Практическая работа № 9
Реляционная алгебра
Цели:формирование навыков выполнения основных операций над отношениями.