Тема 3. Реляционная алгебра

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

3.1. Операции над таблицами (операции реляционной алгебры).

Над реляционными таблицами можно выполнять пять основных операций:

• проекция,

• селекция,

• декартово произведение,

• объединение,

• разность.

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

• соединение,

• пересечение,

• деление.

Таким образом, данная реляционная алгебра является избыточной. Однако общепринятый язык доступа к данным в реляционных базах SQL базируется именно на этой алгебре, которая носит имя британского ученого-математика Эдгара Кодда (1923-2003).

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

Пример проекции представлен на рис. 3.1.

Исходная таблица Т
Шифр	Автор	Название	Год издания	Число страниц
И54	Иванов А.Б.	Волоконная оптика	1999	664
Д01	Шабалин С.А.	Измерения для всех	1991	560
И81	Иванов А.Б.	Волоконная оптика	2001	693

Проекция исходной таблицы П2 = π (Т, {Автор, Название})
Автор	Название
Иванов А.Б.	Волоконная оптика
Шабалин С.А.	Измерения для всех

Рис. 3.1. Пример применения к таблице Т операции «проекция».

Селекция (selection, обозначается "σ") – это унарная операция, результатом которой является подмножество записей исходной таблицы, удовлетворяющих условиям, которые накладываются на значения определённых полей.

На рис. 3.2 приведены примеры селекции записей из таблицы Т, представленной на рис. 3.1.

Селекция из исходной таблицы С1 = σ (Т, {Год издания < 2000}) - книги, изданные до 2000 г.
Шифр	Автор	Название	Год издания	Число страниц
И54	Иванов А.Б.	Волоконная оптика	1999	664
Д01	Шабалин С.А.	Измерения для всех	1991	560

Селекция из исходной таблицы С2 = σ (Т, {Автор = “Иванов А.Б.” И Год издания < 2000}) – книги Иванова А.Б., изданные до 2000 года
Шифр	Автор	Название	Год издания	Число страниц
И54	Иванов А.Б.	Волоконная оптика	1999	664

Рис. 3.2. Примеры селекции записей из таблицы

Декартово произведение таблиц (cartesian product, обозначается "×")— это бинарная операция, результатом которой, является таблица, заголовок которой является сцеплением заголовков двух исходных таблиц и состоящая из записей, составленных из сцепленных записей исходных таблиц (рис. 3.3). Исходные таблицы не должны иметь одинаковых полей.

Таблица Т1 Номер производителя Производитель 1 Hewlett Packard 2 Western Digital 3 IBM	Таблица Т2 Номер магазина Адрес 10 Ул. Некрасова, 21 11 Ленинский пр., 45
Декартово произведение Т1 ´ Т2 Номер производителя Производитель Номер магазина Адрес 1 Hewlett Packard 10 Ул. Некрасова, 21 2 Western Digital 10 Ул. Некрасова, 21 3 IBM 10 Ул. Некрасова, 21 1 Hewlett Packard 11 Ленинский пр., 45 2 Western Digital 11 Ленинский пр., 45 3 IBM 11 Ленинский пр., 45

Рис. 3.3. Декартово произведение таблиц

Объединение (union, обозначается "U") – это бинарная операция, которую можно производить над таблицами, имеющими одинаковые заголовки, результатом которой является таблица, включающая все записи обеих таблиц без повторов.

Таблица Т1 – студенты, изучающие физику Студент Группа Иванов И.И. М-01 Петров П.П. М-01 Сидоров С.С. М-03	Таблица Т2 – студенты, изучающие химию Студент Группа Петров П.П. М-01 Сергеев С.С. М-02 Федоров Ф.Ф. М-02
Объединение Т1 È Т2 – студенты, изучающие физику и/или химию Студент Группа Иванов И.И. М-01 Петров П.П. М-01 Сидоров С.С. М-03 Сергеев С.С. М-02 Федоров Ф.Ф. М-02

Рис. 3.4. Объединение таблиц.

Разность (set difference, обозначается "–") – это бинарная операция, которую можно производить над таблицами Т1 и Т2, имеющими одинаковые заголовки, результатом которой является таблица Т1–Т2, включающая подмножество тех записей Т1, которых нет в таблице Т2.

Разность Т1 - Т2 – студенты, изучающие физику и не изучающие химию Студент Группа Иванов И.И. М-01 Сидоров С.С. М-03	Разность Т2 – Т1 – студенты, изучающие химию и не изучающие физику Студент Группа Федоров Ф.Ф. М-02

Рис. 3.5. Разность таблиц, представленных на рис. 3.4.

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

Соединение (join, обозначается " ") – это операция, аргументами которой в общем случае являются таблицы Т1 и Т2 и условие У, а результатом – таблица, заголовок которой является сцеплением заголовков двух исходных таблиц и состоящая из записей, удовлетворяющих условию У и составленных из сцепленных записей исходных таблиц. Соединение может быть получено сочетанием операций декартова произведения и селекции: Т1 Т2 = σ_У (Т1 × Т2). Пример соединения представлен на рис. 3.6.

