3.2. Нормализация отношений

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

3.2.1. Обзор нормальных форм

Процесс нормализации отношений основан на концепции нормальных форм (НФ).


Говорят, что отношение находится в некоторой НФ, если оно удовлетворяет заданному набору условий.

Известно несколько НФ (рис. 4).

Из рис. 4 видно, что все условия, необходимые для некоторой НФ, должны выполняться и для всех последующих НФ.

Первые три НФ были определены Коддом, следующая – нормальная форма Бойса-Кодда (НФБК) – Бойсом и Коддом, 4 и 5 НФ были определены Фейгином.

Возникает вопрос, можно ли продолжить нормализацию дальше, получить 6, 7 и т.д. НФ? Действительно, существуют дополнительные НФ, но 5 НФ считается в некотором смысле окончательной. А для практического проектирования достаточной считают 3 НФ.

3.2.2. Декомпозиция без потерь

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

Например, рассмотрим отношение Студенты (№ЗачетнойКнижки, Фамилия, Имя, Отчество, КодГруппы, Адрес, Телефон).

Выполним декомпозицию на два отношения:

Студенты1 (№ЗачетнойКнижки, Фамилия, Имя, Отчество) и

Студенты2 (КодГруппы, Адрес, Телефон)

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

Выполним декомпозицию по-другому:

Студенты3 (№ЗачетнойКнижки, Фамилия, Имя, Отчество) и

Студенты4 (№ЗачетнойКнижки, Адрес, Телефон)

Вот это – декомпозиция без потерь. Можно соединить полученные два отношения, получив первоначальное.

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

Возникает вопрос: какие условия должны соблюдаться для того, чтобы проекции первоначального отношения при обратном соединении гарантировали получение исходного отношения? На этот вопрос дает ответ теорема Хеза:

Пусть R (А, В, С) – отношение, где А, В, С – подмножества множества его атрибутов.

Если R удовлетворяет ФЗ А → В, то R равно соединению его проекций {А, В} и {А, С}.

(Заметим, что теорема не утверждает «тогда и только тогда»).

3.2.3. Первая, вторая и третья нормальные формы

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

Иными словами:

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

Например, если в отношении есть поле ФИО, отношение не находится в 1 НФ, т.к. значения этого поля можно разделить на фамилию, имя и отчество.

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

Например, рассмотрим отношение Успеваемость (№ЗачетнойКнижки, Фамилия, Имя, Отчество, Дисциплина, Оценка).

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

Можно тогда в качестве первичного ключа взять множество атрибутов {№ЗачетнойКнижки, Дисциплина}. В этом случае от такого ключа зависят все атрибуты, но атрибуты Фамилия, Имя, Отчество зависят приводимо, т.к. из детерминанта следующей ФЗ можно убрать атрибут Дисциплина без нарушения зависимости:

{№ЗачетнойКнижки, Дисциплина} → {Фамилия, Имя, Отчество}

И при таком первичном ключе отношение не находится во 2 НФ.

Чтобы получить отношения во 2 НФ произведем декомпозицию. Можно это сделать по теореме Хеза.

Отношение Успеваемость удовлетворяет ФЗ:

{№ЗачетнойКнижки} → {Фамилия, Имя, Отчество} (А → В)

Вне этой ФЗ осталось следующее множество атрибутов: {Дисциплина, Оценка} (С)

Тогда по теореме Хеза отношение Успеваемость равно соединению его проекций с такими множествами атрибутов:

{№ЗачетнойКнижки, Фамилия, Имя, Отчество} ({А, В})

{№ЗачетнойКнижки, Дисциплина, Оценка} ({А, С})

То есть, декомпозиция без потерь возможна на отношения:

Студенты (№ЗачетнойКнижки, Фамилия, Имя, Отчество)

Успеваемость1 (№ЗачетнойКнижки, Дисциплина, Оценка).

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

Иными словами:

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

Например, добавим в отношение Студенты атрибут СтаростаГруппы. Тогда в отношении будут следующие ФЗ:

{№ЗачетнойКнижки} → {КодГруппы}, {КодГруппы} → {СтаростаГруппы}

То есть атрибут СтаростаГруппы зависит от первичного ключа (№ЗачетнойКнижки) транзитивно через атрибут КодГруппы, а не напрямую.

Значит, это отношение не находится в 3 НФ.

Проведем декомпозицию. В данном случае по теорема Хеза может быть два варианта декомпозиции.

1 вариант основан на ФЗ {№ЗачетнойКнижки}→{Фамилия, Имя, Отчество, КодГруппы}.

В результате получим такие проекции:

{№ЗачетнойКнижки, Фамилия, Имя, Отчество, КодГруппы} и

{№ЗачетнойКнижки, СтаростаГруппы}

2 вариант основан на ФЗ {КодГруппы}→{СтаростаГруппы}.

В результате получим такие проекции:

{КодГруппы, СтаростаГруппы}

{КодГруппы, №ЗачентойКнижки, Фамилия, Имя, Отчество}

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

В результате при декомпозиции на две проекции

Группы (КодГруппы, СтаростаГруппы) и

Студенты1 (№ЗачетнойКнижки, Фамилия, Имя, Отчество, КодГруппы)

получим отношения в 3 НФ.

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

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

Успеваемость (№ЗачетнойКнижки, Фамилия, Имя, Отчество, КодГруппы, СтаростаГруппы, Дисциплина, Оценка).

Изобразим диаграмму ФЗ этого отношения:

 

Какие могут произойти аномалии при обновлении данных в таком отношении?

Например, такие:

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

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

Все полученные отношения находятся во2 НФ и в 3 НФ.

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

Полученные отношения являются независимыми проекциями.

Проекции R1 и R2 отношения R независимы тогда и только тогда, когда выполняются два условия:

1) каждая ФЗ в отношении R является логическим следствием ФЗ в проекциях R1 и R2;

2) общие атрибуты проекций R1 и R2 образуют потенциальный ключ хотя бы для одной из них.

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

Выполняется и второе условие: для проекций (1) и (2) общий атрибут – КодГруппы, он первичный ключ для (2); для (1) и (3) общий атрибут - №ЗачетнойКнижки, он первичный ключ для (1).

А вот если разбить отношение Успеваемость на следующие проекции:

(4)

 

первое условие выполнится, а второе - не выполнится (атрибут КодГруппы общий для (4) и (5), но не является потенциальным ключом ни в одном из них). То есть, эти проекции не являются независимыми.

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

Но это не означает, что любое неатомарное отношение может быть разбито на атомарные отношения. И не всегда есть смысл такого разбиения.

Например, отношение Студенты (№ЗачетнойКнижки, Фамилия, Имя, Отчество, КодГруппы) атомарно. А отношение Студенты1 (ЗачетнойКнижки, Фамилия, Имя, Отчество, КодГруппы, Адрес, ДомашнийТелефон) неатомарно, т.к. домашний телефон зависит от адреса, поэтому отношение Студенты1 можно разбить на такие независимые проекции: Студенты2 (ЗачетнойКнижки, Фамилия, Имя, Отчество, Адрес) и АдресаТелефоны (Адрес, ДомашнийТелефон). Но в этом нет смысла.

3.2.4. Нормальная форма Бойса-Кодда

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

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

Для отношений, обладающих этими свойствами данного ранее определения 3 НФ недостаточно, поэтому Бойс и Кодд ввели определение НФ Бойса-Кодда.

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

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

Можно заметить, что определение НФБК проще, чем 3 НФ, т.к. в нем нет упоминания 2 НФ и не используется понятие транзитивной зависимости.

Например, рассмотрим отношение с двумя перекрывающимися потенциальными ключами.

Успеваемость (№ЗачетнойКнижки, КодДисциплины, НазваниеДисциплины, Оценка)

Потенциальные ключи: {№ЗачетнойКнижки, КодДисциплины} и {№ЗачетнойКнижки, НазваниеДисциплины}.

Это отношение не в НФБК, т.к. в нем есть такие ФЗ:

КодДисциплины → НазваниеДисциплины

НазваниеДисциплины → КодДисциплины

А детерминанты этих ФЗ не являются потенциальными ключами.

Это отношение также не в 3 НФ, т.к. не находится во 2 НФ, потому что атрибут НазваниеДисциплины зависит только от части первичного ключа (ФЗ {№ЗачетнойКнижки, КодДисциплины} → {НазваниеДисциплины} приводима).

Видно, что этому отношению присуща избыточность.

Возможна декомпозиция на два отношения:

Дисциплина (КодДисциплины, НазваниеДисциплины)

Успеваемость1 (№ЗачетнойКнижки, КодДисциплины, Оценка)

Рассмотрим пример отношения, которое находится в 3 НФ, но не находится в НФБК. Пусть в БД Факультет есть отношение Занятия (КодГруппы, Дисциплина, Преподаватель):

КодГруппы

Дисциплина

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

ИНФ-21

ПО ЭВМ

Пятышева Е.А.

ИНФ-22

ПО ЭВМ

Суворова Т.Н.

ИНФ-31

СУБД

Шиляева М.С.

ИНФ-32

СУБД

Петухова М.В.

   

Введем следующие ограничения:

a) каждую дисциплину у конкретной группы ведет только один преподаватель, но одну и ту же дисциплину могут вести разные преподаватели;

b) каждый преподаватель ведет только одну дисциплину (в действительности это не всегда так, но мы предположим именно это).

Тогда существует два потенциальных ключа: {КодГруппы, Дисциплина} и {КодГруппы, Преподаватель}. Опять ситуация с двумя перекрывающимися потенциальными ключами. Первый из них назначим первичным.

Это отношение в 3 НФ, т.к.

  1. Оно находится во 2 НФ. Докажем это: единственная ФЗ неключевого атрибута {КодГруппы, Дисциплина} → Преподаватель. Она неприводима, т.к. атрибут КодГруппы из детерминанты исключить нельзя (одну и ту же дисциплину могут вести разные преподаватели, т.е. не верна ФЗ Дисциплина → Преподаватель); атрибут Дисциплина тоже исключить нельзя (группа изучает несколько дисциплин у разных преподавателей, т.е. не верна ФЗ КодГруппы → Преподаватель).
  2. Отношение находится и в 3 НФ. Докажем это: в единственной ФЗ для неключекого атрибута (см. 1) этот неключевой атрибут нетранзитивно зависит от первичного ключа.

Но это отношение не в НФБК, т.к. есть ФЗ Преподаватели → Дисциплины (по условию каждый преподаватель может вести только одну дисциплину), и детерминант этой ФЗ не является потенциальным ключом.

Поэтому в отношении Занятия могут произойти аномалии обновления. Например, если требуется удалить информацию о группе ИНФ-31, то при этом утратится информация о том, что дисциплину СУБД ведет преподаватель Шиляева М.С.

Необходима декомпозиция на проекции, которые будут в НФБК:

ГП (Группа, Преподаватель) и ПД (Преподаватель, Дисциплина)

Но эти проекции не являются независимыми, т.к. при попытке вставить новую запись в одну из них может возникнуть противоречие. Например, вставляем в отношение ГП кортеж {ИНФ-31, Васенина Е.А.}, но если, допустим, Васенина Е.А. преподает дисциплину ИТО, и в этом отношении есть уже кортеж {ИНФ-31, Огородников Е.В.} и преподаватель Огородников Е.В. тоже преподает дисциплину ИТО. Возникнет противоречие (два преподавателя ведут одну дисциплину у одной группы). А проверить это можно только в отношении ПД.

Вывод: не всегда можно достичь две цели сразу – разбить на отношения в НФБК и чтобы эти отношения были независимы.

Действительно, отношение Занятия является атомарным, но атомарность не является ни необходимым, ни достаточным условие хорошего макета БД. А если стремиться к НФБК, то это в некоторых случаях усложняет БД.

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

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

Проектирование реляционных баз данных


*****

© 2009-2017 Банк лекций siblec.ru
Лекции для преподавателей и студентов. Формальные, технические, естественные, общественные, гуманитарные, и другие науки.