Пример.

НФ

НФ

НФ

Отдел

Служащий

Работник_отдела

Аномалии вставки. Существует два типа аномалий вставки:

1. При вставке новых служащих в отношение Работник_отделанеобходимо указать все сведения об отделе, в котором он работает.

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

Аномалии удаления. При удалении из отношения Работник_отдела, например, четвертой строки, сведения об отделе В5 теряются.

Аномалии обновления. При попытке обновления значения одного из атрибутов для некоторого из отделов в отношении Работник_отдела(например, телефона отдела В3) необходимо обновить соответствующие значения во всех записях с этим отделом. В противном случае БД будет содержать противоречивые сведения.

.Функциональные зависимости

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

R1=rel(Учебная группа, Студент, Студент из группы = afn[1, 1], Группа студентов = afn[5, 10]).

Это означает, что студент может учиться максимум и минимум в одной группе. С другой стороны, группа может состоять минимум из пяти и максимум из тридцати студентов.

Особый класс отношений с параметрами доступа [1, 1] и [0, 1] называют функциональными отношениями и обозначают как E ® F, где в отношении

Концепция функционального отношения аналогична понятию ключа.

E – вероятностный или потенциальный ключ отношения R(A), если:

1. (Единственность идентификатора) E®A.

2. (Не избыточность) Не существует атрибута в E, который мог бы быть удален без разрушения свойства 1.

3. Каждый атрибут из R функционально зависит от E.

4. Набор атрибутов из R в E максимально независимое множество, то есть каждое подмножество E и никакие другие атрибуты из R не могут быть добавлены к E без разрушения этой функциональной независимости.

Итак, функциональная зависимость задает связь между атрибутами отношения. Например, если в отношении R содержатся атрибуты A, B, атрибут B функционально зависит от A (A®B), то каждое значение атрибута A связано только с одним значением B (Причем каждый атрибут A, B могут состоять из одного или нескольких атрибутов). Если нам известно значение атрибута A, то при рассмотрении отношения с такой зависимостью, в любой момент времени во всех строках этого отношения, содержащих указанное значение А, мы найдем одно и то же значение B, то есть, если две строки имеют одно и то же значение атрибута A, то они имеют одно и то же значение атрибута B. Однако, для заданного значения атрибута B может существовать несколько различных значений A. Детерминантом функциональной зависимости называется атрибут или группа атрибут, расположенных слева от символа стрелки (Экциндентные вершины на диаграмме функциональных зависимостей). A®B (A – детерминанта).

Рассмотрим функциональные зависимости отношения Работник_отдела.

ИНН ® ФИО

ИНН ® АдресС

ИНН ® Должность

ИНН ® Ставка

ИНН ® № отдела

ИНН ® АдресО

ИНН ® Телефон

№ отдела ® АдресО

№ отдела ® Телефон

АдресО ® № отдела

АдресО ® Телефон

Телефон ® АдресО

Телефон ® № отдела

Итого 13 функциональных зависимостей, в которых ИНН, № отдела, АдресО, Телефон играют роль детерминантов. Обобщенно можно записать:

ИНН ® ФИО, АдресС, Должность, Ставка, № отдела, АдресО, Телефон

№ отдела ® АдресО, Телефон

АдресО ® № отдела, Телефон

Телефон ® № отдела, АдресО

(Нарисовать диаграмму функциональных зависимостей)

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

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

Единственный потенциальный ключ в примере ИНН, так как все атрибуты зависят от него. Хотя атрибуты № отдела, АдресО и Телефон детерминанты, они не являются потенциальными ключами.

Процесс нормализации

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

Первая нормальная форма – отношение, в котором на пересечении каждого столбца и строки содержится только одно значение (отсутствуют сложные домены).

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

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

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

Оба подхода корректны. Однако, при втором подходе, полученные отношения находятся в 1НФ и обладают меньшей избыточностью. Первый подход будет показан ниже. Здесь приведем пример второго похода.

Пусть задано отношение:

Учебная группа (№ группы, Занятия, Студент)

Причем домены Занятияи Студентявляются непростыми доменами.

Занятия(Календарный план, Предмет, Код предмета, Преподаватель)

Студент(№ зачетки, ФИОС)

Календарный план(Дата, Аудитория)

Преподаватель(ИНН, ФИОП)

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

1 шаг:

Занятия(№ группы, Календарный план, Предмет, Код предмета, Преподаватель)

Студент(№ группы, № зачетки, ФИОС)

2 шаг.

Календарный план(№ группы, Предмет, Код предмета, Дата, Аудитория)

Преподаватель(№группы, Код предмета, ИНН, ФИОП)

Студент(№ группы, № зачетки, ФИОС)

Такая форма процедуры нормализации применима при следующих условиях:

1. Граф связи непростых доменов имеет вид дерева.

2. Основной ключ не содержит в качестве своей составляющей непростой домен.

В некотором отношении атрибут B называется полностью зависимым от атрибута A, если атрибут B функционально зависит от полного значения атрибута A и не зависит ни от какого подмножества полного значения атрибута A.

Функциональная зависимость A®B является полной функциональной зависимостью, если удаление какого-либо атрибута из A приводит к утрате этой зависимости.

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

Переход от 1 НФ к 2 НФ состоит в замене отношения его проекциями.

Дано отношение R(A, B, C, D).

R(A, B, C, D) заменяется на отношения R1(A, B, C,) и R2( B, D).

Если для атрибутов A, B, C некоторого отношения существуют зависимости A ® B, B ® C, при условии, что атрибут A не зависит ни от B, ни от C, то говорят, что атрибут C транзитивно зависит от A через атрибут B.

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

Переход от 2 НФ к 3 НФ состоит в замене отношения его проекциями.

R(A, B, C), в котором A ® B, B ® C, заменяется на отношения R1(A, B,) и R2( B, C).

Нормальная форма Бойса – Кодда (НФБК или усиленная 3 НФ)

НФБК учитывает функциональные зависимости, в которых участвуют потенциальные ключи, а не только первичный ключ. Отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом.

Для отношения с единственным потенциальным ключом его 3 НФ и НФБК являются эквивалентными. Для проверки принадлежности отношения к НФБК надо найти все его детерминанты и убедится в том, что они являются потенциальными ключами. Если это не так выполнить нормализацию, приняв потенциальный ключ за основной.

Пусть задан следующий отчет:

На основе этого отчета можем построить ненормализованную таблицу «Проверка»:

Для получения первой нормальной формы воспользуемся выравниванием таблицы.

Отношение «Проверка» имеет три потенциальных ключа (№ объекта, ПДата), (№ Сл., ПДата, ПВремя), (Транс., Пдата, Пвремя). В качестве первичного ключа выберем (№ объекта, Пдата). Отношение «Проверка» определим следующим образом:

Проверка(№ объекта, Пдата, Пвремя, Адрес, Коммент, № Сл., ФИО, Транс).

Построим функциональные зависимости:

Fd1: № объекта, Пдата ® Пвремя, Адрес, Коммент, № Сл., ФИО, Транс (Первичный ключ).

Fd2: № объекта ® Адрес (Частичная зависимость).

Fd3: № сл ® ФИО (Транзитивная зависимость)

Fd4: № сл, Пдата ® Транс

Fd5: Транс, Пдата, Пвремя ® № объекта, Адрес, Коммент, № Сл, ФИО (Потенциальный ключ).

Fd6: № сл, Пдата, Пвремя ® № объекта, Адрес, Коммент, ФИО (Потенциальный ключ)

Это же можно представить в виде диаграммы:

Отношение «Проверка» может быть преобразовано во вторую НФ путем удаления частичной зависимости из этого отношения путем создания двух новых отношений «Объект» и «Проверка1».

Объект(№ объекта, Адрес)

Проверка1(№ объекта, Пдата, Пвремя, Коммент, № Сл., ФИО, Транс).

Теперь проанализируем полученные отношения.

Отношение «Объект»:

№ объекта ® Адрес

Отношение «Проверка1»:

Fd1*: № объекта, Пдата ® Пвремя, Коммент, № Сл., ФИО, Транс

Fd3: № сл ® ФИО

Fd4: № сл, Пдата ® Транс

Fd5*: Транс, Пдата, Пвремя ® № объекта, Коммент, № Сл, ФИО

Fd6*: № сл, Пдата, Пвремя ® № объекта, Коммент, ФИО

Отношение «Объект» не содержит транзитивных зависимостей, следовательно, находится в третьей нормальной форме.

В отношении «Проверка1» есть транзитивная зависимость:

№ объекта, Пдата ® № Сл ® ФИО.

Транзитивная зависимость удаляется преобразованием отношения «Проверка1» в два отношения «Служащий» и «Проверка2».

Служащий(№ Сл, ФИО)

Проверка2(№ объекта, Пдата, Пвремя, Коммент, № Сл, Транс)

Проанализируем отношение «Проверка2».

Fd1**: № объекта, Пдата ® Пвремя, Коммент, № Сл., Транс

Fd4: № сл, Пдата ® Транс

Fd5**: Транс, Пдата, Пвремя ® № объекта, Коммент, № Сл

Fd6*: № сл, Пдата, Пвремя ® № объекта, Коммент

В отношении содержится детерминант № Сл, Пдата, который не является потенциальным ключом. Поэтому это отношение может страдать от аномалии обновления. Отношение «Проверка2» не находится в НФБК. Для его преобразования его в НФБК его надо разбить на два новых отношения:

Транспорт_для_сотрудника(№сл, Пдата, Транс)

Инспекция(№ объекта, Пдата, Пвремя, Коммент, № Сл).

Схема декомпозиции будет выглядеть:

Результирующие отношения имеют вид:

Объект(№ объекта, Адрес)

Служащий(№ Сл, ФИО)

Транспорт_для_сотрудника(№ сл, Пдата, Транс)

Инспекция(№ объекта, Пдата, Пвремя, Коммент, № Сл).