Математическая модель структуры Базы Данных

Таблица 23 Отношение X DEVIDEBY Y

Оказалось, что  только поставщик с номером 1 поставляет все детали.

Примеры использования реляционных операторов

Пример 12. Получить имена поставщиков, поставляющих деталь номер 2.

Решение:

Пример 13. Получить имена поставщиков, поставляющих по крайней мере одну гайку.

Решение:

Ответ на этот запрос можно получить и иначе:

Пример 14. Получить имена поставщиков, поставляющих все детали.

Решение:

Пример 15. Получить имена поставщиков, не поставляющих деталь номер 2.

Решение:

Ответ на этот запрос можно получить и пошагово:

- получить список номеров всех  поставщиков

- соединить данные о поставщиках и поставках

- в данных о поставщиках и  поставках оставить только данные  о поставках детали номер 2.

- получить список номеров поставщиков,  поставляющих деталь номер 2.

- получить список номеров поставщиков,  не поставляющих деталь номер 2.

- соединить список номеров поставщиков,  не поставляющих деталь номер  2 с данными о поставщиках (получатся  полные данные о поставщиках,  не поставляющих деталь номер  2).

- искомый ответ (имена поставщиков,  не поставляющих деталь номер  2).

Зависимые реляционные операторы

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

Оператор  соединения

Оператор соединения определяется через операторы декартового произведения и выборки. Для оператора естественного соединения добавляется оператор проекции.

Оператор  пересечения

Оператор пересечения  выражается через вычитание следующим  образом:

Оператор  деления

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

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

Примитивные реляционные операторы

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

Оператор  декартового произведения

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

Оператор  проекции

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

Оператор  выборки

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

Операторы объединения и  вычитания

Доказательство  примитивности операторов объединения  и вычитания более сложны и  мы их здесь не приводим.

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

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

Плохая  нормализация отношений

Данный пример взят из книги Гилуа М.М. [6, стр.43].

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

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

Рассмотрим запрос "Найти все химические элементы, содержание которых в каком-либо из веществ превышает заданный процент (скажем, 90)".

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

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

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

Правильнее разбить  это отношение на три различных  отношения:

1. ВЕЩЕСТВО(НОМ_ВЕЩЕСТВА, ВЕЩЕСТВО),
2. ЭЛЕМЕНТЫ(НОМ_ЭЛЕМЕНТА, ЭЛЕМЕНТ),
3. ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ(НОМ_ВЕЩЕСТВА, НОМ_ЭЛЕМЕНТА, ПРОЦЕНТ).

Таблица 25 Отношение ВЕЩЕСТВО

Таблица 26 Отношение ЭЛЕМЕНТЫ

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

Для отношений, нормализованных таким образом, исходный запрос реализуется следующей  последовательностью операторов:

1. R1(НОМЕР_ВЕЩЕСТВА,НОМ_ЭЛЕМЕНТА,ПРОЦЕНТ)= ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ[ПРОЦЕНТ>90]. (Выборка из отношения).
2. R2(НОМ_ЭЛЕМЕНТА) = R1[НОМ_ЭЛЕМЕНТА]. (Проекция отношения).
3. R3(НОМ_ЭЛЕМЕНТА,ЭЛЕМЕНТ)= R2[НОМ_ЭЛЕМЕНТА=НОМ_ЭЛЕМЕНТА]ЭЛЕМЕНТЫ. (Естественное соединение)
4. ОТВЕТ(ЭЛЕМЕНТ) = R3[ЭЛЕМЕНТ]. (Проекция таблицы).

На языке SQL такой  запрос реализуется одной командой:

SELECT ЭЛЕМЕНТЫ.ЭЛЕМЕНТ

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

  WHERE

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

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

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

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

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

Таблица 28 Отношение СОТРУДНИКИ

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

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

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

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

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