ОРГАНИЗАЦИЯ БАЗ ДАННЫХ И ЗНАНИЙ ТЕМА 4 ДОСТУП К ДАННЫМ В РЕЛЯЦИОННЫХ МОДЕЛЯХ ХРАНЕНИЯ ДАННЫХ

2.4. Манипуляционная часть Специальные реляционные операторы 1. Выборка (ограничение, селекция) Определение 6. Выборкой (ограничением, селекцией) на отношении A с условием C называется отношение с тем же заголовком, что и у отношения A, и телом, состоящем из кортежей, значения атрибутов которых при подстановке в условие C дают значение ИСТИНА. C представляет собой логическое выражение, в которое могут входить атрибуты отношения A и (или) скалярные выражения. В простейшем случае условие C имеет вид, где - один из операторов сравнения (=,,,, и т.д.), а X и Y - атрибуты отношения A или скалярные значения. Такие выборки называются -выборки (тата-выборки) или -ограничения, -селекции. Синтаксис операции выборки:, или

Операция выборки – это некоторое «горизонтальное» сечение нашего отношения, т.е. множество кортежей, являющееся подмножеством исходного отношения. Пример Пусть дано отношение A с информацией о сотрудниках: Смысл операции выборки очевиден - выбрать кортежи отношения, удовлетворяющие некоторому условию. Т.о., операция выборки дает "горизонтальный срез" отношения по некоторому условию. Отношение A Результат выборки будет иметь вид: Отношение A WHERE Зарплата<3000 Табельный номер Фамилия Зарплата 1Иванов Петров Сидоров 3000 Табельный номер Фамилия Зарплата 1Иванов Петров 2000

ВЫБОРКА (ОГРАНИЧЕНИЕ, ГОРИЗОНТАЛЬНОЕ ПОДМНОЖЕСТВО)

2. Проекция Определение 7. Проекцией отношения A по атрибутам X, Y,…, Z, где каждый из атрибутов принадлежит отношению A, называется отношение с заголовком (X, Y,…, Z) и телом, содержащим множество кортежей вида (x, y,…, z), таких, для которых в отношении A найдутся кортежи X со значением атрибута равным x, значением атрибута Y равным y, …, значением атрибута Z равным z. Синтаксис операции проекции: Замечание. Операция проекции дает "вертикальный срез" отношения, в котором удалены все возникшие при таком срезе дубликаты кортежей.

Номер поставщика Наименование поставщика Город поставщика 1Иванов Уфа 2Петров Москва 3Сидоров Москва 4Сидоров Челябинск Город поставщика Уфа Москва Челябинск Пример: Пусть дано отношение А с информацией о поставщиках, включающих наименование и месторасположение: Отношение A (Поставщики) Отношение A[Город поставщика]

ПРОЕКЦИЯ (ВЕРТИКАЛЬНОЕ ПОДМНОЖЕСТВО)

3. Соединение Операция соединения отношений, наряду с операциями выборки и проекции, является одной из наиболее важных реляционных операций. Обычно рассматривается несколько разновидностей операции соединения: 1)Общая операция соединения 2) -соединение (тата-соединение) 3)Экви-соединение 4)Естественное соединение Наиболее важным из этих частных случаев является операция естественного соединения. Все разновидности соединения являются частными случаями общей операции соединения. Общая операция соединения Определение 8. Соединением отношений А и В по условию С называется отношение представляет собой логическое выражение, в которое могут входить атрибуты отношений А и В и (или) скалярные выражения.

Таким образом, операция соединения есть результат последовательного применения операций декартового произведения и выборки. Если в отношениях А и В имеются атрибуты с одинаковыми наименованиями, то перед выполнением соединения такие атрибуты необходимо переименовать. Тэта-соединение Определение 9. Пусть отношение A содержит атрибут X, отношение B содержит атрибут Y, а - один из операторов сравнения ( и т.д.). Тогда -соединением отношения A по атрибуту X с отношением B по атрибуту Y называют отношение Это частный случай операции общего соединения. Иногда, для операции -соединения применяют следующий, более короткий синтаксис:

Пример Рассмотрим некоторую компанию, в которой хранятся данные о поставщиках и поставляемых деталях. Пусть поставщикам и деталям присвоен некий статус. Пусть бизнес компании организован таким образом, что поставщики имеют право поставлять только те детали, статус которых не выше статуса поставщика (смысл этого может быть в том, что хороший поставщик с высоким статусом может поставлять больше разновидностей деталей, а плохой поставщик с низким статусом может поставлять только ограниченный список деталей, важность которых (статус детали) не очень высока). Номер поставщика Наименование поставщика X (Статус поставщика) 1Иванов 4 2Петров 1 3Сидоров 2 Номер детали Наименование детали Y (Статус детали) 1Болт 3 2Гайка 2 3Винт 1 Отношение A (Поставщики)Отношение B (Детали) Ответ на вопрос "какие поставщики имеют право поставлять какие детали?" дает -соединение :

