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

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

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

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

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

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

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

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

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

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

Номер поставщика PNUM	Наименование поставщика PNAME	Номер детали DNUM	Наименование детали DNAME	Поставляемое количество VOLUME
	Иванов		Болт
	Иванов		Гайка
	Иванов		Винт
	Петров		Болт
	Петров		Гайка
	Сидоров		Болт

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

7.1.4. Деление

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

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

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

A DEVIDEBY B

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

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

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

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

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

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

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

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

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

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

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

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

7.2. Реляционные операторы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7.3. Выводы

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

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

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

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

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

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

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

Лекция 8. Реляционное исчисление.

Дата добавления: 2014-01-05