double arrow

Реляционное исчисление

Выводы

Невыразимость транзитивного замыкания реляционными операторами

WHERE

ЭЛЕМЕНТЫ.НОМ_ЭЛЕМЕНТА=ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.НОМ_ЭЛЕМЕНТА

AND ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.ПРОЦЕНТ>90;

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

Пример 17. Рассмотрим отношение, описывающее сотрудников некоего предприятия. Отношение содержит данные о табельном номере сотрудника, фамилии, должности и табельном номере руководителя сотрудника – СОТРУДНИКИ (ТАБ_НОМ, ФАМИЛИЯ, ДОЛЖНОСТЬ, ТАБ_НОМ_РУК):

Таблица 28 Отношение СОТРУДНИКИ
ТАБ_НОМ ФАМИЛИЯ ДОЛЖНОСТЬ ТАБ_НОМ_РУК
Иванов Директор
Петров Глав.бухгалтер
Сидоров Бухгалтер
Васильев Начальник цеха
Сухов Мастер
Шарипов Рабочий

Рассмотрим запрос «Перечислить всех руководителей (прямых и непрямых) данного сотрудника».

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

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

Одной из задач, связанных с представлением табличных данных является построение так называемых кросс-таблиц.

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

Таблица 29 Данные о продажах
Товар Месяц Количество
Компьютеры Январь
Принтеры Январь
Сканеры Январь
Компьютеры Февраль
Принтеры Февраль
Сканеры Февраль

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

Таблица 30 Кросс-таблица
Товар Январь Февраль
Компьютеры
Принтеры
Сканеры

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

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

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

Теоретико-множественные операторы: объединение, пересечение, вычитание, декартово произведение.

Специальные реляционные операторы: выборка, проекция, соединение, деление.

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

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

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


Предположим, что мы работаем с базой данных, обладающей схемой СОТРУДНИКИ (СОТР_НОМ, СОТР_ИМЯ, СОТР_ЗАРП, ОТД_НОМ) и ОТДЕЛЫ (ОТД_НОМ, ОТД_КОЛ, ОТД_НАЧ), и хотим узнать имена и номера сотрудников, являющихся начальниками отделов с количеством сотрудников больше 50.

Если бы для формулировки такого запроса использовалась реляционная алгебра, то мы получили бы алгебраическое выражение, которое читалось бы, например, следующим образом:

  • выполнить соединение отношений СОТРУДНИКИ и ОТДЕЛЫ по условию СОТР_НОМ = ОТД_НАЧ;
  • ограничить полученное отношение по условию ОТД_КОЛ > 50;
  • спроецировать результат предыдущей операции на атрибут СОТР_ИМЯ, СОТР_НОМ.

Мы четко сформулировали последовательность шагов выполнения запроса, каждый из которых соответствует одной реляционной операции. Если же сформулировать тот же запрос с использованием реляционного исчисления, которому посвящается этот раздел, то мы получили бы формулу, которую можно было бы прочитать, например, следующим образом: Выдать СОТР_ИМЯ и СОТР_НОМ для сотрудников таких, что существует отдел с таким же значением ОТД_НАЧ и значением ОТД_КОЛ большим 50.

Во второй формулировке мы указали лишь характеристики результирующего отношения, но ничего не сказали о способе его формирования. В этом случае система должна сама решить, какие операции и в каком порядке нужно выполнить над отношениями СОТРУДНИКИ и ОТДЕЛЫ. Обычно говорят, что алгебраическая формулировка является процедурной, т.е. задающей правила выполнения запроса, а логическая - описательной (или декларативной), поскольку она всего лишь описывает свойства желаемого результата. Как мы указывали в начале лекции, на самом деле эти два механизма эквивалентны и существуют не очень сложные правила преобразования одного формализма в другой.


Сейчас читают про: