Как найти пересечение отношений

Так
как отношения это множества, то над ними
можно производить операции.

Операции
над отношениями можно разделить на 2
класса:

1. Операции,
которые сводятся к теоретико-множественным
операциям.

2. Операции,
которые не сводятся к теоретико-мно­жествен­ным
операциям.

Рассмотрим
операции 1-го класса.

2.26.1. Объединение отношений

Пусть
заданы следующие бинарные отношения

,

и

,

,
заданные на одном и том же множестве

.

Объединением
отношений

и

называется отношение

,
определяемое объединением соответствующих
множеств:

.

Для

и

соотношение

выполняется тогда и только тогда, когда
выполнено хотя бы одно из соотношений

или

.

Пример 2.22

Пусть

множество
вещественных чисел, накотором заданы
бинарные отношения

,

и

,

.
Отношение
означает
«быть больше», т.е.

можно записать как

.
Отношение

означает «быть равным», т.е.

можно записать как

.
Тогда отношение

означает «быть болше или равным». Для
любых

и

из
множества

соотношение

(или в другой форме

)
означает, что элемент

больше или равен элементу

,
т.е.

.

2.26.2. Пересечение отношений

Рассмотрим
те же отношения

,

и

,

,
заданные на одном и том же множестве

.

Пересечением
отношений

и

называется отношение

,
определяемое пересечением соответствующих
множеств:

.

Для

и

соотношение

выполняется тогда и только тогда, когда
одновременно выполнено каждое из
соотношений

и

.

Пример 2.23

Рассмотрим

множество вещественных чисел, накотором
заданы бинарные отношения

,

и

,

.
Отношение

означает «быть не меньше», т.е. запись

имеет вид

,
а

«быть не равным», т.е.

имеет вид

.
Тогда отношение

означает «быть строго больше». Для любых

и

из
множества

соотношение

(или в другой форме

)
означает, что элемент

строго больше элемента

,
т.е.

.

2.26.3. Разность отношений

Рассматриваются
те же отношения

,

и

,

,
заданные на одном и том же множестве

.
Разностью отношений

и

называется
отношение

,
определяемое пересечением соответствующих
множеств:

.

Для

и

соотношение

выполняется тогда и только тогда, когда
соотношение выполняется

,
а соотношение

не выполняется, т.е. когда

и

.

Пример
2.24

Если

множество
вещественных чисел, накотором заданы
бинарные отношения

,

и

,

,
отношение
означает
«быть больше, т.е.

а

«быть не равным», т.е.

.
Тогда отношение

означает «быть болше или равно». Для
любых

и

из
множества

соотношение

(или в другой форме

)
означает, что элемент

больше или равенэлемента

,
т.е.

.

2.26.4. Включение отношений

Нестрогое
включение

отношения

в отношение

выполняется тогда и только тогда, когда
множество упорядоченных пар, для которых
выполняется отношение

,
содержится содержится в множестве пар,
для которых выполнено отношение

:

.

Строгое
включение

отношения

в отношение

выполняется тогда и только тогда, когда
множество упорядоченных пар отношения

является подмножеством пар отношения

и

:

.

Пример
2.25

На
множестве

рассмотрим
отношения

и

из
предыдущего примера:

,

и

,

,
где

«быть меньше», т.е.

,
а

«быть меньшим или равным», т.е.

.
Тогда

,
т.е.

.

Рассмотрим
операции второго класса, т.е. операции,
не сводящиеся к теоретико-множественным.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

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

Так что если вы собираетесь начать свое обучение в этой области или вам просто стало интересно, прошу под кат.

Реляционная база данных

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

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

таблица PRODUCTS

Таблица состоит из 4х строк, строка в таблице является кортежем в реляционной теории. Множество упорядоченных кортежей называется отношением.
Перед тем как дать определение отношения, введем еще один термин — домен. Домены применительно к таблице это столбцы.

Для ясности, теперь введем строгое определение отношения.

