Таблица 5 Отношение A MINUS B
Декартово произведение
Определение 5. Декартовым произведением двух отношений  и  называется отношение, заголовок которого является сцеплением заголовков отношений  и  :
 ,
а тело состоит из кортежей, являющихся сцеплением кортежей отношений и :
 ,
таких, что  ,  .
Синтаксис операции декартового произведения:
Замечание. Мощность произведения равна произведению мощностей отношений и , т.к. каждый кортеж отношения соединяется с каждым кортежем отношения .
Замечание. Если в отношения и имеются атрибуты с одинаковыми наименованиями, то перед выполнением операции декартового произведения такие атрибуты необходимо переименовать.
Замечание. Перемножать можно любые два отношения, совместимость по типу при этом не требуется.
Пример 5. Пусть даны два отношения и с информацией о поставщиках и деталях:
Номер поставщика
|
Наименование поставщика
|
1
|
Иванов
|
2
|
Петров
|
3
|
Сидоров
|
Таблица 6 Отношение A (Поставщики)
Номер детали
|
Наименование детали
|
1
|
Болт
|
2
|
Гайка
|
3
|
Винт
|
Таблица 7 Отношение B (Детали)
Декартово произведение отношений и будет иметь вид:
Номер поставщика
|
Наименование поставщика
|
Номер детали
|
Наименование детали
|
1
|
Иванов
|
1
|
Болт
|
1
|
Иванов
|
2
|
Гайка
|
1
|
Иванов
|
3
|
Винт
|
2
|
Петров
|
1
|
Болт
|
2
|
Петров
|
2
|
Гайка
|
2
|
Петров
|
3
|
Винт
|
3
|
Сидоров
|
1
|
Болт
|
3
|
Сидоров
|
2
|
Гайка
|
3
|
Сидоров
|
3
|
Винт
|
Таблица 8 Отношение A TIMES B
Замечание. Сама по себе операция декартового произведения не очень важна, т.к. она не дает никакой новой информации, по сравнению с исходными отношениями. Для реальных запросов эта операция почти никогда не используется. Однако операция декартового произведения важна для выполнения специальных реляционных операций, о которых речь пойдет ниже.
Специальные реляционные операторы
Выборка (ограничение, селекция)
Определение 6. Выборкой (ограничением, селекцией) на отношении с условием  называется отношение с тем же заголовком, что и у отношения , и телом, состоящем из кортежей, значения атрибутов которых при подстановке в условие дают значение ИСТИНА. представляет собой логическое выражение, в которое могут входить атрибуты отношения и (или) скалярные выражения.
В простейшем случае условие имеет вид  , где  - один из операторов сравнения ( и т.д.), а  и  - атрибуты отношения или скалярные значения. Такие выборки называются -выборки (тэта-выборки) или -ограничения, -селекции.
Синтаксис операции выборки:
 ,