Важным частным случаем соединения является эквисоединение, когда условие У подразумевает равенство значений полей двух соединяемых таблиц (рис. 3.7).

Таблица Т1 Номер товара Наименование товара Цена 1 Принтер HP LaserJet 1100 300 2 Кабель USB 3 м 15 3 Мышь Logitech 5	Таблица Т2 Номер магазина Адрес 10 Ул. Некрасова, 21 11 Ленинский пр., 45
Соединение join(Т1, Т2, Цена < 100) Номер товара Наименование товара Цена Номер магазина Адрес 2 Кабель USB 3 м 15 10 Ул. Некрасова, 21 2 Кабель USB 3 м 15 11 Ленинский пр., 45 3 Мышь Logitech 5 10 Ул. Некрасова, 21 3 Мышь Logitech 5 11 Ленинский пр., 45

Рис. 3.6. Соединение таблиц.

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

Таблица Т1 – средние цены Номер товара Наименование товара Средняя цена 1 Принтер HP LaserJet 1100 300 2 Кабель USB 3 м 13 3 Мышь Logitech 4	Таблица Т2 – розничные цены Номер товара Номер магазина Цена 1 10 300 1 11 310 2 10 15 3 10 5 2 11 13
Эквисоединение join(Т1, Т2, Средняя цена = Цена AND Т1.Номер товара = Т2.Номер товара) – какие товары можно купить по средним ценам Т1.Номер товара Наименование товара Средняя цена Т2.Номер товара Номер магазина Цена 1 Принтер HP LaserJet 1100 300 1 10 300 2 Кабель USB 3 м 13 2 11 13

Рис. 3.7. Эквисоединение таблиц.

Пересечение (intersection, обозначается "∩") – это бинарная операция, которую можно производить над таблицами Т1 и Т2, имеющими одинаковые заголовки, результатом которой является таблица Т1 ∩ Т2, включающая все записи, имеющиеся и в таблице Т1 и в таблице Т2. Пересечение может быть получено сочетанием двух операций разности: Т1 ∩ Т2 = Т1 – (Т1 – Т2) = = Т2 – (Т2 – Т2). Пример пересечения показан на рис. 3.9.

Таблица Т1 Номер товара Наименование товара Номер магазина Цена 1 Принтер HP LaserJet 1100 10 300 2 Принтер HP LaserJet 1100 11 310 3 Кабель USB 3 м 10 15	Таблица Т2 Номер магазина Адрес 10 Ул. Некрасова, 21 11 Ленинский пр., 45
Эквисоединение join(Т1, Т2, Т1.Номер магазина = Т2.Номер магазина) Номер товара Наименование товара Т1.Номер магазина Цена Т2.Номер магазина Адрес 1 Принтер HP LaserJet 1100 10 300 10 Ул. Некрасова, 21 2 Принтер HP LaserJet 1100 11 310 11 Ленинский пр., 45 3 Кабель USB 3 м 10 15 10 Ул. Некрасова, 21
Естественное соединение natural join(Т1, Т2, Т1.Номер магазина = Т2.Номер магазина) Номер товара Наименование товара Номер магазина Цена Адрес 1 Принтер HP LaserJet 1100 10 300 Ул. Некрасова, 21 2 Принтер HP LaserJet 1100 11 310 Ленинский пр., 45 3 Кабель USB 3 м 10 15 Ул. Некрасова, 21

Рис. 3.8. Отличие эквисоединение от естественного соединения таблиц.

Пересечение Т1 ∩ Т2 – студенты, изучающие и физику и химию
Студент	Группа
Петров П.П.	М-01
Сергеев С.С.	М-02

Рис. 3.9. Пересечение таблиц Т1 и Т2, представленных на рис. 3.4.

Деление (division, обозначается "/") – бинарная операция, в некотором смысле обратная декартову произведению. Поэтому операцию можно производить над таблицами, имеющими такие заголовки, что заголовок делителя является частью заголовка делимого. Результатом деления таблица, состоящая из тех записей, декартово произведение которых с делителем входит в делимое (рис. 3.10).

Обратите внимание, что декартово произведение частого и делителя НЕ всегда позволяет получить делимое. Поэтому операция деления не всегда совершенно обратна декартову произведению. Случай, показанный на рис. 3.10, соответствует так называемому делению с остатком. Если декартово произведение частого и делителя дает делимое (в таблице-делимом нет «лишних» значений), то имеет место точное реляционное деление.

Деление можно выразить через операции декартова произведения, разности и проекции: Т1 / Т2 = π_{ЗТ1 ∩ ЗТ2} (Т1 – ((Т1 × Т2) – Т1)). ЗТ1 ∩ ЗТ2 – отбираются те поля Т1, которых нет в Т2