Пусть даны N множеств D1,D2, …. Dn (домены), отношением R над этими множествами называется множество упорядоченных N-кортежей вида <d1,d1,…dn>, где d1 принадлежит D1 и тд. Множества D1,D2,..Dn называются доменами отношения R.
Каждый элемент кортежа представляет собой значение одного из атрибутов, соответствующего одному из доменов.

Ключи в отношениях

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

таблица DRIVERS

Видно, что в организации может быть несколько водителей, и чтобы однозначно идентифицировать водителя необходимо и значение из столбца “Название организации” и из “Имя водителя”. Такой ключ называется составным.

В реляционной БД таблицы взаимосвязаны и соотносятся друг с другом как главные и подчиненные. Связь главной и подчиненнной таблицы осуществляется через первичный ключ (primary key) главной таблицы и внешний ключ ( foreign key ) подчиненной таблицы.
Внешний ключ это атрибут или набор атрибутов, который в главной таблице является первичным ключем.

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

Операции реляционной алгебры

Основные восемь операций реляционной алгебры были предложены Э.Коддом.

• Объединение
• Пересечение
• Вычитание
• Декартово произведение
• Выборка
• Проекция
• Соединение
• Деление

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

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

таблица SELLERS

Условимся, что в этой таблице ID это внешний ключ, связанный с первичным ключом таблицы PRODUCTS.

Для начала рассмотрим самую простую операцию — имя отношения. Её результатом будет такое же отношение, то есть выполнив операцию PRODUCTS, мы получим копию отношения PRODUCTS.

Проекция

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

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

π_{(ID, PRICE)} PRODUCTS

В результате этой операции получим отношение:

Выборка

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

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

σ_(PRICE>90) PRODUCTS

В условии выборки мы можем использовать любое логическое выражение. Сделаем еще одну выборку с ценой больше 90 и ID товара меньше 300:

σ_{(PRICE>90 ^ ID<300)} PRODUCTS

Совместим операторы проекции и выборки. Мы можем это сделать, потому что любой из операторов в результате возвращает отношение и в качестве аргументов использует также отношение.
Из таблицы с продуктами выберем все компании, продающие продуты дешевле 110.

π_COMPANYσ_{(PRICE<100 )} PRODUCTS

Умножение

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

Получим декартово произведения таблиц PRODUCTS и SELLERS.
Синтаксис операции:

PRODUCTS × SELLERS
Можно заметить, что у двух этих таблиц есть одинаковый домен ID. В подобной ситуации домены с одинаковыми названиями получают префикс в виде названия соответствующего отношения, как показано ниже.
Для краткости перемножим не полные отношения, а выборки с условием ID<235

(цветом выделены одни и те же кортежи)

Для примера использования этой операции представим себе необходимость выбрать продавцов с ценами меньше 90. Без произведения необходимо было бы сначала получить ID продуктов из первой таблицы, потом по этим ID из второй таблицы получить нужные имена SELLER, а с использованием произведения будет такой запрос:

π_(SELLER) σ_{(RODUCTS.ID=SELLERS.ID ^ PRICE<90)} PRODUCTS × SELLERS

В результате этой операции получим отношение:

Соединение и естественное соединение

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

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

Попробуем соединить отношения PRODUCTS и SELLERS и получим отношение.

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

Синтаксис операции:
PRODUCTS ⋈ SELLERS;

Получится такое отношение:

Пересечение и вычитание.

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

Источники информации

• Основы использования и проектирования баз данных — В. М. Илюшечкин
• курс лекций Introduction to Databases — Jennifer Widom, Stanford University

_{Буду благодарен за аргументированные замечания}

Привет, сегодня поговорим про реляционная алгебра, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое
реляционная алгебра, операции объединение пересечение разность декартово произведение выборка проекция соединение , настоятельно рекомендую прочитать все из категории Базы данных, знаний и хранилища данных. Big data, СУБД и SQL и noSQL.

Обзор реляционной алгебры

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

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

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

