Теория баз данных. Урок 2. Операции реляционной алгебры.

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

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

Переименование. В результате такой операции возникает новое отношение с другими именами атрибутов. Записывается эта операция вот так: R RENAME Atr₁, Atr₂, … AS NewAtr₁, NewAtr₂, …, где R — отношение, подвергаемое операции переименования, Atr₁, Atr₂, … — исходные имена атрибутов, NewAtr₁, NewAtr₂, … — новые имена атрибутов. По сути, эта операция - просто присвоение столбцам (всем или только нескольким) других имен.

Выборка. Отношение с тем же заголовком, что и у отношения A, и телом, состоящим из кортежей, значения атрибутов которых при подстановке в условие c дают значение ИСТИНА. c представляет собой логическое выражение, в которое могут входить атрибуты отношения A, а также скалярные выражения.  Записывается эта операция A WHERE c. По сути, выборка - это что-то типа операции select  из языка запросов SQL. Почему "что-то типа"? Потому что реляционная алгебра - это не SQL и отношение - не таблица (см.  прошлый урок). Но определенные сходства с этой операцией из SQL есть. Если вы не знаете, что такое SQL - просто пропускайте мои замечания по поводу SQL мимо ушей, они для тех, кто много работал с базами данных практически, но с теорией знаком слабо.

Проекция. Если из существующего отношения вырезать отдельные столбцы и из полученной таблицы удалить дубликаты кортежей, то получится проекция. Обозначается как A[X, Y, …, Z] или PROJECT A {x, y, …, z}.

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

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

Рассмотрим пример. Допустим, у нас есть две таблицы:

и

В результате у нас будет таблица из 6 строк:

Почему из 6 строк? Потому что есть строки, которые присутствуют и в той и в другой таблице (они выделены желтым цветом), а в отношении не должно быть повторов. Операция UNION из языка SQL (по крайней мере, для MySQL точно, я проверял), ведет себя точно так же. Аналогичная операция есть в теории множеств (объединение двух множеств), см. первые нескольких уроках из серии "Математический анализ для чайников".

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

Вычитание.  Отношение с тем же заголовком, что и у совместимых по типу отношений A и B, и телом, состоящим из кортежей, принадлежащих отношению A и не принадлежащих отношению B. Обозначается  A MINUS B. Если применить данную операцию к нашим таблицам, то получим:

Декартово произведение. Отношение (A₁, A₂, …, A_m, B₁, B₂, …, B_m), заголовок которого является сцеплением заголовков отношений A(A₁, A₂, …, A_m) и B(B₁, B₂, …, B_m), а тело состоит из кортежей, являющихся сцеплением кортежей отношений A и B: a₁, a₂, …, a_m, b₁, b₂, …, b_m), таких, что (a₁, a₂, …, a_m)ÎA, и (b₁, b₂, …, b_m)Î B.. Обозначается эта операция A TIMES B.

И так, что будет если мы перемножим таблицы из нашего примера? Получиться вот такая хитрая таблица из 16 строк. Но мы для удобства возьмем перемножение таблиц из нашего примера, но состоящие только из двух первых строк. Что бы в итоге у нас получилось не 16, а только 4 строки.

Итак, вот первая исходная таблица:

А вот вторая:

Результат перемножения:

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

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

Таблица 1.

Таблица 2.

Результат.

Заметьте, и тут нет дублей.

А что если перемножить какую то таблицу саму на себя? Например, таблицу 2 из нашего примера? Давайте, посмотрим:

Как видим, и тут не будет дублей, если их, конечно, нет в исходных таблицах.

Кстати, операция декартова произведения чем то напоминает full join в SQL.

Идем дальше.

Соединение. Операция соединения отношений A и B по предикату P логически эквивалентна последовательному применению операций декартового произведения A и B и выборки по предикату P. Если в отношениях имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты необходимо переименовать. Обозначается как (A TIMES B) WHERE P.

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

Таблица 1.

Таблица 2.

Применяя к ним операцию соединения, получаем по условию равенства товара (Таблица1 TIMES Таблица2) WHERE Таблица1.Товар=Таблица2.Товар:

Данная операция похожа на left join из языка SQL.

Деление. Пожалуй, это сама сложная операция реляционной алгебры. По научному она формулируется так: Отношение с заголовком (X₁, X₂, …, X_n) и телом, содержащим множество кортежей (x₁, x₂, …, x_n), таких, что для всех кортежей (y₁, y₂, …, y_m) Î B в отношении A(X₁, X₂, …, X_n, Y₁, Y₂, …, Y_m) найдется кортеж (x₁, x₂, …, x_n, y₁, y₂, …, y_m). Обозначается такая хитрая операция A DIVIDEBY B. По сути, деление в реляционной алгебре - это что-то обратное декартовому произведению.  Но не совсем. Что бы было более понятно, давайте рассмотрим пример. Пусть у нас имеется отношение R1 с заголовками A и B:

и отношение R2 с заголовком B:

Тогда в результате деления останется вот такая таблица с заголовком A:

Как получился такой результат? Мы нашли в отношении R1 все строки, где имеются значения из отношения R2, они выделены желтым цветом.  Но в эти строки надо включить только те, которые образуют законченное декартово произведение. Давайте выделим отдельно эти найденные строки:

Строки {S2, P2} и {S3,P2} выкидываем, потому что для них нет пары для второй стороны из отношения R2, то есть, нет кортежей {S2, P4} и {S3, P4}. А вот для кортежей {S1, P2} и {S1,P4} такая пара есть, это {S4,P2} и {S4,P4}. Поэтому эти строки оставляем, оставляем так же и их пары:

Ну, и собственно, удаляем столбец B.