Преподаватель

ФИО	Долж	Оклад	Стаж	Надб	Каф	Предм	Группа	ВидЗан
Иванов И.М.	преп	500	5	100	25	СУБД	256	Лабор
Иванов И.М.	Преп	500	5	100	25	Информ	123	Лабор
Петров М.И.	Ст.преп	800	7	100	25	СУБД	256	Лекция
Петров М.И.	Ст.преп	800	7	100	25	Графика	256	Лабор
Сидоров Н.Г.	Преп	500	10	150	25	Информ	123	Лекция
Сидоров Н.Г.	Преп	500	10	150	25	Графика	256	Лекция
Егоров В.В.	Преп	500	5	100	24	ПЭВМ	244	Лекция

Рис. 6.4. Исходное отношение ПРЕПОДАВАТЕЛЬ

Неявная избыточность проявляется в одинаковых окладах у всех преподавателей и в одинаковых надбавках к окладу за одинаковый стаж. Если оклад изменится с 500 руб. до 510руб., то это значение надо изменить у всех преподавателей. Если при этом будет пропущен Сидоров, то база станет противоречивой. Это пример аномалии редактирования отношения с неявной избыточностью.

Исключение избыточности состоит в нормализации отношений.

6.2. Метод нормальных форм

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

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

Атрибут В функционально зависит от атрибута А, если каждому значению А соответствует в точности одно значение В. Математически функциональная зависимость В от А обозначается записью А  В. Это означает, что во всех кортежах с одинаковым значением атрибута а АТРИБУТ в БУДЕТ ИМЕТЬ ТАКЖЕ ОДНО И ТО ЖЕ ЗНАЧЕНИЕ. Атрибуты А и В могут быть составными – состоять из двух и более атрибутов. В отношении Преподаватель Функциональные зависимости следующие: ФИО  Каф, ФИО  Долж, Долж  Оклад и др.

Функциональная взаимозависимость. Если существует функциональная зависимость вида А  В и В  А, то между А и В имеется взаимно однозначное соответствие, или функциональная взаимозависимость. Математически взаимозависимость обозначается как А  В или В  А.

Пример. Атрибут N (серия и номер паспорта) находится в функциональной взаимозависимости с атрибутом ФИО (фамилия, имя и отчество), если предполагается, что ситуация наличия в отношении полного совпадения фамилий, имен и отчеств у двух людей исключена.

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

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

Атрибут С зависит от атрибута А транзитивно (существует транзитивная зависимость), если для атрибутов А, В, С выполняются условия А  В и В  С, но обратная зависимость отсутствует. В примере транзитивной зависимостью связаны атрибуты:

ФИО  Долж  Оклад

В отношении R атрибут В многозначно зависит от атрибута А, если каждому значению А соответствует множество значений В, не связанных с другими атрибутами из R. Многозначные зависимости могут быть «один ко многим» (1:М), «многие к одному» (М:1) или «многие ко многим» (М:М), Обозначаемые соответственно: А  В, А  В и А  В.

В рассматриваемом примере имеется многозначная зависимость М:М между атрибутами ФИО  Предмет (один преподаватель может вести несколько предметов и один предмет могут вести несколько преподавателей).

Поскольку зависимость между атрибутами является причиной аномалий, то стараются такие отношения разделить на несколько отношений. В результате образуется совокупность связанных отношений (таблиц) со связями вида 1:1, 1:М, М:1 и М:М. Связи между таблицами отражают зависимости между атрибутами различных отношений.

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

Выявление зависимостей между атрибутами. Выявление зависимостей между атрибутами необходимо для выполнения проектирования базы данных методом нормальных форм.

Пример. Пусть задано отношение R со схемой R(А1, А2, А3) вида:

А1	А2	А3
12	21	34
17	21	34
11	24	33
13	25	31
15	23	35
14	22	32

Априори известно, сто существуют функциональные зависимости:

А1А2 и А2А3.

Из анализа видно, что в отношении существуют еще зависимости:

А1А3, А1А2А3, А1А2А3А1А2, А1А2А2А3 и т.п..

В отношении отсутствует функциональная зависимость атрибута А1 от атрибута А2 и от атрибута А3, т.е.

А2  А1, А3  А1.

Отсутствие зависимости А1 от А2 объясняется тем, что одному и тому же значению атрибута А2 (21) соответствуют разные значения атрибута А1 (12 и 17).

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

В отношении Преподаватель можно вывести следующие функциональные зависимости:

А) Б)

ФИО  Оклад

ФИО  Долж

ФИО  Стаж

ФИО  Надб

ФИО  Каф

Стаж  Надб

Долж  Оклад

Оклад  Долж

ФИО. Предм. Группа  Оклад

Рис. 6.5. Зависимости между атрибутами.

Предполагается, что один преподаватель в одной группе может проводить один вид занятий (лекции или лабораторные работы). ФИО – уникальны. Имеется зависимость ФИО  Стаж, а обратное утверждение не верно, т.к. одинаковый стаж имеют несколько преподавателей. Относительно других зависимостей рассуждения аналогичны. Между должностью и окладом устанавливается взаимно однозначная зависимость.

Один преподаватель в одной группе по разным предметам может проводить разные виды занятий. Определение ВидаЗанятий связано с указанием ФИО, Предмета и Группы. Действительно, Петров М.И. в 256-й группе читает лекции и проводит лабораторные занятия, но лекции читает по СУБД, а лабораторные работы по Графике.

Зависимости между атрибутами ФИО, Предмет и Группа не выведены, т.к. они образуют составной ключ и не учитываются в процессе нормализации отношения (таблицы).

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

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

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

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

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

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

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

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

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

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

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

Пример. Пусть в отношении R(A,B,C,D,E,…) имеется функциональная зависимость С  D. Декомпозиция отношения R на два новых отношения R1(A, B,C,E,…) и R2(C,D) устранит функциональную зависимость атрибутов и переведет отношение R в следующую нормальную форму. Отношение R2 является проекцией отношения R на атрибуты C и D.

Исходное отношение Преподаватель имеет составной ключ ФИО, Предм, Группа и находится в 1НФ. Атрибуты Стаж, Надб, Каф, Долж, Оклад находятся в функциональной зависимости от части составного ключа – атрибута ФИО. Эта частичная зависимость приводит к явной и неявной избыточности данных, что создает проблемы их редактирования. Часть избыточности устраняется при переводе отношения во 2НФ.

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

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

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

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

Переведем отношение Преподаватель во 2НФ. В результате получим два отношения R1 и R2.

А) Б)

R 1

ФИО	Предм	Группа	ВидЗан
Иванов И.М.	СУБД	256	Лабор
Иванов И.М.	Информ	123	Лабор
Петров М.И.	СУБД	256	Лекция
Петров М.И.	Графика	256	Лабор
Сидоров Н.Г.	Информ	123	Лекция
Сидоров Н.Г.	Графика	256	Лекция
Егоров В.В.	ПЭВМ	244	Лекция

R2

ФИО	Долж	Оклад	Стаж	Надб	Каф
Иванов И.М.	Преп	500	5	100	25
Петров М.И.	Ст.преп	800	7	100	25
Сидоров Н.Г.	Преп	500	10	150	25
Егоров В.В.	Преп	500	5	100	24

Рис. 6.6. Отношения базы данных ПРЕПОДАВАТЕЛЬ во 2 НФ

В отношении R1 первичный ключ составной ФИО, Предм, Группа , в отношении R2 ключ – ФИО. В результате исключена явная избыточность данных о преподавателях. В R2 по-прежнему имеет место неявное дублирование данных.

Для дальнейшего совершенствования переведем отношения в 3НФ.

Третья нормальная форма.

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

Существует и альтернативное определение.

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

В рассматриваемом примере в отношении R1 отсутствуют транзитивные зависимости, а в отношении R2 они есть:

ФИО  Долж  Оклад,

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

ФИО  Стаж  Надб

Устраним транзитивные зависимости, преобразуя отношение R2 в три отношения R3, R4 и R5, каждое из которых находится в 3НФ.

А) Б)

R 3

ФИО	Долж	Стаж	Каф
Иванов И.М.	Преп	5	25
Петров М.И.	Ст.преп	7	25
Сидоров Н.Г.	Преп	10	25
Егоров В.В.	Преп	5	24

R4

Долж	О клад
Преп	500
Ст.преп	800

R5

Стаж	Н адб
5	100
7	100
10	150

Рис. 6.7. Отношения базы данных в 3НФ

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

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

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

Четвертая нормальная форма.

Рассмотрим отношение ПРОЕКТЫ:

Номер_проекта	Код_сотрудника	Задание_сотрудника
001	05	1
001	05	2
001	05	3
004	02	1
004	02	2
004	03	1
004	03	2
004	05	1
004	05	2
007	06	1

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

Недостаток отношения ПРОЕКТЫ состоит в том, что при подключении/отстранении от проекта некоторого сотрудника приходится добавлять/исключать из отношения столько кортежей, сколько заданий имеется в проекте.

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

Номер_проекта  Код_сотрудника

Номер проекта Задание_сотрудника.

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

Дальнейшая нормализация отношений, типа ПРОЕКТЫ, лсновывается на следующей теореме.

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

Под проецированием без потерь здесь понимается такой способ декомпозиции отношения, при котором оно полностью и без избыточности восстанавливается путем естественного соединения полученных отношений. Пример. Пусть имеется простейшее отношение R(A,B,C) вида:

R R1 R2

А	В	С		А	В		А	С
К	15	1		К	15		К	1
К	15	2		Л	10		К	2
Л	10	1		М	20		Л	1
М	20	1					М	1
М	20	2					М	2
М	20	3					М	3

Отношения R1 и R2 – проекции на атрибуты А, В и А, С.

Результатом операции соединения бинарных отношений R1(A,B) и R2(A,C) по атрибуту А является тернарное отношение с атрибутами A, B иC, кортежи которого получаются путем связывания отношений R1 и R2 по типу 1:М на основе совпадения значений атрибута А. Порожденное таким образом отношение будет в точности совпадать с исходным.

Определение четвертой нормальной формы. Отношение R находится в четвертой нормальной форме (4НФ) в том и только в том случае, когда существует многозначная зависимость А  В, а все остальные атрибуты R функционально зависят от А.

Отношение ПРЕКТЫ можно представить в виде двух отношений: ПРОЕКТЫ-СОТРУДНИКИ и ПРОЕКТЫ-ЗАДАНИЯ:

ПРОЕКТЫ-СОТРУДНИКИ (первичный ключ – оба атрибута)

Номер_проекта	Код_сотрудника
001	05
004	02
004	03
004	05
007	06

ПРОЕКТЫ- ЗАДАНИЯ (первичный ключ – оба атрибута)

Номер_проекта	Задание_сотрудника
001	1
001	2
001	3
004	1
004	2
007	1

Оба полученных отношения находятся в 4НФ, нет дублирования значений кодов сотрудников. Соединение этих проектов приведет к получению исходного отношения ПРОЕКТЫ.

В общем случае не всякое отношение можно восстановить после такого проецирования. Восстановление возможно потому, что каждый сотрудник, участвующий в некотором проекте, выполнял все задания по этому проекту (принцип 1:М), а связь между сотрудниками и проектами М:М.

Пятая нормальная форма.

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

Рассмотрим отношение СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ ВИДА:

Код_сотрудника	Код_отдела	Номер проекта
01	РД	036
02	АД	004
03	УП	004
04	АД	019
05	ЛС	001
05	ЛС	004
06	УП	007
08	ВЦ	013
09	ВЦ	014
10	СЖ	013

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

Определение. Отношение R(X,Y,…,Z) удовлетворяет зависимости соединения, которую обозначим как *(X,Y,…,Z), в том и только в том случае, если R восстанавливается без потерь путем соединения своих проекций на X, Y, …, Z. Зависимость соединения является обобщением функциональной и многозначной зависимостей.

Определение пятой нормальной формы. Отношение R находится в 5НФ (или нормальной форме проекции-соединения – PJ/NF) в том и только том случае, когда любая зависимость соединения в R следует из существования некоторого возможного ключа в R.

Образуем составные атрибуты отношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ:

СО = {Код_сотрудника, Код_отдела }

СП = {Код_сотрудника, Номер_проекта}

ОП = {Код_отдела, Номер_проекта}

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

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

Пусть имеем составные атрибуты СОТРУДНИКИ-ОТДЕЛЫ, СОТРУДНИКИ-ПРОЕКТЫ и ОТДЕЛЫ-ПРОЕКТЫ, полученные проецированием исходного отношения СОТРУДНИКИ-ОТДЕЛЫ-ПРОЕКТЫ.

СОТРУДНИКИ-ОТДЕЛЫ СОТРУДНИКИ-ПРОЕКТЫ ОТДЕЛЫ-ПРОЕКТЫ

Код_ сотрудника	Код_ отдела		Код_ сотрудника	Номер проекта		Код_ отдела	Номер проекта
01	РД		01	036		РД	036
02	АД		02	004		АД	004
03	УП		03	004		УП	004
04	АД		04	019		АД	019
05	ЛС		05	001		ЛС	001
05	ЛС		05	004		ЛС	004
06	УП		06	007		УП	007
08	ВЦ		08	013		ВЦ	013
09	ВЦ		09	014		ВЦ	014
10	СЖ		10	013		СЖ	013

Попарные соединения полученных трех отношений будут иметь вид:

*(СО, СП)

Код_сотрудника	Код_отдела	Код_проекта
01	РД	036
02	АД	004
03	УП	004
04	АД	019
05	ЛС	001
05	ЛС	004
06	УП	007
08	ВЦ	013
09	ВЦ	014
10	СЖ	013

*(СО, ОП) *(СП, ОП)

Код_ сотрудника	Код_ Отдела	Номер_ проекта		Код_ Сотрудника	Код_ отдела	Номер_ проекта
01	РД	036		01	РД	036
02	АД	004		02	АД	004
02	АД	019		02	ЛС	004
03	УП	004		02	УП	004
03	УП	007		03	АД	004
04	АД	004		03	ЛС	004
04	АД	019		03	УП	004
05	ЛС	001		04	АД	019
05	ЛС	004		05	ЛС	001
06	УП	004		05	АД	004
06	УП	007		05	ЛС	004
08	ВЦ	013		05	УП	004
08	ВЦ	014		06	УП	004
09	ВЦ	013		06	УП	007
09	ВЦ	014		08	ВЦ	013
10	СЖ	013		08	ВЦ	014
				09	ВЦ	013
				09	ВЦ	014
				10	СЖ	013

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

Отношения СОТРУДНИКИ-ОТДЕЛЫ, СОТРУДНИКИ-ПРОЕКТЫ и ОТДЕЛЫ-ПРОЕКТЫ находятся в 5НФ.

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

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

• Частичных зависимостей неключевых атрибутов от ключа (удовлетворение требований 2НФ);

• Транзитивных зависимостей неключевых атрибутов от ключа (удовлетворение требований 3НФ);

• Зависимости ключей (атрибутов составных ключей)от неключевых атрибутов (удовлетворение требований БКНФ).

Кроме метода нормальных форм Кодда, для проектирования базы данных применяют и другие методы, например, метод ER-диаграмм (метод «сущность-связь»). Этот метод используется при проектировании больших баз данных. На последнем этапе метода ER-диаграмм отношения, полученные в результате проектирования, проверяются на принадлежность их к БКНФ. После завершения проектирования создается база данных с помощью СУБД.

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