4. Проектирование реляционных баз данных. Теория нормализации. [3. C.104-117, 18 – тема 5]

Процесс проектирования БД представляет собой последовательность переходов от неформального словесного описания информационной структуры предметной области к формализованному описанию объектов предметной области в терминах некоторой формальной модели. В общем случае можно выделить следующие этапы проектирования:

• словесное описание информационных объектов предметной области;

• проектирование инфологической модели предметной области — частично формализованное описание объектов предметной области в терминах некоторой инфологической модели, например в терминах ER (Entity RelationShip)-модели;

• даталогическое или логическое проектирование БД, т. е. описание БД в терминах принятой даталогической модели данных;

• физическое проектирование БД, т. е. выбор эффективного размещения БД на внешних носителях для обеспечения наиболее эффективной работы приложения.

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

Корректной схемой БД называется схема БД, в которой отсутствуют нежелательные функциональные зависимости.

Процесс разработки корректной схемы реляционной БД называется логическим проектированием БД. 

Проектирование схемы БД может быть выполнено двумя путями:

• путем декомпозиции (разбиения), когда исходное множество отношений, входящих в схему БД заменяется другим множеством отношений (число их при этом возрастает), являющихся проекциями исходных отношений;

• путем синтеза, т. е. компоновки из заданных исходных элементарных зависимостей схемы БД. 

В теории реляционных баз данных выделяют 6 нормальных форм, которые имеют специальные названия:

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

• вторая нормальная форма (2NF);

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

• нормальная форма Бойса–Кодда (BCNF);

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

• пятая нормальная форма, или форма проекции-соединения (5NF или PJNF).

Функциональной зависимостью набора атрибутов В отношения R от набора атрибутов A того же отношения, обозначаемой как

R.A -> R.B или A -> B,

называется такое соотношение проекций R[A] и R[B], при котором в каждый момент времени любому элементу проекции R[A] соответствует только один элемент проекции R[B], входящий вместе с ним в какой либо кортеж отношения R. Функциональная зависимость R.A -> R.B называется полной, если набор атрибутов B функционально зависит от A и не зависит функционально от любого подмножества A, т. е. R.A -> R.B называется полной, если , что читается следующим образом: для любого A1, являющегося подмножеством А, R.B функционально не зависит от R.A1, в противном случае зависимость R.A -> R.B называется неполной.

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

Соответственно ненормализованные отношения, могут интерпретироваться как таблицы с неравномерным заполнением, например таблица «Расписание», которая имеет следующий вид:

                                                                                                       Расписание

Преподаватель	День  недели	Номер  пары	Название дисциплины	Тип занятий	Группа
Петров В.И	Понед.  Вторник  Вторник	1  1  2	Теор.выч. проц.  Комп. графика Комп. графика	Лекция  Лаб.раб   Лаб.раб	4906  4907  4906
Киров В.А.	Понед.  Вторник  Вторник	2  3  4	Теор.информ.  Пр-е на С++   Пр-е на С++	Лекция  Лаб.раб  Лаб.раб	4906  4907  4906
Минин А.А.	Понед.  Среда  Четверг	3  3  4	Защита инф.  Пр-е на VB  Пр-е на VB	Лекция  Лаб.раб  Лаб.раб	4944  4942  4922

 

Для приведения отношения «Расписание» к 1-й нормальной форме необходимо дополнить каждую строку фамилией преподавателя.

                                                                                                       Расписание

Преподаватель	День  недели	Номер  пары	Название дисциплины	Тип занятий	Группа
Петров В.И  Петров В.И  Петров В.И	Понед.  Вторник  Вторник	1  1  2	Теор.выч. проц.  Комп. графика  Комп. графика	Лекция   Лаб.раб  Лаб.раб	4906  4907  4906
Киров В.А.  Киров В.А.  Киров В.А.	Понед. Вторник Вторник	2  3  4	Теор.информ.  Пр-е на С++   Пр-е на С++	Лекция  Лаб.раб  Лаб.раб	4906  4907  4906
Минин А.А.  Минин А.А.  Минин А.А.	Понед. Среда Четверг	3  3  4	Защита инф.  Пр-е на VB   Пр-е на VB	Лекция  Лаб.раб  Лаб.раб	4944  4942  4922

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

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

R<ФИО, Номер зач.кн., Группа, Дисциплина, оценка>

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

Номер зач. кн.-> Группа

Номер зач. кн.->ФИО

И в этом случае для приведения ко 2-й нормальной форме надо разбить исходное отношение на 2 со следующими схемами:

R1<ФИО,Номер.зач.кн.,Группа>

R2<Номер зач.кн.,Дисциплина,Оценка>

3. Отношение находится в 3-й нормальной форме тогда и только тогда, когда оно находится во 2-й нормальной форме и не содержит транзитивных зависимостей.

Рассмотрим отношение, соответствующее описанию студента в некотором вузе.

R<ФИО,Номер.зач.кн.,Группа,Факультет,Специальность,Выпускающая кафедра>.

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

Номер.зач.кн. -> ФИО

Номер.зач.кн. -> Группа

Номер.зач.кн. -> Факультет

Номер.зач.кн. -> Специальность

Номер.зач.кн. -> Выпускающая кафедра

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

Группа -> Факультет

Группа -> Специальность

Группа -> Выпускающая кафедра

Выпускающая кафедра -> Факультет

И эти зависимости образуют транзитивные группы зависимостей. Чтобы избежать этого, мы можем предложить следующий набор отношений:

R1<Номер.зач.кн.,ФИО,Специальность,Группа>

R2<Группа,Выпускающая кафедра)>

R3(Выпускащая кафедра,Факультет)

4. Отношение находится в нормальной форме Бойса–Кодда, если оно находится в 3-й нормальной форме и каждый детерминант отношения является возможным ключом отношения.

Отношение, которое моделирует сдачу текущей сессии имеет следующую структуру:

<ФИО, Номер зач.кн., Идентификатор студента, Дисциплина, Дата, Оценка>

Если считать, что «Номер зач. кн.» и «Идентификатор студента» однозначно характеризуют его, то мы имеем два возможных ключа:

Идентификатор студента, Дисциплина

Номер зач.кн., Дисциплина

Кроме того, у нас существует 2 тривиальные функциональные зависимости:

Номер зач.кн.-> ФИО

Идентификатор-> ФИО

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

R1<Номер зач.кн.,ФИО>

R2<Идентификатор, Номер зач.кн.>

R3<Идентификатор, Дисциплина, Дата, Оценка>

Нормальные формы высших порядков связаны с наличием многозначных зависимостей. Многозначные зависимости, обозначаемые как A->>B, — это устойчивые соотношения между значениями атрибутов A и B, когда одному значению атрибута A соответствует некоторое устойчивое множество значений атрибута B. 

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

Имеем отношение «Планирование занятий»

Студент	Группа	Предмет	Номер лабораторной
Иванов	121	БД	ЛР-1
Иванов	121	БД	ЛР-2
Иванов	121	Сети	ЛР-1
Иванов	121	Сети	ЛР-2
Иванов	121	Сети	ЛР-2
Петров	122	БД	ЛР-1
Петров	122	БД	ЛР-2
Петров	122	ОС	ЛР-1
Петров	122	ОС	ЛР-2

 

В этом отношении 2 многозначных функциональных зависимости:

Группа ->> Предмет

Предмет->> Номер лабораторной работы.

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

Группы

Студент	Группа
Иванов	121
Петров	122

Учебный план

Группа	Предмет
121	БД
121	Сети
122	БД
122	ОС

Практика

Предмет	Номер лабораторной
БД	ЛР-1
БД	ЛР-2
Сети	ЛР-1
Сети	ЛР-2
Сети	ЛР-3
ОС	ЛР-1
ОС	ЛР-2

 

Теперь в каждом отношении у нас присутствует только одна многозначная зависимость, поэтому можно утверждать, что отношение находится в 4-й нормальной форме.

Декомпозиция отношения R на проекции R1=R[X,Y] и R2=R[X,Z] будет декомпозицией без потерь тогда и только тогда, когда имеется многозначная зависимость X->>Y|Z.

5. Отношение R находится в 4-й нормальной форме тогда и только тогда, когда отношение находится в нормальной форме Бойса–Кодда и не содержит нетривиальных многозначных зависимостей.

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

R

X	Y	Z
1	1	2
1	2	1
2	1	1
1	1	1

R[X,Y]

X	Y
1	1
1	2
2	1

R[X,Z]

X	Z
1	2

R[Y,Z]

Y	Z
1	2
2	1
1	1

 

Как легко заметить, отношение R не восстанавливается ни по одному из попарных соединений R₁JOIN R₂, R₁JOIN R₃ или R₂JOIN R₃. Действительно, соединение R₁JOIN R₂ имеет следующий вид.

 

X	Y	Z
1	1	2
1	1	1
1	2	2
1	2	1
2	1	1

 

Можно предположить, что отношение R удовлетворяет следующей зависимости соединения: *(XY,XZ,YZ).

6. Отношение R не находится в 5-й нормальной форме, если в отношении найдется нетривиальная зависимость соединения.

Отношение R находится в 5-й нормальной форме тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.

В нашем случае набор из трех проекций и соответствует 5-й нормальной форме отношения R.