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

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

2 Базы данных Обзор реляционной алгебры Кодда Лекция 4 Набор основных алгебраических операций состоит из восьми операций, которые делятся на два класса: теоретико-множественные операции; специальные реляционные операции.

3 Базы данных Обзор реляционной алгебры Кодда Лекция 4 Теоретико-множественные операции: объединение отношений; пересечение отношений; взятие разности отношений; взятие декартова произведения отношений. Специальные реляционные операции: ограничение отношения; проекция отношения; соединение отношений; деление отношений.

4 Базы данных Обзор реляционной алгебры Кодда Лекция 4 В состав алгебры включается операция присваивания, позволяющая сохранить в базе данных результаты вычисления алгебраических выражений, и операция переименования атрибутов, дающая возможность корректно сформировать заголовок (схему) результирующего отношения.

5 Базы данных Общая интерпретация реляционных операций Лекция 4 При выполнении операции объединения (UNION) двух отношений с одинаковыми заголовками производится отношение, включающее все кортежи, которые входят хотя бы в одно из отношений-операндов. Операция пересечения (INTERSECT) двух отношений с одинаковыми заголовками производит отношение, включающее все кортежи, которые входят в оба отношения-операнда. Отношение, являющееся разностью (MINUS) двух отношений с одинаковыми заголовками, включает все кортежи, входящие в отношение-первый операнд, такие, что ни один из них не входит в отношение, которое является вторым операндом.

6 Базы данных Общая интерпретация реляционных операций Лекция 4 При выполнении декартова произведения (TIMES) двух отношений, пересечение заголовков которых пусто, производится отношение, кортежи которого производятся путем объединения кортежей первого и второго операндов. Результатом ограничения (WHERE) отношения по некоторому условию является отношение, включающее кортежи отношения- операнда, удовлетворяющее этому условию. При выполнении проекции (PROJECT) отношения на заданное подмножество множества его атрибутов производится отношение, кортежи которого являются соответствующими подмножествами кортежей отношения-операнда.

7 Базы данных Общая интерпретация реляционных операций Лекция 4 При соединении (JOIN) двух отношений по некоторому условию образуется результирующее отношение, кортежи которого производятся путем объединения кортежей первого и второго отношений и удовлетворяют этому условию. У операции реляционного деления (DIVIDE BY) два операнда бинарное и унарное отношения. Результирующее отношение состоит из унарных кортежей, включающих значения первого атрибута кортежей первого операнда таких, что множество значений второго атрибута (при фиксированном значении первого атрибута) включает множество значений второго операнда. Операция переименования (RENAME) производит отношение, тело которого совпадает с телом операнда, но имена атрибутов изменены.

8 Базы данных Общая интерпретация реляционных операций Лекция 4 Операция присваивания (:=) позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД. В построении реляционного выражения могут участвовать все реляционные операции, кроме операции присваивания.

9 Базы данных Общая интерпретация реляционных операций Лекция 4 Приоритет операций: RENAME WHERE = PROJECT TIMES = JOIN = INTERSECT = = DIVIDE BY UNION = MINUS

10 Базы данных Замкнутость реляционной алгебры и операция переименования Лекция 4 Каждое значение-отношение характеризуется заголовком (или схемой) и телом (или множеством кортежей). Каждая операция должна производить отношение в полном смысле, т. е. оно должно обладать и телом, и заголовком. Только в этом случае можно будет строить вложенные выражения. Когда возникает конфликт именования атрибутов в отношениях- операндах одной реляционной операции, тогда к одному из операндов сначала применяется операция переименования, а затем основная операция выполняется без всяких проблем.

11 Базы данных Операции объединения, пересечения, взятия разности Лекция 4 В теории множеств: результатом объединения двух множеств A{a} и B{b} является такое множество C{c}, что для каждого с либо существует такой элемент a, принадлежащий множеству A, что c=a, либо существует такой элемент b, принадлежащий множеству B, что c=b ; пересечением множеств A и B является такое множество C{c}, что для любого c существуют такие элементы a, принадлежащий множеству A, и b, принадлежащий множеству B, что c=a=b ; разностью множеств A и B является такое множество C{c}, что для любого c существует такой элемент a, принадлежащий множеству A, что c=a, и не существует такой элемент b, принадлежащий B, что c=b.

12 Базы данных Операции объединения, пересечения, взятия разности Лекция 4 Совместимость отношений: два отношения совместимы по объединению в том и только в том случае, когда обладают одинаковыми заголовками. В развернутой форме это означает, что в заголовках обоих отношений содержится один и тот же набор имён атрибутов, и одноименные атрибуты определены на одном и том же домене.

13 Базы данных Операции объединения, пересечения, взятия разности Лекция 4 Рассмотрим операции на следующем примере:

14 Базы данных Операции объединения, пересечения, взятия разности Лекция 4

15 Базы данных Операция расширенного декартова произведения Лекция 4 В теории множеств: декартовым произведением множеств A{a} и B{b} является такое множество пар C{ }, что для каждого элемента множества C существуют такой элемент a множества A, что c 1 =a, и такой элемент b множества B, что c 2 =b. При взятии расширенного декартова произведения двух отношений элементом результирующего отношения является кортеж, который представляет собой объединение одного кортежа первого отношения и одного кортежа второго отношения. Проблема совместимости: Два отношения совместимы по взятию расширенного декартова произведения в том и только в том случае, если пересечение множеств имён атрибутов, взятых из их схем отношений, пусто.

