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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наименование вещества Водород Гелий … 105 элемент Дезоксирибонуклеиновая кислота     … 0.01 Бензин     …   … … … … …

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

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

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

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

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

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

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

НОМ_ВЕЩЕСТВА ВЕЩЕСТВО   Дезоксирибонуклеиновая кислота   Бензин

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

НОМ_ЭЛЕМЕНТА ЭЛЕМЕНТ   Водород   Гелий … …   …

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

НОМ_ВЕЩЕСТВА НОМ_ЭЛЕМЕНТА ПРОЦЕНТ                 0.01

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

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

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

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

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