Номер поставщика Наименование поставщика X (Статус поставщика) Номер детали Наименован ие детали Y (Статус детали) 1Иванов 41Болт 3 1Иванов 42Гайка 2 1Иванов 43Винт 1 2Петров 13Винт 1 3Сидоров 22Гайка 2 3Сидоров 23Винт 1 Отношение "Какие поставщики поставляют какие детали"

Экви-соединение Наиболее важным частным случаем -соединения является случай, когда есть просто равенство. Синтаксис экви-соединения: Пример : Пусть имеются отношения P, D и PD, хранящие информацию о поставщиках, деталях и поставках соответственно (для удобства введем краткие наименования атрибутов): Номер поставщика PNUM Наименование поставщика PNAME 1Иванов 2Петров 3Сидоров Номер детали DNUM Наименование детали DNAME 1Болт 2Гайка 3Винт Отношение P (Поставщики)Отношение D (Детали)

Номер поставщика PNUM Номер детали DNUM Поставляемое количество VOLUME Отношение PD (Поставки) Ответ на вопрос, какие детали поставляются поставщиками, дает экви- соединение На самом деле, т.к. в отношениях имеются одинаковые атрибуты, то требуется сначала переименовать атрибуты, а потом выполнить экви-соединение. Запись становится более громоздкой:.

Номер поставщика PNUM1 Наименование поставщика PNAME Номер поставщика PNUM2 Номер детали DNUM Поставляемое количество VOLUME 1Иванов Иванов Иванов Петров Петров Сидоров Отношение "Какие детали поставляются какими поставщиками" Недостатком экви-соединения является то, что если соединение происходит по атрибутам с одинаковыми наименованиями (а так чаще всего и происходит!), то в результатирующем отношении появляется два атрибута с одинаковыми значениями. В примере атрибуты PNUM1 и PNUM2 содержат дублирующие данные. Избавиться от этого недостатка можно, взяв проекцию по всем атрибутам, кроме одного из дублирующих. Именно так действует естественное соединение.

Естественное соединение Определение 10. Пусть даны отношения A(A 1,A 2,…,A n,X 1,X 2,…,X p ) и B(X 1,X 2,…,X p,B 1,B 2,…,B m,), имеющие одинаковые атрибуты X 1,X 2,…,X p ) (т.е. атрибуты с одинаковыми именами и определенные на одинаковых доменах). Тогда естественным соединением отношений A и B называется отношение с заголовком (A 1,A 2,…,A n,X 1,X 2,…,X p,B 1,B 2,…,B m,) и телом, содержащим множество кортежей (a 1,a 2,…,a N,x 1,x 2,…,x P,b 1,b 2,…,b M,), таких, что (a 1,a 2,…,a N,x 1,x 2,…,x P )ЄA и (x 1,x 2,…,x P,b 1,b 2,…,b M,)ЄB. Естественное соединение настолько важно, что для него используют специальный синтаксис: A JOIN B Замечание. В синтаксисе естественного соединения не указываются, по каким атрибутам производится соединение. Естественное соединение производится по всем одинаковым атрибутам.

Замечание. Естественное соединение эквивалентно следующей последовательности реляционных операций: a)Переименовать одинаковые атрибуты в отношениях b)Выполнить декартово произведение отношений c)Выполнить выборку по совпадающим значениям атрибутов, имевших одинаковые имена d)Выполнить проекцию, удалив повторяющиеся атрибуты e)Переименовать атрибуты, вернув им первоначальные имена Замечание. Можно выполнять последовательное естественное соединение нескольких отношений. Нетрудно проверить, что естественное соединение (как, впрочем, и соединение общего вида) обладает свойством ассоциативности, т.е. (A JOIN B) JOIN C = A JOIN (B JOIN C), поэтому такие соединения можно записывать, опуская скобки: A JOIN B JOIN C

Номер поставщика PNUM Наименование поставщика PNAME Номер детали DNUM Наимено вание детали DNAME Поставляе мое количество VOLUME 1Иванов 1Болт 100 1Иванов 2Гайка 200 1Иванов 3Винт 300 2Петров 1Болт 150 2Петров 2Гайка 250 3Сидоров 1Болт 1000 Пример Ответ на вопрос "какие детали поставляются поставщиками", более просто записывается в виде естественного соединения трех отношений (для удобства просмотра порядок атрибутов изменен, это является допустимым по свойствам отношений): Отношение P JOIN PD JOIN D

