Введение в системы управления базами данных




Глава 4. Реляционная алгебра


    Обзор реляционной алгебры
    Обзор реляционной алгебры Третья часть реляционной модели, манипуляционная часть, утверждает, что доступ к реляционным данным осуществляется при помощи реляционной алгебры или эквивалентного ему р...
    Замкнутость реляционной алгебры
    Замкнутость реляционной алгебры Реляционная алгебра представляет собой набор операторов, использующих отношения в качестве аргументов, и возвращающие отношения в качестве результата. Таким образом...
    Отношения, совместимые по типу
    Отношения, совместимые по типу Некоторые реляционные операторы (например, объединение) требуют, чтобы отношения имели одинаковые заголовки. Действительно, отношения состоят из заголовка и тела. Оп...
    Определение 1
    Определение 1 . Будем называть отношения совместимыми по типу , если они имеют идентичные заголовки, а именно, Отношения имеют одно и то же множество имен атрибутов , т.е. для любого атрибута в од...
    Оператор переименования атрибутов
    Оператор переименования атрибутов Оператор переименования атрибутов имеет следующий синтаксис: где - отношение, - исходные имена атрибутов, - новые имена атрибутов. В результате применения операто...
    Пример 1
    Пример 1 . Следующий оператор возвращает неименованное отношение, в котором атрибут переименован в :...
    Определение 2
    Определение 2 . Объединением двух совместимых по типу отношений и называется отношение с тем же заголовком, что и у отношений и , и телом, состоящим из кортежей, принадлежащих или , или , или обои...
    Пример 2
    Пример 2 . Пусть даны два отношения и с информацией о сотрудниках:...
    Таблица 1
    Таблица 1 Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Петров 2000 3 Сидоров 3000 Таблица 1 Отношение A...
    Таблица 2
    Таблица 2 Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Пушников 2500 4 Сидоров 3000 Таблица 2 Отношение B Объединение отношений и будет иметь вид:...
    Таблица 3
    Таблица 3 Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Петров 2000 3 Сидоров 3000 2 Пушников 2500 4 Сидоров 3000 Таблица 3 Отношение A UNION B Замечание . Как видно из приведенного примера, по...
    Определение 3
    Определение 3 . Пересечением двух совместимых по типу отношений и называется отношение с тем же заголовком, что и у отношений и , и телом, состоящим из кортежей, принадлежащих одновременно обоим о...
    Пример 3
    Пример 3 . Для тех же отношений и , что и в предыдущем примере пересечение имеет вид:...
    Таблица 4
    Таблица 4 Табельный номер Фамилия Зарплата 1 Иванов 1000 Таблица 4 Отношение A INTERSECT B Замечание . Казалось бы, что в отличие от операции объединения, потенциальные ключи могли бы наследоватьс...
    Определение 4
    Определение 4 . Вычитанием двух совместимых по типу отношений и называется отношение с тем же заголовком, что и у отношений и , и телом, состоящим из кортежей, принадлежащих отношению и не принадл...
    Пример 4
    Пример 4 . Для тех же отношений и , что и в предыдущем примере вычитание имеет вид:...
    Таблица 5
    Таблица 5 Табельный номер Фамилия Зарплата 2 Петров 2000 3 Сидоров 3000 Таблица 5 Отношение A MINUS B...
    Определение 5
    Определение 5 . Декартовым произведением двух отношений и называется отношение, заголовок которого является сцеплением заголовков отношений и : , а тело состоит из кортежей, являющихся сцеплением...
    Пример 5
    Пример 5 . Пусть даны два отношения и с информацией о поставщиках и деталях:...
    Таблица 6
    Таблица 6 Номер поставщика Наименование поставщика 1 Иванов 2 Петров 3 Сидоров Таблица 6 Отношение A (Поставщики)...
    Таблица 7
    Таблица 7 Номер детали Наименование детали 1 Болт 2 Гайка 3 Винт Таблица 7 Отношение B (Детали) Декартово произведение отношений и будет иметь вид:...
    Таблица 8
    Таблица 8 Номер поставщика Наименование поставщика Номер детали Наименование детали 1 Иванов 1 Болт 1 Иванов 2 Гайка 1 Иванов 3 Винт 2 Петров 1 Болт 2 Петров 2 Гайка 2 Петров 3 Винт Определение 6
    Определение 6 . Выборкой (ограничением, селекцией) на отношении с условием называется отношение с тем же заголовком, что и у отношения , и телом, состоящем из кортежей, значения атрибутов которых...
    Пример 6
    Пример 6 . Пусть дано отношение с информацией о сотрудниках:...
    Таблица 9
    Таблица 9 Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Петров 2000 3 Сидоров 3000 Таблица 9 Отношение A Результат выборки будет иметь вид:...
    Таблица 10
    Таблица 10 Табельный номер Фамилия Зарплата 1 Иванов 1000 2 Петров 2000 Таблица 10 Отношение A WHERE Зарплата3000 Смысл операции выборки очевиден - выбрать кортежи отношения, удовлетворяющие некот...
    Определение 7
    Определение 7 . Проекцией отношения по атрибутам , где каждый из атрибутов принадлежит отношению , называется отношение с заголовком и телом, содержащим множество кортежей вида , таких, для которы...
    Пример 7
    Пример 7 . Пусть дано отношение с информацией о поставщиках, включающих наименование и месторасположение:...
    Таблица 11
    Таблица 11 Номер поставщика Наименование поставщика Город поставщика 1 Иванов Уфа 2 Петров Москва 3 Сидоров Москва 4 Сидоров Челябинск Таблица 11 Отношение A (Поставщики) Проекция будет иметь вид:...
    Таблица 12
    Таблица 12 Город поставщика Уфа Москва Челябинск Таблица 12 Отношение A[Город поставщика]...
    Соединение
    Соединение Операция соединения отношений, наряду с операциями выборки и проекции, является одной из наиболее важных реляционных операций. Обычно рассматривается несколько разновидностей операции с...
    Определение 8
    Определение 8 . Соединением отношений и по условию называется отношение представляет собой логическое выражение, в которое могут входить атрибуты отношений и и (или) скалярные выражения. Таким обр...
    Определение 9
    Определение 9 . Пусть отношение содержит атрибут , отношение содержит атрибут , а - один из операторов сравнения ( и т.д.). Тогда - соединением отношения по атрибуту с отношением по атрибуту Пример 8
    Пример 8 . Рассмотрим некоторую компанию, в которой хранятся данные о поставщиках и поставляемых деталях. Пусть поставщикам и деталям присвоен некий статус. Пусть бизнес компании организован таким...
    Таблица 13
    Таблица 13 Номер поставщика Наименование поставщика X (Статус поставщика) 1 Иванов 4 2 Петров 1 3 Сидоров 2 Таблица 13 Отношение A (Поставщики)...
    Таблица 14
    Таблица 14 Номер детали Наименование детали Y (Статус детали) 1 Болт 3 2 Гайка 2 3 Винт 1 Таблица 14 Отношение B (Детали) Ответ на вопрос "какие поставщики имеют право поставлять какие детали?" да...
    Таблица 15
    Таблица 15 Номер поставщика Наименование поставщика X (Статус поставщика) Номер детали Наименование детали Y (Статус детали) 1 Иванов 4 1 Болт 3 1 Иванов 4 2 Гайка 2 1 Иванов 4 3 Винт 1 2 Петров 1...
    Экви-соединение
    Экви-соединение Наиболее важным частным случаем -соединения является случай, когда есть просто равенство. Синтаксис экви-соединения :...
    Пример 9
    Пример 9 . Пусть имеются отношения , и , хранящие информацию о поставщиках, деталях и поставках соответственно (для удобства введем краткие наименования атрибутов):...
    Таблица 16
    Таблица 16 Номер поставщика PNUM Наименование поставщика PNAME 1 Иванов 2 Петров 3 Сидоров Таблица 16 Отношение P (Поставщики)...
    Таблица 17
    Таблица 17 Номер детали DNUM Наименование детали DNAME 1 Болт 2 Гайка 3 Винт Таблица 17 Отношение D (Детали)...
    Таблица 18
    Таблица 18 Номер поставщика PNUM Номер детали DNUM Поставляемое количество VOLUME 1 1 100 1 2 200 1 3 300 2 1 150 2 2 250 3 1 1000 Таблица 18 Отноше...
    Таблица 19
    Таблица 19 Номер поставщика PNUM1 Наименование поставщика PNAME Номер поставщика PNUM2 Номер детали DNUM Поставляемое количество VOLUME 1 Иванов 1 1 100 1 Иванов 1 2 200 1 Иванов 1 3 300 2 Петров...
    Определение 10
    Определение 10 . Пусть даны отношения и , имеющие одинаковые атрибуты (т.е. атрибуты с одинаковыми именами и определенные на одинаковых доменах). Тогда естественным соединением отношений и называе...
    Пример 10
    Пример 10 . В предыдущем примере ответ на вопрос "какие детали поставляются поставщиками", более просто записывается в виде естественного соединения трех отношений (для удобства просмотра порядок...
    Таблица 20
    Таблица 20 Номер поставщика PNUM Наименование поставщика PNAME Номер детали DNUM Наименование детали DNAME Поставляемое количество VOLUME 1 Иванов 1 Болт 100 1 Иванов 2 Гайка 200 1 Иванов 3 Винт 3...
    Определение 11
    Определение 11 . Пусть даны отношения и , причем атрибуты - общие для двух отношений. Делением отношений на называется отношение с заголовком и телом, содержащим множество кортежей , таких, что дл...
    Пример 11
    Пример 11 . В примере с поставщиками, деталями и поставками ответим на вопрос, "какие поставщики поставляют все детали?". В качестве делимого возьмем проекцию , содержащую номера поставщиков и ном...
    Таблица 21
    Таблица 21 Номер поставщика PNUM Номер детали DNUM 1 1 1 2 1 3 2 1 2 2 3 1 Таблица 21 Проекция X=PD[PNUM,DNUM] В качестве делителя возьмем проекцию , содержащую список номеров всех деталей (не обя...
    Таблица 22
    Таблица 22 Номер детали DNUM 1 2 3 Таблица 22 Проекция Y=D[DNUM] Деление дает список номеров поставщиков, поставляющих все детали:...
    Таблица 23
    Таблица 23 Номер поставщика PNUM 1 Таблица 23 Отношение X DEVIDEBY Y Оказалось, что только поставщик с номером 1 поставляет все детали....
    Примеры использования реляционных операторов Пример 12
    . Получить имена поставщиков, поставляющих деталь номер 2. Решение:...
    Пример 13
    Пример 13 . Получить имена поставщиков, поставляющих по крайней мере одну гайку. Решение: Ответ на этот запрос можно получить и иначе:...
    Пример 14
    Пример 14 . Получить имена поставщиков, поставляющих все детали. Решение:...
    Пример 15
    Пример 15 . Получить имена поставщиков, не поставляющих деталь номер 2. Решение: Ответ на этот запрос можно получить и пошагово: - получить список номеров всех поставщиков - соединить данные о пос...
    Зависимые реляционные операторы
    Зависимые реляционные операторы Как было сказано в начале главы, не все операторы реляционной алгебры являются независимыми - некоторые из них выражаются через другие реляционные операторы....
    Оператор соединения
    Оператор соединения Оператор соединения определяется через операторы декартового произведения и выборки. Для оператора естественного соединения добавляется оператор проекции....
    Оператор пересечения
    Оператор пересечения Оператор пересечения выражается через вычитание следующим образом:...
    Оператор деления
    Оператор деления Оператор деления выражается через операторы вычитания, декартового произведения и проекции следующим образом: Таким образом показано, что операторы соединения , пересечения и деле...
    Примитивные реляционные операторы
    Примитивные реляционные операторы Оставшиеся реляционные операторы ( объединение , вычитание , декартово произведение , выборка , проекция ) являются примитивными операторами - их нельзя выразить...
    Оператор декартового произведения
    Оператор декартового произведения Оператор декартового произведения - это единственный оператор, увеличивающий количество атрибутов , поэтому его нельзя выразить через объединение, вычитание, выбо...
    Оператор проекции
    Оператор проекции Оператор проекции - единственный оператор, уменьшающий количество атрибутов, поэтому его нельзя выразить через объединение, вычитание, декартово произведение, выборку....
    Оператор выборки
    Оператор выборки Оператор выборки - единственный оператор, позволяющий проводить сравнения по атрибутам отношения, поэтому его нельзя выразить через объединение, вычитание, декартово произведение,...
    Операторы объединения и вычитания
    Операторы объединения и вычитания Доказательство примитивности операторов объединения и вычитания более сложны и мы их здесь не приводим....
    Запросы, невыразимые средствами реляционной алгебры
    Запросы, невыразимые средствами реляционной алгебры Несмотря на мощь языка реляционной алгебры, имеется ряд типов запросов, которые принципиально нельзя выразить только при помощи операторов реляц...
    Плохая нормализация отношений
    Плохая нормализация отношений Данный пример взят из книги Гилуа М.М. [6, стр.43]....
    Пример 16
    Пример 16 . Пусть имеется отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ с набором атрибутов (Наименование вещества, Водород, Гелий, …, 105_элемент). Значением атрибута "Вещество" являются наименования химич...
    Таблица 24
    Таблица 24 Наименование вещества Водород Гелий … 105 элемент Дезоксирибону-клеиновая кислота 5 3 … 0.01 Бензин 50 0 … 0 … … … … … Таблица 24 Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ Рассмотрим запрос "...
    Таблица 25
    Таблица 25 НОМ_ВЕЩЕСТВА ВЕЩЕСТВО 1 Дезоксирибонуклеиновая кислота 2 Бензин Таблица 25 Отношение ВЕЩЕСТВО...
    Таблица 26
    Таблица 26 НОМ_ЭЛЕМЕНТА ЭЛЕМЕНТ 1 Водород 2 Гелий … … 105 … Таблица 26 Отношение ЭЛЕМЕНТЫ...
    Таблица 27
    Таблица 27 НОМ_ВЕЩЕСТВА НОМ_ЭЛЕМЕНТА ПРОЦЕНТ 1 1 5 1 2 3 1 105 0.01 2 1 50 Таблица 27 Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ Для отношений, нормализованных таким образом, исходный запрос реализуется...
    Невыразимость транзитивного замыкания реляционными операторами
    Невыразимость транзитивного замыкания реляционными операторами Следующий пример иллюстрирует класс запросов, невыразимых средствами реляционной алгебры или реляционного исчисления по причине невыр...
    Пример 17
    Пример 17 . Рассмотрим отношение, описывающее сотрудников некоего предприятия. Отношение содержит данные о табельном номере сотрудника, фамилии, должности и табельном номере руководителя сотрудник...
    Таблица 28
    Таблица 28 ТАБ_НОМ ФАМИЛИЯ ДОЛЖНОСТЬ ТАБ_НОМ_РУК 1 Иванов Директор 1 2 Петров Глав.бухгалтер 1 3 Сидоров Бухгалтер 2 4 Васильев Начальник цеха 1 5 Сухов Мастер 4 6 Шарипов Рабочий 5
Кросс-таблицы
Кросс-таблицы Одной из задач, связанных с представлением табличных данных является построение так называемых кросс-таблиц. Пусть имеется отношение с тремя атрибутами и потенциальным ключом, включа...
Примером такого отношения могут быть данные с объемами продаж различных товаров за некоторые промежутки времени: Таблица 29
Примером такого отношения могут быть данные с объемами продаж различных товаров за некоторые промежутки времени:...
Таблица 29 Товар Месяц Количество Компьютеры Январь 100 Принтеры Январь 200 Сканеры Январь 300 Компьютеры Февраль 150 Принтеры Февраль 250 Сканеры Февраль 350 … … … Таблица 29 Данные о продажах
Требуется представить эти данные в виде таблицы, по строкам которой идут наименования товаров, по столбцам - месяцы, а в ячейках содержатся объемы продаж. Это и будет кросс-таблицей:...
Таблица 30
Таблица 30 Товар Январь Февраль … Компьютеры 100 150 … Принтеры 200 250 … Сканеры 300 350 … Таблица 30 Кросс-таблица Построение кросс-таблицы средствами реляционной алгебры невозможно, т.к. для эт...
Выводы
Выводы Доступ к реляционным данным возможен при помощи операторов реляционной алгебры. Реляционная алгебра представляет собой набор операторов, использующих отношения в качестве аргументов, и возв...








Начало