Манипуляционная часть реляционной модели данных: реляционная алгебра

Общая характеристика Основа – спецификационные операторы, базирующиеся на теории множеств. Языки запросов: алгебраические языки (реляционная алгебра) – как получить требуемый результат языки исчисления предикатов (реляционное исчисление) – что должно быть получено –с переменными-кортежами –с переменными на доменах

Реляционная алгебра: введение (1) Предоставляет средства для записи и интерпретации выражений: операнд1 операция операнд2 результат 1. Операнды и результат – отношения: свойство замкнутости R 1 опц R 2 опц R 3 … 2. Отношение задается интенсионалом (схема отношения) и экстенсионалом (реализация отношения)

Реляционная алгебра: введение (2) Правила наследования имен атрибутов: Даны операнды: R 1 (A 1, A 2, …), R 2 (B 1, B 2, …). Выражение реляционной алгебры: R = R 1 опц R 2 Результат R(C 1, C 2, …), где C i – атрибут, совпадающий с A j, или B k

Операции реляционной алгебры Теоретико-множественные объединение, вычитание, пересечение, прямое (декартово) произведение Специальные выбор (селекция), проекция, соединение, деление Переименования

Операция переименования Изменяет только схему отношения, сохраняя реализацию. Пример: переименовать атрибут C в SC. До переименования После переименования SABC abc dbe SABSC abc dbe

Теоретико-множественные операции Объединение Вычитание Пересечение Прямое (декартово) произведение

Объединение множеств (1) Операция объединения теории множеств: Даны два множества S 1 и S 2. Объединение множеств: S = S 1 S 2 = { s i | s i S 1 и/или s i S 2 }

Объединение множеств (2) D 1 = {1, 3, 5, 7, 9}, D 2 = {a, b, c}, D 3 = {2, 4, 6, 8}. Объединение D 1 и D 2 : S = D 1 D 2 = {1, 3, 5, 7, 9, a, b, c} – множество, но не домен Объединение D 1 и D 3 : D = D 1 D 3 = {1, 3, 5, 7, 9, 2, 4, 6, 8} – домен

Объединение множеств (3) R 1 (A 1 :D 1, A 2 :D 1 ), r 1 = {, } R 2 (A 1 :D 1, A 2 :D 2 ), r 2 = {, } R 3 (A 1 :D 1, A 2 :D 3 ), r 3 = {, } Объединение r = r 1 r 2 = {,,, } – не отношение Объединение r = r 1 r 3 = {,,, } – отношение

Совместимость по объединению Простые домены считаются совместимыми по объединению, если они состоят из элементов одного типа. Два отношения считаются совместимыми по объединению, если: оба отношения имеют одно и то же множество атрибутов, одноименные атрибуты двух отношений определены на совместимых по объединению доменах.

Объединение отношений (1) Объединением (Union) двух отношений r 1 (R 1 ) и r 2 (R 2 ), совместимых по объединению, называется отношение s = r 1 r 2, для которого: схема отношения совпадает с R 1 или R 2, реализация отношения представляет множество кортежей, принадлежащих реализации r 1 и/или r 2

Объединение отношений (2) Даны r 1 (R 1 ), r 2 (R 2 ), r 1 = {t 1i }, r 2 = {t 2i }, R 1 R, R 2 R. s = r 1 r 2 = s(R), s = {t i | t i r 1 и/или t i r 2 } r1r1 ABCr2r2 ABCrABC abcaecabc aecdccaec dbadbddba dcc dbd

Объединение отношений (3) Свойства операции: коммутативна r 1 r 2 r 2 r 1 ассоциативна r 1 (r 2 r 3 ) (r 1 r 2 ) r 3 r 1 r 2 r 3

Вычитание отношений (1) Вычитанием (Except) двух отношений r 1 (R 1 ) и r 2 (R 2 ), совместимых по объединению, называется отношение s = r 1 – r 2, для которого: схема отношения совпадает с R 1 или R 2, реализация отношения представляет множество кортежей, принадлежащих реализации r 1, за исключением тех, которые имеются в r 2

Вычитание отношений (2) Даны r 1 (R 1 ), r 2 (R 2 ), r 1 = {t 1i }, r 2 = {t 2i }, R 1 R, R 2 R. s = r 1 – r 2 = s(R), s = {t i | t i r 1 и t i r 2 } r1r1 ABCr2r2 ABCrABC abcaecabc aecdccdba dbadbd

