Реляционная алгебра
1. Реляционная алгебра
Реляционная алгебра как теоретический язык запросов по сравнению с реляционным исчислением более наглядно описывает выполняемые над отношениями действия.
Примером языка запросов, основанного на реляционной алгебре, является ISBL (Information System Base Language – базовый язык информационных систем). Языки запросов, построенные на основе реляционной алгебры, в современных СУБД широкого распространения не получили. Однако знакомство с ней полезно для понимания сути реляционных операций.
Вариант реляционной алгебры, предложенный Коддом, включает следующие основные операции:
· объединение; +
· разность; +
· пересечение;
· декартово произведение; +
· селекция (выборка); +
Рекомендуемые материалы
· проекция; +
· деление;
· соединение.
Реляционная алгебра Кодда обладает следующими недостатками:
1) восемь перечисленных операций избыточны, т.к. минимальный набор может включать пять операций: объединение, вычитание, произведение, проекция и выборка. Три остальные операции: пересечение, соединение и деление можно определить через пять минимальных. Так, например, соединение – это проекция выборки произведения.
2) восьми операций недостаточно для построения реальной СУБД на принципах реляционной алгебры. Требуются расширения: переименование атрибутов, образование новых вычисляемых атрибутов, вычисление итоговых функций, построение сложных алгебраических выражений, присвоения, сравнения и т.д.
Все операции реляционной алгебры Кодда можно разделить на две группы:
1) базовые теоретико-множественные – это классические операции теории множеств: объединение, разность, пересечение и произведение;
2) специальные реляционные – расширение теоретико-множественных операций: проекция, селекция, деление и соединение.
Графически операции можно представить так.
Объединение Разность Пересечение
![]() | ![]() | ||||
![]() | |||||
Произведение Выборка Проекция
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
![]() | |||||||||
Деление Соединение
![]() | |||||||||||||
![]() | |||||||||||||
![]() | |||||||||||||
![]() | |||||||||||||
![]() | ![]() | ||||||||||||
![]() | |||||||||||||
![]() | |||||||||||||
Операции могут выполняться над одним отношением или над двумя отношениями. При выполнении бинарной операции отношения должны быть совместимыми по структуре. Это означает совместимость имен атрибутов и типов соответствующих доменов.
1. Объединение двух совместимых отношений R1 и R2 одинаковой размерности является отношение К, содержащее все элементы исходных отношений (с исключением повторений)
Пример 1. Пусть отношение R1 множество поставщиков из Лондона, а отношения R2 – множество поставщиков, которые поставляют деталь Р1. Тогда отношение R (R1 UNION R2) означает поставщиков, находящихся в Лондоне, или поставщиков, поставляющих деталь Р1, либо тех и других.
R1
П# | Имя | Статус | Город_П |
S1 | Сергей | 20 | Москва |
S4 | Николай | 20 | Москва |
R2
П# | Имя | Статус | Город_П |
S1 | Сергей | 20 | Москва |
S2 | Иван | 10 | Краснодар |
S5 | Андрей | 30 | Минск |
R (R1 UNION R2)
П# | Имя | Статус | Город_П |
S1 | Сергей | 20 | Москва |
S2 | Иван | 10 | Краснодар |
S4 | Николай | 20 | Москва |
2. Вычитание совместимых отношений R1 и R2 одинаковой размерности есть отношение R (R1 MINUS R2), тело которого состоит из множества кортежей, принадлежащих R1, но не принадлежащих отношению R2.
Пример 2. Для R1 и R2 примера 1 отношение R вычитания R1 из R2 будет представлять собой множество поставщиков, находящихся в Лондоне, но не выпускающих деталь Р1.
R (R1 MINUS R2)
П# | Имя | Статус | Город_П |
S4 | Николай | 20 | Москва |
Результат операции вычитания зависит от порядка следования операндов.
R (R2 MINUS R1)
П# | Имя | Статус | Город_П |
S2 | Иван | 10 | Краснодар |
S5 | Андрей | 30 | Минск |
3. Пересечение двух совместимых отношений R1 и R2 одинаковой размерности R (R1 INTERSECT R2) порождает отношение R с телом, включающим в себя кортежи, одновременно принадлежащие обоим исходным отношениям. Для отношения R1 и R2 результирующее отношение r будет означать всех производителей из Лондона, выпускающих деталь Р1.
R (R1 INTERSECT R2)
П# | Имя | Статус | Город_П |
S1 | Сергей | 20 | Москва |
4. Произведение отношения R1 степени к1 и отношения R2 степени к2 R (R1 TIMES R2), которые не имеют одинаковых имен атрибутов, есть такое отношение R степени (к1+к2), заголовок которого представляет сцепление заголовков отношений R1 и R2, а тело имеет кортежи такие, что первые к1 элементов кортежей принадлежат множеству R1, а последние к2 элементов – множеству R2. При необходимости получить произведение двух отношений, имеющих одинаковые имена одного или нескольких атрибутов, применяется операция переименования RENAME.
Пример 2. Пусть отношение R1 представляет множество номеров текущих поставщиков {S1, S2}, а отношение R2 - множество номеров всех текущих деталей {Р1, Р2, Р3}. Результатом операции R1 TIMES R2 является множество всех пар типа «поставщик-деталь», то есть {(S1,P1), (S1,P2), (S1,P3), (S2,P1), (S2,P2),(S2,P3)}.
В теории множеств результатом операции прямого произведения является множество, каждый элемент которого является парой элементов, первый из которых принадлежит R1, а второй – принадлежит R2, т.е. кортеж будет ((а, б), (в, г)), где кортеж (а, б) принадлежит R1, а кортеж (в, г) – R2. В реляционной алгебре применяют расширенный вариант прямого произведения, при котором элементы кортежей двух исходных отношений сливаются (а, б, в, г).
R1
П# | Имя | Статус | Город_П |
S1 | Сергей | 20 | Москва |
S2 | Иван | 10 | Краснодар |
R2
Д# | Название | Тип | Вес | Город_Д |
P1 | гайка | каленый | 12 | Москва |
P2 | болт | мягкий | 17 | Краснодар |
P3 | винт | твердый | 17 | Ростов |
R (R1 TIMES R2)
П# | Д# | Имя | Статус | Город_П | Название | Тип | Вес | Город_Д |
S1 | P1 | Сергей | 20 | Москва | гайка | каленый | 12 | Москва |
S1 | P2 | Сергей | 20 | Москва | болт | мягкий | 17 | Краснодар |
S1 | P3 | Сергей | 20 | Москва | винт | твердый | 17 | Ростов |
S2 | P1 | Иван | 10 | Краснодар | гайка | каленый | 12 | Москва |
S2 | P2 | Иван | 10 | Краснодар | болт | мягкий | 17 | Краснодар |
S2 | P3 | Иван | 10 | Краснодар | винт | твердый | 17 | Ростов |
5. Выборка (R WHERE f) отношения R по формуле f представляет собой новое отношение с таким же заголовком и телом, состоящим из таких кортежей отношения R, которые удовлетворяют истинности логического выражения, заданного формулой f. Для записи формулы используются операнды: имена атрибутов (или номера столбцов), константы, логические операции (AND, OR< NOT), операции сравнения и скобки.
Пример 3. Пусть дано отношение P – детали. Выбрать выборку R (P WHERE Вес < 14) из отношения P.
P
Д# | Название | Тип | Вес | Город_Д |
P1 | гайка | каленый | 12 | Москва |
P2 | болт | мягкий | 17 | Краснодар |
P3 | винт | твердый | 17 | Ростов |
P4 | винт | каленый | 14 | Москва |
P5 | палец | твердый | 12 | Краснодар |
P6 | шпилька | каленый | 19 | Москва |
P WHERE Вес < 14
Д# | Название | Тип | Вес | Город_Д |
P1 | гайка | каленый | 12 | Москва |
P5 | палец | твердый | 12 | Краснодар |
6. Проекция отношения А на атрибуты X, Y, …, Z (A[X, Y, …, Z]), где множество {X, Y, …, Z} является подмножеством полного списка атрибутов заголовка отношения А, представляет собой отношение с заголовком X, Y, …, Z и телом, содержащим кортежи отношения А, за исключением повторяющихся кортежей. Повторение одинаковых атрибутов в списке X, Y, …, Z запрещается.
Операция проекция допускает следующие дополнительные варианты записи:
· отсутствие списка атрибутов подразумевает указание всех атрибутов (операция тождественной проекции);
· выражение вида R[] означает пустую проекцию, результатом которой является пустое множество;
· операция проекции может применяться к произвольному отношению, в том числе и к результату выборки.
Пример 4. Вычислить проекцию отношения Р.
P [Тип, Город_Д]
Тип | Город_Д |
каленый | Москва |
мягкий | Краснодар |
твердый | Ростов |
твердый | Краснодар |
Вычислить проекцию выборки из отношения S
S
П# | Имя | Статус | Город_П |
S1 | Сергей | 20 | Москва |
S2 | Иван | 10 | Краснодар |
S3 | Борис | 30 | Краснодар |
S4 | Николай | 20 | Москва |
S5 | Андрей | 30 | Минск |
(S WHERE Город_П= ”Краснодар”) [П#]
П# | Город_П |
S2 | Краснодар |
S3 | Краснодар |
7. Деление. Результатом деления отношения R1 с атрибутами A и B на отношение R2 с атрибутом B (R1 DIVIDEBY R2), где A и B простые или составные атрибуты, причем атрибут B – общий атрибут, определенный на одном и том же домене (множестве доменов составного атрибута), является отношение R c заголовком A и телом, состоящим из кортежей r таких, что в отношении R1 имеются кортежи (r, s), причем множество значений s включает множество значений атрибута B отношения R2.
Пример 5. Пусть имеется отношения SP – поставки. R1 – проекция SP[П#, Д#], а R2 – отношение с заголовком Д# и телом {P2, P4}], тогда результатом деления R1на R2 будет отношение R с заголовком П# и телом {S1, S4}.
SP
П# | Д# | Количество |
S1 | P1 | 300 |
S1 | P2 | 200 |
S1 | P3 | 400 |
S1 | P4 | 200 |
S1 | P5 | 100 |
S1 | P6 | 100 |
S2 | P1 | 300 |
S2 | P2 | 400 |
S3 | P2 | 200 |
S4 | P2 | 200 |
S4 | P4 | 300 |
S4 | P5 | 400 |
R1 R2 R1 DIVIDEBY R2
П# | Д# | Д# | П# | ||
S1 | P1 | P2 | S1 | ||
S1 | P2 | P4 | S4 | ||
S1 | P3 | ||||
S1 | P4 | ||||
S1 | P5 | ||||
S1 | P6 | ||||
S2 | P1 | ||||
S2 | P2 | ||||
S3 | P2 | ||||
S4 | P2 | ||||
S4 | P4 | ||||
S4 | P5 |
8. Соединение Сf(R1, R2) отношений R1 и R2 по условию, заданному формулой f, представляет собой отношение R, которое можно получить путем Декартова произведения отношений R1 и R2 с последующим применением к результату операции выборки по формуле f. Правила записи формулы f так же , как и для операции селекции.
Другими словами, соединением отношения R1 по атрибуту А с отношением R2 по атрибуту В (отношения не имеют общих имен атрибутов) является результатом выполнения операции вида: (R1 TIMES R2) WHERE A Q B,
где Q – логическое выражение над атрибутами, определенными на одном (нескольких – для составного атрибута) домене. Соединение Сf(R1, R2), где формула f имеет произвольный вид, называют также Q-соединением.
Операция эквисоединения характеризуется тем, что формула задает равенство операндов. Возможно эквисоединение по одному столбцу. Иногда эквисоединение двух отношений выполняется по таким столбцам, атрибуты которых в обоих отношениях имеют соответственно одинаковые имена и домены. В этом случае говорят об эквисоединении по общему атрибуту.
Операция естественного соединения (операция JOIN) применяется к двум отношениям, имеющим общий атрибут (простой или составной). Этот атрибут в отношениях имеет одно и то же имя (совокупность имен) и определен на одном и том же домене (доменах).
Результатом операции естественного соединения является отношение R, которое представляет собой проекцию эквисоединения отношений R1 и R2 по общему атрибуту на объединенную совокупность атрибутов обоих отношений.
Пример 6. Необходимо найти Q-соединение отношений S и P по атрибутам Город_П и Город_Д соответственно, причем кортежи результирующего отношения должно удовлетворять отношению «больше» (в смысле лексикографического порядка – по алфавиту).
(S TIMES P) WHERE Город_П > Город_Д
S
П# | Имя | Статус | Город_П |
S1 | Сергей | 20 | Москва |
S2 | Иван | 10 | Краснодар |
S3 | Борис | 30 | Краснодар |
S4 | Николай | 20 | Москва |
S5 | Андрей | 30 | Минск |
P
Д# | Название | Тип | Вес | Город_Д |
P1 | гайка | каленый | 12 | Москва |
P2 | болт | мягкий | 17 | Краснодар |
P3 | винт | твердый | 17 | Ростов |
P4 | винт | каленый | 14 | Москва |
P5 | палец | твердый | 12 | Краснодар |
P6 | шпилька | каленый | 19 | Москва |
Эквисоединение.
(S TIMES P) WHERE Город_П > Город_Д
П# | Имя | Статус | Город_П | Д# | Название | Тип | Вес | Город_Д |
S2 | Иван | 10 | Краснодар | P1 | гайка | каленый | 12 | Москва |
S2 | Иван | 10 | Краснодар | P4 | винт | каленый | 14 | Москва |
S2 | Иван | 10 | Краснодар | P6 | шпилька | каленый | 19 | Москва |
S1 | Борис | 30 | Краснодар | P1 | гайка | каленый | 12 | Москва |
S1 | Борис | 30 | Краснодар | P4 | винт | каленый | 14 | Москва |
S1 | Борис | 30 | Краснодар | P6 | шпилька | каленый | 19 | Москва |
Пусть необходимо найти естественное соединение отношений S и P по общему атрибуту, характеризующему город (в отношении S – это Город_П, а в отношении P – Город_Д). Поскольку условие операции требует одинаковости имен атрибутов, по которым выполняется соединение, то применяется операция RENAME переименование атрибутов.
(S RENAME Город_П AS Город) JOIN (P RENAME Город_Д AS Город)
П# | Имя | Статус | Город | Д# | Название | Тип | Вес |
S1 | Сергей | 20 | Москва | P1 | гайка | каленый | 12 |
S1 | Сергей | 20 | Москва | P4 | винт | каленый | 14 |
S1 | Сергей | 20 | Москва | P6 | шпилька | каленый | 19 |
S2 | Иван | 10 | Краснодар | P2 | болт | мягкий | 17 |
S2 | Иван | 10 | Краснодар | P5 | палец | твердый | 12 |
S1 | Борис | 30 | Краснодар | P2 | болт | мягкий | 17 |
S1 | Борис | 30 | Краснодар | P5 | палец | твердый | 12 |
S1 | Николай | 20 | Москва | P1 | гайка | каленый | 12 |
S1 | Николай | 20 | Москва | P4 | винт | каленый | 14 |
S1 | Николай | Лекция "Преимущества и неудобства буферного кеша" также может быть Вам полезна. 20 | Москва | P6 | шпилька | каленый | 19 |