Базы данных Лекция 5 Базисные средства манипулирования реляционными данными: алгебра A Дейта и Дарвена. - презентация

1 Базы данных Лекция 5 Базисные средства манипулирования реляционными данными: алгебра A Дейта и Дарвена

2 Базы данных Базовые операции Алгебры A Лекция 5 Некоторые базовые операции Алгебры A имеют названия обычных логических операций, чтобы избежать путаницы, имена реляционных операций берутся в угловые скобки:,, и т. д. В исходный базовый набор операций входят операции реляционного дополнения, удаления атрибута, переименования атрибута, реляционной конъюнкции и реляционной дизъюнкции.

3 Базы данных Базовые операции Алгебры A: операция реляционного дополнения Лекция 5 Пусть s обозначает результат операции r. Тогда: Hs = Hr (заголовок результата совпадает с заголовком операнда); Bs = {ts : exists tr (tr Br and ts = tr) } (в тело результата входят все кортежи, соответствующие заголовку и не входящие в тело операнда). Операция производит дополнение s заданного отношения r. Заголовком s является заголовок r. Тело s включает все кортежи, соответствующие этому заголовку и не входящие в тело r. Например, пусть в состав домена ДОПУСТИМЫЕ_НОМЕРА_ПРОЕКТОВ, на котором определен атрибут ПРО_НОМ отношения НОМЕРА_ПРОЕКТОВ входит всего пять значений {1, 2, 3, 4, 5}, тогда:

4 Базы данных Базовые операции Алгебры A: операция удаления атрибута Лекция 5 Пусть s обозначает результат операции r A. Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип (или домен) T такой, что Hr (т. е. в состав заголовка отношения r должен входить атрибут A ). Тогда: Hs = Hr minus { }, т. е. заголовок результата получается из заголовка операнда изъятием атрибута A ; Bs = {ts : exists tr exists v (tr Br and v T and tr and ts = tr minus { })}, т. е. в тело результата входят все кортежи операнда, из которых удалено значение атрибута A. Операция эквивалентна взятию проекции r на все атрибуты, кроме A.

5 Базы данных Базовые операции Алгебры A: операция удаления атрибута Лекция 5 Например, результатом СЛУЖАЩИЕ REMOVE ПРО_НОМ будет:

6 Базы данных Базовые операции Алгебры A: операция переименования Лекция 5 Пусть s обозначает результат операции r (A, B). Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип T, такой, что Hr, и чтобы не существовал такой тип T, что Hr. Т. е. в схеме отношения r должен присутствовать атрибут A и не должен присутствовать атрибут B. Тогда: Hs = (Hr minus { }) union { }, т. е. в схеме результата B заменяет A ; Bs = {ts : exists tr exists v (tr Br and v T and tr and ts = (tr minus { }) union { })}, т. е. в кортежах тела результата имя значений атрибута A меняется на B. Операция производит отношение s, которое отличается от заданного отношения r только именем одного его атрибута, которое изменяется с A на B.

7 Базы данных Базовые операции Алгебры A: операция реляционной конъюнкции Лекция 5 Пусть s обозначает результат операции r 1 r 2. Для обеспечения возможности выполнения операции требуется, чтобы если Hr 1 и Hr 2, то T1=T2. Т. е. если в двух отношениях-операндах имеются одноименные атрибуты, то они должны быть определены на одном и том же типе (домене).Тогда: Hs = Hr 1 union Hr 2, т. е. заголовок результата получается путём объединения заголовков отношений-операндов; Bs = { ts : exists tr 1 exists tr 2 ((tr 1 Br 1 and tr 2 Br 2 ) and ts = tr 1 union tr 2 )} ; при этом кортеж результата определяется как объединение кортежей операндов, поэтому: o если схемы отношений-операндов имеют непустое пересечение, то операция работает как естественное соединение; o если пересечение схем операндов пусто, то работает как расширенное декартово произведение; o если схемы отношений полностью совпадают, то результатом операции является пересечение двух отношений-операндов.

8 Базы данных Базовые операции Алгебры A: операция реляционной конъюнкции Лекция 5

9 Базы данных Базовые операции Алгебры A: операция реляционной конъюнкции Лекция 5

10 Базы данных Базовые операции Алгебры A: операция реляционной дизъюнкции Лекция 5 Пусть s обозначает результат операции r 1 r 2. Для обеспечения возможности выполнения операции требуется, чтобы если Hr 1 и Hr 2, то должно быть T1 = T2 (одноименные атрибуты должны быть определены на одном и том же типе). Тогда: Hs = Hr 1 union Hr 2 (из схемы результата удаляются атрибуты- дубликаты); Bs = { ts : exists tr 1 exists tr 2 ((tr 1 Br 1 or tr 2 Br 2 ) and ts = tr 1 union tr 2 )} ;

