 |
Проектирование реляционных БД с использованием нормализации
|
|
|
|
Избыточность данных, аномалии обновления
Каждый разработчик при проектировании БД преследует основную цель – сгруппировать атрибуты в отношении таким образом, чтобы минимизировать избыточность данных.
Пример: Требуется создать БД для хранения информации об итогах текущей сессии на некотором факультете. В БД нужно хранить:
1. ФИО студента.
2. № группы.
3. Название предмета.
4. ФИО преподавателя.
5. Должность преподавателя.
6. Оценка.
Пусть заданы следующие ограничения на предметную область:
1. ФИО студента уникально.
2. В одной группе учится произвольное количество студентов. Конкретному студенту относится свой № группы.
3. ФИО преподавателя уникально.
4. Преподаватель может занимать только одну должность.
5. Преподаватель может принимать экзамен по нескольким дисциплинам.
Пусть вся информация хранится в одном отношении.
| ФИО студента | № группы | Предмет | ФИО преподавателя | Должность преподавателя |
| Иванов | ТОЭ | Зуб | Доцент | |
| Иванов | ВМ | Ильин | Доцент | |
| … | … | … | … | … |
| Петров | ТОЭ | Зуб | Доцент | |
| Петров | ВМ | Ильин | Доцент | |
| … | … | … | … | … |
PK=ФИО студента+Предмет
В отношениях с избыточность возникают проблемы, которые называются аномалиями обновления. Такие аномалии проявляются при операциях, изменяющих состояние таблицы.
Различают следующие виды аномалий:
1. Аномалии вставки.
2. Аномалии удаления.
3. Аномалии изменения.
Причина аномалий – избыточность данных, порождённая тем, что в отношении хранится разнородная информация.
Устранить аномалии можно выполнив нормализацию отношений.
Нормализация отношений – это формальный метод анализа отношений на основе первичных или потенциальных ключей и существующих зависимостей между аномалиями.
|
|
|
Основные определения
Будет рассмотрен классический подход, при котором весь процесс проектирования производится путём последовательных приближений от исходного отношения к удовлетворительному в определенном смысле набору отношений.
На каждом шаге проектирования с помощью нормализации получается набор отношений в одной из нормальных форм, обладающий лучшими свойствами, чем предыдущий набор. Каждой нормальной форме соответствует определённый набор ограничений. Отношение находится в некоторой нормальной форме, если оно удовлетворяет свойственному этой форме набору ограничений.
Нормальные формы отношений основываются на понятии функциональной зависимости.
Функциональная зависимость
Атрибут у функционально зависит от атрибута х, X→Y в том и только в том случае, если каждому значению x соответствует в точности одно связанное значение у. Значение у связано со значением х в том смысле, что должно входить со значением х в какой-либо кортеж отношения.
Функциональную зависимость можно выявить исходя из базовых свойств самих атрибутов путём логического анализа.
Определение: Функциональную зависимость можно интерпретировать следующим образом.
Если в отношении, удовлетворяющем функциональной зависимости X→Y имеется 2 кортежа s и t с одинаковыми x значениями, причём s(x)=t(x), то обязательно должно выполняться и s(x)=t(x).
Такая интерпретация определения функциональной зависимости (ФЗ) является основой алгоритма проверки наличия ФЗ в отношении:
1. Пересортировать отношение к по x столбцам так, чтобы кортежи с одинаковыми х значениями оказались рядом.
2. Если какая-либо совокупность кортежей с одинаковыми х значениями имеют одинаковые у значения, то алгоритм возвращает значение истина, ложь в противном случае.
Рассмотрим отношение, в котором для простоты будем считать, что у каждого из студентов уникальная фамилия.
|
|
|
Студент (Группа, Фамилия, Пол, Факультет, Кафедра, Куратор)
| Группа | Фамилия | Пол | Факультет | Кафедра | Куратор |
| Балашов | М | ФВТ | ЭВМ | Байков | |
| Катеринченко | М | ФВТ | ЭВМ | Сарычев | |
| Кольцова | Ж | ФВТ | САПР ВС | Телков | |
| Малин | М | ФВТ | АТ | Фёдоров | |
| Никулин | М | ФВТ | ЭВМ | Сарычев | |
| Чертов | М | ФВТ | ЭВМ | Терёхин |
Наложены ограничения (бизнес-правила):
1. Каждому студенту соответствует 1 конкретный половой признак.
2. Каждый студент обучается только в одной группе.
3. Каждой группе прикреплён 1 куратор.
4. Каждая группа относится к одному факультету.
5. Каждая группа относится к конкретной кафедре.
6. Каждая кафедра относится к конкретному факультету.
7. Каждый куратор работает на определённой кафедре.
На основе наложенных ограничений можно сформировать следующие ФЗ:
1. Атрибут пол функционально зависит от атрибута студент.
2. Атрибут группа функционально зависит от атрибута студент.
3. Атрибут куратор функционально зависит от атрибута группа.
4. Атрибут факультет функционально зависит от атрибута группа.
5. Атрибут кафедра функционально зависит от атрибута группа.
6. Атрибут факультет функционально зависит от атрибута кафедра.
7. Атрибут кафедра функционально зависит от атрибута куратор.
Можно дать и другое понятие функциональной зависимости. Для Рассматриваемых 7 зависимостей описание примет следующий вид:
1. Студент функционально определяет атрибут пол.
2. Студент функционально определяет атрибут группа.
3. Группа функционально определяет атрибут куратор.
4. Группа функционально определяет атрибут факультет.
5. Группа функционально определяет атрибут кафедра.
6. Кафедра функционально определяет атрибут факультет.
7. Куратор функционально определяет атрибут кафедра.
Символьная запись функциональных зависимостей:
1. Студент → пол.
2. Студент → группа.
3. Группа → куратор.
4. Группа → факультет.
5. Группа → кафедра.
6. Кафедра → факультет.
7. Куратор → кафедра.
Составной атрибут – это набор атрибутов. Детерминант – левая часть функциональной зависимости.
Полная функциональная зависимость – функциональна зависимость вида X→Y называется полной, если атрибут Y не зависит функционально от любого подмножества X, если X – составной атрибут.
|
|
|
Транзитивная функциональная зависимость – ФЗ X→Y называется транзитивной, если существует такой атрибут Z, что
1. Имеется ФЗ X→Z.
2. Имеется ФЗ Z→Y.
3. Отсутствует ФЗ Z→X.
4. Z не является подмножеством X.
5. Z не включает в себя Y.
Потенциальный ключ – это атрибут или множество атрибутов, которые в данном отношении могут однозначно (функционально полно) идентифицировать (определить) значение всех остальных атрибутов.
Потенциальный ключ – набор атрибутов, однозначно определяющий кортеж отношения.
Первичный ключ – один из потенциальных ключей, назначенных в качестве первичного.
Внешний ключ – атрибут отношения R2, совпадающий с первичным (в общем случае потенциальным) ключом в отношении R1.
Ключевой атрибут – атрибут, входящий в состав ключа.
Неключевой атрибут – атрибут отношения, не входящий в состав ни одного из потенциальных ключей (в частности первичного).
Последовательность нормальных форм
Существует несколько нормальных форм (последовательность нормальных форм, которые одна от другой отличаются тем, что каждая последующая лучше позволяет исключить избыточное дублирование данных). Обычно выделяют следующую последовательность нормальных форм:
1. Первая нормальная форма.
2. Вторая нормальная форма.
3. Третья нормальная форма.
4. Нормальная форма Бойса-Кодда.
5. Четвёртая нормальная форма.
6. Пятая нормальная форма.
7. Доменно-ключевая нормальная форма.
Основные свойства нормальных форм:
1. Каждая следующая НФ более устойчива к аномалиям обновлений (модификации).
2. При переходе к следующей НФ свойства предыдущих НФ сохраняются.
Получение нормальных форм
В основе проектирования БД лежит декомпозиция отношения, находящегося в нормализованной форме на 2 или более отношения, удовлетворяющим ограничениям, содержащим НФ.
1. При разбиении исходной таблицы на несколько надо позаботиться о возможности в будущем соединить эту таблицу в одну. Поэтому надо добавлять во вновь сформированные таблицы новые атрибуты.
|
|
|
2. БД находится в определённой нормальной форме, если все её таблицы находятся в этой форме. Иначе принадлежность БД к НФ будет определяться по самому слабому её звену.
Первая НФ
Состояние БД до первой НФ называется ненормализованной формой. Ненормализованная форма (ННФ) представляет собой таблицу, состоящую из одной или нескольких повторяющихся групп данных.
Для первой нормальной формы все атрибуты отношений должны быть атомарны, неделимы с точки зрения СУБД. То есть на пересечении каждой строки и столбца должны находится элементарные неделимые значения атрибутов.
Значения в доменах не должны представлять собой списки, множества простых и сложных значений.
Определение атомарности не всегда происходит легко, так как в разных случаях одни и те же атрибуты могут рассматриваться как атомарные, так и как делимые. При определении свойства атомарности следует определить, будут ли значения использоваться по отдельности или нет.
Пример:
Рождение (Имя, Дата)
Илья, 4 сентября 1984 г.
Павел, 3 января 1980 г.
Если данное отношение будет обрабатываться таким образом, что отдельно будет обрабатываться день, месяц и год рождения, то дату следует разбить на части и привести к 1 НФ.
Рождение (Имя, День. Месяц, Год)
Можно выделить 2 основные причины для приведения к 1 НФ:
1. Только 1 НФ позволяет представлять ФЗ с данной степенью детализации.
2. В неприведённых к 1 НФ отношениях могут возникать трудности при изменении данных.
Вторая НФ
Если первая нормальная форма представлялась необходимой для представления ограничений, накладываемых на данные в реляционной модели данных, то последующие нормальные формы- результат попыток избавиться от аномалий в работе и избыточности данных. Попробуем рассмотреть более подробно отношение расписание (таблица ниже):
| Расписание | Специальность | Предмет | Группа | Лектор |
| Физика | Гущин | |||
| Химия | Пронин | |||
| Физика | Гущин | |||
| Химия | Пронин | |||
| Химия | Никитин |
Ключом данного отношения является составной атрибут(ГРУППА, ПРЕДМЕТ), кроме того, в отношении выполняется F-зависимость ГРУППА→СПЕЦИАЛЬНОСТЬ. Отношение обладает рядом нежелательных свойств:
1. Операция удаления кортежа<расписание;ГРУППА=742, ПРЕДМЕТ=<<химия> приводит к потере информации о том что группа 742 обучается по специальности.
2. Отношение не содержит информации о принадлежности к специальностям групп, расписание для которых еще не составлено (лектор не назначен).
|
|
|
3. Для групп 740 и741 дублируется информация о их принадлежности к соответствующим специальностям.
Все приведенные недостатки будут устранены, если провести декомпозицию отношения расписание на два отношения предметы и специальности следующим образом:
| предметы | (Группа | Предмет | Лектор) |
| Физика | Гущин | ||
| Химия | Пронин | ||
| Физика | Гущин | ||
| Химия | Пронин | ||
| Химия | Никитин | ||
| Специальности | (Группа | Специальность) | |
Для второй нормальной форме (2НФ) должна обеспечиваться 1НФ и каждый неключевой атрибут должен функционально полно зависеть от первичного ключа.
Полная функциональная зависимость (неключевого атрибута от ключа) означает, что если ключ составной, то любой неключевой атрибут зависит от всего ключа и не зависит ни от какой его части.
Алгоритм приведения ко второй НФ:
1. Выявить все ФЗ.
2. Если имеются ФЗ между неключевым атрибутом и частью составного ключа, то
а) те неключевые атрибуты, которые зависят от части ключа, выносятся в отдельное отношение. Первичном ключом нового отношения будет часть составного ключа, входящего в ФЗ.
б) в исходном отношении остаются все неключевые атрибуты.
Исходное отношение расписание не находится во второй нормальной форме из-за того, что атрибут СПЕЦИАЛЬНОСТЬ функционально неполно зависит от ключа К=ГРУППА ПРЕДМЕТ, поскольку имеется зависимость ГРУППА → СПЕЦИАЛЬНОСТЬ, а атрибут ГРУППА есть подмножество ключа (ГРУППА ПРЕДМЕТ).
Отношения предметы и специальности оба во второй нормальной форме и следовательно схема базы данных, состоящей из двух таблиц – предметы и специальности – тоже находится во второй нормальной форме.
Пример: рассмотрим отношение, моделирующее сдачу студентом текущей сессии. Схема этого отношения определяется следующим набором атрибутов:
(Ф.И.О,Номер зач. КН.,Группа, Дисциплина, Оценка).
Так как каждый студент сдает целый набор дисциплин в процессе сессии, то первичным ключом отношения может быть (Номер зач. Кн.,Дисциплина), который однозначно определяет каждую строку отношения. С другой стороны, атрибуты ФИО и Группа зависят только от части первичного ключа – от значения атрибута Номер зач. КН., поэтому в отношении имеются неполные функциональные зависимости.
Какие аномалии или неудобства могут возникнуть, если мы оставим исходное отношение и не будем его разбивать на два?
Возможны по крайней мере три вида аномалий: при добавлении записей, при обновлении записей, при удалении записей:
1) Невозможно занести в базу данных информацию (строки) о студентах, которые еще не сдавали ни одной дисциплины, т.к. первичный ключ не может содержать неопределенное значение (атрибут Дисциплина является частью первичного ключа и предпологается, что название дисциплины вводится в базу вместе с оценкой, полученной по этой дисциплине, лишь после получения этой оценки).
2) Рассмотрим ситуацию, когда студент переведен из одной группы в другую. Тогда в первом случае из-за дублирования информации (если мы не разбивали исходное отношение на два) мы должны найти все записи с данным студентом и в них изменить значение атрибута Группа на новое.
3) Если студент сдавал лишь одну дисциплину, то при удалении кортежа,содержащего ненужное (пересданное) значение оценки, теряется вся информация и о самом студенте.
Для приведения данного отношения ко второй нормальной форме следует разбить его на проекции. Такими проекциями могут быть два отношения:
(Номер зач кн.ФИО, Группа)
(Номер зач. КН., Дисциплина, Оценка)
Этот набор отношений не содержит неполных функциональных зависимостей, и поэтому эти отношения находятся во второй нормальной форме.
Третья НФ
Для третьей нормальной формы (3НФ) отношение должно находиться во второй нормальной форме, а также каждый неключевой атрибут должен нетранзитивно зависеть только от первичного ключа, проще говоря: должны отсутствовать функциональные зависимости между неключевыми атрибутами.
Рассмотрим теперь отношение лекторы (), имеющее первичный ключ = ЛЕКТОР, удовлетворяющее F-зависимостям ЛЕКТОР---КАФЕДРА и КАФЕДРА--- ФАКУЛЬТЕТ и находящееся во второй нормальной форме (ключ не является составным), но, несмотря на это, обладающее рядом нежелательных свойсв.
| Лекторы | (Лектор | Кафедра | Факультет) |
| Кузьмин | ЭВМ | ФВТ | |
| Логинов | ЭВМ | ФВТ | |
| Скворцов | САПР ВС | ФВТ | |
| Терёхин | ВПМ | ФВТ | |
| Шумов | ТОР | РТФ |
Приведем эти свойства:
1. Содержится избыточная информация о принадлежности кафедры факультету.
2. Не имеется возможности хранить информацию о принадлежности к определенным факультетам кафедр, для преподавателей которых нет ни одной записи в отношении лекторы.
3. При удалении записи DEL (лекторы; ЛЕКТОР = <<Шумов>>) пропадает полностью информация о принадлежности кафедры ТОР к РТФ.
Все эти проблемы решаются после декомпозиции отношения на пару --- преподаватели и кафедры.
| Преподаватели | (Лектор | Кафедра) |
| Кузьмин | ЭВМ | |
| Логинов | ЭВМ | |
| Скворцов | САПР ВС | |
| Терехин | ВПМ | |
| Шумов | ТОР | |
| Кафедры | (Кафедра | Факультет) |
| ЭВМ | ФВТ | |
| САПР ВС | ФВТ | |
| ВПМ | ФВТ | |
| ТОР | РТФ |
Для рассмотренного ранее отношения со схемой R= ЛЕКТОР КАФЕДРА ФАКУЛЬТЕТ наличие транзитивной зависимости факультета от лектора препятствует наличию 3НФ, а для схемы базы данных R={ЛЕКТОР КАФЕДРА, КАФЕДРА ФАКУЛЬТЕТ} транзитивной зависимости нет и следовательно как каждая из схем отношений так и схема базы данных в целом находятся в 3НФ.
Пример: Рассмотрим отношение, связывающее студентов с группами, факультетами и специальностями,на которых он учится.
(ФИО. Номер зач., кн., Группа, Факультет, Выпускающая кафедра)
Первичным ключом отношения является Номер зач. КН., однако рассмотрим остальные функциональные зависимости:
1. Группа в которой учится студент, однозначно определяет факультет, на котором он учится, а также выпускающую кафедру;
2. Выпускающая кафедра однозначно определяет факультет, на котором обучаются студенты, выпускаемые на данной кафедре
Т.е. у нас есть по крайней мере следующие функциональные зависимости между неключевыми атрибутами:
Группа ---Выпускающая кафедра
Группа --- Факультет
Выпускающая кафедра --- Факультет
Для того чтобы избежать этого, мы можем предложить следующий набор отношений:
(Номер зач., кН., ФИО, Группа)
(Группа, Выпускающая кафедра)
(Выпускающая кафедра, Факультет)
Первичные ключи отношений подчеркнуты. Полученный набор отношений находится в третьей нормальной форме.
Нормальная форма Бойса-Кодда
Нормальная форма Бойса-Кодда (НФБК) является развитием 3 НФ и требует, чтобы в отношении были только такие ФЗ, левая часть которых (детерминант) является потенциальным ключом отношения.
Условия, когда для отношения может требовать НФБК:
· Отношение имеет 2 или более потенциальных ключа.
· Два потенциальных ключа являются составными.
· Они перекрываются, то есть могут иметь составные атрибуты.
Пример: Рассмотрим отношение, моделирующее сдачу студентом текущих экзаменов. Предположим, что студент может сдавать экзамен по одной дисциплине несколько раз, если он получил неудовлетворительную оценку. Допустим, что во избежание возможных полных однофамильцев, мы можем однозначно идентифицировать студента номером его зачётной книги, но с другой стороны, у нас ведётся электронный учёт успеваемости студентов, поэтому каждому студенту присваивается в период его обучения в ВУЗе уникальный номер идентификатор. Отношение, которое моделирует сдачу текущей сессии, имеет следующую схему:
(Номер зачётной книжки, Идентификатор студента, Дисциплина, Дата, Оценка)
Возможными ключами отношения являются:
1. Номер зачётной книжки, Дисциплина, Дата.
2. Идентификатор студента, Дисциплина, Дата.
Какие функциональные зависимости у нас имеются?
· Номер зачётной книжки, Дисциплина, Дата → Оценка.
· Идентификатор студента, Дисциплина, Дата → Оценка.
· Номер зачётной книжки → Идентификатор студента.
· Идентификатор студента → Номер зачётной книжки.
Оценим это отношение:
1. Это отношение находится в 3 НФ, потому, что неполных функциональных зависимостей неключевых атрибутов от атрибутов возможного ключа здесь не присутствует и нет транзитивных зависимостей.
2. Но это отношение не удовлетворяет требованиям НФБК, так как в 2 последних ФЗ детерминантом является не весь ключ, а часть ключа.
Для приведения отношения к НФБК надо разделить отношение на 2 со следующими схемами:
(Идентификатор студента, Дисциплина, Дата, Оценка)
Первые 3 атрибута составляют PK.
И 2 схема: (Номер зачётной книжки, идентификатор студента).
Алгоритм приведения к НФБК:
1. Определить все функциональные зависимости.
2. Если имеются ФЗ вида X → Y, где X не является ключом, то
а) Y выносится в отдельную таблицу. Ключом нового отношения будет.
б) Из пары X и Y остаётся лишь X.
Четвёртая НФ
В отношении R(A, B, C) существует многозначная зависимость. A→В в том и только в том случае, если множество значений В, соответствующее паре А и С, зависит только от А и не зависит от С.
Когда мы рассматривали ФЗ, то каждому значению детерминанта соответствовало только одно значение зависящего от него атрибута. При рассмотрении многозначных зависимостей мы выделяем случаи, когда одному значению некоторого атрибута соответствует устойчивое постоянное множество значений другого атрибута.
Пусть дано отношение, которое моделирует предстоящую сдачу экзаменов. Допустим, оно имеет вид:
(Номер зачётной книжки, Группа, Дисциплина)
Перечень дисциплин, которые должен сдавать студент однозначно определяется не его фамилией, а номером группы (то есть специальностью, на которой он учится).
В данном отношении участвуют 2 многозначные зависимости:
1. Группа → Дисциплина.
2. Группа → Номер зачётной книжки.
Это означает, что каждой группе однозначно соответствует перечень дисциплин по учебному плану и номер группы определяет список студентов, которые в этой группе учатся.
Если мы будем работать в исходном отношении, то мы не сможем хранить информацию о новой группе и новом учебном плане, пока в неё не будут зачислены студенты. При изменении перечня дисциплин по учебному плану, внести эти изменения для всех студентов, занимающихся в данной группе весьма затруднительно. С другой стороны, если мы добавляем студента в уже существующую группу, то мы должны добавить множество кортежей, соответствующих перечню дисциплин для данной группы. Эти аномалии модификации как раз и связаны с наличием 2 многозначных зависимостей.
В теории реляционных баз данных доказывается, что в общем случае в отношении R(A, B, C) существует многозначная зависимость A → B в том и только в том случае, когда существует многозначная зависимость А → С. Дальнейшая нормализация отношений, подобных нашему, основывается на теореме Фейджина.
Теорема Фейджина: Отношение R(A, B, C) можно спроецировать без потерь в отношения R1 (A, B) и R2(A, C) в том и только в том случае, когда существует многозначная зависимость А → В | С. (что равнозначно наличию 2 зависимостей А → В и А → С).
Под проецированием без потерь понимается такой способ декомпозиции отношения, путём применения операции проекции, при котором исходное отношение полностью и без избыточности восстанавливается путём естественного соединения полученных отношений. Практически теорема доказывает существование эквивалентной схемы для отношения, в котором существует несколько многозначных зависимостей.
Отношение R находится в 4 НФ в том и только в том случае, если в случае существования многозначной зависимости А → В все остальные атрибуты R функционально зависят от А.
Пятая НФ
Последней нормальной формой является пятая нормальная форма, которая связана с анализом нового вида зависимостей, зависимостей «проекции соединения». Это твид зависимостей является в некотором роде обобщением многозначных зависимостей.
Отношения R(A,B,C) удовлетворяет зависимости соединения (A, B, C) в том и только в том случае, когда R восстанавливается без потерь путём соединения своих проекций.
Наличие PJ зависимости в отношении делает его в некотором роде избыточным и затрудняет операции модификации.
Отношение R находится в пятой НФ в том и только в том случае, когда любая зависимость соединения в R следует из существования некоторого возможного ключа в R.
Пятая нормальная форма редко используется на практике. В большей степени она является теоретическим исследованием. Очень тяжело определить само наличие зависимостей «проекции-соединения», потому, что утверждение о наличии такой зависимости делается для всех возможных состояний БД, а не только для текущего экземпляра отношения R1. Однако знание о возможном наличии подобных зависимостей, даже теоретическое нам всё же необходимо.
|
|
|