или
Пример 6. Пусть дано отношение с информацией о сотрудниках:
Табельный номер
|
Фамилия
|
Зарплата
|
1
|
Иванов
|
1000
|
2
|
Петров
|
2000
|
3
|
Сидоров
|
3000
|
Таблица 9 Отношение A
Результат выборки  будет иметь вид:
Табельный номер
|
Фамилия
|
Зарплата
|
1
|
Иванов
|
1000
|
2
|
Петров
|
2000
|
Таблица 10 Отношение A WHERE Зарплата<3000
Смысл операции выборки очевиден - выбрать кортежи отношения, удовлетворяющие некоторому условию. Таким образом, операция выборки дает "горизонтальный срез" отношения по некоторому условию.
Проекция
Определение 7. Проекцией отношения по атрибутам  , где каждый из атрибутов принадлежит отношению , называется отношение с заголовком  и телом, содержащим множество кортежей вида  , таких, для которых в отношении найдутся кортежи со значением атрибута равным  , значением атрибута равным  , …, значением атрибута  равным  .
Синтаксис операции проекции:
Замечание. Операция проекции дает "вертикальный срез" отношения, в котором удалены все возникшие при таком срезе дубликаты кортежей.
Пример 7. Пусть дано отношение с информацией о поставщиках, включающих наименование и месторасположение:
Номер поставщика
|
Наименование поставщика
|
Город поставщика
|
1
|
Иванов
|
Уфа
|
2
|
Петров
|
Москва
|
3
|
Сидоров
|
Москва
|
4
|
Сидоров
|
Челябинск
|
Таблица 11 Отношение A (Поставщики)
Проекция  будет иметь вид:
Город поставщика
|
Уфа
|
Москва
|
Челябинск
|
Таблица 12 Отношение A[Город поставщика]
Соединение
Операция соединения отношений, наряду с операциями выборки и проекции, является одной из наиболее важных реляционных операций.
Обычно рассматривается несколько разновидностей операции соединения:
Общая операция соединения
-соединение (тэта-соединение)
Экви-соединение
Естественное соединение
Наиболее важным из этих частных случаев является операция естественного соединения. Все разновидности соединения являются частными случаями общей операции соединения.
Общая операция соединения
Определение 8. Соединением отношений и по условию называется отношение
представляет собой логическое выражение, в которое могут входить атрибуты отношений и и (или) скалярные выражения.
Таким образом, операция соединения есть результат последовательного применения операций декартового произведения и выборки. Если в отношениях и имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты необходимо переименовать.
Тэта-соединение
Определение 9. Пусть отношение содержит атрибут , отношение содержит атрибут , а - один из операторов сравнения ( и т.д.). Тогда -соединением отношения по атрибуту с отношением по атрибуту называют отношение
Это частный случай операции общего соединения.
Иногда, для операции -соединения применяют следующий, более короткий синтаксис:
Пример 8. Рассмотрим некоторую компанию, в которой хранятся данные о поставщиках и поставляемых деталях. Пусть поставщикам и деталям присвоен некий статус. Пусть бизнес компании организован таким образом, что поставщики имеют право поставлять только те детали, статус которых не выше статуса поставщика (смысл этого может быть в том, что хороший поставщик с высоким статусом может поставлять больше разновидностей деталей, а плохой поставщик с низким статусом может поставлять только ограниченный список деталей, важность которых (статус детали) не очень высока).
Номер поставщика
|
Наименование поставщика
|
X
(Статус поставщика)
|
1
|
Иванов
|
4
|
2
|
Петров
|
1
|
3
|
Сидоров
|
2
|
Таблица 13 Отношение A (Поставщики)
Номер детали
|
Наименование детали
|
Y
(Статус детали)
|
1
|
Болт
|
3
|
2
|
Гайка
|
2
|
3
|
Винт
|
1
|
Таблица 14 Отношение B (Детали)
Ответ на вопрос "какие поставщики имеют право поставлять какие детали?" дает -соединение  :
Номер поставщика
|
Наименование поставщика
|
X
(Статус поставщика)
|
Номер детали
|
Наименование детали
|
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
|
Таблица 15 Отношение "Какие поставщики поставляют какие детали"
Естественное соединение
Определение 10. Пусть даны отношения  и  , имеющие одинаковые атрибуты  (т.е. атрибуты с одинаковыми именами и определенные на одинаковых доменах).
Тогда естественным соединением отношений и называется отношение с заголовком  и телом, содержащим множество кортежей  , таких, что  и  .
Естественное соединение настолько важно, что для него используют специальный синтаксис:
Замечание. В синтаксисе естественного соединения не указываются, по каким атрибутам производится соединение. Естественное соединение производится по всем одинаковым атрибутам.
Замечание. Естественное соединение эквивалентно следующей последовательности реляционных операций:
Переименовать одинаковые атрибуты в отношениях
Выполнить декартово произведение отношений
Выполнить выборку по совпадающим значениям атрибутов, имевших одинаковые имена
Выполнить проекцию, удалив повторяющиеся атрибуты
Переименовать атрибуты, вернув им первоначальные имена
Замечание. Можно выполнять последовательное естественное соединение нескольких отношений. Нетрудно проверить, что естественное соединение (как, впрочем, и соединение общего вида) обладает свойством ассоциативности, т.е.
поэтому такие соединения можно записывать, опуская скобки:
Пример 10. В предыдущем примере ответ на вопрос "какие детали поставляются поставщиками", более просто записывается в виде естественного соединения трех отношений  (для удобства просмотра порядок атрибутов изменен, это является допустимым по свойствам отношений):
Номер поставщика
PNUM
|
Наименование поставщика
PNAME
|
Номер детали
DNUM
|
Наименование детали
DNAME
|
Поставляемое количество
VOLUME
|
1
|
Иванов
|
1
|
Болт
|
100
|
1
|
Иванов
|
2
|
Гайка
|
200
|
1
|
Иванов
|
3
|
Винт
|
300
|
2
|
Петров
|
1
|
Болт
|
150
|
2
|
Петров
|
2
|
Гайка
|
250
|
3
|
Сидоров
|
1
|
Болт
|
1000
|
Таблица 20 Отношение P JOIN PD JOIN D
Деление
Определение 11. Пусть даны отношения  и  , причем атрибуты  - общие для двух отношений. Делением отношений на называется отношение с заголовком  и телом, содержащим множество кортежей  , таких, что для всех кортежей  в отношении найдется кортеж  .
Отношение выступает в роли делимого, отношение выступает в роли делителя. Деление отношений аналогично делению чисел с остатком.
Синтаксис операции деления:
Замечание. Типичные запросы, реализуемые с помощью операции деления, обычно в своей формулировке имеют слово "все" - "какие поставщики поставляют все детали?".
Пример 11. В примере с поставщиками, деталями и поставками ответим на вопрос, "какие поставщики поставляют все детали?".
В качестве делимого возьмем проекцию  , содержащую номера поставщиков и номера поставляемых ими деталей:
Номер поставщика
PNUM
|
Номер детали
DNUM
|
1
|
1
|
1
|
2
|
1
|
3
|
2
|
1
|
2
|
2
|
3
|
1
|
Таблица 21 Проекция X=PD[PNUM,DNUM]
В качестве делителя возьмем проекцию  , содержащую список номеров всех деталей (не обязательно поставляемых кем-либо):
Таблица 22 Проекция Y=D[DNUM]
Деление  дает список номеров поставщиков, поставляющих все детали:
Таблица 23 Отношение X DEVIDEBY Y
Оказалось, что только поставщик с номером 1 поставляет все детали.
Зависимые реляционные операторы
Как было сказано в начале главы, не все операторы реляционной алгебры являются независимыми - некоторые из них выражаются через другие реляционные операторы.
Оператор соединения
Оператор соединения определяется через операторы декартового произведения и выборки. Для оператора естественного соединения добавляется оператор проекции.
Оператор пересечения
Оператор пересечения выражается через вычитание следующим образом:
Оператор деления
Оператор деления выражается через операторы вычитания, декартового произведения и проекции следующим образом:
Таким образом показано, что операторы соединения, пересечения и деления можно выразить через другие реляционные операторы, т.е. эти операторы не являются примитивными.
Примитивные реляционные операторы
Оставшиеся реляционные операторы (объединение, вычитание, декартово произведение, выборка, проекция) являются примитивными операторами - их нельзя выразить друг через друга.
Оператор декартового произведения
Оператор декартового произведения - это единственный оператор, увеличивающий количество атрибутов, поэтому его нельзя выразить через объединение, вычитание, выборку, проекцию.
Оператор проекции
Оператор проекции - единственный оператор, уменьшающий количество атрибутов, поэтому его нельзя выразить через объединение, вычитание, декартово произведение, выборку.
Оператор выборки
Оператор выборки - единственный оператор, позволяющий проводить сравнения по атрибутам отношения, поэтому его нельзя выразить через объединение, вычитание, декартово произведение, проекцию.
Операторы объединения и вычитания
Доказательство примитивности операторов объединения и вычитания более сложны и мы их здесь не приводим.
Запросы, невыразимые средствами реляционной алгебры
Несмотря на мощь языка реляционной алгебры, имеется ряд типов запросов, которые принципиально нельзя выразить только при помощи операторов реляционной алгебры. Это вовсе не означает, что ответы на эти запросы нельзя получить вообще. Просто, для получения ответов на подобные запросы приходится применять процедурные расширения реляционных языков.
Дополнительные операции реляционной алгебры,предложенные Дейтом, включают следующие операции.
Операция переименования позволяет изменить имя атрибута отношения и имеет вид:
RENAME <исходное отношение> <старое имя атрибута> AS <новое имя атрибута>, где <исходное отношение> задается именем отношения либо выражением реляционной алгебры.
В последнем случае выражение заключают в круглые скобки. Например:
RENAME Город_П AS Город_размещения_Поставщика.
Замечание.
Для удобства записи выражений одновременного переименования нескольких атрибутов Дейтом введена операция множественного переименования, которая представима следующим образом:
RENAME <отн.> <ст. имя атр.1> AS <нов. имя атр.1>,<ст. имя атр.2> AS <нов. имя атр.2>,... ,<ст. имя arp.N> AS <нов. имя aTp.N>.
Операция расширения порождает новое отношение, похожее на исходное, но отличающееся наличием добавленного атрибута, значения которого получаются путем некоторых скалярных вычислений. Операция расширения имеет вид:
EXTEND <исходное отношение> ADD <выражение> AS <новый атрибут>, где к исходному отношению добавляется (ключевое слово ADD) <новый атрибут>, подсчитываемый по правилам, заданным <выражением>.
Исходное отношение может быть задано именем отношения и с помощью выражения реляционной алгебры, заключенного в круглые скобки. При этом имя нового атрибута не должно входить в заголовок исходного отношения и не может использоваться в <выражении>. Помимо обычных арифметических операций и операций сравнения, в выражении можно использовать различные функции, называемые итоговыми, такие как:
COUNT (количество), SUM (сумма), AVG (среднее), МАХ (максимальное), MIN (минимальное).
Например:
EXTEND (PJOIN SP) ADD (Вес * Количество) AS Общий_Вес.
Замечания.
 Пользуясь операцией расширения, можно выполнить переименование атрибута. Для этого нужно в выражении указать имя атрибута, в конструкции AS определить новое имя этого атрибута, затем выполнить проекцию полученного отношения на множество атрибутов, исключая старый атрибут. Таким образом, запись (EXTEND S ADD Город_П AS Город) [П#, Имя, Статус, Город] эквивалента конструкции S RENAME Город_П AS Город.
Подобно тому, как это сделано для операции переименования, Дейт определил операцию множественного расширения, которая позволяет в одной синтаксической конструкции вычислять несколько новых атрибутов. Формально операция пред-ставима следующим образом:
EXTEND <отн.> ADD <выр.1> AS <атр.1>, <выр.2> AS <атр.2>,... ,<выр.N> AS <атр.N>.
Операция подведения итогов SUMMARIZE выполняет "вертикальные" или групповые вычисления и имеет следующий формат:
SUMMARIZE <исх. отн> BY (<список атрибутов;") ADD <выр.> AS <новый атрибут>, где исходное отношение задается именем отношения либо заключенным в круглые скобки выражением реляционной алгебры, <список атрибутов> представляет собой разделенные запятыми имена атрибутов исходного отношения A1, A2, ..., AN, <выр.> - скалярное выражение, аналогичное выражению операции EXTEND, а <новый атрибут> - имя формируемого атрибута.
В списке атрибутов и в выражении не должен использоваться <новый атрибут>.
Результатом операции SUMMARIZE является отношение R с заголовком, состоящим из атрибутов списка, расширенного новым атрибутом. Для получения тела отношения R сначала выполняется проецирование (назовем проекцию R1) исходного отношения на атрибуты A1, A2,..., AN, после чего каждый кортеж проекции расширяется новым (N+1)-M атрибутом. Поскольку проецирование, как правило, приводит к сокращению количества кортежей по отношению к исходному отношению (удаляются одинаковые кортежи), то можно считать, что происходит своеобразное группирование кортежей исходного отношения: одному кортежу отношения R1 соответствует один или более (если было дублирование при проецировании) кортежей исходного отношения. Значение (N+1)-гo атрибута каждого кортежа отношения R формируется путем вычисления выражения над соответствующей этому кортежу группой кортежей исходного отношения.
Пример 8. Подведение итогов.
Пусть требуется вычислить количество поставок по каждому из поставщиков.
SUMMARIZE SP BY (П#) ADD COUNT AS Количество_поставок
П#
|
Количество_поставок
|
S1
|
6
|
S2
|
2
|
S3
|
1
|
S4
|
3
|
|
Отметим, что функция COUNT определяет количество кортежей в каждой из групп исходного отношения.
Операция множественного подведения итогов, подобно соответствующим операциям переименования и расширения, выполняет одновременно несколько "вертикальных" вычислений и записывает результаты в отдельные новые атрибуты. Простейшим примером такой операции может служить следующая запись:
SUMMARIZE SP BY (Д#) ADD SUM Количество AS Общее_число_прставок AVG Количество AS Среднее_число_поставок.
К основным операторам, позволяющим изменять тело существующего отношения, отнесем операции:
реляционного присвоения,
вставки,
обновления,
удаления.
Операцию присвоения можно представить следующим образом:
<выражение-цель>:= <выражение-источник>, где оба выражения задают совместимые (точнее, эквивалентные) по структуре отношения.
Типичный случай выражений: в левой части - имя отношения, а в правой - некоторое выражение реляционной алгебры. Выполнение операции присвоения сводится к замене предыдущего значения отношения на новое (начальное значение, если тело отношения было пустым), определенное выражением-источником.
С помощью операции присвоения можно не только полностью заменить все значения отношения-цели, но и добавить или удалить кортежи. Приведем пример, в котором в отношение S дописывается один кортеж:
S:=S UNION {{< П# : 'S6' >, < Имя: 'Борис' >, < Статус: '50' >, <Город_П : 'Мадрид' >}}.
Более удобными операциями изменения тела отношения являются операции вставки, обновления и удаления.
Операция вставки INSERT имеет следующий вид:
INSERT <выражение-источник> INTO <выражение-цель>, где оба выражения должны быть совместимы по структуре.
Выполнение операции сводится к вычислению <выражение-источник> и вставке полученных кортежей в отношение, заданное <выражение-цель>. Пример:
INSERT (S WHERE Город_П='Москва') INTO Temp.
Операция обновления UPDATE имеет следующий вид:
UPDATE <выражение-цель> <список элементов>, где <список элементов> представляет собой последовательность разделенных запятыми операций присвоения <атрибут> := <скалярное выражение>.
Результатом выполнения операции обновления является отношение, полученное после присвоения соответствующих значений атрибутам отношения, заданного целевым выражением.
Например, UPDATE P WHERE Тип='каленый' Город := 'Киев'. Эта операция предписывает изменить значение атрибута Город (независимо от того, каким оно было) на новое значение - 'Киев' таких кортежей отношения P, атрибут Тип которых имеет значение 'каленый'.
Операция удаления DELETE имеет следующий вид:
DELETE <выражение-цель>, где <выражение-цель> представляет собой реляционное выражение, описывающее удаляемые кортежи.
Например, DELETE S WHERE Статус < 20.
Операция реляционного сравнения может использоваться для прямого сравнения двух отношений. Она имеет синтаксис:
<выражение1> ? <выражение2>, где оба выражения задают совместимые по структуре отношения, а знак ? - один из следующих операторов сравнения: = (равно), ? (не равно), < (собственное подмножество), < (подмножество), >. (надмножество), > (собственное надмножество).
Например, сравнение: "Совпадают ли города поставщиков и города хранения деталей?" можно записать так:
S [Город_П] = Р [Город_Д].
В теории баз данных известно, что исходное отношение может быть получено из набора соответствующих ему нормализованных путем их естественного соединения [6]. Причем, в силу коммутативности и ассоциативности операции соединения, порядок их соединения не имеет значения.
Таким образом, (3) примет вид:
q = (EXTEND (r1 JOIN r2, JOIN … JOIN rs) ADD f(A1, A2, …, Ak) AS N) [ L, N ] (4)
Полученное соотношение позволяет вести расчет величины n множеству абонентов, используя для этого не отдельные значения характеристик, а их множества. Другими словами при расчете программа оперирует не с отдельными значениями переменных, а с векторами, составленными из множества значений одного атрибута, взятых для всех абонентов. Такой подход позволяет сократить количество операций чтения/записи и тем самым повысить скорость выполнения операции в целом. Поясним этот факт следующими рассуждениями.
|
