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

Вторая часть реляционной модели, манипуляционная часть, утверждает, что доступ к реляционным данным осуществляется при помощи реляционной алгебры или эквивалентного ему реляционного исчисления.

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

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

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

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

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

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

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

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

• объединение;
• пересечение;
• вычитание;
• декартово произведение.

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

• выборка (селекция, ограничение) ;
• проекция;
• соединение;
• деление.

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

Рисунок. 3.3. Графическая интерпретация некоторых операций реляционной алгебры

Кроме того, в состав алгебры включается операция присваивания, позволяющая сохранить в базе данных результаты вычисления алгебраических выражений, и операция переименования атрибутов, дающая возможность корректно сформировать заголовок (схему) результирующего отношения. Если не вдаваться в некоторые тонкости, которые мы рассмотрим в следующих подразделах, то почти все операции предложенного выше набора обладают очевидной и простой интерпретацией:

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

Синтаксис операции объединения:

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

Пример 3.1 Пусть даны два отношения и с информацией о сотрудниках:

Отношение A

Табельный номер	Фамилия	Зарплата
1	Иванов
2	Петров
3	Сидоров

Отношение В

Табельный номер	Фамилия	Зарплата
1	Иванов
4	Пушников
3	Сидоров

Объединение отношений иОтношение A UNION B будет иметь вид:

Табельный номер	Фамилия	Зарплата
	Иванов
	Петров
	Сидоров
	Пушников

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

Синтаксис операции пересечения:

Пример 3.2 Для тех же отношений и , что и в предыдущем примере пересечение

A INTERSECT B имеет вид:

Табельный номер	Фамилия	Зарплата
	Иванов
3	Сидоров

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

Синтаксис операции вычитания:

Пример 3.3 Для тех же отношений и , что и в предыдущем примере вычитание Отношение A MINUS B имеет вид:

Табельный номер	Фамилия	Зарплата
2	Петров

 

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

Синтаксис операции декартового произведения:

Замечание. Мощность произведения равна произведению мощностей отношений и , т.к. каждый кортеж отношения соединяется с каждым кортежем отношения .

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

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

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

Отношение A (Поставщики)

Номер поставщика	Наименование поставщика
1	Иванов
2	Петров
3	Сидоров

Отношение B (Детали)

Номер детали	Наименование детали
1	Болт
2	Гайка
3	Винт

Декартово произведение отношений и Отношение A TIMES B будет иметь вид:

Номер поставщика	Наименование поставщика	Номер детали	Наименование детали
	Иванов		Болт
	Иванов		Гайка
	Иванов		Винт
	Петров		Болт
	Петров		Гайка
	Петров		Винт
	Сидоров		Болт
	Сидоров		Гайка
	Сидоров		Винт

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

5. Ограничение (выборка, селекция). Результатом ограничения отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию. Выборкой (ограничением, селекцией)на отношении с условием называется отношение с тем же заголовком, что и у отношения , и телом, состоящем из кортежей, значения атрибутов которых при подстановке в условие дают значение ИСТИНА. представляет собой логическое выражение, в которое могут входить атрибуты отношения и (или) скалярные выражения.

В простейшем случае условие имеет вид , где - один из операторов сравнения ( и т.д.), а и - атрибуты отношения или скалярные значения.

Синтаксис операции выборки: , или

Пример 3.5 Пусть дано отношение с информацией о сотрудниках:

Отношение A

Табельный номер	Фамилия	Зарплата
1	Иванов
2	Петров
3	Сидоров

Результат выборки будет иметь вид:

Табельный номер	Фамилия	Зарплата
1	Иванов
2	Петров

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

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

Синтаксис операции проекции:

Замечание. Операция проекции дает «вертикальный срез» отношения, в котором удалены все возникшие при таком срезе дубликаты кортежей.

Пример 3.6 Пусть дано отношение с информацией о поставщиках, включающих наименование и месторасположение:

Отношение A (Поставщики)

Номер поставщика	Наименование поставщика	Город поставщика
1	Иванов	Уфа
2	Петров	Москва
3	Сидоров	Москва
4	Сидоров	Челябинск

 

Проекция будет иметь вид:

Город поставщика

Уфа

Москва

Челябинск

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

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

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

Обычно рассматривается несколько разновидностей операции соединения:

• общая операция соединения;
• -соединение (тэта-соединение);
• эквисоединение;
• естественное соединение

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