Данная операция имеет сходство с ДЕКАРТОВЫМ ПРОИЗВЕДЕНИЕМ. Однако, здесь добавлено условие, согласно которому вместо полного произведения всех строк в результирующее отношение включаются только строки, удовлетворяющие определенному соотношению между атрибутами соединения (А1,A2) соответствующих отношений.

4. Деление Определение 11. Пусть даны отношения A(X 1,X 2,…,X n,Y 1,Y 2,…,Y m ) и B(Y 1,Y 2,…,Y m ), причем атрибуты Y 1,Y 2,…,Y m - общие для двух отношений. Делением отношений A на B называется отношение с заголовком X 1,X 2,…,X n и телом, содержащим множество кортежей x 1,x 2,…,x N, таких, что для всех кортежей y 1,y 2,…,y M в отношении A найдется кортеж x 1,x 2,…,x N,y 1,y 2,…,y M. Отношение A выступает в роли делимого, отношение B выступает в роли делителя. Деление отношений аналогично делению чисел с остатком. Синтаксис операции деления: A DEVIDBY B Замечание. Типичные запросы, реализуемые с помощью операции деления, обычно в своей формулировке имеют слово "все" - "какие поставщики поставляют все детали?".

Номер поставщика PNUM Номер детали DNUM Номер детали DNUM Номер поставщика PNUM 1 В качестве делимого возьмем проекцию X=PD[PNUM,DNUM], содержащую номера поставщиков и номера поставляемых ими деталей: В качестве делителя возьмем проекцию Y=D[DNUM], содержащую список номеров всех деталей (не обязательно поставляемых кем- либо): Деление X DEVIDEBY Y дает список номеров поставщиков, поставляющих все детали Проекция X=PD[PNUM,DNUM] Проекция Y=D[DNUM] Отношение X DEVIDEBY Y

Некоторые операции реляционной алгебры

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

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

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

Запросы, невыразимые средствами реляционной алгебры Имеется ряд типов запросов, которые принципиально нельзя выразить только при помощи операторов реляционной алгебры. Для получения ответов на подобные запросы приходится применять процедурные расширения реляционных языков. Пример: Пусть имеется отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ с набором атрибутов (Наименование вещества, Водород, Гелий, …, 105_элемент). Значением атрибута "Вещество" являются наименования химических веществ, значениями остальных атрибутов - процентный состав соответствующих элементов в этом веществе. Такое отношение могло бы иметь, к примеру, следующий вид: Наименование вещества ВодородГелий…105 элемент Дезоксирибону-клеиновая кислота 53…0.01 Бензин 500…0 …………… Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ

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

Правильнее разбить это отношение на три различных отношения: I.ВЕЩЕСТВО(НОМ_ВЕЩЕСТВА, ВЕЩЕСТВО), II.ЭЛЕМЕНТЫ(НОМ_ЭЛЕМЕНТА, ЭЛЕМЕНТ), III.ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ(НОМ_ВЕЩЕСТВА, НОМ_ЭЛЕМЕНТА, ПРОЦЕНТ). НОМ_ВЕЩЕ СТВА ВЕЩЕСТВО 1Дезоксирибонуклеин овая кислота 2Бензин НОМ_ЭЛЕМЕН ТА ЭЛЕМЕНТ 1Водород 2Гелий …… 105… НОМ_ВЕЩЕС ТВА НОМ_ЭЛЕМЕ НТА ПРОЦЕНТ Отношение ЭЛЕМЕНТЫ Отношение ВЕЩЕСТВО Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕ СТВ

Для отношений, нормализованных таким образом, исходный запрос реализуется следующей последовательностью операторов: 1.R1(НОМЕР_ВЕЩЕСТВА,НОМ_ЭЛЕМЕНТА,ПРОЦЕНТ)= ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ[ПРОЦЕНТ>90]. (Выборка из отношения). 2.R2(НОМ_ЭЛЕМЕНТА) = R1[НОМ_ЭЛЕМЕНТА]. (Проекция отношения). 3.R3(НОМ_ЭЛЕМЕНТА,ЭЛЕМЕНТ)= R2[НОМ_ЭЛЕМЕНТА=НОМ_ЭЛЕМЕНТА]ЭЛЕМЕНТЫ. (Естественное соединение) 4.ОТВЕТ(ЭЛЕМЕНТ) = R3[ЭЛЕМЕНТ]. (Проекция таблицы). На языке SQL такой запрос реализуется одной командой: SELECT ЭЛЕМЕНТЫ.ЭЛЕМЕНТ FROM ЭЛЕМЕНТЫ, ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ WHERE ЭЛЕМЕНТЫ.НОМ_ЭЛЕМЕНТА= ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.НОМ_ ЭЛЕМЕНТА AND ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.ПРОЦЕНТ>90;

