Замыкание множества зависимостей

Некоторые ФЗ могут подразумевать другие ФЗ. Например, если для отношения R выполняются ФЗ А ® В и В ® С, то также выполняется зависимость А ® С, которая называется транзитивной функциональной зависимостью, т.е. С транзитивно через В зависит от А.

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

Ряд зависимостей могут быть выведены из других путем применения правил, названных аксиомами Армстронга, по имени исследователя, впервые сформулировавшего их. Это три основных аксиомы:

Пусть А, В, С – произвольные подмножества множества атрибутов отношения R, а запись АВ означает объединение А и В.

1. Рефлексивность: если В является подмножеством А, то А B
2. Дополнение: если А B, то AC BC
3. Транзитивность: если A B и B C, то A C.

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

Из трех описанных правил для упрощения вычисления замыкания можно вывести несколько других правил. Пусть D – другое произвольное подмножество множества атрибутов R.

4. Самоопределение: А ® А.

5. Декомпозиция: если А ® ВС, то А ® В и А ® С.

6. Объединение: если А ® В и А ® С, то А ® ВС.

7. Композиция: если А ® В и С ® В, то АС ® ВD.

Нормальные формы

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

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

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

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

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

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

• первая нормальная форма (1 НФ);
• вторая нормальная форма (2 НФ);
• третья нормальная форма (3 НФ);
• нормальная форма Бойса-Кодда (НФБК);
• четвертая нормальная форма (4 НФ);
• пятая нормальная форма (5 НФ).

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

ОПРЕДЕЛЕНИЕ

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

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

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

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

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

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

 

ОПРЕДЕЛЕНИЕ

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

Рассмотрим отношение, моделирующее сдачу студентами текущей сессии. Структура этого отношения определяется следующим набором атрибутов:

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

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

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

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

А почему надо приводить отношения ко второй нормальной форме? Иначе говоря, какие аномалии или неудобства могут возникнуть, если мы оставим исходное отношение и не будем его разбивать на два? Давайте рассмотрим ситуацию, когда студент переведен из одной группы в другую. Тогда в первом случае (если мы не разбивали исходное отношение на два) мы должны найти все записи с данным студентом и в них изменить значение атрибута Группа на новое. Во втором же случае меняется только один кортеж в первом отношении. И конечно, опасность нарушения корректности (непротиворечивости содержания) БД в первом случае выше. Может получиться так, что часть кортежей поменяет значения атрибута Группа, а часть по причине сбоя в работе аппаратуры останется в старом состоянии. И тогда наша БД будет содержать записи, которые относят одного студента одновременно к разным группам. Чтобы этого не произошло, мы должны принимать дополнительные непростые меры, например организовывать процесс согласованного изменения с использованием сложного механизма транзакций, который мы будем рассматривать в лекциях, посвященных вопросам распределенного доступа к БД. Если же мы перешли ко второй нормальной форме, то мы меняем только один кортеж. Кроме того, если у нас есть студенты, которые еще не сдавали экзамены, то в исходном отношении мы вообще не можем хранить о них информацию, а во второй схеме информация о студентах и их принадлежности к конкретной группе хранится отдельно от информации, которая связана со сдачей экзаменов, и поэтому мы можем в этом случае отдельно работать со студентами и отдельно хранить и обрабатывать информацию об успеваемости и сдаче экзаменов, что в действительности и происходит.

ОПРЕДЕЛЕНИЕ

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

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

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

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

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

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

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

Первичные ключи отношений выделены.

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

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

ОПРЕДЕЛЕНИЕ

Отношение находится в нормальной форме Бойса—Кодда, если каждый детерминант отношения является потенциальным ключом отношения.

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

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

Возможными ключами отношения являются Номер_зач.кн, Дисциплина, Дата и Идентификатор_студента, Дисциплина, Дата.

Какие функциональные зависимости у нас имеются?

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

• Откуда взялись две последние функциональные зависимости? Но ведь мы предварительно описали, что каждому студенту ставится в соответствие один номер зачетной книжки и один Идентификатор_студента, поэтому по значению Номер зач.кн. можно однозначно определить Идентификатор_студента (это третья зависимость) и обратно (и это четвертая зависимость). Оценим это отношение.
• Это отношение находится в третьей нормальной форме, потому что неполных функциональных зависимостей неключевых атрибутов от атрибутов возможного ключа здесь не присутствует и нет транзитивных зависимостей. А как же третья и четвертая зависимости, разве они не являются неполными? Нет, потому что зависимым не является неключевой атрибут, то есть атрибут, не входящий ни в один возможный ключ. Но вот под четвертую нормальную форму наше отношение не подходит, потому что у нас есть два детерминанта Номер зач.кн. и Идентификатор_студента, которые не являются возможными ключами отношения. Для приведения отношения к нормальной форме Бойса—Кодда надо разделить отношение, например, на два со следующими схемами:

· (Идентификатор_студента, Дисциплина, Дата, Оценка) · (Номер зач.кн., Идентификатор_студента)

или наоборот:

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

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

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