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

Вспомним некоторые определения из курса дискретной математики.

Пусть М – некоторое множество элементов.

Предикат (логическое высказывание) – это функция b = f(x₁, …, x_m), где x_i  M, b  {True, False}, m:=1,…,m.

Модель – это множество элементов M с заданными над элементами предикатами.

Операция p: y = p(x₁, …, x_n); y, x_i  M, i:=1,…,n.

Алгебра (абстрактная) – это модель с конечным множеством операций.

Иными словами, алгебра - это множество объектов из основного множества M c заданной на нем конечной совокупностью операций, замкнутых относительно этого (основного) множества M. Основное множество в реляционной алгебре – это множество отношений (отношения следует понимать в смыле педыдущей главы). Кодд определил 7 базовых операций и одну дополнительную. Вообще говоря, эта совокупность операций избыточна, т.е. некоторые операции могут быть определены через другие операции.

Теоретико-множественные операции являются основными, их всего 4. Остальные называются специальными.

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

Отношение Маг1

Шифр товара	Наименование товара
Ф1	Бананы
Ф2	Арбузы
Ф3	Авокадо
Ф4	Яблоки
Ф5	Помидоры
Ф6	Фейхоа

Отношение Маг2

Шифр товара	Наименование товара
Ф1	Бананы
Ф7	Груши
Ф2	Арбузы
Ф6	Фейхоа

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

3.1.1. Объединение отношений R1 и R2 (записывается как R1  R2) – это отношение R3, {r|r  R1  r  R2} содержащее множество кортежей, принадлежащих R1 или R2 или и R1 и R2.  – логическое сложение (ИЛИ).

Для Маг1  Маг2 результатом является отношение:

Шифр товара	Наименование товара
Ф1	Бананы
Ф2	Арбузы
Ф3	Авокадо
Ф7	Груши
Ф4	Яблоки
Ф5	Помидоры
Ф6	Фейхоа

3.1.2. Пересечение отношений R1 и R2 (записывается R1  R2) – это отношение R3, {r|r  R1  r  R2} содержащее множество кортежей, принадлежащих и R1 и R2

 – логическое умножение (И)

Для Маг1  Маг2 результатом является отношение:

Шифр товара	Наименование товара
Ф1	Бананы
Ф2	Арбузы
Ф6	Фейхоа

3.1.3. Разность отношений R1 и R2 (записывается R1 \ R2) – это отношение R3, {r| r  R1  r not  R2} содержащее множество кортежей, принадлежащих R1 но не принадлежащих R2.

Маг1 \ Маг2:

Шифр товара	Наименование товара
Ф3	Авокадо
Ф4	Яблоки
Ф5	Помидоры

Маг2 \ Маг1:

Шифр товара	Наименование товара
Ф7	Груши

Как можно видеть из вышеприведенных примеров Объединение и Пересечение – коммутативны, Разность – нет.

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

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

Пусть отношение МагО содержит список обязательного минимума товаров для каждого магазина. Схема отношения МагО совпадает со схемами Маг1 и Маг2.

Какие продукты есть и в первом и во втором магазинах, но нет в МагО?

Маг1  Маг2 \ МагО

Какие продукты есть в первом магазине, отсутсвуют во втором магазине, но входят в обязательный список?

(Маг1 \ Маг2  МагО)

Какие продукты из обязательных есть и в первом и во втором магазинах?

(Маг1  МагО)  (Маг2  МагО)

Каких продуктов из числа обязательных нет ни в первом, ни во втором магазинах?

МагО \ (Маг1  Маг2)

Для дальнейшего введем определение:

сцеплением (конкатенацией) кортежей с = <c1, …, cn> и q = <q1, …, qm> является кортеж, полученный добавлением значений 2 кортежа в конец 1 кортежа:

(c, q) = <c1, …, cn, q1, …, qm>

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

3.1.4. Расширенное декартово произведение отношения R1 со схемой S_R1 = (A1, …, An) и отношения R2 со схемой S_R2 = (B1, …, Bm) – это отношение R3 степени n+m со схемой S_R3 = (A1, …, An, B1, …, Bm), содержащее кортежи, полученные сцеплением каждого картежа R1 с каждым кортежем R2.

R1 = {r}, R2 = {q}

R1  R2 = {(r, q) | r  R1  q  R2}

Ввиду возможности перестановки атрибутов в отношении,  - коммутативна. Эта операция обычно используется для получения универсума – всех мыслимых возможностей.

Пусть МагО содержит следующие кортежи:

Ф1 Бананы

Ф9 Апельсины

Ф11 Ананасы

Введем отношение Магазины – это отношение просто перечисляет имеющиеся магазины.

Магазины:

Наименование магазина

Привет

Ласточка

Рябинка

МагО  Магазины:

Ф1 Бананы Привет

Ф1 Бананы Ласточка

Ф1 Бананы Рябинка

Ф9 Апельсины Привет

Ф9 Апельсины Ласточка

Ф9 Апельсины Рябинка

Ф11 Ананасы Привет

Ф11 Ананасы Ласточка

Ф11 Ананасы Рябинка

Введем отношение МагР – оно хранит сведения о фактическом наличии товаров в каждом из магазинов:

МагР:

Шифр товара Наименование товара Наименование магазина

Ф1 Бананы Привет

Ф1 Бананы Ласточка

Ф9 Апельсины Ласточка

Ф9 Апельсины Рябинка

Ф11 Ананасы Привет

Какие продукты из списка обязательных (МагО) отсутствуют в каких магазинах:

МагО  Магазины \ МагР:

Шифр товара Наименование товара Наименование магазина

Ф1 Бананы Рябинка

Ф9 Апельсины Привет

Ф11 Ананасы Ласточка

Ф11 Ананасы Рябинка

Набор из 4 теоретико-множественных операций избыточен т.к. например

R1  R2 = (R1  R2) \ (R1 \ R2) \ (R2 \ R1).