Реляционная алгебра – механизм манипулирования реляционными данными Все операции производятся над отношениями, и результатом операции является отношение. - презентация

1 Реляционная алгебра – механизм манипулирования реляционными данными Все операции производятся над отношениями, и результатом операции является отношение. R=f(R 1, R 2, …, R n )

2 Две группы операций РА теоретико-множественные операции специальные реляционные операции

3 Теоретико-множественные операции объединения отношений; пересечения отношений; взятия разности отношений; взятия декартова произведения отношений.

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

5 Объединение union При выполнении операции объединения (UNION) двух отношений с одинаковыми заголовками производится отношение, включающее все кортежи, которые входят хотя бы в одно из отношений-операндов. A B = { c: c A OR c B}

6 Пересечение intersect пересечением множеств A и B является такое множество C{c}, что для любого c существуют такие элементы a, принадлежащий множеству A, и b, принадлежащий множеству B, что c=a=b; A B = { c: c A AND c B}

7 Разность minus разностью множеств A и B является такое множество C{c}, что для любого c существует такой элемент a, принадлежащий множеству A, что c=a, и не существует такой элемент b, принадлежащий B, что c=b. A \ B = { c: c A AND c B}

8

9 Избыточность пересечения

10 A B = A \ (A \ B) A B = B \ (B \ A)

11

12

13 Чему тождественно равно выражение (A B) \ (A \ B) (A B) (B \ (A \B)) (A B) (B \ A) A B

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

15 Переименование атрибутов Оператор переименования атрибутов имеет следующий синтаксис: A RENAME Atr 1, Atr 2 AS NewAtr 1, NewAtr 2 где Atr 1, Atr 2 - старые значения атрибутов NewAtr 1, NewAtr 2 - новые значения атрибутов A (a, b, c) B (a, d) A×B (A.a, b, c, B.a, d)

16 Декартово произведение times Заголовок R 1 × R 2 R (a 1, a 2, …, a n, b 1, b 2, …, b m ), Тело R 1 × R 2 ={r a 1, r a 2, …, r a n, r b 1, r b 2, …, r b m : r a 1, r a 2, …, r a n R 1, r b 1, r b 2, …, r b m R 2 }. Мощность [R 1 × R 2 ]= [R 1 ] × [R 2 ] На основе ДК производится операция соединения

17 Декартово произведение - пример

18 Свойства операций (OP) Ассоциативность (A OP B) OP C = A OP (B OP C) Коммутативность (кроме разности) A OP B = B OP A

19 Реляционные операции ограничение отношения (селекция) – горизонтальная вырезка; проекцию отношения – вертикальная вырезка; соединение отношений (по условию, эквисоединение и естественное соединение); деление отношений.

20 Селекция (where) Простое условие требует наличия двух операндов: ограничиваемого отношения и условия ограничения (f). Условие ограничения может иметь вид: – (a comp-op b), где а и b – имена атрибутов ограничиваемого отношения; атрибуты a и b определены на одном домене, для значений которого поддерживается операция сравнения comp_op,; – (a comp-op const), где a – имя атрибута ограничиваемого отношения, а const – константа; атрибут a должен быть определен на домене или базовом типе, для значений которого поддерживается операция сравнения comp_op. – Операцией сравнения comp-op могут быть = > <

21 Селекция (where) Условие может состоять из нескольких простых условий, связанных булевскими операторами AND NOT OR Приоритеты – NOT AND OR Результатом селекции является отношение, заголовок которого совпадает с заголовком отношения-операнда, а в тело входят те кортежи отношения-операнда, для которых значением условия ограничения является true.

22 Как обойтись только простыми условиями? A WHERE (comp1 AND comp2) (A WHERE comp1) ???? (A WHERE comp2); A WHERE (comp1 OR comp2) (A WHERE comp1) ???? (A WHERE comp2); A WHERE NOT comp1 (A WHERE comp1) ????.

23 Так обойтись только простыми условиями A WHERE (comp1 AND comp2) = (A WHERE comp1) (A WHERE comp2); A WHERE (comp1 OR comp2) = (A WHERE comp1) (A WHERE comp2); A WHERE NOT comp1 = A \ (A WHERE comp1).

24 Селекция (where) σ A WHERE f = { c: c A AND f} σ f (A)= { c A : f(c) }

25 Селекция - пример σ СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 WHERE (СЛУ_ЗАРП > AND (СЛУ_ОТД_НОМ = 310 OR СЛУ_ОТД_НОМ = 315))

26 Проекция Операция взятия проекции также требует наличия двух операндов – проецируемого отношения A и подмножества множества имен атрибутов, входящих в заголовок отношения A. Атрибутами результирующего отношения являются один или несколько атрибутов исходного, возможно в другом порядке.

27 Проекция PROJECT Проекцией отношения A по атрибутам X, Y, …, Z, где каждый из атрибутов принадлежит отношению, называется отношение с заголовком (X, Y, …, Z) и телом, содержащим множество кортежей вида (x, y, …z), таких, для которых в отношении найдутся кортежи со значением атрибута X равным x, значением атрибута Y равным y, …, значением атрибута Z равным z. Синтаксис операции проекции: (X, Y, … Z) (A) = {x, y, …z : a 1, a 2, …, a n A AND x= ai 1, y=ai 2, …, z=a im }, Операция проекции дает " вертикальный срез " отношения, в котором удалены все возникшие при таком срезе дубликаты кортежей.

28 Проекция - пример PROJECT (СЛУ_ОТД_НОМ) СЛУЖАЩИЕ_В_ПРОЕКТЕ_1

29 Соединение по условию – JOIN Тэта-соединение Требует наличия двух операндов – соединяемых отношений и третьего операнда – простого условия. Условие – см. селекцию. Операнды совместимы по взятию декартова произведения. A JOIN B WHERE comp = (A × B) WHERE comp. R fS = σ f (R×S)

30 Соединение по условию - JOIN (ПРО_ЗАРП – средняя зарплата по проекту) Соединение по условию - JOIN

31 Соединение по условию – JOIN СЛУЖАЩИЕ JOIN ПРОЕКТЫ WHERE (СЛУ_ЗАРП > ПРО_ЗАРП)

32 Эквисоединение Операция соединения называется операцией эквисоединения (EQUIJOIN), если условие соединения имеет вид (a = b), где a и b – атрибуты разных операндов соединения. Этот случай важен потому, что он чаще всего встречается на практике, и для него существуют наиболее эффективные алгоритмы реализации.

33 Эквисоединение СЛУЖАЩИЕ JOIN (ПРОЕКТЫ RENAME ПРО_НОМ AS ПРО_НОМ1)) WHERE (СЛУ_ЗАРП = ПРО_ЗАРП)

34 Естественное соединение NATURAL JOIN Операция естественного соединения применяется к паре отношений A и B, обладающих (возможно, составным) общим атрибутом c (т. е. атрибутом с одним и тем же именем и определенным на одном и том же домене). Пусть ab обозначает объединение заголовков отношений A и B. Тогда естественное соединение A и B – это спроецированный на ab результат эквисоединения A и B по условию A.c = B.c).

35 Естественное соединение через другие операции?

36 Естественное соединение через другие операции Переименование Декартово произведение Селекция Проекция R S = атрибуты R,S\S.A σ R.A=S.A (R×S)

37 Естественное соединение - пример СЛУЖАЩИЕ NATURAL JOIN ПРОЕКТЫ (естественное соединение – выдать полную информацию о служащих и проектах, в которых они участвуют).

38 Деление DIVIDE Пусть заданы два отношения: A с заголовком {a 1, a 2,..., a n, b 1, b 2,..., b m } B с заголовком {b 1, b 2,..., b m }. Будем считать, что атрибут b i отношения A и атрибут b i отношения B (i = 1, 2, …, m) не только обладают одним и тем же именем, но и определены на одном и том же домене. Назовем множество атрибутов {a j } составным атрибутом a, а множество атрибутов {b j } – составным атрибутом b. После этого будем говорить о реляционном делении «бинарного» отношения A{a, b} на унарное отношение B{b}.

39 Деление По определению, результатом деления A на B (A DIVIDE BY B) является «унарное» отношение C (a), тело которого состоит из кортежей v таких, что в теле отношения A содержатся кортежи для любого w из B. Операция реляционного деления не является примитивной и выражается через операции декартова произведения, взятия разности и проекции. (A DIVIDE BY B) = С : С×B A

40 Деление - пример Найдем всех сотрудников, которые работают и в 1, и во 2 проектах.

41 Деление R DIVIDE S = 1,2,...r-s (R)- 1,2,...r-s ( 1,2,...r-s (R)xS)-R).

42 Примеры: Кто работает только в одном проекте. Найти табельный номер начальника. Кто получает зарплату больше, чем его начальник. У кого самая большая зарплата.