Замкнутость реляционной алгебры

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

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

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

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

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

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

• Объединение
• Пересечение
• Вычитание
• Декартово произведение

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

• Выборка
• Проекция
• Соединение
• Деление

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

Реляциционная алгебра состоит из операций над отношениями и их составляющими (атрибутами и кортежами). Результат любой операции реляционной алгебры — новое отношение. Такие системы операций называются замкнутыми. Рассмотрим семь основных операций (рис. 1) реляционной алгебры. Они разделены на две группы. В первую входят операции, совершаемые над любыми множествами:

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

Во вторую группу входят операции, применимые только к отношениям:

• выборка,
• проекция,
• соединение.

Рис. 1. Операции реляционной алгебры

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

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

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

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

Операции объединения, пересечения и разности имеют следующие особенности:

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

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

Проекция также производится над кортежами одного отношения. Результат проекции — новое отношение содержащее только заданные атрибуты исходного отношения.

Пример проекции

Из отношения Жители нужно выбрать только фамилии жителей

На языке SQL запрос запрос выглядит так:

     SELECT DISTINCT ФИО FROM Жители;

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

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

Семантически общие атрибуты описывают общие свойства соединяемых отношений. Общие атрибуты должны иметь один тип

Отношения, совместимые по типу

Некоторые реляционные операторы (например, объединение) требуют, чтобы отношения имели одинаковые заголовки. Действительно, отношения состоят из заголовка и тела. Операция объединения двух отношений есть просто объединение двух множеств кортежей, взятых из тел соответствующих отношений. Но будет ли результат отношением? Во-первых, если исходные отношения имеют разное количество атрибутов, то, очевидно, что множество, являющееся объединением таких разнотипных кортежей нельзя представить в виде отношения. Во-вторых, пусть даже отношения имеют одинаковое количество атрибутов, но атрибуты имеют различные наименования. Как тогда определить заголовок отношения, полученного в результате объединения множеств кортежей? В-третьих, пусть отношения имеют одинаковое количество атрибутов, атрибуты имеют одинаковые наименования, но определенны на различных доменах. Тогда снова объединение кортежей не будет образовывать отношение.

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

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

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

Оператор переименования атрибутов

Оператор переименования атрибутов имеет следующий синтаксис:

где

— отношение,

— исходные имена атрибутов,

— новые имена атрибутов.

В результате применения оператора переименования атрибутов получаем новое отношение, с измененными именами атрибутов.

Пример 1.

Следующий оператор возвращает неименованное отношение, в котором атрибут переименован в :

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

Объединение

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

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

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

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

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

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

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

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

Замечание. Как видно из приведенного примера, потенциальные ключи, которые были в отношениях и не наследуются объединением этих отношений. Поэтому, в объединении отношений и атрибут «Табельный номер» может содержать дубликаты значений. Если бы это было не так, и ключи наследовались бы, то это противоречило бы понятию объединения как «объединение множеств». Конечно, объединение отношений и имеет, как и любое отношение, потенциальный ключ, например, состоящий из всех атрибутов.

Пересечение

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

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

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

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

Замечание. Казалось бы, что в отличие от операции объединения, потенциальные ключи могли бы наследоваться пересечением отношений. Однако это не так. Вообще, никакие реляционные операторы не передают результатирующему отношению никаких данных о потенциальных ключах. В качестве причины этого можно было бы привести тривиальное соображение, что так получается более просто и симметрично — все операторы устроены одинаково. На самом деле причина более глубока, и заключается в том, что потенциальный ключ — семантическое понятие, отражающее различимость объектов предметной области. Наличие потенциальных ключей не выводится из структуры отношения, а явно задается для каждого отношения, исходя из его смысла. Реляционные же операторы являются формальнымиоперациями над отношениями и выполняются одинаково, независимо от смысла данных, содержащихся в отношениях. Поэтому, реляционные операторы ничего не могут «знать» о смысле данных. Трактовка результата реляционных операций — дело пользователя.