Вычитание отношений (3) Свойства операции: не коммутативна не ассоциативна

Пересечение отношений (1) Пересечением (Intersect) двух отношений r 1 (R 1 ) и r 2 (R 2 ), совместимых по объединению, называется отношение s = r 1 r 2, для которого: схема отношения совпадает с R 1 или R 2, реализация отношения представляет множество кортежей, содержащихся и в r 1, и в r 2

Пересечение отношений (2) Даны r 1 (R 1 ), r 2 (R 2 ), r 1 = {t 1i }, r 2 = {t 2i }, R 1 R, R 2 R. s = r 1 r 2 = s(R), s = {t i | t i r 1 и t i r 2 } r1r1 ABCr2r2 ABCrABC abcaecaec aecdcc dbadbd

Пересечение отношений (3) Свойства операции: коммутативна r 1 r 2 r 2 r 1 ассоциативна r 1 (r 2 r 3 ) (r 1 r 2 ) r 3 r 1 r 2 r 3 Операцию пересечения можно выразить через операцию вычитания: r 1 r 2 = r 1 – (r 1 – r 2 )

Декартово произведение (1) Декартовым произведением двух отношений r 1 (R 1 ) и r 2 (R 2 ), схемы отношений которых не имеют одноименных атрибутов, называется отношение s = r 1 r 2, для которого: схема отношения определяется сцеплением (объединением) схем R 1 и R 2, реализация отношения представляет множество кортежей, которое получается путем сцепления каждого кортежа из r 1 с каждым кортежем из r 2

Декартово произведение (2) Даны r 1 (R 1 ), R 1 (A 1, A 2, …, A m ), r 2 (R 2 ), R 2 (B 1, B 2, …, B n ), r 1 = {t 1i }, r 2 = {t 2i }, R 1 R 2 = 0 s = r 1 r 2 = s(R), R(A 1, A 2, …, A m, B 1, B 2, …, B n ), s = {u i v j | u i r 1, v j r 2 } r1r1 ABr2r2 XYZsABXYZ abadxabadx cbxacabxac cdbabcdb cbadx cbxac cbcdb

Декартово произведение (3) Свойства операции: коммутативна r 1 r 2 r 2 r 1 ассоциативна r 1 (r 2 r 3 ) = (r 1 r 2 ) r 3 = r 1 r 2 r 3 В теории множеств данная операция и не коммутативна, и не ассоциативна

Специальные операции Проекция Выбор (или селекция) Соединение Деление

Проекция (1) Проекцией отношения r(R), R = {A i }, на некоторый список имен атрибутов (подмножество атрибутов) L из R, L R, называется отношение s = L (r), для которого: схема отношения определяется списком L, реализация отношения есть множество кортежей, полученных из кортежей отношения r путем вычеркивания элементов, соответствующих атрибутам R – L, и исключением дубликатов

Проекция (2) Дано r(R), R(A 1, A 2, …, A m ), r = { } s(L) = L (r), L(B 1, B 2, …, B k ), B i R, s = { | таких, что u i = t j, если B i A j } rABCD S = AB (r) AB abcdab abxcdb dbac

Проекция (3) Свойство проекции: Если Y R и X R, то Y ( X (r)) X ( Y (r)) X Y (r) Если Y X R, то Y ( X (r)) Y (r)

Выбор (1) Выбором из отношения r(R) по условию F называется отношение s = F (r), для которого: схема отношения совпадает со схемой R, реализация отношения есть множество кортежей из r, удовлетворяющих условию F

Выбор (2) Условие (предикат) F: операнды – атрибуты отношения и/или константы; операции – операции отношения (=, и т.д.) и логические операции (,, ).

Выбор (3) Дано r(R), r = {t i } s(R) = F (r), s = {u i | u i R и F(u i ) – истинно} rABC A = a C = c (r) ABC abcabc adcadc cbd

Выбор (4) Свойства операции: коммутативна F1 ( F2 (r)) = F2 ( F1 (r)) = F1 F2 (r) дистрибутивна относительно операций = (,, –): F (r s) = F (r) F (s)

Соединение Естественное соединение Соединение по условию

Естественное соединение (1) Естественным соединением отношений r 1 (R 1 ), R 1 = XY, и r 2 (R 2 ), R 2 = YZ, где Y – общее подмножество атрибутов из R 1 и R 2, определенных на одних и тех же доменах, называется отношение s(R) = r 1 r 2, для которого: схема отношения R = R 1 R 2 = XYZ, реализация отношения есть множество кортежей {t}, для которых XY (t) r 1 и YZ (t) r 2

Естественное соединение (2) Даны r 1 (R 1 ), R 1 = XY, и r 2 (R 2 ), R 2 = YZ. s(R) = r 1 r 2, R = R 1 R 2 = XYZ, s = {t | таких, что XY (t) r 1 и YZ (t) r 2 } r1r1 ABCr2r2 BCDs = r 1 r 2 ABCD abcbcdabcd dbcbceabce bbfadbdbcd cadabfdbce cadb

Левое внешнее соединение r 1 r 2 – включает результат операции естественного соединения, дополненный и теми кортежами из r 1, для которых нет соответствующих кортежей из r 2 r1r1 ABCr2r2 BCDs = r 1 r 2 ABCD abcbcdabcd dbcbceabce bbfadbdbcd cadabfdbce bbf– cadb

Правое внешнее соединение r1r1 ABCr2r2 BCDs = r 1 r 2 ABCD abcbcdabcd dbcbceabce bbfadbdbcd cadabfdbce cadb –abf r 1 r 2 – включает результат операции естественного соединения, дополненный и теми кортежами из r 2, для которых нет соответствующих кортежей из r 1

Полное внешнее соединение r1r1 ABCr2r2 BCDs = r 1 r 2 ABCD abcbcdabcd dbcbceabce bbfadbdbcd cadabfdbce bbf– cadb –abf

Соединение по условию (1) Даны два отношения r 1 (R 1 ) и r 2 (R 2 ), для которых R 1 R 2 =. Атрибут A R 1 сравним по условию с атрибутом B R 2. Соединением отношений r 1 (R 1 ) и r 2 (R 2 ) по условию называется отношение s(R) = r 1 r 2, для которого: схема отношения R = R 1 R 2 = R 1 R 2, реализация отношения есть множество кортежей, полученных сцеплением кортежей из r 1 и r 2, удовлетворяющих условию A B A B

Соединение по условию (2) Даны r 1 (R 1 ) и r 2 (R 2 ), R 1 R 2 =. s(R) = r 1 r 2, R = R 1 R 2, s = {uv | таких, что u r 1, v r 2 и для u и v выполняется условие } A B r1r1 ABCr2r2 XYr = r 1 r 2 ABCXY B < X

Деление (1) Даны два отношения r 1 (R 1 ) и r 2 (R 2 ), для которых R 2 R 1 и R 2 не пусто. Частным от деления отношения r 1 на отношение r 2 называется отношение s(R) = r 1 r 2, для которого: схема отношения R = R 1 – R 2, реализация отношения есть множество кортежей t таких, что для всех u i r 2 существует v j r 1 такой, что v j (R 1 – R 2 ) = t и v j (R 2 ) = u i

Деление (2) Даны r 1 (R 1 ), r 2 (R 2 ), R 2 R 1, R 2 0. s(R) = r 1 r 2, R = R 1 – R 2, s = {t j | u r 2 (t j u r 1 )} Другими словами, s r 2 r 1 Выражение реляционной алгебры, эквивалентное операции деления: r 1 r 2 = R1-R2 (r 1 ) – R1-R2 (( R1-R2 (r 1 ) r 2 ) – r 1 )

Деление: пример r1r1 ABCDr2r2 CD r = r 1 r 2 AB abcdcdbc abcfefed bcef bccd edef edcd edcf

Примеры запросов (1) Схема базы данных: S(Sid, SN, SC) – ПОСТАВЩИК ( Номер поставщика, Имя, Город) P(Pid, PN, PC) – ДЕТАЛЬ ( Номер детали, Название, Цена) SP(Sid (FK1), Pid (FK2), QTY) – ПОСТАВКА ( Номер поставщика, Номер детали, Количество)

Примеры запросов (2) Получить имена поставщиков, поставляющих деталь с номером P1. SN ( Pid = P1 (S SP)) Получить имена поставщиков, не поставляющих деталь с номером P1. SN (S) – SN ( Pid = P1 (S SP))

Примеры запросов (3) Получить имена поставщиков, поставляющих только деталь с номером P1 SN ( Pid =P1 (S SP)) – SN ( Pid P1 (S SP)) Получить имена поставщиков, поставляющих все детали SN (( Sid,Pid (SP) Pid (P)) S)