Функциональные и многозначные зависимости. Аксиомы Армстронга. Нормальные формы и нормализация отношений.

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

Между атрибутами А и В существует функциональная зависимость, если любое значение атрибута А однозначно определяет значение атрибута В. Пример: В отношении R (преподаватель, кафедра) между атрибутами преподаватель и кафедра имеется функциональная зависи­мость, поскольку каждый преподаватель может быть припи­сан лишь к одной кафедре (предполагается, что совмести­тельство не допускается). Функциональные зависимости представляют собой связи типа "один ко многим", существующие внутри отношения. Некоторые функциональные зависимости могут быть нежелательны.

Обобщением понятия функциональной (однозначной) зависи­мости является понятие многозначной зависимости. Наличие в от­ношении многозначной зависимости является необходимым и достаточным условием его декомпозиции на две проекции. Многозначная зависимость имеет смысл только для отношений с тремя и более атрибутами. Проще всего понятие многозначной зависимости объяснить для отношения с тремя атрибутами. Пусть дано некоторое отношение R(A1, А2, A3), для которого выполняются следующие условия: 1. атрибут А1 не определяет однозначно атрибут А2, т. е. нет функциональной зависимости {А1}à{А2}; 2. атрибуты А2 и A3 не зависят друг от друга, т. е. в отношении R(A1, А2, A3) любое значение А2 может сочетаться в корте­жах с любым значением A3. Тогда в отношении R(A1, А2, A3) выполняется многозначная зависимость между атрибутами А1 и А2, которая обозначается как { А1 }->>{ А2 }. При этом говорят, что атрибут А1 многозначно определяет атрибут А2. Это частное определение многозначной зависимости, возможно, и не очень понятное. Пример: Пусть дано отношение R (преподаватель, дисциплина, увлечение), которое содержит сведения о преподавателях, дис­циплинах, занятия по которым они проводят, и личных увлече­ниях (хобби). Предполагается, что один преподаватель может проводить занятия по нескольким дисциплинам, т. е. атрибут преподаватель не определяет однозначно атрибут дисциплина. Далее, мы считаем, что нет никакой связи между дисциплинами и увлечениями преподавателей. Иначе говоря, если известно, что преподаватель читает студентам, например, математический анализ, то из этого нельзя однозначно определить, чем конкрет­но он увлекается. И наоборот, если мы знаем о конкретном ув­лечении преподавателя классической музыкой, то не можем од­нозначно сказать, какой именно дисциплиной он занимается. Все это означает, что в рассматриваемом отношении значения атрибутов дисциплина и увлечение могут сочетаться произволь­ным образом. Итак, атрибуты дисциплина и увлечение не зави­сят друг от друга, а атрибут преподаватель не однозначно опре­деляет атрибут дисциплина.

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

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

Множество всех функциональных зависимостей, которые подразумеваются заданным множеством функциональных зависимостей S, называется замыканием множества S и обозначается символом S⁺. Из приведенного определения следует, что для решения сфор­мулированной задачи необходимо найти способ вычисления S⁺ на основе S. Первая попыт­ка решить эту проблему была предпринята в статье Армстронга, в которой автор предложил набор правил вывода новых функциональных зависимостей на ос­нове заданных (эти правила также называются аксиомами Армстронга). Правила вывода могут формулироваться разными способами, и самым простым из них является следующий. Пусть А, В и С — произвольные подмножества множества атрибутов заданной переменной-отношения R. Условимся также, что символическая запись АВ означает объе­динение множеств А и В. Тогда правила вывода определяются следующим образом.

1. Правило рефлексивности: если множество В является подмножеством множества А, то А à В.

2. Правило дополнения: если А à В, то АС à ВС.

3. Правило транзитивности: если А à В и В à С, то А à С.

Каждое из этих трех правил может быть непосредственно доказано на основе опре­деления функциональной зависимости (первое из них — просто определение триви­альной зависимости).

Нормализация. База данных может быть спроектирована хорошо или плохо.

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

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

Таблицы классифицируются по тем видам аномалий модифика­ции, которым они подвержены. Это так называемые нормаль­ные формы таблиц (отношений). В своей статье 1970 г. И. Кодд определил три источника аномалий и три формы таблиц, сво­бодных от них. В последующие годы он и другие исследователи обнаружили другие виды аномалий и предложили формы таб­лиц, которые им не подвержены. Из всего сказанного выше следует определение: Нормализация – обратимый пошаговый процесс замены данной совокупности отношений другой схемой с устранением избыточных функциональных зависимостей.

1NF Таблица находится в первой нормальной форме, если каждый её атрибут атомарен. Под выражением «атрибут атомарен» понимается, что атрибут может содержать только одно значение. Замечание: в реляционной модели отношение всегда находится в 1 (или более высокой) нормальной форме в том смысле, что иные отношения не рассматриваются в реляционной модели. То есть само определение понятия отношение заведомо подразумевает наличие 1NF.

2NF Таблица находится во второй нормальной форме, если она находится в 1 НФ, и при этом любой её атрибут, не входящий в состав первичного ключа, функционально полно зависит от первичного ключа. Функционально полная зависимость означает, что атрибут функционально зависит от всего первичного составного ключа, но при этом не находится в функциональной зависимости от какой-либо из входящих в него атрибутов(частей).

3NF. Таблица находится в третьей нормальной форме, если она находится во 2 НФ, и при этом любой её неключевой атрибут функционально зависит только от первичного ключа. Или что тоже самое - "нет зависимостей неключевых атрибутов от других неключевых атрибутов + 2НФ".

НФБК. Между третьей и четвертой формами существует еще одна разновидность — нормальная форма Бойса-Кодда (НФБК). Все зависимые от первичного ключа атрибуты должны быть потенциальными ключами отношения. Если это условие не выполняется для них создаётся отдельное отношение. Чтобы сущность соответствовала НФБК, она должна находиться в 3 НФ. Любая сущность с единственным возможным ключом, соответствующая требованиям 3 НФ, автоматически находится в НФБК.

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

5NF. Таблица находится в 5NF, если она находится в 4NF и любая многозначная зависимость соединения в ней является тривиальной.

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