16 Базы данных Операция расширенного декартова произведения Лекция 4 Пример расширенного декартова произведения:

17 Базы данных Теоретико-множественные операции Лекция 4 Все четыре теоретико-множественные операции являются ассоциативными, т. е. если обозначить через OP любую из четырёх операций, то (A OP B) OP C = A OP (B OP C) Все операции, кроме взятия разности, являются коммутативными, т. е. A OP B = B OP A

18 Базы данных Специальные реляционные операции: операция ограничения Лекция 4 Операция ограничения WHERE требует наличия двух операндов: ограничиваемого отношения и простого условия ограничения. Простое условие ограничения может иметь: вид (a comp-op b), где i>a и i>b имена атрибутов ограничиваемого отношения; атрибуты i>a и i>b должны быть определены на одном и том же домене, для значений базового типа данных которого поддерживается операция сравнения i>comp-op, или на базовых типах данных, над значениями которых можно выполнять эту операцию сравнения; или вид (a comp-op const), где a имя атрибута ограничиваемого отношения, а const литерально заданная константа; атрибут a должен быть определен на домене или базовом типе, для значений которого поддерживается операция сравнения comp-op.

19 Базы данных Специальные реляционные операции: операция ограничения Лекция 4 Операцией сравнения comp-op могут быть «=», «», «>», «», «

20 Базы данных Специальные реляционные операции: операция ограничения Лекция 4 Для обозначения вызова операции ограничения будем использовать конструкцию A WHERE comp, где A ограничиваемое отношение, а comp простое условие сравнения. Пусть comp1 и comp2 два простых условия ограничения. Тогда по определению: A WHERE (comp1 AND comp2) обозначает то же самое, что и (A WHERE comp1) INTERSECT (A WHERE comp2) ; A WHERE (comp1 OR comp2) обозначает то же самое, что и (A WHERE comp1) UNION (A WHERE comp2) ; A WHERE NOT comp1 обозначает то же самое, что и A MINUS (A WHERE comp1). Эти соглашения позволяют задействовать операции ограничения, в которых условием ограничения является произвольное булевское выражение, составленное из простых условий с использованием логических связок AND, OR, NOT и скобок.

21 Базы данных Специальные реляционные операции: операция ограничения Лекция 4 Например, результатом выполнения СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 WHERE (СЛУ_ЗАРП > AND (СЛУ_ОТД_НОМ = 310 OR СЛУ_ОТД_НОМ = 315)) будет: На интуитивном уровне операцию ограничения лучше всего представлять как взятие некоторой «горизонтальной» вырезки из отношения-операнда (выборка некоторых строк из таблицы).

22 Базы данных Специальные реляционные операции: операция взятия проекции Лекция 4 Операция взятия проекции также требует наличия двух операндов проецируемого отношения A и подмножества множества имен атрибутов, входящих в заголовок отношения A. При выполнении операции проекции выделяется «вертикальная» вырезка отношения-операнда с естественным уничтожением потенциально возникающих кортежей-дубликатов. Результат операции PROJECT СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 {СЛУ_ОТД_НОМ}

23 Базы данных Специальные реляционные операции: операция соединения отношений Лекция 4 Общая операция соединения (называемая также соединением по условию) требует наличия двух операндов соединяемых отношений и третьего операнда простого условия. Пусть соединяются отношения A и B. Как и в случае операции ограничения, условие соединения comp имеет вид либо (a comp-op b), либо (a comp-op const), где a и b имена атрибутов отношений A и B, const литерально заданная константа, и comp-op допустимая в данном контексте операция сравнения. Тогда по определению результатом операции соединения A JOIN B WHERE comp совместимых по взятию расширенного декартова произведения отношений A и B является отношение, получаемое путём выполнения операции ограничения по условию comp расширенного декартова произведения отношений A и B ( A JOIN B WHERE comp (A TIMES B) WHERE comp ).

24 Базы данных Специальные реляционные операции: операция соединения отношений Лекция 4 Существует важный частный случай соединения эквисоединение ( EQUIJOIN ) и простое, но важное расширение операции эквисоединения естественное соединение ( NATURAL JOIN ). Операция соединения называется операцией эквисоединения, если условие соединения имеет вид ( a = b ), где a и b атрибуты разных операндов соединения. Операция естественного соединения применяется к паре отношений A и B, обладающих (возможно, составным) общим атрибутом c. Пусть AB обозначает объединение заголовков отношений A и B. Тогда естественное соединение A и B это спроецированный на AB результат эквисоединения A и B по условию A.c = B.c. Основной смысл операции естественного соединения состоит в возможности восстановления сложной сущности, декомпозированной по причине требования первой нормальной формы.

25 Базы данных Специальные реляционные операции: операция деления отношений Лекция 4 Пусть заданы два отношения 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}. По определению, результатом деления A на B ( A DIVIDE BY B ) является «унарное» отношение C{a}, тело которого состоит из кортежей v таких, что в теле отношения A содержатся кортежи v UNION w такие, что множество {w} включает тело отношения B.

26 Базы данных Специальные реляционные операции: операция деления отношений Лекция 4 Например, результатом СЛУЖАЩИЕ DIVIDE BY НОМЕРА_ПРОЕКТОВ будет: