Нормализация

Рассматриваемые вопросы: 1.Нормализация 2.Классы отношений 3.Первоя нормальная форма 4.Вторая нормальная форма 5.Третья нормальная форма 6.Анализ критериев для нормализованных и ненормализованных моделей данных 7.Корректность процедуры нормализации – декомпозиция без потерь. Теорема Хеза 8.Нормальная Форма Бойса-Кодда (НФБК) 9.Четвертая Нормальная Форма 10.Пятая Нормальная Форма 11.Доменно-ключевая нормальная форма 12.Синтез отношений 13.Правила построения отношений 14.Оптимизация: денормализация и преднамеренная (контролируемая) избыточность

Нормализация Нормализация – это процесс преобразования отношения, имеющего некоторые недостатки, в отношение, которое этих недостатков не имеет. Нормализацию можно использовать как критерий для определения корректности, целостности и правильности отношений. Изменение данных для некоторых отношений может привести к нежелательным последствиям, называемым аномалиями модификации (modification anomalies). Аномалии могут быть устранены путем разбиения исходного отношения на два или более новых отношения. В большинстве случаев только переопределенные, или нормализованные, отношения гарантируют целостность данных.

Классы отношений Отношения можно классифицировать по типам аномалий модификации, которым они подвержены. Классы отношений и способы предотвращения аномалий называются нормальными формами (normal forms). Классификация нормальных форм: первая нормальная форма (1 НФ); вторая нормальная форма (2 НФ); третья нормальная форма (3 НФ); нормальная форма Бойса-Кодда (НФБК); четвертая нормальная форма (4 НФ); пятая нормальная форма (5 НФ); доменно-ключевая нормальная форма (ДКНФ).

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

Первая нормальная форма Алгоритм нормализации (приведение к 1НФ) Шаг 1. Задаем одно или несколько отношений, отображающих понятия предметной области. Шаг 2. Выписываем обнаруженные функциональные зависимости по модели предметной области. Исключаем дублирование информации, а именно значений ключевых атрибутов, кортежей и т.п., формируем уникальное описание объектов предметной области. Если на пересечении строки и столбца каждый элемент является уникальным, то все отношения автоматически находятся в 1НФ.

Первая нормальная форма Пример Отношение СТУДЕНТ_КАФЕДРА_СЕКЦИЯ (Код кафедры студента, Номер зачетки, ФИО студента, Телефон кафедры, Секция и Плата)описывает студенческий спортивный клуб. Потенциальный ключ - Номер зачетки студента и Секция, которую он посещает.

Первая нормальная форма Аномалии модификации В отношении СТУДЕНТ_КАФЕДРА_СЕКЦИЯ данные хранятся с большой избыточностью. При изменении состояния предметной области и соответствующих изменениях состояния базы данных возникает большое количество проблем. Проблемы называются аномалиями обновления Аномалии - это неадекватность модели данных предметной области, либо некоторые дополнительные трудности в реализации ограничений предметной области средствами СУБД

Первая нормальная форма Виды аномалий: Аномалии вставки (INSERT) Аномалии обновления (UPDATE) Аномалии удаления (DELETE)

Первая нормальная форма Аномалии вставки (INSERT) В отношение СТУДЕНТ_КАФЕДРА_СЕКЦИЯ нельзя вставить данные о студенте, который пока не посещает никакую из перечисленных секций. Поскольку атрибут Секция входит в состав потенциального ключа, и, следовательно, не может содержать null- значений. Причина аномалии – хранение в одном отношении разнородной информации. Вывод – логическая модель данных неадекватна модели предметной области. База данных, основанная на такой модели, будет работать неправильно.

Первая нормальная форма Аномалии обновления (UPDATE) В отношении СТУДЕНТ_КАФЕДРА_СЕКЦИЯ присутствует повторения данных в некоторых кортежах. Изменения этих данных должны одновременно выполняться во всех местах, иначе отношение станет некорректным. Таким образом, обновление базы данных одним действием реализовать невозможно. Причина аномалии – избыточность данных, также порожденная тем, что в одном отношении хранится разнородная информация. Вывод – увеличивается сложность разработки базы данных. База данных, основанная на такой модели, будет работать правильно только при наличии дополнительного программного кода в виде триггеров.

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

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

Первая нормальная форма Функциональные зависимости Символическая запись функциональной зависимости: Множество атрибутов называется детерминантом функциональной зависимости, а множество атрибутов называется зависимой частью. Если атрибуты составляют потенциальный ключ отношения, то любой атрибут отношения функционально зависит от

Первая нормальная форма Функциональные зависимости Примеры функциональных зависимостей в отношении СТУДЕНТ_КАФЕДРА_СЕКЦИЯ Зависимость атрибутов от ключа отношения: {Номер зачетки, Секция} Код кафедры {Номер зачетки, Секция} ФИО студента {Номер зачетки, Секция} Телефон кафедры {Номер зачетки, Секция} Плата Зависимость атрибутов, характеризующих студента от Номера зачетки студента: Номер зачетки Код кафедры Номер зачетки ФИО студента Номер зачетки Телефон кафедры Зависимость стоимости от названия секции: Секция Плата

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

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

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

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

Вторая нормальная форма Алгоритм перехода от 1 НФ ко 2 НФ. Отношения находятся в 1НФ. Шаг 1. Обнаруживаем в отношениях зависимость атрибутов от части сложного ключа. Шаг 2. Проводим декомпозицию этих отношений на несколько отношений: - те атрибуты, которые зависят от части сложного ключа выносятся в отдельное отношение вместе с этой частью ключа, - в исходном отношении остаются все ключевые атрибуты.

Вторая нормальная форма Исходное отношение: Ключ: – сложный. Функциональные зависимости: – зависимость всех атрибутов от ключа отношения. – зависимость некоторых атрибутов от части сложного ключа. Декомпозированные отношения: – остаток от исходного отношения. Ключ – атрибуты, вынесенные из исходного отношения вместе с частью сложного ключа. Ключ.

Вторая нормальная форма Пример Отношение СТУДЕНТ_КАФЕДРА_СЕКЦИЯ декомпозируем на два отношения – СТУДЕНТ_КАФЕДРА и СЕКЦИЯ. Функциональные зависимости: Отношение СТУДЕНТ_КАФЕДРА (Код кафедры, Номер зачетки, ФИО студента, телефон кафедры) Номер зачетки Код кафедры Номер зачетки ФИО студента Номер зачетки Телефон кафедры Отношение СЕКЦИЯ (Секция, Плата) Секция Плата

Вторая нормальная форма Пример Декомпозиция отношения СТУДЕНТ_КАФЕДРА_СЕКЦИЯ: а – отношение СТУДЕНТ_КАФЕДРА, б – отношение СЕКЦИЯ

Вторая нормальная форма Оставшиеся аномалии вставки (INSERT) В отношение СТУДЕНТ_КАФЕДРА нельзя вставить кортеж {103, ТИ3110, Пушников А.И., }, т.к. при этом получится, что два сотрудника одной кафедры под номером 103 (Сидоров К.А. и Пушников А.И.) имеют разные номера телефонов кафедры, а это противоречит модели предметной области. Оставшиеся аномалии обновления (UPDATE) Одни и те же номера телефонов кафедры повторяются в некоторых кортежах отношения. Поэтому если на кафедре меняется номер телефона, то такие изменения необходимо одновременно выполнить во всех местах, где этот номер телефона встречаются, иначе отношение станет некорректным. Оставшиеся аномалии удаления (DELETE) При удалении некоторых данных по-прежнему может произойти потеря другой информации.

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

Третья нормальная форма Алгоритм перехода от 2 НФ к 3 НФ. Отношения находятся во 2 НФ. Шаг 1. Обнаруживаем зависимость некоторых неключевых атрибутов от других неключевых атрибутов Шаг 2. Проводим декомпозицию этих отношений следующим образом: - те неключевые атрибуты, которые зависят от других неключевых атрибутов, выносятся в отдельное отношение - в новом отношении ключом становится детерминант функциональной зависимости

Третья нормальная форма Исходное отношение: Ключ: Функциональные зависимости: – зависимость всех атрибутов от ключа отношения. – зависимость некоторых неключевых атрибутов других неключевых атрибутов. Декомпозированные отношения: – остаток от исходного отношения. Ключ – атрибуты, вынесенные из исходного отношения вместе с детерминантом функциональной зависимости. Ключ

Третья нормальная форма Пример Отношение СТУДЕНТ_КАФЕДРА декомпозируем на два отношения – СТУДЕНТ и КАФЕДРА. Функциональные зависимости : Отношение СТУДЕНТ (Код кафедры, Номер зачетки, ФИО студента) Номер зачетки Код кафедры Номер зачетки ФИО студента Отношение КАФЕДРА (Код кафедры, Телефон кафедры) Код кафедры Телефон кафедры

Третья нормальная форма Пример Декомпозиция отношения СТУДЕНТ_КАФЕДРА: а – отношение СТУДЕНТ, б – отношение КАФЕДРА

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

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

Корректность процедуры нормализации – декомпозиция без потерь. Теорема Хеза Пример, показывающий, что декомпозиция без потерь происходит не всегда Отношение R НомерФамилияЗарплата 1Иванов1000 2Петров1000

Корректность процедуры нормализации – декомпозиция без потерь. Теорема Хеза Декомпозиции отношения R на два отношения НомерЗарплата Отношение R1Отношение R2 ФамилияЗарплата Иванов1000 Петров1000

Корректность процедуры нормализации – декомпозиция без потерь. Теорема Хеза Естественное соединение проекций, имеющих общий атрибут Зарплата, будет следующим (каждая строка одной проекции соединится с каждой строкой другой проекции): Отношение НомерФамилияЗарплата 1Иванов1000 1Петров1000 2Иванов1000 2Петров1000 Данная декомпозиция не является декомпозицией без потерь, т.к. исходное отношение не восстанавливается в точном виде по проекциям

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

Отношение находится в нормальной форме Бойса-Кодда (НФБК) тогда и только тогда, когда детерминанты (уникальные ключи) всех функциональных зависимостей являются потенциальными ключами. Если отношение находится в НФБК, то оно автоматически находится и в 3НФ. Нормальная форма Бойса-Кодда

Алгоритм нормализации (приведение к НФБК) Шаг 1. Если имеются отношения, содержащие несколько потенциальных ключей, проверяем, имеются ли функциональные зависимости, детерминанты которых не являются потенциальными ключами. Шаг 2. Если функциональные зависимости имеются, проводим дальнейшую декомпозицию отношений: те атрибуты, которые зависят от детерминантов, не являющихся потенциальными ключами выносятся в отдельное отношение вместе с детерминантами.

Нормальная форма Бойса-Кодда Пример Требуется хранить данные о получении книг некоторыми кафедрами: - названия кафедр являются уникальными - каждая кафедра имеет свой уникальный код Отношение КАФЕДРА_КНИГИ Отношение КАФЕДРА_КНИГИ содержит два потенциальных ключа – {Код кафедры, Код книги} и {Название кафедры, Код книги}

Нормальная форма Бойса-Кодда Пример Отношение КАФЕДРА_КНИГИ не находится в НФБК, т.к. имеются зависимости Код кафедры Название кафедры и Название кафедры Код кафедры, детерминанты которых не являются потенциальными ключами. Проведем декомпозицию, вынося эти детерминанты и зависимые от них части в отдельное отношение. Отношения КАФЕДРА и ПОЛУЧАЕМЫЕ_КНИГИ, полученные в результате декомпозиции находятся в НФБК. Отношение КАФЕДРА Отношение ПОЛУЧАЕМЫЕ_КНИГИ

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

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

Четвертая нормальная форма Алгоритм перехода от НФБК к 4 НФ. Отношения находятся в НФБК. Шаг 1. Если в отношениях обнаружены нетривиальные многозначные зависимости, проводим декомпозицию для исключения таких зависимостей.

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

Четвертая нормальная форма Пример В отношении АБИТУРИЕНТЫ_ФАКУЛЬТЕТЫ_ПРЕДМЕТЫ имеется нетривиальная многозначная зависимость Факультет Абитуриент|Предмет. Отношение АБИТУРИЕНТЫ_ФАКУЛЬТЕТЫ_ПРЕДМЕТЫ

Четвертая нормальная форма Пример Отношение АБИТУРИЕНТЫ_ФАКУЛЬТЕТЫ_ПРЕДМЕТЫ находится в НФБК, но не в 4НФ. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения: Отношение ФАКУЛЬТЕТЫ_ АБИТУРИЕНТЫ Отношение ФАКУЛЬТЕТЫ_ ПРЕДМЕТЫ

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

Пятая нормальная форма Теорема Фейджина (другая формулировка). Отношение удовлетворяет зависимости соединения тогда и только тогда, когда имеется многозначная зависимость Т.к. теорема Фейджина является взаимно обратной, то ее можно взять в качестве определения многозначной зависимости. Зависимость соединения называется нетривиальной зависимостью соединения, если выполняется два условия: Одно из множеств атрибутов не содержит потенциального ключа отношения Ни одно из множеств атрибутов не совпадает со всем множеством атрибутов отношения Зависимость соединения называется тривиальной зависимостью соединения, если выполняется одно из условий: Либо все множества атрибутов содержат потенциальный ключ отношения Либо одно из множеств атрибутов совпадает со всем множеством атрибутов отношения

Пятая нормальная форма Алгоритм перехода от 4 НФ к 5 НФ. Отношения находятся в 5 НФ. Шаг 1. Если в отношениях обнаружены нетривиальные зависимости соединения, то необходимо провести декомпозицию для исключения таких зависимостей.

Анализ критериев для нормализованных и ненормализованных моделей данных

Доменно-ключевая нормальная форма Понятие ДКНФ – отношение находится в доменно-ключевой нормальной форме, если каждое ограничение, накладываемое на это отношение, является логическим следствием определения доменов и ключей. Ограничение - любое правило, регулирующее возможные статические значения атрибутов и достаточно точное для того, чтобы можно было установить, выполняется оно или нет. Ключ (key) – это уникальный идентификатор кортежа, как его уже определили. Домен (domain) – это описание допустимых значений атрибута. Состоит из двух частей: 1. Физическое описание – это множество значений, которые может принимать атрибут. 2. Логическое (семантическое) описание – это смысл данного атрибута.

Правила построения отношений Связь «один к одному» Атрибуты, имеющие связь «один к одному», должны фигурировать вместе, по крайней мере, в одном отношении. Пусть отношение носит имя А, а его атрибуты – А и В. Либо А, либо В должен быть ключом отношения R. Если некоторый атрибут функционально определяется атрибутом А или В, он может быть добавлен в отношение R. Атрибут, не определяемый функционально атрибутами А или В, не может быть добавлен в отношение R. Атрибуты А и В должны находиться вместе в отношении R и более ни в каком другом отношении. Для представления пары (А, В) в отношениях, отличных от R, должен последовательно использоваться один из атрибутов, А или В.

Правила построения отношений Связь «Многие к одному» Атрибуты, имеющие связь «многие к одному», могут находиться вместе в одном отношении. Пускай в отношении S атрибут С определяет атрибут D. Атрибут С должен быть ключом отношения S. Если некоторый атрибут определяется атрибутом С, он может быть добавлен в отношение S. Атрибут, не определяемый функционально атрибутом С, не может быть добавлен в отношение S.

Правила построения отношений Связь «многие ко многим» Атрибуты, имеющие связь «многие ко многим», могут сосуществовать в одном отношении. Пускай в отношении Т имеются два таких атрибута, Е и F. Ключом отношения Т должна быть комбинация (Е, F). Если некоторый атрибут определяется сочетанием атрибутов (Е, F), он может быть добавлен в отношение Т. Атрибут, не определяемый функционально сочетанием атрибутов (Е, F), не может быть добавлен в отношение Т. Если добавление нового атрибута G расширяет ключ отношения до (Е, F, G), это значит, что тема отношения изменилась. Либо атрибут G логически не принадлежит отношению Т, либо следует выбрать другое имя для отношения в соответствии с поменявшейся темой.

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

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