Нормализация БД

Формирование исходного отношения.

Проектирование БД начинается с определения всех объектов, сведения о которых будут включены в базу, и определения их атрибутов. Затем атрибуты сводятся в исходное отношение.

Пример.

ПРЕПОДАВАТЕЛЬ

ФИО	Должность	Оклад	Стаж	Д_Стаж	Каф	Предмет	Группа	Занятие
Иванов И.И.	Доцент	1 200				БД		Лекция
Иванов И.И.	Доцент	1 200				Программирование		Практ
Петров П.П.	Ст. преп.					Алгебра		Лекция
Петров П.П.	Ст. преп.					Алгебра		Практ
Петров П.П.	Ст. преп.					Высш. мат.		Практ
Сидоров С.С.	Профессор					Геометрия		Лекция
Сидоров С.С.	Профессор					Геометрия		Практ
Сидоров С.С.	Профессор					Геометрия		Лекция
Кузнецов К.К.	Ассистент					Информ.		Практ

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

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

Неявная избыточность проявляется в повторяющихся суммах оклада (при одинаковой должности) и надбавках за одинаковый стаж.

Средством исключения избыточности в отношениях (и следовательно различных аномалий) является нормализация отношений.

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

Основные виды зависимостей меду атрибутами отношений: функциональные, транзитивные и многозначные.

Атрибут B функционально зависит от атрибута A (A→B), если каждому значению A соответствует в точности одно значение B. Другими словами, во всех кортежах с одинаковым значением атрибута A атрибут B будет иметь также одно и тоже значение. Атрибуты A и B могут быть составными.

В рассматривавшемся отношении можно выделить функциональные зависимости ФИО→Каф, ФИО→Должность, Должность→Оклад и другие.

Функциональная взаимозависимость (взаимно однозначное соответствие) между A и B имеется в том случае если существуют функциональные зависимости вида A→B и B→A.

Пример.

Должность«Оклад, Стаж«Д_Стаж

Частичной зависимостью (частичной функциональной зависимостью) называется зависимость неключевого атрибута от части составного ключа.

Пример.

Атрибут Должность находится в функциональной зависимости от атрибута ФИО, являющегося частью ключа. Следовательно атрибут Должность находится в частичной зависимости от ключа отношения.

Альтернативным вариантом является полная функциональная зависимость ключевого атрибута от всего составного ключа.

Атрибут Занятие находится в полной функциональной зависимости от составного ключа.

Атрибут C зависит от атрибута A транзитивно (существует транзитивная зависимость), если для атрибутов A, B, C выполняются условия A→B и B→C, но обратная зависимость отсутствует.

Пример.

ФИО→Должность→Оклад

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

Многозначные зависимости могут быть 1:M, M:1, M:M, обозначаемые соответственно AÞB, AÜB и AÛB.

Пример.

ФИОÛПредмет.

Взаимно независимые атрибуты. Два и более атрибута называются взаимно независимыми, если ни один из этих атрибутов не является функционально зависимым от других атрибутов.

В случае двух атрибутов отсутствие зависимости атрибута A от атрибута B можно обозначить как AØ®B. Случай, когда AØ®B и BØ®A, можно обозначить AØ=B.

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

Пример. Задано отношение R со схемой R(A1, A2, A3).

A1	A2	A3

В R существуют функциональные зависимости:

A1®A2 и A2®A3.

Анализируя отношение можно установить, что существуют также зависимости:

A1®A3, A1A2®A3, A1A2A3®A1A2, A1A2®A2A3 и т.п.

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

A2Ø®A1, A3Ø®A1и т.д.

Отсутствие такого рода зависимостей объясняется тем, что одному значению атрибута A2 соответствуют разные значения атрибута A1. Т.о. имеет место многозначность, а не функциональность.

Обозначим исходное множество F=(A1®A2, A2®A3), а полное множество функциональных зависимостей F⁺=(A1®A3, A1A2®A3, A1A2A3®A1A2, A1A2®A2A3, …).

Существует 8 основных аксиом вывода ФЗ: рефлексивности, пополнения, транзитивности, расширения, продолжения, псевдотранзитивности, объединения и декомпозиции. Аксиомы обеспечивают получение всех ФЗ.

Пример. Выявим зависимости между атрибутами отношения ПРЕПОДАВАТЕЛЬ.

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

Наиболее часто выделяют следующую последовательность нормальных форм:

первая нормальная форма (1НФ);

вторая нормальная форма (2НФ);

третья нормальная форма (3НФ);

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

четвертая нормальная форма (4НФ);

пятая нормальная форма (5НФ).

Без соответствующей формализации мы определяли первые три НФ следующим образом.

Таблица в первой нормальной форме должна удовлетворять следующим требованиям.

Нет повторяющихся записей.

Отсутствие повторяющихся групп полей.

Строки (записи) не упорядочены.

Столбцы (поля) не упорядочены.

Вторая нормальная форма таблицы:

удовлетворяет условиям первой нормальной формы;

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

Понятие второй нормальной формы применимо только к таблицам имеющим составной индекс.

Третья нормальная форма таблицы:

удовлетворяет условиям второй нормальной формы;

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

Определим перечисленные НФ опираясь на понятие функциональной зависимости.

1НФ. Отношение находится в 1НФ, если все его атрибуты являются простыми (имеют единственное значение). Исходное отношение строится таким образом, чтобы оно было в 1НФ.

Перевод отношения в следующую НФ осуществляется методом «декомпозиции без потерь».

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

Пример. Исходное отношение ПРЕПОДАВАТЕЛЬ находится в 1НФ и имеет составной ключ ФИО, Предмет, Группа, День.

Атрибуты Стаж, Д_Стаж, Каф, Должность, Оклад находятся в функциональной зависимости от атрибута ФИО, являющегося частью составного ключа.

Эта частичная зависимость приводит к следующему.

В отношении присутствует явное и неявное избыточное дублирование.

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

Часть избыточности устраняется при переводе отношения в 2НФ.

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

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

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

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

В результате получим два отношения R1 (ПРЕПОДАВАТЕЛЬ (ФИО, Предмет, Группа, День, Вид) и R2 (ПРЕПОДАВАТЕЛЬ (ФИОб Должность, Оклад, Стаж, Д_Стаж, Каф).

В отношении R1 первичный ключ является составным (он аналогичен первичному ключу первоначального отношения). В отношении R2 ключ ФИО.

Исследование отношений R1 и R2 показывает, что переход к 2НФ позволил исключить явную избыточность данных в таблице R2 – повторение строк со сведениями о преподавателях. В R2 по-прежнему имеет место неявное дублирование данных. Для дальнейшего совершенствования отношения необходимо преобразовать его в 3НФ.

3НФ.

Рассмотрим два определения 3НФ.

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

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

В отношении R1 транзитивные зависимости отсутствуют.

Транзитивные зависимости отношения R2:

ФИО®Должность®Оклад;

ФИО®Оклад®Должность;

ФИО®Стаж®Д_Стаж.

Транзитивные зависимости порождают избыточное дублирование информации в отношении. Для их устранения выполним проекцию на атрибуты, являющиеся причиной транзитивных зависимостей, преобразуем отношение R2 в отношения R3 (R2(ФИО, Должность, Стаж, Каф)), R4 (R2(Должность, Оклад)), R5 (R2(Стаж, Д_Стаж)), каждое из которых находится в 3НФ.

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

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

Отношение находится в БКНФ, если оно находится в 3НФ и в нем отсутствуют зависимости ключей (атрибутов составного ключа) от неключевых атрибутов.

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

4НФ. Отношение R находится в 4НФ в том и только том случае, когда существует многозначная зависимость AÞB, а все остальные атрибуты R функционально зависят от A.

Отношение CTX.

Предмет	Преподаватель	Пособие
Физика	Иванов И.И.	Уравнения мат. физики
Физика	Иванов И.И.	Оптика
Физика	Петров П.П.	Уравнения мат. физики
Физика	Петров П.П.	Оптика
Математика	Иванов И.И.	Уравнения мат. физики
Математика	Иванов И.И.	Векторная алгебра
Математика	Иванов И.И.	Тригонометрия

Схема отношения CTX выглядит следующим образом: {Предмет: c, Преподаватель: t, Пособие: x }. Первичным ключом является вся совокупность атрибутов. Отношение CTX находится в БКНФ, поскольку является “полностью ключевым”.

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

В отношении CTX существуют две многозначные зависимости:

ПредметÞПреподаватель;

ПредметÞПособие.

В произвольном отношении R(A, B, C) могут одновременно существовать многозначные зависимости AÞB и AÞC, обозначим это обстоятельство как AÞB|C (ПредметÞПреподаватель|Пособие).

Теорема Фейджина (Fagin R.). Отношение R(A, B, C) можно спроецировать без потерь в отношения R1(A, B) и R2(A, C) в том и только том, случае, когда существует зависимость AÞB|C.

Рассматриваемое отношение можно представить в виде двух отношений CT(Предмет, Преподаватель) и CX(Предмет, Пособие).

Оба полученных отношения находятся в 4НФ и свободны от замеченных недостатков.

Задание. Соедините полученные отношенияи убедитесь в том, что в точности получится отношение CTX.

Дата добавления: 2015-05-10