Невыразимость транзитивного замыкания реляционными операторами Существует класс запросов, невыразимых средствами реляционной алгебры или реляционного исчисления по причине невыразимости средствами реляционной алгебры транзитивного замыкания отношений. Определение : Пусть отношение R задано на декартовом квадрате A 2 некоторого множества A. Транзитивным замыканием отношения R называется новое отношение, состоящее из кортежей (x, y), для которых выполняется: либо кортеж (x, y) Є R, либо найдется конечная последовательность элементов (z 1, z 2, …, z n ) Є A, такая, что все кортежи (x, z 1 ), (z 1, z 2 ), …, (z n, y) принадлежат отношению R. Очевидно, что.

Пример : Пусть множество A представляет собой следующее множество деталей и конструкций: A = {Болт, Гайка, Двигатель, Автомобиль, Колесо, Ось} причем некоторые из деталей и конструкций могут использоваться при сборке других конструкций. Взаимосвязь деталей описывается отношением R ("непосредственно используется в") и состоит изследующих кортежей: Конструкция Где используется Болт Двигатель Болт Колесо Гайка Двигатель Гайка Колесо Двигатель Автомобиль Колесо Автомобиль Ось Колесо Конструкция Где используется Болт Двигатель Болт Колесо Гайка Двигатель Гайка Колесо Двигатель Автомобиль Колесо Автомобиль Ось Колесо Болт Автомобиль Гайка Автомобиль Ось Автомобиль Отношение R Очевидный смысл замыкания состоит в описании включения деталей друг в друга не только непосредственно, а через использование их в промежуточных деталях, например, болт используется в автомобиле, т.к. он используется в двигателе, а двигатель используется в автомобиле. Транзитивное замыкание отношения R

Пример : Рассмотрим отношение, которое содержит данные о табельном номере сотрудника, фамилии, должности и табельном номере руководителя сотрудника – СОТРУДНИКИ (ТАБ_НОМ, ФАМИЛИЯ, ДОЛЖНОСТЬ, ТАБ_НОМ_РУК): ТАБ_НОМФАМИЛИЯДОЛЖНОСТЬТАБ_НОМ_РУК 1Иванов Директор 1 2Петров Глав.бухгалтер 1 3Сидоров Бухгалтер 2 4Васильев Начальник цеха 1 5Сухов Мастер 4 6Шарипов Рабочий 5 ………… Отношение СОТРУДНИКИ Ответ на запрос "Перечислить всех руководителей (прямых и непрямых) данного сотрудника" может быть получен при помощи понятия транзитивного замыкания. Однако транзитивное замыкание не может быть выражено операторами реляционной алгебры.

Кросс-таблицы Одной из задач, связанных с представлением табличных данных является построение так называемых кросс-таблиц. Пусть имеется отношение с тремя атрибутами и потенциальным ключом, включающим первые два атрибута. Примером такого отношения могут быть данные с объемами продаж различных товаров за некоторые промежутки времени: Товар МесяцКоличество Компьютеры Январь 100 Принтеры Январь 200 Сканеры Январь 300 Компьютеры Февраль 150 Принтеры Февраль 250 Сканеры Февраль 350 ……… Товар ЯнварьФевраль… Компьютеры … Принтеры … Сканеры … Требуется представить эти данные в виде таблицы, по строкам которой идут наименования товаров, по столбцам - месяцы, а в ячейках содержатся объемы продаж. Это и будет кросс-таблицей: Построить такую таблицу невозможно, т.к. необходимо превратить данные в ячейках таблицы в наименования новых столбцов таблицы Кросс-таблица

Выводы Доступ к реляционным данным возможен при помощи операторов реляционной алгебры. Реляционная алгебра замкнута таким образом, что результаты одних реляционных выражений можно использовать в других выражениях. Реляционные операторы объединены в две группы: I.Теоретико-множественные операторы: объединение, пересечение, вычитание, декартово произведение. II.Специальные реляционные операторы: выборка, проекция, соединение, деление. Для выполнения некоторых реляционных операторов требуется, чтобы отношения были совместимы по типу. Операторы соединения, пересечения и деления можно выразить через другие реляционные операторы, т.е. эти операторы не являются примитивными. Оставшиеся реляционные операторы (объединение, вычитание, декартово произведение, выборка, проекция) являются примитивными операторами - их нельзя выразить друг через друга. Запросы, требующие построения транзитивного замыкания отношений, построения кросс-таблиц нельзя выразить средствами реляционной алгебры. Для получения ответов на подобные запросы приходится использовать процедурные расширения реляционных языков.