11 Базы данных Базовые операции Алгебры A: операция реляционной дизъюнкции Лекция 5 при этом: o если у операндов нет общих атрибутов, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr 1 и tr 2, соответствующих заголовкам отношений-операндов, и хотя бы один из этих кортежей принадлежит телу одного из операндов; o если у операндов имеются общие атрибуты, то в тело результирующего отношения входят все такие кортежи ts, которые являются объединением кортежей tr 1 и tr 2, соответствующих заголовкам отношений-операндов, если хотя бы один из этих кортежей принадлежит телу одного из операндов, и значения общих атрибутов tr 1 и tr 2 совпадают; o если же схемы отношений-операндов совпадают, то тело отношения-результата является объединением тел операндов.

12 Базы данных Базовые операции Алгебры A: операция реляционной дизъюнкции Лекция 5

13 Базы данных Базовые операции Алгебры A: операция реляционной дизъюнкции Лекция 5

14 Базы данных Полнота Алгебры A Лекция 5 В состав базовых операций Алгебры A входят: операция в качестве аналога операции PROJECT ; операция переименования атрибутов ; UNION является частным случаем операции ; TIMES, INTERSECT и NATURAL JOIN частные случаи операции. Осталось показать, что через операции Алгебры A выражаются операции взятия разности MINUS, ограничения ( WHERE ), соединения общего вида ( JOIN ) и реляционного деления ( DIVIDE BY ).

15 Базы данных Полнота Алгебры A: выводимость операции взятия разности Лекция 5 Для примера воспользуемся отношениями:

16 Базы данных Полнота Алгебры A: выводимость операции взятия разности Лекция 5

17 Базы данных Полнота Алгебры A: выводимость операции взятия разности Лекция 5 В итоге:

18 Базы данных Полнота Алгебры A: интерпретация операции ограничения Лекция 5 Например, СЛУЖАЩИЕ_1 ЗАРП_20000

19 Базы данных Полнота Алгебры A: интерпретация операции ограничения Лекция 5 Например, СЛУЖАЩИЕ_1 ЗАРП_БОЛЬШЕ_

20 Базы данных Полнота Алгебры A: интерпретация операции ограничения Лекция 5 Например, СЛУЖАЩИЕ_1 ЗАРП_НЕ_22000

21 Базы данных Полнота Алгебры A: интерпретация операции ограничения Лекция 5 Например, выразим СЛУЖАЩИЕ_1 WHERE СЛУ_НОМЕР = РУК_НОМ как СЛУЖАЩИЕ_1 ((((СЛУЖАЩИЕ_1 СЛУ_НОМЕР) СЛУ_ИМЯ) СЛУ_ЗАРП) (РУК_НОМ, СЛУ_НОМЕР))

22 Базы данных Полнота Алгебры A: интерпретация операции ограничения Лекция 5 Например СЛУЖАЩИЕ_2 ПРЕМ_БОЛЬШЕ_ЗАРП

23 Базы данных Полнота Алгебры A: соединения общего вида Лекция 5 В общем случае, чтобы получить результат соединения общего вида произвольных отношений A и B, нужно: выполнить над одним из отношений одну или несколько операций, чтобы избавиться от общих имен атрибутов; выполнить над полученными отношениями операцию, производящую расширенное декартово произведение; и для полученного отношения выполнить одну или несколько операций с отношениями-константами, чтобы должным образом ограничить его.

24 Базы данных Полнота Алгебры A: реляционное деление Лекция 5 Пусть имеются отношения r 1 {A, B} и r 2 {B}. Утверждается, что результат r 1 DIVIDE BY r 2 совпадает с результатом выражения (r 1 PROJECT A) MINUS (((r 2 TIMES (r 1 PROJECT A)) MINUS r 1 ) PROJECT A) в терминах операций реляционной алгебры Кодда или (r 1 B) (((r 2 (r 1 B)) r 1 ) B) в терминах операций Алгебры A.

25 Базы данных Избыточность Алгебры A Лекция 5 В формальной математической логике стандартным базисом для выражения всех возможных булевских функций является набор {NOT, AND, OR} (отрицание, дизъюнкция и конъюнкция). Известно, что этот набор традиционен, но избыточен, поскольку верны тождества A AND B NOT (NOT A OR NOT B) и A OR B NOT (NOT A AND NOT B) Аналогичные тождества справедливы для операций, и Алгебры A. Тем самым, в наборе базовых операций Алгебры A можно оставить операции и (или и ).

26 Базы данных Избыточность Алгебры A: реляционные аналоги штриха Шеффера и стрелки Пирса Лекция 5 Более того, в алгебре логики существуют две операции, через каждую из которых выражаются все три «базовые» операции: «штрих Шеффера» sh (A, B) NOT A OR NOT B ; «стрелка Пирса» pi (A, B) NOT A AND NOT B. Аналогичные тождества справедливы для реляционных вариантов штриха Шеффера (r1, r2) r1 r2 и стрелки Пирса (r1, r2) r1 r2 Поэтому можно свести набор операций Алгебры A к трём операциям: (или ); ;.

27 Базы данных Избыточность Алгебры A: избыточность операции переименования Лекция 5

28 Базы данных Избыточность Алгебры A: избыточность операции переименования Лекция 5 Можно сократить набор операций Алгебры A до двух операций: (или ) ;.