Вычитание

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

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

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

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

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

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

,

а тело состоит из кортежей, являющихся сцеплением кортежей отношений и :

,

таких, что , .

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

Замечание . Об этом говорит сайт https://intellect.icu . Мощность произведения равна произведению мощностей отношений и , т.к. каждый кортеж отношения соединяется с каждым кортежем отношения .

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

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

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

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

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

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

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

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

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

Выборка (ограничение, селекция)

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

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

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

,

или

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

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

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

Таблица 10 Отношение A WHERE Зарплата<3000

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

Проекция

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

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

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

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

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

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

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

Соединение

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

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

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

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

Общая операция соединения

Определение 8. Соединением отношений и по условию называется отношение

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

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

Тэта-соединение

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

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

Иногда, для операции -соединения применяют следующий, более короткий синтаксис:

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

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

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

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

Таблица 15 Отношение «Какие поставщики поставляют какие детали»

Экви-соединение

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

Синтаксис экви-соединения:

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

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

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

Таблица 18 Отношение PD (Поставки)

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

Обычно, такой сложной формой записи не пользуются. Но как бы то ни было, в результате имеем отношение:

Таблица 19 Отношение «Какие детали поставляются какими поставщиками»

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

Естественное соединение

Определение 10. Пусть даны отношения и , имеющие одинаковые атрибуты (т.е. атрибуты с одинаковыми именами и определенные на одинаковых доменах).

Тогда естественным соединением отношений и называется отношение с заголовком и телом, содержащим множество кортежей , таких, что и .

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

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

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

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

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

поэтому такие соединения можно записывать, опуская скобки:

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

Таблица 20 Отношение P JOIN PD JOIN D

Деление

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

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

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

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

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

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

Таблица 21 Проекция X=PD[PNUM,DNUM]

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

Таблица 22 Проекция Y=D[DNUM]

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

Таблица 23 Отношение X DEVIDEBY Y

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

Примеры использования реляционных операторов

Пример 12. Получить имена поставщиков, поставляющих деталь номер 2.

Решение:

Пример 13. Получить имена поставщиков, поставляющих по крайней мере одну гайку.

Решение:

Ответ на этот запрос можно получить и иначе:

Пример 14. Получить имена поставщиков, поставляющих все детали.

Решение:

Пример 15. Получить имена поставщиков, не поставляющих деталь номер 2.

Решение:

Ответ на этот запрос можно получить и пошагово:

— получить список номеров всех поставщиков

— соединить данные о поставщиках и поставках

— в данных о поставщиках и поставках оставить только данные о поставках детали номер 2.

— получить список номеров поставщиков, поставляющих деталь номер 2.

— получить список номеров поставщиков, не поставляющих деталь номер 2.

— соединить список номеров поставщиков, не поставляющих деталь номер 2 с данными о поставщиках (получатся полные данные о поставщиках, не поставляющих деталь номер 2).

— искомый ответ (имена поставщиков, не поставляющих деталь номер 2).

Зависимые реляционные операторы

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

Оператор соединения

Оператор соединения определяется через операторы декартового произведения и выборки. Для оператора естественного соединения добавляется оператор проекции.

Оператор пересечения

Оператор пересечения выражается через вычитание следующим образом:

Оператор деления

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

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

Примитивные реляционные операторы

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

Оператор декартового произведения

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

Оператор проекции

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

Оператор выборки

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

Операторы объединения и вычитания

Доказательство примитивности операторов объединения и вычитания более сложны и мы их здесь не приводим.

Запросы, невыразимые средствами реляционной алгебры

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

Плохая нормализация отношений

Данный пример взят из книги Гилуа М.М. [6, стр.43].

Пример 16. Пусть имеется отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ с набором атрибутов (Наименование вещества, Водород, Гелий, …, 105_элемент). Значением атрибута «Вещество» являются наименования химических веществ, значениями остальных атрибутов — процентный состав соответствующих элементов в этом веществе. Такое отношение могло бы иметь, к примеру, следующий вид:

