Реляционная алгебра
Тема: Манипулирование отношениями (Реляционная алгебра).
Гибкость реляционной базы заключается в том, что отношения можно разрезать и склеивать. Для этого введены разнообразные операции.
a. Прежде всего, нужно уметь выделять из отношения нужные столбцы. Эта операция называется проекцией. В операции проектирования участвует единственный операнд, который обозначается ИФ (имя файла) – это может быть как файл с исходными данными, так и полученный в результате преобразований реляционной алгебры.
Формат записи операции следующий:
рroj «список имен полей» (*ИФ*)
В список имен полей входят только те поля, которые должны составлять структуру файла ИФ.
Результат операции проектирования формируется следующим образом:
a. Из файла ИФ удаляются все поля, имена которых не фигурируют в списке;
b. Из полученной в пункте а) совокупности записей удаляются повторяющиеся, так что итог не содержит одинаковых записей.
Рекомендуемые материалы
Пример 1 приведен на рисунке 27.1
Служащий
| №_служащего | Имя_служащего | №_отдела | Зарплата | Адрес |
| 53702 | Васильев | 721 | 120 | Москва |
| 53703 | Иванов | 721 | 230 | Москва |
| 53791 | Кузнецов | 007 | 500 | Новосибирск |
| 53800 | Галкин | 402 | 110 | С.-Петербург |
| 53805 | Семин | 721 | 190 | Москва |
| 53806 | Федоров | 402 | 100 | С.-Петербург |
Служ.= proj №_служащего, Имя_служащего, №_отдела, з/п (Служащий)
Отдел = proj №_отдела, Адрес (Служащий)
Служащий
| №_служащего | Имя_служащего | №_отдела | Зарплата |
| 53702 | Васильев | 721 | 120 |
| 53703 | Иванов | 721 | 230 |
| 53791 | Кузнецов | 007 | 500 |
| 53800 | Галкин | 402 | 110 |
| 53805 | Семин | 721 | 190 |
| 53806 | Федоров | 402 | 100 |
Отдел
| №_отдела | Адрес |
| 721 | Москва |
| 007 | Новосибирск |
| 402 | С.-Петербург |
Рис. 27.1
б. Операция соединения отношений является обратной к операции разрезания (проекции). В операции соединения участвуют два операнда, обозначаемые ИФ1 и ИФ2.
Формат записи операции: ИФ1 join ИФ2.
Результатом операции соединения является конкатенация (слияние двух строк в одну) каждой записи ИФ1 с каждой записью ИФ2, у которых совпадают данные в общем поле, причем само это поле в образующейся записи помещается лишь однажды. Общее поле должно иметь одинаковое имя и тип в обоих файлах.
a. Для простоты возьмем одно общее поле.
Пример 2: Служ. join Отд.
Результатом операции будет восстановление файла Служащий.
b. Соединение двух файлов, не имеющих ни одного общего поля, является пустое множество.
c. Если у файлов ИФ1 и ИФ2 несколько общих полей, то соединение включает конкатенацию каждой записи ИФ1 с каждой записью ИФ2, у которой совпадают с первой значения всех общих полей.
Пример 3
ИФ1 ИФ2
| G1 | F1 | F2 |
| d | 3 | H |
| h | 7 | N |
| y | 4 | H |
| F1 | F2 | G2 |
| 3 | H | A |
| 3 | H | B |
| 7 | N | A |
| 4 | H | C |
| 4 | H | B |
ИФ1 join ИФ2
| G1 | F1 | F2 | G2 |
| d | 3 | H | A |
| d | 3 | H | B |
| h | 7 | N | A |
| y | 4 | H | C |
| y | 4 | H | b |
Рис.27.2
Можно вывести еще целый ряд операций над отношениями.
в. Операция выбора. Имеет один операнд – ИФ.
Синтаксис операции выбора: sel условие (ИФ).
Результатом операции является совокупность записей ИФ, объединяющая лишь те из них, которые удовлетворяют заданному условию.
Пример 4: sel №_отдела > 100 (Отд.)
Результат операции
| №_отдела | Отдел |
| 721 | Москва |
| 402 | С. - Петербург |
Рис. 27.3
В условии одиночные символы и строки помещают в апострофы, чтобы отличать от имен полей и др.
Условие, определяющее результат выбора, представляет собой выражение, которое может включать операции сравнения >, =, <, < >, < =, > =, а также логические операции and(“и”), or(“или”) и not(“не”).
Наряду с перечисленными операциями в реляционной алгебре определены операции объединения, пересечения и вычитания, которые применяются только к файлам с одинаковыми именами и типами полей, то есть у файлов операндов должна совпадать структура записей.
г. Операция объединения.
Синтаксис: ИФ1 union ИФ2.
Результат – совокупность записей, входящих в один, а возможно и в два операнда.
Пример 5:
ИФ1 ИФ2 ИФ1 union ИФ2
| F1 | G2 |
| a | 4 |
| b | 5 |
| c | 6 |
| F1 | G1 |
| d | 2 |
| b | 5 |
| e | 4 |
| c | 6 |
| F1 | G1 |
| a | 4 |
| b | 5 |
| c | 6 |
| d | 2 |
| e | 4 |
Рис. 27.4
При ответах на некоторые запросы вместо объединения предпочтительнее пользоваться выбором, включая в его условие операцию «ИЛИ». Это замечание для тех запросов, которые используют информацию из одного файла. В примере , демонстрирующем такую ситуацию, использованы файлы с рисунка 26.
Пример 6: определить номера отделов, в которых используются номера работ 7 и 12.
proj №_отдела (sel (№_работы = 7) оr (№_работы = 12)(Работа))
Пример 7: определить имя служащего либо работающего в третьем отделе, либо занимающего должность зам. начальника отдела
proj Имя_служащего (sel №_отдела = 3 (Служащий))
union proj Имя_служащего(Служащий join proj №_служащего (sel должность = «зам. начальника отдела» (Трудовая деятельность))
д. Операция пересечения.
Синтаксис: ИФ1 intersection ИФ2.
Результат – набор записей, входящих в состав обоих файлов.
Пример:
ИФ1 ИФ2 ИФ1 intersection ИФ2
| F1 | G1 |
| a | 8 |
| b | 5 |
| c | 6 |
| F1 | G1 |
| e | 12 |
| b | 5 |
| d | 1 |
| c | 6 |
| F1 | G1 |
| b | 5 |
| c | 6 |
Рис.27.5
Замечание. Для запросов, использующих один файл удобнее пользоваться операцией выбора с логическим «И».
Пример 8: определить №_отдела, в котором выполняют работу вида 2 и 4.
рroj №_отдела (sel (№_работы = 2) and (№_работы = 4)(Работа)).
Пример 9: определить № отдела, в которой выполняют работу 9 и ведут отчетность по форме 5
proj №_отдела(sel отчетность = 5 (отдел)) intersection proj №_отдела(sel№_работы = 9 (Работа)).
е. Операция вычитания.
Синтаксис: ИФ1 difference ИФ2
Результат – совокупность записей, имеющихся в ИФ1, но отсутствующих в ИФ2.
Пример 10:
ИФ1 ИФ2 ИФ1 union ИФ2
| F1 | G1 |
| a | 4 |
| b | 5 |
| c | 6 |
| f | 5 |
| F1 | G1 |
| d | 1 |
| b | 5 |
| e | 4 |
| c | 6 |
| F1 | G1 |
| a | 4 |
| f | 5 |
Рис.27.6
Пример 11: составить список сотрудников, у которых нет детей
proj Имя_служащего((proj №_служащего (Служащий) difference proj №_служащего (Дети)) join Служащий).
ё. Операция деления.
Синтаксис: ИФ1 division ИФ2
Условия выполнения – каждое поле ИФ2 имело те же имя и тип, что и одно из полей ИФ1. В результате деления получается файл, поля которого содержатся в ИФ1, но отсутствуют в ИФ2. Запись включается в результат только при том условии, что в ИФ1 она сцеплена с каждой записью из ИФ2.
Пример12:
ИФ1 ИФ2 ИФ1 division ИФ2
| G2 | F1 | G1 |
| A | d | 3 |
| C | h | 7 |
| B | h | 7 |
| B | y | 4 |
| A | y | 4 |
| A | h | 7 |
| B | d | 3 |
| C | y | 4 |
| F1 | G1 |
| 3 | d |
| 7 | h |
| 4 | y |
| G2 |
| A |
| B |
Рис.27.7
Запись А, В включена в результат, так как в ИФ1 есть записи,
| G2 | G1 | F1 |
| A | d | 3 |
| A | h | 7 |
| A | y | 4 |
аналогично для записи В, запись С отсутствует, так как в ИФ1 нет записи С d З.
Пример 13:
Определить список отделов, в которых выполняются все виды работ.
Работа division (proj №_работы, описание работы (Работа)).
ж. Операция Умножение (декартово произведение).
Синтаксис: ИФ1 product ИФ2
Результат – совокупность записей, представляющих конкатенацию каждой записи ИФ1 с каждой записью ИФ2.
Пример 14:
| F1 | F2 |
| b | 4 |
| d | 7 |
ИФ1 ИФ2 ИФ1 product ИФ2
| F3 | F4 |
| A | 4 |
| C | R |
| ИФ1.F1 | ИФ1.F2 | ИФ1.F3 | ИФ1.F4 |
| b | 4 | A | 4 |
| b | 4 | C | R |
| d | 7 | A | 4 |
| d | 7 | C | R |
Рис.27.8
В образованном файле каждое поле сохраняет прежнее имя, но оно дополняется именем файла, из которого взято. Это делается, чтобы избежать совпадения имен полей в одноименном файле.
Пример 15: определить список лиц, которые получили повышение оклада после того, как Иванов (№_служащего 15) занял должность главного инженера.
proj Имя_служащего (proj №_служащего (sel Изм, Окл. Дата_устр.> Труд. Деятельность. Дата_назначения (Изм. оклада product (sel №_служащего = 15 and должность = «главный инженер» (Труд. деятельность)))) join служащий).
Систему операций, используемую для манипулирования отношениями, называют алгеброй отношений. Оператор в ней имеет одно или несколько отношений в качестве операнда и образует новое отношение по определенному правилу.
Можно и далее разработать набор операций для своих узких целей, использую исчисление отношений. Исчисление отношений – это аппарат для формулирования отношения, которое можно получить из хранимых в БД отношений, он предоставляет машине самой решать, какие операции необходимо выбрать для получения нужного отношения из БД.
Символика в исчислении отношений.
| Символ | Объяснение |
| x • y | Множество значений элементов данных из доменов у отношения х. |
| A(x1·y1, x2·y2… ) | Отношение с именем А задано над доменами, которые являются множествами значений х1·у1, х1·у2, … соответственно. |
| ∃ | «Существует» |
| : | «Такой, что». Выражение слева от двоеточия означает то, что должно быть найдено выражение справа – условие. |
| ∀ | Для любого |
| ⋀ | «И» должны выполняться одновременно условия слева и справа от знака. |
| ⋁ | «ИЛИ» должно выполняться хотя бы одно из двух условий. |
| − | «НЕ» условие, записанное справа от знака должно не выполняться. |
| ≠, =, <, >. | Не равно, равно, меньше, больше |
| ‘x’ | Символьное значение х. |
Рис. 28.
В таблице на рисунке 28 приведен список символов, которые используются в вычислении отношений. Рассмотрим несколько типичных примеров использования исчисления отношений:
Пример 1: из отношения служащий образовать отношение Q, включающее признаки Имя_служащего и з/пл для всех сотрудников отдела 721 с з/пл более 2000:
Q (Служащий ∙ Имя_служащего, Служащий ∙ з/пл):Служащий · №_отдела = 721 ∧ Служащий ∙ з/пл > 2000.
Пример 2: с помощью отношений
Р123 (учетный_№, Дата_преступления, вид_преступления, срок_заключения)
А117(учетный_№, Имя, адрес, почтовый_индекс)
А125(учетный_№, Имя, профессия, годовой_доход)
образовать отношение Q, содержащее признаки: вид_преступления и срок_заключения лиц с профессией Бухгалтер:
Q(Р123∙вид_преступления, Р123∙срок_заключения) : ∃ А125 (А125 ∙ профессия = «Бухгалтер» ∧ А125 ∙ учетный номер = Р123 ∙ Учетный_№).
Пример 3: используя отношения
Студент (№_студента, Имя_студента, прочие_сведения_о_студенте).
Преподаватель (№_преподавателя, Имя_преподавателя, прочие_сведения_о_преподавателе)
Студ_Преп(№_студента, №_преподавателя)
образовать отношение, содержащее сведения о студентах, которые обучаются у всех преподавателей:
Q(Студент∙№_студента, Студент∙Имя_студента) : ∀ преподаватель ∃ ∧ Студ_Преп (Студ_преп∙№_студента = Студент ∙ №_студента ∧ Студ_Преп ∙ №_преподавателя = Преподаватель ∙ №_преподавателя).
Отметим некоторые преимущества исчисления отношений по сравнению с алгеброй отношений. Во-первых, пользователя не интересует, каким именно образом машина получит нужный ему результат; машина же имеет некоторую свободу для выбора наилучшего способа получения результата. Во-вторых, процедуры, обеспечивающие секретность данных, выглядят гораздо проще, так как они связаны явно выраженными в запросе требованиями к данным, а не с процедурами пользователя. В-третьих, для пользователя – непрограммиста естественнее требовать данные по их названиям, чем вводить собственный набор операций.
Недостатком исчисления отношений является сложность его разработки. Исчисление отношений требует более высокого уровня автоматизации.
Итак, можно выделить три уровня автоматизации, применяемые в языках пользователя БД:
1. Исчисление. Высший уровень автоматизации. Пользователь непосредственно обращается к машине, и машина его понимает.
2. Алгебра. Пользователь вводит набор операций высокого уровня над отношениями (или другими группами данных).
3. Кортеж. Низший уровень. Программист работает с записями или кортежами.
Преимущества реляционной базы (базы, заданной в третьей нормальной форме).
a. Простота. Использование двумерных таблиц для представления большинства структур данных – самый простой способ работы с БД для необученного или не очень опытного пользователя.
b. Гибкость. Операции реляционной алгебры позволяют ПП – листам получать разнообразные файлы в нужной им форме.
c. Точность. Направленные связи, ставшие обычным явлением в базах могут быть опущены. Отношения по своей природе обладают более точным смыслом и поддаются математически точным методам манипулирования с использованием таких средств, как алгебра отношений и исчисление отношений.
d. Секретность. Контроль секретности упрощается. Для каждого отношения задается правомерность доступа.
e. Связность. Реляционное представление дает явную картину взаимосвязей атрибутов из различных отношений и файлов.
Рекомендация для Вас - Повторители.
f. Простота внедрения. Физическое размещение плоских файлов может оказаться намного проще, чем размещение древовидных и сетевых структур.
g. Независимость данных. Структура БД должна допускать возможность ее роста, то есть добавление новых атрибутов и отношений. Методы использования данных также изменчивы. Могут добавляться новые кортежи и удаляться старые. То же касается и элементов данных.
При задании базы в нормализованной форме с независимым ПО перестройка данных не потребует изменения ПП – м.
h. ЯМД. С помощью алгебры отношений или исчисления отношений можно построить простой и гибкий ЯМД. Для данных в виде неплоский структур язык манипулирования либо получается необоснованно сложным для пользователя, либо ограничен по своим возможностям.
i. Ясность. Логическая схема БД при изображении связей с помощью стрелок выглядит ясной, пока количество стрелок невелико.
