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

Лекция 6. Реляционная алгебра. Теоретико-множественные операторы

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

В реализациях конкретных реляционных СУБД сейчас не используется в чистом виде ни реляционная алгебра, ни реляционное исчисление. Фактическим стандартом доступа к реляционным данным стал язык SQL (Structured Query Language). Язык SQL представляет собой смесь операторов реляционной алгебры и выражений реляционного исчисления, использующий синтаксис, близкий к фразам английского языка и расширенный дополнительными возможностями, отсутствующими в реляционной алгебре и реляционном исчислении. Вообще, язык доступа к данным называется реляционно-полным, если он по выразительной силе не уступает реляционной алгебре, т.е. любой оператор реляционной алгебры может быть выражен средствами этого языка. Именно таким и является язык SQL. Практически все операции реляционной модели предназначены для организации запросов к БД в терминах отношений. Эти запросы относятся к включению, соединению, выборке кортежей соответствующих отношений.

Традиционно определяют восемь реляционных операторов, объединенных в две группы.

Теоретико-множественные операторы:

· Объединение

· Пересечение

· Вычитание

· Декартово произведение

Рекомендуемые материалы

Специальные реляционные операторы:

· Выборка

· Проекция

· Соединение

· Деление

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

Отношения, совместимые по типу

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

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

· отношения имеют одно и то же множество имен атрибутов, т.е. для любого атрибута в одном отношении найдется атрибут с таким же наименованием в другом отношении;

· атрибуты с одинаковыми именами определены на одних и тех же доменах (или типах, если домены не поддерживаются).

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

Теоретико-множественные операторы

Объединением двух совместимых по типу отношений А и В называется отношение с тем же заголовком, что и у отношений А и В, и телом, состоящим из совокупности кортежей обоих отношений.

Синтаксис операции объединения: A  UNION  B (A È В)

Замечание. Объединение, как и любое отношение, не может содержать одинаковых кортежей. Поэтому, если некоторый кортеж входит и в отношение А, и отношение В, то в объединение он входит один раз.

Пусть даны два отношения А (таблица 6.1) и В (таблица 6.2) с информацией о сотрудниках:

Таблица 6.1 - Отношение А

Таблица 6.2. Отношение В

В результате операции объединения (A È В) будет получено отношение C с тем же заголовком что и у отношений А и В (таблица 6.3):

Отношение С, не наследует первичного ключа. Поэтому, в объединении отношений А и В атрибут «Табельный номер» может содержать дубликаты значений. Наследование ключей противоречило бы понятию объединения как «объединению множеств». Конечно, объединение отношений А и В имеет, как и любое отношение, потенциальный ключ, например, состоящий из всех атрибутов.

Таблица 6.3 - Результирующее отношение (A È В)

Вообще, никакие реляционные операторы не передают результирующему отношению никаких данных о потенциальных ключах. Причина заключается в том, что потенциальный ключ - семантическое понятие, отражающее различимость объектов предметной области. Наличие потенциальных ключей не выводится из структуры отношения, а явно задается для каждого отношения, исходя из его смысла. Реляционные же операторы являются формальными операциями над отношениями и выполняются одинаково, независимо от смысла данных, содержащихся в отношениях. Поэтому, реляционные операторы ничего не могут «знать» о смысле данных. Трактовка результата реляционных операций - дело пользователя.

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

Синтаксис операции пересечения: A INTERSECT B (A Ç В)

Для исходных отношений (таблицы 6.1 и 6.2) пересечение примет вид (таблица 6.4):

Таблица 6.4 - Результирующее отношение (A Ç В)

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

Синтаксис операции вычитания: A MINUS B (A В)

Для исходных отношений (таблицы 6.1 и 6.2) результат вычитания примет вид (таблица 6.5):

Таблица 6.5 - Результирующее отношение (A В)

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

Синтаксис операции декартового произведения: A TIMES B (A Ä В)

Пусть даны два отношения с информацией о поставщиках А и деталях В.

Пример. Пусть даны два отношения А и В с информацией о поставщиках и деталях (таблицы 6.6 и 6.7). Тогда декартово произведение отношений А и В примет вид указанный в таблице 6.8.

Таблица 6.6 - Отношение А (Поставщики)

Таблица 6.7 - Отношение В (Детали)

Таблица 6.8 - Результирующие отношение (A Ä В)

Замечания:

1. Мощность произведения A Ä B равна произведению мощностей отношений А и В, т.к. каждый кортеж отношения А соединяется с каждым кортежем отношения В.

2. Если в отношениях А и В имеются атрибуты с одинаковыми именами, то перед выполнением операции такие атрибуты необходимо переименовать.

3. Перемножать можно любые два отношения, совместимость по типу при этом не требуется.

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

Контрольные вопросы

1. Какие отношения называются совместимыми по типу?

2. В чем смысл реляционного оператора «Объединение»?

3. В чем причины утраты первичного ключа при использовании реляционных операций?

4. В чем смысл реляционного оператора «Пересечение»?

5. В чем смысл реляционного оператора «Вычитание»?

6. Почему невозможно использование операций «Объединения», «Пересечения» и «Вычитания», если исходные отношения не совместимы по типу?

7. В чем смысл реляционного оператора «Декартово произведение»?

8. Чему равна мощность декартова произведения?

Задания для самостоятельной работы

Задание 1. Даны два отношения А (таблица 6.9) и В (таблица 6.10) содержащие данные о товарах, необходимо выполнить операции объединения, пересечения и вычитания. Попытайтесь определить смысл результирующих отношений.

Таблица 6.9 – Отношение А

Таблица 6.10 – Отношение В

Задание 2. Выполните декартово произведение двух отношений приведенных на рисунке 5.2