Таблица 24 Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ

Рассмотрим запрос «Найти все химические элементы, содержание которых в каком-либо из веществ превышает заданный процент (скажем, 90)».

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

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

На самом деле, этот пример показывает, что таблица плохо нормализована (нормализация отношений рассматривается в гл.6 и 7). В таблице есть набор однотипных атрибутов («Водород», «Гелий» и т.д. в количестве 105 столбцов).

Правильнее разбить это отношение на три различных отношения:

1. ВЕЩЕСТВО(НОМ_ВЕЩЕСТВА, ВЕЩЕСТВО),
2. ЭЛЕМЕНТЫ(НОМ_ЭЛЕМЕНТА, ЭЛЕМЕНТ),
3. ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ(НОМ_ВЕЩЕСТВА, НОМ_ЭЛЕМЕНТА, ПРОЦЕНТ).

Таблица 25 Отношение ВЕЩЕСТВО

Таблица 26 Отношение ЭЛЕМЕНТЫ

Таблица 27 Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ

Для отношений, нормализованных таким образом, исходный запрос реализуется следующей последовательностью операторов:

1. R1(НОМЕР_ВЕЩЕСТВА,НОМ_ЭЛЕМЕНТА,ПРОЦЕНТ)= ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ[ПРОЦЕНТ>90]. (Выборка из отношения).
2. R2(НОМ_ЭЛЕМЕНТА) = R1[НОМ_ЭЛЕМЕНТА]. (Проекция отношения).
3. R3(НОМ_ЭЛЕМЕНТА,ЭЛЕМЕНТ)= R2[НОМ_ЭЛЕМЕНТА=НОМ_ЭЛЕМЕНТА]ЭЛЕМЕНТЫ. (Естественное соединение)
4. ОТВЕТ(ЭЛЕМЕНТ) = R3[ЭЛЕМЕНТ]. (Проекция таблицы).

На языке SQL такой запрос реализуется одной командой:

SELECT ЭЛЕМЕНТЫ.ЭЛЕМЕНТ
  FROM ЭЛЕМЕНТЫ, ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ
  WHERE
    ЭЛЕМЕНТЫ.НОМ_ЭЛЕМЕНТА=ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.НОМ_ЭЛЕМЕНТА
    AND ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.ПРОЦЕНТ>90;

Невыразимость транзитивного замыкания реляционными операторами

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

Пример 17. Рассмотрим отношение, описывающее сотрудников некоего предприятия. Отношение содержит данные о табельном номере сотрудника, фамилии, должности и табельном номере руководителя сотрудника – СОТРУДНИКИ (ТАБ_НОМ, ФАМИЛИЯ, ДОЛЖНОСТЬ, ТАБ_НОМ_РУК):

Таблица 28 Отношение СОТРУДНИКИ

Рассмотрим запрос «Перечислить всех руководителей (прямых и непрямых) данного сотрудника».

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

Кросс-таблицы

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

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

Таблица 29 Данные о продажах

Требуется представить эти данные в виде таблицы, по строкам которой идут наименования товаров, по столбцам — месяцы, а в ячейках содержатся объемы продаж. Это и будет кросс-таблицей:

Таблица 30 Кросс-таблица

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

Выводы

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

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

Теоретико-множественные операторы: объединение, пересечение, вычитание, декартово произведение.

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

Для выполнения некоторых реляционных операторов требуется, чтобы отношения были совместимы по типу.

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

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

Вау!! 😲 Ты еще не читал? Это зря!

• реляционная алгебра ,
• реляционные соединения , операции над отношениями , реляционная алгебра ,

Напиши свое отношение про реляционная алгебра. Это меня вдохновит писать для тебя всё больше и больше интересного. Спасибо Надеюсь, что теперь ты понял что такое реляционная алгебра, операции объединение пересечение разность декартово произведение выборка проекция соединение
и для чего все это нужно, а если не понял, или есть замечания,
то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории
Базы данных, знаний и хранилища данных. Big data, СУБД и SQL и noSQL

