5.4.Проектирование базы данных

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

Основная идея реляционной алгебры состоит в том, что

• отношения являются множествами,

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

Математически отношение определяется следующим образом.

Пусть даны N множеств D1, D2, …, DN, тогда R есть отношение над этими множествами, если R есть множество упорядоченных n-кортежей вида <d1, d2, …, dN> , где d1 – элемент из D1, d2 – элемент из D2, dN – элемент из DN. D1, D2, , DN называются доменами отношения R. Существует много подходов к определению реляционной алгебры, которые различаются наборами операций и способами их интерпретации, но, в принципе, являются более или менее равносильными. В данном разделе описывается немного расширенный начальный вариант алгебры, который был предложен Коддом («алгебра Кодда»). В этом варианте набор основных алгебраических операций состоит из восьми операций, которые делятся на два класса – теоретико-множественные операции и специальные реляционные операции.

В состав теоретико-множественных операций входят операции:

• объединения отношений;

• пересечения отношений;

• взятия разности отношений;

• взятия декартова произведения отношений.

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

• ограничение отношения;

• проекцию отношения;

• соединение отношений;

• деление отношений.

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

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

Пример. Пусть даны два отношения A и B с информацией о сотрудниках (таблицы: 5.1 и 5.2).

Таблица 5.1. Отношение A

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

Таблица 5.2. Отношение B

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

Объединение отношений A и B будет иметь вид, представленный в таблице 5.3).

Таблица 5.3. Отношение A UNION B

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

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

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

Таблица 5.4. Отношение A INTERSECT B

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

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

Пример. Для тех же отношений A и B, что и в предыдущем примере вычитание имеет вид (таблица 5.5):

Таблица 5.5. Отношение A MINUS B

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

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

Пример. Пусть даны два отношения A и B с информацией о поставщиках и деталях (таблицы 5.6 и 5.7):

Таблица 5.6. Отношение A (Поставщики)

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

Таблица 5.7. Отношение B (Детали)

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

Декартово произведение отношений A и B будет иметь вид (таблица 5.8):

Таблица 5.8. Отношение A TIMES B

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

Результатом ограничения (WHERE) отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию.

Пример. Пусть дано отношение A с информацией о сотрудниках (таблица 5.9).

Таблица 5.9. Отношение A

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

Результат выборки A WHERE Зарплата < 3000 будет иметь вид:

Таблица 5.10. Отношение A WHERE Зарплата<30000.

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

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

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

Таблица 5.11. Отношение A (Поставщики)

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

Проекция A[Город поставщика] будет иметь вид (таблица 5.12):

Таблица 5.12. Отношение A[Город поставщика]

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

Уфа

Москва

Челябинск

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

Пример. Пусть поставщикам (отношение P) и деталям (отношение D) присвоен некий статус. Поставщики имеют право поставлять только те детали, статус которых не выше статуса поставщика (таблицы 5.13 и 5.14).

Таблица 5.13. Отношение P (Поставщики)

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

Таблица 5.14. Отношение D (Детали)

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

Ответ на вопрос «какие поставщики имеют право поставлять какие детали?» даёт соединение P[X>=Y]D (таблица 5.15):

Таблица 5.15

Отношение PD: «Какие поставщики поставляют какие детали»

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

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

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

В качестве делимого возьмем проекцию Z=PD[PNUM, DNUM], содержащую номера поставщиков и номера поставляемых ими деталей (таблица 5.16):

Таблица 5.16. Проекция Z=PD[PNUM,DNUM]

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

В качестве делителя возьмем проекцию K=D[DNUM], содержащую список номеров всех деталей (не обязательно поставляемых кем-либо). Проекция представлена с помощью таблицы 5.17:

Таблица 5.17. Проекция K=D[DNUM]

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

1

2

3

Деление Z DEVIDEBY K даёт список номеров поставщиков, поставляющих все детали (таблица 5.18):

Таблица 5.18. Отношение Z DEVIDEBY K

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

1

Поставщик с номером 1 поставляет все детали.

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

Пример: City RENAME City_Num AS Cityld

Оператор возвращает отношение, в котором атрибут City_Num переименован в Cityld.

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

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

RENAME >= WHERE = PROJECT >= TIMES = JOIN = INTERSECT = = DIVIDE BY >= UNION = MINUS