Тэта-соединение. Пусть отношение содержит атрибут , отношение содержит атрибут , а - один из операторов сравнения ( и т.д.). Тогда -соединением отношения по атрибуту с отношением по атрибуту называют отношение

Это частный случай операции общего соединения.

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

Отношение A (Поставщики)

Номер поставщика	Наименование поставщика	X (Статус поставщика)
	Иванов
	Петров
	Сидоров

Отношение B (Детали)

Номер детали	Наименование детали	Y (Статус детали)
	Болт
	Гайка
	Винт

Ответ на вопрос "какие поставщики имеют право поставлять какие детали?" дает -соединение : Отношение "Какие поставщики поставляют какие детали"

Номер поставщика	Наименование поставщика	X (Статус поставщика)	Номер детали	Наименование детали	Y (Статус детали)
	Иванов			Болт
	Иванов			Гайка
	Иванов			Винт
	Петров			Винт
	Сидоров			Гайка
	Сидоров			Винт

Эквисоединение. Наиболее важным частным случаем -соединения является случай, когда есть просто равенство. Синтаксис эквисоединения:

Пример 3.8 Пусть имеются отношения , и , хранящие информацию о поставщиках, деталях и поставках соответственно (для удобства введем краткие наименования атрибутов):

Отношение P (Поставщики)

Номер поставщика PNUM	Наименование поставщика PNAME
	Иванов
	Петров
	Сидоров

Отношение D (Детали)

Номер детали DNUM	Наименование детали DNAME
	Болт
	Гайка
	Винт

Отношение PD (Поставки)

 

Номер поставщика PNUM	Номер детали DNUM	Поставляемое количество VOLUME

Ответ на вопрос, какие детали поставляются поставщиками, дает эквисоединение . На самом деле, т.к. в отношениях имеются одинаковые атрибуты, то требуется сначала переименовать атрибуты, а потом выполнить эквисоединение. В результате имеем отношение «Какие детали поставляются какими поставщиками?»

Номер поставщика PNUM1	Наименование поставщика PNAME	Номер поставщика PNUM2	Номер детали DNUM	Поставляемое количество VOLUME
	Иванов
	Иванов
	Иванов
	Петров
	Петров
	Сидоров

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

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

Естественное соединение настолько важно, что для него используют специальный синтаксис:

Замечание. В синтаксисе естественного соединения не указываются, по каким атрибутам производится соединение. Естественное соединение производится по всем одинаковым атрибутам.

Замечание. Естественное соединение эквивалентно следующей последовательности реляционных операций:

1. Переименовать одинаковые атрибуты в отношениях
2. Выполнить декартово произведение отношений
3. Выполнить выборку по совпадающим значениям атрибутов, имевших одинаковые имена
4. Выполнить проекцию, удалив повторяющиеся атрибуты
5. Переименовать атрибуты, вернув им первоначальные имена

Пример 3.9 В предыдущем примере ответ на вопрос «Какие детали поставляются поставщиками?», более просто записывается в виде естественного соединения трех отношений (для удобства просмотра порядок атрибутов изменен, это является допустимым по свойствам отношений):

Отношение P JOIN PD JOIN D

Номер поставщика PNUM	Наименование поставщика PNAME	Номер детали DNUM	Наименование детали DNAME	Поставляемое количество VOLUME
	Иванов		Болт
	Иванов		Гайка
	Иванов		Винт
	Петров		Болт
	Петров		Гайка
	Сидоров		Болт

 

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

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

Синтаксис операции деления:

Замечание. Типичные запросы, реализуемые с помощью операции деления, обычно в своей формулировке имеют слово «все» - «Какие поставщики поставляют все детали?».

Пример 3.10 В примере с поставщиками, деталями и поставками ответим на вопрос, «Какие поставщики поставляют все детали?».

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

Проекция X=PD[PNUM,DNUM]

Номер поставщика PNUM	Номер детали DNUM

В качестве делителя возьмем проекцию , содержащую список номеров всех деталей (не обязательно поставляемых кем-либо):

Проекция Y=D[DNUM]

Номер детали DNUM

Деление дает список номеров поставщиков, поставляющих все детали:

Отношение X DEVIDEBY Y

Номер поставщика PNUM

Оказалось, что только поставщик с номером 1 поставляет все детали.

9. Переименование. Операция переименования производит отношение, тело которого совпадает с телом операнда, но имена атрибутов изменены.

10. Присваивание. Операция присваивания позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД.