Следует различать простое (неизбыточное) и избыточное дублирование
данных. Наличие первого из них допускается в базах данных, а избыточное
дублирование данных может приводить к проблемам при обработке данных.
Приведем примеры обоих вариантов дублирования.
Пример неизбыточного дублирования данных
представляет приведенное на рис. 5.1 отношение С_Т с атрибутами
Сотрудник и Телефон. Для сотрудников, находящихся в одном помещении,
номера телефонов совпадают. Номер телефона 4328 встречается несколько
раз, хотя для каждого служащего номер телефона уникален. Поэтому ни один
из номеров не является избыточным. Действительно, при удалении одного
из номеров телефонов будет утеряна информация о том, по какому номеру
можно дозвониться до одного из служащих.
С_Т
Сотрудник
Телефон
Иванов
3721
Петров
4328
Сидоров
4328
Егоров
4328
Рис. 5.1. Неизбыточное дублирование
Пример избыточного дублирования (избыточности) представляет
приведенное на рис. 5.2а отношение С_Т_Н, которое, в отличие от
отношения С_Т, дополнено атрибутом Н_комн (номер комнаты сотрудника).
Естественно предположить, что все служащие в одной комнате имеют один и
тот же телефон. Следовательно, в рассматриваемом отношении имеется
избыточное дублирование данных. Так, в связи с тем, что Сидоров и Егоров
находятся в той же комнате, что и Петров, их номера можно узнать из
кортежа со сведениями о Петрове.
С_Т_Н
а)
Сотрудник
Телефон
Н_комн
Иванов
3721
109
Петров
4328
111
Сидоров
4328
111
Егоров
4328
111
С_Т_Н
б)
Сотрудник
Телефон
Н_комн
Иванов
3721
109
Петров
4328
111
Сидоров
---
111
Егоров
---
111
Рис. 5.2. Избыточное дублирование
На рис. 5.2б приведен пример неудачного отношения С_Т_Н, в котором
вместо телефонов Сидорова и Егорова поставлены прочерки (неопределенные
значения). Неудачность подобного способа исключения избыточности
заключается в следующем. Во-первых, при программировании придется
потратить дополнительные усилия на создание механизма поиска информации
для прочерков таблицы. Во-вторых, память все равно выделяется под
атрибуты с прочерками, хотя дублирование данных и исключено. В-третьих,
что особенно важно, при исключении из коллектива Петрова кортеж со
сведениями о нем будет исключен из отношения, а значит уничтожена
информация о телефоне 111-й комнаты, что недопустимо.
Возможный способ выхода из данной ситуации приведен на рис.
5.3. Здесь показаны два отношения С_Н и Н_Т, полученные путем
декомпозиции исходного отношения С_Т_Н. Первое из них содержит
информацию о номерах комнат, в которых располагаются сотрудники, а
второе - информацию о номерах телефонов в каждой из комнат. Теперь, если
Петрова и уволят из учреждения и, как следствие этого, удалят всякую
информацию о нем из баз данных учреждения, это не приведет к утере
информации о номере телефона в 111-й комнате.
Т_Н
Телефон
Н_комн
3721
109
4328
111
С_Н
Сотрудник
Н_комн
Иванов
109
Петров
111
Сидоров
111
Егоров
111
Рис. 5.3. Исключение избыточного дублировани
Процедура декомпозиции отношения С_Т_Н на два отношения С_Н и Н_Т
является основной процедурой нормализации отношений.
Избыточное дублирование данных создает проблемы при
обработке кортежей отношения, названные Э. Коддом "аномалиями обновления
отношения". Он показал, что для некоторых отношений проблемы возникают
при попытке удаления, добавления или редактирования их кортежей.
Аномалиями будем называть такую ситуацию в таблицах
БД, которая приводит к противоречиям в БД, либо существенно усложняет
обработку данных.
Выделяют три основные вида аномалий: аномалии модификации
(или редактирования), аномалии удаления и аномалии добавления.
Аномалии модификации проявляются в том, что
изменение значения одного данного может повлечь за собой просмотр всей
таблицы и соответствующее изменение некоторых других записей таблицы.
Так, например, изменение номера телефона в комнате 111
(рис. 5.2а), что представляет собой один единственный факт, потребует
просмотра всей таблицы С_Т_Н и изменения поля Н_комн согласно текущему
содержимому таблицы в записях, относящихся к Петрову, Сидорову и
Егорову.
Аномалии удаления состоят в том, что при удалении
какого-либо данного из таблицы может пропасть и другая информация,
которая не связана напрямую с удаляемым данным.
В той же таблице С_Т_Н удаление записи о сотруднике Иванове
(например, по причине увольнения или ухода на заслуженный отдых)
приводит к исчезновению информации о номере телефона, установленного в
109-й комнате.
Аномалии добавления возникают в случаях, когда
информацию в таблицу нельзя поместить до тех пор, пока она неполная,
либо вставка новой записи требует дополнительного просмотра таблицы.
Примером может служить операция добавления нового
сотрудника все в ту же таблицу С_Т_Н. Очевидно, будет
противоестественным хранение сведений в этой таблице только о комнате и
номере телефона в ней, пока никто из сотрудников не помещен в нее. Более
того, если в таблице С_Т_Н поле Служащий является ключевым, то хранение
в ней неполных записей с отсутствующей фамилией служащего просто
недопустимо из-за неопределенности значения ключевого поля.
Вторым примером возникновения аномалии добавления может
быть ситуация включения в таблицу нового сотрудника. При добавлении
таких записей для исключения противоречий желательно проверить номер
телефона и соответствующий номер комнаты хотя бы с одним из сотрудников,
сидящих с новым сотрудником в той же комнате. Если же окажется, что у
нескольких сотрудников, сидящих в одной комнате, имеются разные
телефоны, то вообще не ясно, что делать (то ли в комнате несколько
телефонов, то ли какой-то из номеров ошибочный).
ФОРМИРОВАНИЕ ИСХОДНОГО ОТНОШЕНИЯ
Проектирование БД начинается с определения всех объектов, сведения о
которых будут включены в базу, и определения их атрибутов. Затем
атрибуты сводятся в одну таблицу - исходное отношение.
Пример. Формирование исходного отношения.
Предположим, что для учебной части факультета создается БД о
преподавателях. На первом этапе проектирования БД в результате общения с
заказчиком (заведующим учебной частью) должны быть определены
содержащиеся в базе сведения о том, как она должна использоваться и
какую информацию заказчик хочет получать в процессе ее эксплуатации. В
результате устанавливаются атрибуты, которые должны содержаться в
отношениях БД, и связи между ними. Перечислим имена выделенных атрибутов
и их краткие характеристики:
ФИО - фамилия и инициалы преподавателя. Исключаем
возможность совпадения фамилии и инициалов у преподавателей.
Должн - должность, занимаемая преподавателем.
Оклад - оклад преподавателя.
Стаж - преподавательский стаж.
Д_Стаж - надбавка за стаж.
Каф - номер кафедры, на которой числится преподаватель.
Предм - название предмета (дисциплины), читаемого
преподавателем.
Группа - номер группы, в которой преподаватель проводит
занятия.
ВидЗан - вид занятий, проводимых преподавателем в
учебной группе.
Одно из требований к отношениям заключается в том, чтобы
все атрибуты отношения имели атомарные (простые) значения. В исходном
отношении каждый атрибут кортежа также должен быть простым. Пример
исходного отношения ПРЕПОДАВАТЕЛЬ приведен на рис. 5.4.
ПРЕПОДАВАТЕЛЬ
ФИО
Должн
Оклад
Стаж
ДСтаж
Каф
Предм
Группа
ВидЗан
Иванов И.М.
преп
500
5
100
25
СУБД
256
Практ
Иванов И.М.
преп
500
5
100
25
ПЛ/1
123
Практ
Петров М.И.
ст. преп
800
7
100
25
СУБД
256
Лекция
Петров М.И.
ст. преп
800
7
100
25
Паскаль
256
Практ
Сидоров Н.Г.
преп
500
10
150
25
ПЛ/1
123
Лекция
Сидоров Н.Г.
преп
500
10
150
25
Паскаль
256
Лекция
Егоров В.В.
преп
500
5
100
24
ПЭВМ
244
Лекция
Рис. 5.4. Исходное отношение ПРЕПОДАВАТЕЛЬ
Указанное отношение имеет следующую схему ПРЕПОДАВАТЕЛЬ(ФИО, Должн,
Оклад, Стаж, Д_Стаж, Каф, Предм, Группа, ВидЗан).
Исходное отношение ПРЕПОДАВАТЕЛЬ содержит избыточное
дублирование данных, которое и является причиной аномалий
редактирования. Различают избыточность явную и неявную.
Явная избыточность заключается в том, что в
отношении ПРЕПОДАВАТЕЛЬ строки с данными о преподавателях, проводящих
занятия в нескольких группах, повторяются соответствующее число раз.
Например, в отношении ПРЕПОДАВАТЕЛЬ все данные по Иванову повторяются
дважды. Поэтому, если Иванов И.М. станет старшим преподавателем, то этот
факт должен быть отражен в обеих строках. В противном случае будет
иметь место противоречие в данных, что является примером аномалии
редактирования, обусловленной явной избыточностью данных в отношении.
Неявная избыточность в отношении ПРЕПОДАВАТЕЛЬ
проявляется в одинаковых окладах у всех преподавателей и в одинаковых
добавках к окладу за одинаковый стаж. Поэтому, если при изменении
окладов за должность с 500 на 510 это значение изменят у всех
преподавателей, кроме, например, Сидорова, то база станет
противоречивой. Это пример аномалии редактирования для варианта с
неявной избыточностью.
Средством исключения избыточности в отношениях и, как
следствие, аномалий является нормализация отношений, рассмотрим ее более
подробно.
Метод нормальных форм
Проектирование БД является одним из этапов жизненного цикла
информационной системы. Основной задачей, решаемой в процессе
проектирования БД, является задача нормализации ее отношений.
Рассматриваемый ниже метод нормальных форм является классическим методом
проектирования реляционных БД. Этот метод основан на фундаментальном в
теории реляционных баз данных понятии зависимости между атрибутами
отношений.
ЗАВИСИМОСТЬ МЕЖДУ АТРИБУТАМИ
Рассмотрим основные виды зависимостей между атрибутами отношений:
функциональные, транзитивные и многозначные.
Понятие функциональной зависимости является базовым, так
как на его основе формулируются определения всех остальных видов
зависимостей.
Атрибут В функционально зависит от атрибута А, если
каждому значению А соответствует в точности одно значение В.
Математически функциональная зависимость В от А обозначается записью
А->В. Это означает, что во всех кортежах с одинаковым значением
атрибута А атрибут В будет иметь также одно и то же значение. Отметим,
что А и В могут быть составными - состоять из двух и более атрибутов.
В отношении на рис. 5.4 можно выделить функциональные
зависимости между атрибутами ФИО->Каф, ФИО->Должн, Должн->Оклад
и другие. Наличие функциональной зависимости в отношении определяется
природой вещей, информация о которых представлена кортежами отношения. В
отношении на рис. 5.4 ключ является составным и состоит из атрибутов
ФИО, Предмет, Группа.
Функциональная взаимозависимость. Если существует
функциональная зависимость вида А->В и В->А, то между А и В
имеется взаимно однозначное соответствие, или функциональная
взаимозависимость. Наличие функциональной взаимозависимости между
атрибутами А и В обозначим как А<->В или В<->А.
Пример. Пусть имеется некоторое отношение,
включающее два атрибута, функционально зависящие друг от друга. Это
серия и номер паспорта (N) и фамилия, имя и отчество владельца (ФИО).
Наличие функциональной зависимости поля ФИО от N означает не только тот
факт, что значение поля N однозначно определяет значение поля ФИО, но и
то, что одному и тому же значению поля N соответствует только
единственное значение поля ФИО. Понятно, что в данном случае действует и
обратная ФЗ: каждому значению поля ФИО соответствует только одно
значение поля N. В данном примере предполагается, что ситуация наличия
полного совпадения фамилий, имен и отчеств двух людей исключена.
Если отношение находится в 1НФ, то все неключевые атрибуты
функционально зависят от ключа с различной степенью зависимости.
Альтернативным вариантом является полная функциональная
зависимость
Атрибут С зависит от атрибута А транзитивно
(существует транзитивная зависимость), если для атрибутов А, В, С
выполняются условия А->В и В->С, но обратная зависимость
отсутствует. В отношении на рис. 5.4 транзитивной зависимостью связаны
атрибуты:
ФИО->Должн->Оклад Между атрибутами может иметь место
многозначная зависимость.
В отношении R атрибут В многозначно зависит от
атрибута А, если каждому значению А соответствует множество значений В,
не связанных с другими атрибутами из R.
Многозначные зависимости могут быть "один ко многим" (1:М),
"многие к одному" (М: 1) или "многие ко многим" (М:М), обозначаемые
соответственно: А=>В, А<=В и А<=>В.
Например, пусть преподаватель ведет несколько предметов, а
каждый предмет может вестись несколькими преподавателями, тогда имеет
место зависимость ФИО<=>Предмет. Так, из таблицы 7.2, приведенной
на рис. 5.4., видно, что преподаватель Иванов И.М. ведет занятия по двум
предметам, а дисциплина СУБД - читается двумя преподавателями: Ивановым
И.М. и Петровым М.И.
Замечание. В общем случае между двумя атрибутами
одного отношения могут существовать зависимости: 1:1,1:М,М:1 и М:М.
Поскольку зависимость между атрибутами является причиной аномалий,
стараются расчленить отношения с зависимостями атрибутов на несколько
отношений. В результате образуется совокупность связанных отношений
(таблиц) со связями вида 1:1,1:М, М:1 и М:М . Связи между таблицами отражают
зависимости между атрибутами различных отношений.
Взаимно независимые атрибуты. Два или более атрибута
называются взаимно независимыми, если ни один из этих атрибутов не
является функционально зависимым от других атрибутов.
В случае двух атрибутов отсутствие зависимости атрибута А
от атрибута В можно обозначить так: А-.->В. Случай, когда А-.->В и
B-i->A, можно обозначить А-.=В.
неключевого атрибута от всего составного ключа. В нашем
примере атрибут ВидЗан находится в полной функциональной зависимости от
составного ключа.
называется зависимость неключевого атрибута от части
составного ключа. В рассматриваемом отношении атрибут Должн находится в
функциональной зависимости от атрибута ФИО, являющегося частью ключа.
Тем самым атрибут Должн находится в частичной зависимости от ключа
отношения.
Нормальные формы
Процесс проектирования БД с использованием метода нормальных форм
является итерационным и заключается в последовательном переводе
отношений из первой нормальной формы в нормальные формы более высокого
порядка по определенным правилам. Каждая следующая нормальная форма
ограничивает определенный тип функциональных зависимостей, устраняет
соответствующие аномалии при выполнении операций над отношениями БД и
сохраняет свойства предшествующих нормальных форм.
Выделяют следующую последовательность нормальных форм:
первая
нормальная форма (1НФ);
вторая
нормальная форма (2НФ);
третья
нормальная форма (3НФ);
усиленная
третья нормальная форма, или нормальная форма Бойса-Кодда (БКНФ);
четвертая
нормальная форма (4НФ);
пятая
нормальная форма (5НФ).
Первая нормальная форма. Отношение находится в 1НФ,
если все его атрибуты являются простыми (имеют единственное значение).
Исходное отношение строится таким образом, чтобы оно было в 1НФ.
Перевод отношения в следующую нормальную форму
осуществляется методом "декомпозиции без потерь". Такая декомпозиция
должна обеспечить то, что запросы (выборка данных по условию) к
исходному отношению и к отношениям, получаемым в результате
декомпозиции, дадут одинаковый результат.
Вторая нормальная форма. Отношение находится в 2НФ, если оно
находится в 1НФ и каждый неключевой атрибут функционально полно зависит
от первичного ключа (составного).
Для устранения частичной зависимости и перевода отношения в
2НФ необходимо, используя операцию проекции, разложить его на несколько
отношений следующим образом:
построить
проекцию без атрибутов, находящихся в частичной функциональной
зависимости от первичного ключа;
построить
проекции на части составного первичного ключа и атрибуты, зависящие от
этих частей.
Третья нормальная форма. Определение 1. Отношение находится в
3НФ, если оно находится в 2НФ и каждый неключевой атрибут нетранзитивно
зависит от первичного ключа.
Существует и альтернативное определение.
Определение 2. Отношение находится в 3НФ в том и только в
том случае, если все неключевые атрибуты отношения взаимно независимы и
полностью зависят от первичного ключа.
Доказать справедливость этого утверждения несложно.
Действительно, то, что неключевые атрибуты полностью зависят от
первичного ключа, означает, что данное отношение находится в форме 2НФ.
Взаимная независимость атрибутов (определение приведено выше) означает
отсутствие всякой зависимости между атрибутами отношения, в том числе и
транзитивной зависимости между ними. Таким образом, второе определение
3НФ сводится к первому определению.
первая
нормальная форма (1НФ);