Базисные средства манипулирования реляционными данными: реляционная алгебра и реляционное исчисление. Лекция №6

Август 23, 2022

Главная
Информатика
Базисные средства манипулирования реляционными данными: реляционная алгебра и реляционное исчисление. Лекция №6

Содержание

2. Реляционные операторы Традиционно, вслед за Коддом, определяют восемь реляционных операторов, объединенных в две группы. Теоретико-множественные операторы:
3. Соединение Операция соединения отношений, наряду с операциями выборки и проекции, является одной из наиболее важных реляционных
4. Общая операция соединения Определение. Соединением отношений A и B по условию c называется отношение (A TIMES
5. Тэта-соединение Определение. Пусть отношение A содержит атрибут X, отношение B содержит атрибут Y, а θ -
6. Пример Рассмотрим некоторую компанию, в которой хранятся данные о поставщиках и поставляемых деталях. Пусть поставщикам и
7. Пример Отношение A (Поставщики) Отношение B (Детали) Отношение "Какие поставщики поставляют какие детали" (A TIMES B)
8. Экви-соединение Наиболее важным частным случаем θ-соединения является случай, когда θ есть просто равенство. Синтаксис экви-соединения: (A
9. Пример Отношение P (Поставщики) Отношение D (Детали) Отношение PD (Поставки)
10. Пример Отношение "Какие детали поставляются какими поставщиками" Недостатком экви-соединения является то, что если соединение происходит по
11. Естественное соединение Определение. Пусть даны отношения A(A1,A2,…,AN,X1,…,XP) и B(X1,…,XP, B1,B2,…,BM), имеющие одинаковые атрибуты X1,…,XP (т.е. атрибуты
12. Пример Отношение P JOIN PD JOIN D
14. Деление Определение. Пусть даны отношения A(X1,X2,…,XN,Y1,Y2,…,YM) и B(Y1,Y2,…,YM), причем атрибуты Y1,Y2,…,YM - общие для двух отношений.
15. Пример Проекция X=PD[PNUM,DNUM] Проекция Y=D[DNUM] Отношение X DEVIDEBY Y дает список номеров поставщиков, поставляющих все детали
16. УРА! ПЕРЕМЕНА!
17. Зависимые реляционные операторы Не все операторы реляционной алгебры являются независимыми - некоторые из них выражаются через
18. Примитивные реляционные операторы Оставшиеся реляционные операторы объединение, вычитание, декартово произведение, выборка, Проекция являются примитивными операторами -
19. Примитивные реляционные операторы Оператор декартового произведения Оператор декартового произведения - это единственный оператор, увеличивающий количество атрибутов,
20. Запросы, невыразимые средствами реляционной алгебры Несмотря на мощь языка реляционной алгебры, имеется ряд типов запросов, которые
21. Плохая нормализация отношений Пример. Пусть имеется отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ с набором атрибутов (Наименование вещества, Водород, Гелий, …,
22. Продолжение Рассмотрим запрос "Найти все химические элементы, содержание которых в каком-либо из веществ превышает заданный процент
23. Отношение ВЕЩЕСТВО Отношение ЭЛЕМЕНТЫ Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ
24. Невыразимость транзитивного замыкания реляционными операторами Рассмотрим запрос "Перечислить всех руководителей (прямых и непрямых) данного сотрудника". Ответом
25. Кросс-таблицы Пусть имеется отношение с тремя атрибутами и потенциальным ключом, включающим первые два атрибута. Примером такого
26. Выводы Традиционно определяют восемь реляционных операторов, объединенных в две группы. Теоретико-множественные операторы: объединение, пересечение, вычитание, декартово
27. Выводы Не все операторы реляционной алгебры являются независимыми - некоторые из них выражаются через другие реляционные
29. Скачать презентацию

Слайд 2

Реляционные операторы
Традиционно, вслед за Коддом, определяют восемь реляционных операторов, объединенных в

две группы.
Теоретико-множественные операторы:
Объединение
Пересечение
Вычитание
Декартово произведение
Специальные реляционные операторы:
Выборка
Проекция
Соединение
Деление
Не все они являются независимыми, т.е. некоторые из этих операторов могут быть выражены через другие реляционные операторы.

Слайд 3

Соединение
Операция соединения отношений, наряду с операциями выборки и проекции, является

одной из наиболее важных реляционных операций.
Обычно рассматривается несколько разновидностей операции соединения:
Общая операция соединения
θ -соединение (тэта-соединение)
Экви-соединение
Естественное соединение
Наиболее важным из этих частных случаев является операция естественного соединения. Все разновидности соединения являются частными случаями общей операции соединения.

Слайд 4

Общая операция соединения
Определение. Соединением отношений A и B по условию

c называется отношение
(A TIMES B) WHERE c
c представляет собой логическое выражение, в которое могут входить атрибуты отношений A и B и (или) скалярные выражения.
Таким образом, операция соединения есть результат последовательного применения операций декартового произведения и выборки. Если в отношениях A и B имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты необходимо переименовать.

Слайд 5

Тэта-соединение
Определение. Пусть отношение A содержит атрибут X, отношение B содержит

атрибут Y, а θ - один из операторов сравнения (=,<,> и т.д.). Тогда θ-соединением отношения A по атрибуту X с отношением B по атрибуту Y называют отношение
(A TIMES B) WHERE X θ Y
Это частный случай операции общего соединения.

Слайд 6

Пример
Рассмотрим некоторую компанию, в которой хранятся данные о поставщиках и поставляемых

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

Слайд 7

Пример
Отношение A (Поставщики)
Отношение B (Детали)
Отношение "Какие поставщики поставляют какие

детали"
(A TIMES B) WHERE X>=Y

Слайд 8

Экви-соединение
Наиболее важным частным случаем θ-соединения является случай, когда θ есть

просто равенство.
Синтаксис экви-соединения:
(A TIMES B) WHERE X=Y

Слайд 9

Пример
Отношение P (Поставщики)
Отношение D (Детали)
Отношение PD (Поставки)

Слайд 10

Пример
Отношение "Какие детали поставляются какими поставщиками"
Недостатком экви-соединения является то, что

если соединение происходит по атрибутам с одинаковыми наименованиями (а так чаще всего и происходит!), то в результатирующем отношении появляется два атрибута с одинаковыми значениями. В нашем примере атрибуты PNUM1 и PNUM2 содержат дублирующие данные. Избавиться от этого недостатка можно, взяв проекцию по всем атрибутам, кроме одного из дублирующих. Именно так действует естественное соединение.

Слайд 11

Естественное соединение
Определение. Пусть даны отношения A(A1,A2,…,AN,X1,…,XP) и B(X1,…,XP, B1,B2,…,BM), имеющие

одинаковые атрибуты X1,…,XP (т.е. атрибуты с одинаковыми именами и определенные на одинаковых доменах).
Тогда естественным соединением отношений A и B называется отношение с заголовком (A1,A2,…,AN,X1,…,XP,B1,B2,…,BM) и телом, содержащим множество кортежей (a1,a2,…,aN,x1,…,xP,b1,b2,…,bM), таких, что (a1,a2,…,aN,x1,…,xP) Є A и (a1,a2,…,aN,x1,…,xP,b1,b2,…,bM) Є B.
Естественное соединение настолько важно, что для него используют специальный синтаксис:
A JOIN B

Слайд 12

Пример
Отношение P JOIN PD JOIN D

Слайд 13

Слайд 14

Деление
Определение. Пусть даны отношения A(X1,X2,…,XN,Y1,Y2,…,YM) и B(Y1,Y2,…,YM), причем атрибуты Y1,Y2,…,YM -

общие для двух отношений. Делением отношений A на B называется отношение с заголовком (X1,X2,…,XN) и телом, содержащим множество кортежей (x1,x2,…,xn), таких, что для всех кортежей (y1,y2,…,ym) Є B в отношении A найдется кортеж (x1,x2,…,xn, y1,y2,…,ym).
Отношение A выступает в роли делимого, отношение B выступает в роли делителя. Деление отношений аналогично делению чисел с остатком.
Синтаксис операции деления:
A DEVIDEBY B

Слайд 15

Пример
Проекция X=PD[PNUM,DNUM]
Проекция Y=D[DNUM]
Отношение X DEVIDEBY Y дает список номеров

поставщиков,
поставляющих все детали

Слайд 16

УРА! ПЕРЕМЕНА!

Слайд 17

Зависимые реляционные операторы
Не все операторы реляционной алгебры являются независимыми -

некоторые из них выражаются через другие реляционные операторы.
Оператор соединения
Оператор соединения определяется через операторы декартового произведения и выборки. Для оператора естественного соединения добавляется оператор проекции.
Оператор пересечения
Оператор пересечения выражается через вычитание следующим образом:
A INTERSECT B = A MINUS (A MINUS B)
Оператор деления
Оператор деления выражается через операторы вычитания, декартового произведения и проекции следующим образом:

Слайд 18

Примитивные реляционные операторы
Оставшиеся реляционные операторы
объединение,
вычитание,
декартово произведение,
выборка,

Проекция
являются примитивными операторами - их нельзя выразить друг через друга.

Слайд 19

Примитивные реляционные операторы
Оператор декартового произведения
Оператор декартового произведения - это единственный

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

Слайд 20

Запросы, невыразимые средствами реляционной алгебры
Несмотря на мощь языка реляционной алгебры,

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

Слайд 21

Плохая нормализация отношений
Пример. Пусть имеется отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ с набором атрибутов

(Наименование вещества, Водород, Гелий, …, 105_элемент).
Значением атрибута "Вещество" являются наименования химических веществ, значениями остальных атрибутов - процентный состав соответствующих элементов в этом веществе. Такое отношение могло бы иметь, к примеру, следующий вид:

Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ

Слайд 22

Продолжение
Рассмотрим запрос "Найти все химические элементы, содержание которых в каком-либо из

веществ превышает заданный процент (скажем, 90)".
С алгоритмической точки зрения этот запрос выполняется элементарно - просматриваются все столбцы таблицы, если в столбце присутствует хотя бы одно значение, большее 90, то запоминается заголовок этого столбца. Набор наименований запомненных столбцов и является ответом на запрос.
Формально невозможно выразить этот запрос в рамках реляционной алгебры, т.к. ответом на этот запрос должен быть список атрибутов отношений, удовлетворяющих определенному условию. В реляционной алгебре нет операторов, манипулирующих с наименованиями атрибутов.
На самом деле, этот пример показывает, что таблица плохо нормализована. В таблице есть набор однотипных атрибутов ("Водород", "Гелий" и т.д. в количестве 105 столбцов).

Слайд 23

Отношение ВЕЩЕСТВО
Отношение ЭЛЕМЕНТЫ
Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ

Слайд 24

Невыразимость транзитивного замыкания реляционными операторами
Рассмотрим запрос "Перечислить всех руководителей (прямых

и непрямых) данного сотрудника".
Ответом на запрос может быть получен при помощи понятия транзитивного замыкания. Однако транзитивное замыкание не может быть выражено операторами реляционной алгебры

Отношение СОТРУДНИКИ

Слайд 25

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

первые два атрибута. Примером такого отношения могут быть данные с объемами продаж различных товаров за некоторые промежутки времени:
Требуется представить эти данные в виде таблицы, по строкам которой идут наименования товаров, по столбцам - месяцы, а в ячейках содержатся объемы продаж. Это и будет кросс-таблицей:
Построение кросс-таблицы средствами реляционной алгебры невозможно, т.к. для этого требуется превратить данные в ячейках таблицы в наименования новых столбцов таблицы.

Данные о продажах

Кросс-таблица

Слайд 26

Выводы
Традиционно определяют восемь реляционных операторов, объединенных в две группы.
Теоретико-множественные

операторы:
объединение,
пересечение,
вычитание,
декартово произведение.
Специальные реляционные операторы:
выборка,
проекция,
соединение,
деление.
Для выполнения некоторых реляционных операторов требуется, чтобы отношения были совместимы по типу.

Слайд 27

Выводы
Не все операторы реляционной алгебры являются независимыми - некоторые из

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

Базисные средства манипулирования реляционными данными: реляционная алгебра и реляционное исчисление. Лекция №6

Содержание

Реляционные операторыТрадиционно, вслед за Коддом, определяют восемь реляционных операторов, объединенных в

Соединение Операция соединения отношений, наряду с операциями выборки и проекции, является

Общая операция соединения Определение. Соединением отношений A и B по условию

Тэта-соединение Определение. Пусть отношение A содержит атрибут X, отношение B содержит

ПримерРассмотрим некоторую компанию, в которой хранятся данные о поставщиках и поставляемых

ПримерОтношение A (Поставщики) Отношение B (Детали) Отношение "Какие поставщики поставляют какие

Экви-соединение Наиболее важным частным случаем θ-соединения является случай, когда θ есть

ПримерОтношение P (Поставщики) Отношение D (Детали) Отношение PD (Поставки)

ПримерОтношение "Какие детали поставляются какими поставщиками" Недостатком экви-соединения является то, что

Естественное соединение Определение. Пусть даны отношения A(A1,A2,…,AN,X1,…,XP) и B(X1,…,XP, B1,B2,…,BM), имеющие

ПримерОтношение P JOIN PD JOIN D

ДелениеОпределение. Пусть даны отношения A(X1,X2,…,XN,Y1,Y2,…,YM) и B(Y1,Y2,…,YM), причем атрибуты Y1,Y2,…,YM -

ПримерПроекция X=PD[PNUM,DNUM] Проекция Y=D[DNUM] Отношение X DEVIDEBY Y дает список номеров

УРА! ПЕРЕМЕНА!

Зависимые реляционные операторы Не все операторы реляционной алгебры являются независимыми -

Примитивные реляционные операторы Оставшиеся реляционные операторы объединение, вычитание, декартово произведение, выборка,

Примитивные реляционные операторы Оператор декартового произведенияОператор декартового произведения - это единственный

Запросы, невыразимые средствами реляционной алгебры Несмотря на мощь языка реляционной алгебры,

Плохая нормализация отношений Пример. Пусть имеется отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ с набором атрибутов

ПродолжениеРассмотрим запрос "Найти все химические элементы, содержание которых в каком-либо из

Отношение ВЕЩЕСТВО Отношение ЭЛЕМЕНТЫ Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ

Невыразимость транзитивного замыкания реляционными операторами Рассмотрим запрос "Перечислить всех руководителей (прямых

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

Выводы Традиционно определяют восемь реляционных операторов, объединенных в две группы. Теоретико-множественные

Выводы Не все операторы реляционной алгебры являются независимыми - некоторые из

Похожие презентации