Тема: Реляционная алгебра. Операции реляционной алгебры Кодда.

Цель: формирование представления об основных операциях реляционной алгебры.

План:

1. Реляционная алгебра. Недостатки и преимущества.
2. Операции реляционной алгебры Кодда.
1. Классические операции;
2. Специальные операции.
3. Выполнить лабораторно-практическую работу «Реляционная алгебра. Классические операции теории множеств».
4. Выполнить лабораторно-практическую работу «Реляционная алгебра. Специальные операции теории множеств»

1. Реляционная алгебра. Недостатки и преимущества.

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

Примером языка запросов, основанного на реляционной алгебре, явля­ется ISBL (Information System Base Language — базовый язык информаци­онных систем). Языки запросов, построенные на основе реляционной ал­гебры, в современных СУБД широкого распространения не получили. Однако знакомство с ней полезно для понимания сути реляционных опе­раций, выражаемых другими используемыми языками.

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

Реляционная алгебра Кодда облада­ет несколькими недостатками. Во-первых, восемь перечисленных операций по охвату своих функций, с одной стороны, избыточны, так как минимально необходимый набор составляют пять операций: объединение, вычитание, произведение, проекция и выборка. Три другие операции (пересечение, со­единение и деление) можно определить через пять минимально необходи­мых. Так, например, соединение — это проекция выборки произведения.

Во-вторых, этих восьми операций недостаточно для построения реаль­ной СУБД на принципах реляционной алгебры. Требуются расширения, включающие операции: переименования атрибутов, образования новых вы­числяемых атрибутов, вычисления итоговых функций, построения слож­ных алгебраических выражений, присвоения, сравнения и т. д.

Рассмотрим перечисленные операции более подробно, сначала — опера­ции реляционной алгебры Кодда, а затем — дополнительные операции, вве­денные Дейтом.

 

2.Операции реляционной алгебры Кодда.

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

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

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

 

a.      Классические операции.

Объединением двух совместимых отношений R1 и R2 одинаковой раз­мерности (Rl UNION R2) является отношение R, содержащее все элементы исходных отношений (с исключением повторений).

Рис.1.

Пример 1.

Пусть отношением R1 будет множество поставщиков из Лондона, а от­ношение R2 — множество поставщиков, которые поставляют деталь Р1. Тог­да отношение R обозначает поставщиков, находящихся в Лондоне, или по­ставщиков, выпускающих деталь Р1, либо тех и других.

 

Отношение R1

П#	Имя	Статус	Город_п
S1	Сергей	20	Москва
S2	Николай	20	Москва

 

Отношение R2

П#	Имя	Статус	Город_п
S1	Сергей	20	Москва
S2	Иван	10	Киев

 

Отношение R(R1 UNION R2) – результирующее отношение содержит все элементы исходных отношений

П#	Имя	Статус	Город_п
S1	Сергей	20	Москва
S2	Иван	10	Киев
S4	Николай	20	Москва

 

Вычитание (разность) совместимых отношений R1 и R2 одинаковой размерности (Rl MINUS R2) есть отношение, тело которого состоит из множества кортежей, принадлежащих R1, но не принадлежащих отношению R2.

Рис.2.

Для тех же отношений R1 и R2 из примера 1 отношение R будет представ­лять собой множество поставщиков, находящихся в Лондоне, но не выпус­кающих деталь Р1, т. е. R={(S4, Николай, 20, Москва)}.

П#	Имя	статус	Город_п
S4	Николай	20	Москва

 

Заметим, что результат операции вычитания зависит от порядка следо­вания операндов, т. е. Rl MINUS R2 и R2 MINUS R1 — не одно и то же.

 

Пересечение двух совместимых отношений R1 и R2 одинаковой размер­ности (Rl INTERSECT R2) порождает отношение R с телом, включающим в себя кортежи, одновременно принадлежащие обоим исходным отноше­ниям. Рис.3.

Для отношений R1 и R2 результирующее отношение R будет озна­чать всех производителей из Лондона, выпускающих деталь Р1. Тело отно­шения R состоит из единственного элемента (S1, Сергей, 20, Москва).

П#	Имя	статус	Город_п
S1	Сергей	20	Москва

 

Произведение отношения R1 степени к1 и отношения R2 степени к2 (Rl TIMES R2), которые не имеют одинаковых имен атрибутов, есть такое отношение R степени (к1+к2), заголовок которого представляет сцепление заголовков отношений R1 и R2, а тело — имеет кортежи, такие, что первые к1 элементов кортежей принадлежат множеству R1, а последние к2 элемен­тов — множеству R2. При необходимости получить произведение двух от­ношений, имеющих одинаковые имена одного или нескольких атрибутов, применяется операция переименования RENAME, рассматриваемая далее.

Рис.4.

 

В теории множеств результатом операции прямого про­изведения является множество, каждый элемент которого является па­рой элементов, первый из которых принадлежит R1, а второй — принад­лежит R2. Поэтому кортежами декартова произведения бинарных отношений будут кортежи вида: ((а, б), (в, г)), где кортеж (а, б) принадле­жит отношению R1, а кортеж (в, г) — принадлежит отношению R2.

 

Пример 2.

Пусть отношение R1 представляет собой множество номеров всех теку­щих поставщиков {SI, S2}, а отношение R2 — множество номеров всех текущих деталей {Р1, Р2 }. Результатом операции R1 TIMES R2 является множество всех пар типа «поставщик — деталь», т. е. {(S1.P1), (S1.P2), (S2.P1), (S2.P2)}.

Отношение R1

П#	Имя	Город_п
S1	Сергей	Москва
S2	Николай	Москва

Отношение R2

Р#	название	тип
P1	Гайка	Каленый
P2	Угол	Твердый

 

Результирующее отношение R (R1 TIMES R2) – тело состоит из кортежей – множества всех пар.

П#	Имя	Город_п	Р#	название	тип
S1	Сергей	Москва	P1	Гайка	Каленый
S1	Сергей	Москва	P2	Угол	Твердый
S2	Николай	Москва	P1	Гайка	Каленый
S2	Николай	Москва	P2	Угол	Твердый

 

 

b.      Специальные операции.

Выборка (R WHERE f) отношения R по формуле f представляет собой новое отношение с таким же заголовком и телом, состоящим из таких корте­жей отношения R, которые удовлетворяют истинности логического выраже­ния, заданного формулой f. Для записи формулы используются операнды — имена атрибутов (или номера столбцов), константы, логические операции (AND — И, OR — ИЛИ, NOT — НЕ), операции сравнения и скобки. Рис.5

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

R1

Р#	название	тип	вес
P1	Гайка	Каленый	12
P2	Угол	Твердый	13
P3	Шайба	Каленый	10,5
P4	Болт	Каленый	14
P5	Гайка	Твердый	11

 

Результирующее отношение

R(1 WHERE вес <13)

Р#	название	тип	вес
P1	Гайка	Каленый	12
P3	Шайба	Каленый	10,5
P5	Гайка	Твердый	11

 

Результирующее отношение

R (R1 WHERE тип = «каленый» AND вес <13)

Р#	название	тип	вес
P1	Гайка	Каленый	12
P3	Шайба	Каленый	10,5

 

Проекция отношения А на атрибуты X, Y,..., Z (А [X, Y,..., Z]), где множество {X, Y,..., Z} является подмножеством полного списка атрибутов заголовка отно­шения А, представляет собой отношение с заголовком X, Y,..., Z и телом, содер­жащим кортежи отношения А, за исключением повторяющихся кортежей. Повторение одинаковых атрибутов в списке X, Y,..., Z запрещается.

Операция проекции допускает следующие дополнительные варианты записи:

-      отсутствие списка атрибутов подразумевает указание всех атрибутов (операция тождественной проекции);

-      выражение вида R[ ] означает пустую проекцию, результатом которой является пустое множество;

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

Рис. 6

 

Пример 4. На основании отношения R1

 создана проекция R (название)

название

Гайка

Угол

Шайба

Болт

 

 

 

 

 

 

 

 

Пример 5. На основании отношения R1

создана проекция R(R1 whereТип = «каленый»)

[ название]

название	тип
Гайка	Каленый
Шайба	Каленый
Болт	Каленый

Результатом деления отношения R1 с атрибутами А и В на отношение R2 с атрибутом В (Rl DIVIDEBY R2), где А и В простые или составные атрибу­ты, причем атрибут В — общий атрибут, определенный на одном и том же домене (множестве доменов составного атрибута), является отношение R с заголовком А и телом, состоящим из кортежей г таких, что в отношении R1 имеются кортежи (г, s), причем множество значений s включает множество значений атрибута В отношения R2.

 

Рис. 7

Пример 6. Даны два отношения R1 и R2.

R1

Р#	название	P#	тип	вес
P1	Гайка	P1	Каленый	12
P2	Угол	P2	Твердый	13
P3	Шайба	P3	Каленый	10,5
P4	Болт	P4	Каленый	14
P5	Гайка	P5	Твердый	11

R2

Р#	вес
P1	12
P2	13
P3	10,5
P4	14

Результирующее отношение R(R1 DIVIDEBY R2) –вычитание из множества полей первого отношения множества полей второго отношения (одинаковые записи не дублируются)

Р#	название	тип
P1	Гайка	Каленый
P2	Угол	Твердый
P3	Шайба	Каленый
P4	Болт	Каленый

Соединение C_f(Rl, R2) отношений R1 и R2 по условию, заданному фор­мулой f, представляет собой отношение R, которое можно получить путем Декартова произведения отношений R1 и R2 с последующим применением к результату операции выборки по формуле f. Правила записи формулы f такие же, как и для операции селекции.

Другими словами, соединением отношения R1 по атрибуту А с отноше­нием R2 по атрибуту В (отношения не имеют общих имен атрибутов) явля­ется результат выполнения операции вида:

(Rl TIMES R2) WHERE A 0 В,

где Q — логическое выражение над атрибутами, определенными на од­ном (нескольких — для составного атрибута) домене. Соединение C_f(Rl, R2), где формула f имеет произвольный вид (в отличие от частных случаев, рассматриваемых далее), называют также Q-соединением.

Важными с практической точки зрения частными случаями соединения являются эквисоединение и естественное соединение.

Рис.8.

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

Пример 5. Соединение отношений R1, R2

R1

Р#	название	тип	Город_П
P1	Гайка	Каленый	Киев
P2	Угол	Твердый	Киев
P3	Шайба	Каленый	Урай

 

R2

П#	Имя	статус	Город_Д
S1	Сергей	20	Москва
S2	Иван	10	Киев
S3	Петр	15	Урай

Результирующее отношение R(R1,R2) по атрибутам Город_П и Город_Д.

Р#	название	тип	Город_П	П#	Имя	статус	Город_Д
P1	Гайка	Каленый	Киев	S2	Иван	10	Киев
P2	Угол	Твердый	Киев	S2	Иван	10	Киев
P3	Шайба	Каленый	Урай	S3	Петр	15	Урай