Операция объединения

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

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

SELECT R.a1, R.a2 
FROM R
UNION
SELECT S.b2, S.b1 
FROM S

Операция пересечения

Операция пересечения ( INTERSECT ) определяет отношение, которое содержит кортежи, присутствующие как в отношении R, так и в отношении S. Отношения R и S должны быть совместимы по объединению .

Пересечением двух таблиц R и S является таблица, содержащая все строки, присутствующие в обеих исходных таблицах одновременно.

SELECT R.a1, R.a2
FROM R,S
WHERE R.a1=S.b1 AND R.a2=S.b2

   или

SELECT R.a1, R.a2
FROM R
WHERE R.a1 IN    
    (SELECT S.b1 FROM S
     WHERE S.b1=R.a1) AND R.a2 IN
         (SELECT S.b2
          FROM S
          WHERE S.b2=R.a2)

Операция разности

Разность ( EXCEPT ) R-S двух отношений R и S состоит из кортежей, которые имеются в отношении R, но отсутствуют в отношении S. Причем отношения R и S должны быть совместимы по объединению.

Разностью двух таблиц R и S является таблица, содержащая все строки, которые присутствуют в таблице R, но отсутствуют в таблице S.

SELECT R.a1, R.a2
FROM R
WHERE NOT EXISTS 
    (SELECT S.b1,S.b2
     FROM S
     WHERE S.b1=R.a2 AND S.b2=R.a1)

Операция деления отношений

Результат операции деления R:S — набор кортежей отношения R, определенных на множестве атрибутов C, которые соответствуют комбинации всех кортежей отношения S .

T1=ПC( R );
T2=ПC( (S X T1) -R );
T=T1 - T2.

Отношение R определено на множестве атрибутов A, а отношение S — на множестве атрибутов B, причем и C=A — B.

Пусть A ={имя, пол, рост, возраст, вес}; B ={имя, пол, возраст}; C ={рост, вес}.

Пример 5.16. Деление отношений в SQL.

• Создание отношения R

  CREATE TABLE R
  (i     int primary key,
  имя    varchar(3),
  пол    varchar(3),
  рост   int,
  возраст int,
  вес    int)

  5.16a.
  Деление отношений в SQL.

• Создание отношения S

  CREATE TABLE S
  (i     int primary key,
  имя    varchar(3),
  пол    varchar(3),
  возраст int)

  5.16b.
  Деление отношений в SQL.

• Создание отношения T1

  CREATE VIEW T1
  AS 
  SELECT рост,вес
  FROM R

  5.16c.
  Деление отношений в SQL.

• Создание отношения TT

  CREATE VIEW TT AS
  SELECT S.имя, S.пол, S.возраст, 
         T1.рост, T1.вес
  FROM S, T1

  5.16d.
  Деление отношений в SQL.

• Создание отношения T2

  CREATE VIEW T2
  AS
  SELECT TT.рост, TT.вес
  FROM TT
  WHERE NOT EXISTS 
      (SELECT R.рост, R.вес
       FROM R
       WHERE TT.имя=R.имя AND TT.пол=R.пол
             AND TT.возраст=R.возраст 
             AND TT.рост=R.рост 
  		   AND TT.вес=R.вес)

  5.16e.
  Деление отношений в SQL.

• Создание отношения T

  SELECT T1.рост, T1.вес
  FROM T1
  WHERE NOT EXISTS 
      (SELECT T2.рост,T2.вес
       FROM T2
       WHERE T1.рост=T2.рост AND T1.вес=T2.вес)

  5.16f.
  Деление отношений в SQL.

Понять то, как происходит пересечение множеств, легко на простом примере:
Если A ={1, 3, 5, 7} и B ={2,3,6,7,9}, то A ∩ B = {3,7}.
Или: если A ={1, 4, 5, 8} и B ={2,5,7,8,9}, то A • B = {5,8}

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