Лекция №9

Тема: «Нормализация»

Цель нормализации

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

первая (1НФ), вторая (2НФ) и третья (ЗНФ). Затем Р. Бойсом и Э. Ф. Коддом было сформулировано более строгое определение третьей нормальной формы, которое получило название нормальной формы Бойса-Кодда (НФБК). Все эти нормальные формы основаны на функциональных зависимостях, существующих между атрибутами отношения [212], Нормальные формы более высокого порядка, которые превосходят НФБК, были введены позднее. К ним относятся четвертая(4НФ) и пятая (5НФ) нормальные формы.Но на практике эти нормальные формы более высоких порядков используются крайне редко.

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

Избыточность данных и аномалии
обновления

Основная цель проектирования реляционной базы данных заключается в группировании атрибутов в отношения таким образом, чтобы минимизировать избыточность данных и тем самым сократить объем памяти, необходимый для физического хранения отношений, представленных в виде таблиц. Проблемы, связанные с избыточностью данных, можно проиллюстрировать, сравнив отношения Staff и Branch табл. 13.1 и 13.2 с отношением StaffBranch табл. 13-3. При работе с отношениями, содержащими избыточные данные,могут возникать проблемы, которые называются аномалиями обновления и подразделяются на аномалии вставки, удаления и модификации.

Отношение StaffBranch является альтернативной формой представления отношений Staff и Branch. Упомянутые отношения описываются следующим образом:

 

Функциональные зависимости

Функциональная зависимость (functional dependency) описывает связь между атрибутами и является одним из основных понятий нормализации.

Характеристики функциональных зависимостей:

При описании функциональных зависимостей в настоящем разделе подразумевается, что реляционная схема имеет атрибуты (А, В, С, . . ., Z) и что вся база данных может быть представлена в виде одного универсального отношения R = (А, В, С, . . . , Z). Из этого предположения следует, что каждый атрибут в базе данных имеет уникальное имя.

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

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

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

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

 

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

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

Правила вывода для функциональных
зависимостей

Множество всех функциональных зависимостей, которые могут быть выведены из заданного множества функциональных зависимостей X, называется замыканием X и записывается как X*. Для успешной работы, безусловно, необходимо определить ряд правил, позволяющих вычислить X* из X. Набор правил вывода,называемый аксиомами Армстронга, показывает способы вывода новых функциональных зависимостей из заданных [7]. Предположим, что А, В и С — подмножества атрибутов отношения R. Аксиомы Армстронга приведены ниже.

Рефлексивность. Если В — подмножество А, то А—>В.

Дополнение. Если А —> В, то А, С—>В, С.

Транзитивность. Если А—>В и В —> С, то А —> С.

На основе трех правил, приведенных выше, можно вывести несколько дополнительных правил, позволяющих упростить практическую задачу вычисления X4 . Допустим, что D — еще одно подмножество атрибутов отношения R, и сформулируем следующие правила.

Самоопределение. А —> А.

Декомпозиция. Если А—>В, с, то А —> В и А—>С.

Объединение. Если А —> В и А —> С, то А —> В, с.

Композиция. Если А —> В и C —> D, то А, С—>В, D.

Процесс нормализации

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

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

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

 

Первая нормальная форма (1НФ)

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

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

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

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

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

Вторая нормальная форма (2НФ)

Вторая нормальная форма (2НФ) основана на понятии полной функциональной зависимости, которая описывается ниже.

Полная функциональная зависимость

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

Функциональная зависимость А—>в является полной функциональной зависимостью, если удаление какого-либо атрибута из А приводит к утрате этой зависимости. Функциональная зависимость А —> В называется частичной, если в А есть некий атрибут, при удалении которого эта зависимость сохраняется.

Определение второй нормальной формы

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

Третья нормальная форма (ЗНФ)

Транзитивная зависимость. Если для атрибутов А, в и с некоторого отношения существуют зависимости вида А —> В и В —> С, это означает, что атрибут с транзитивно зависит от атрибута А через атрибут В. Транзитивная зависимость является одним из типов функциональной зависимости.

Определение третьей нормальной формы

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

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

Общее определение второй и третьей
нормальных форм

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

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

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

Нормальная форма Бойса-Кодда (НФБК)

Нормальная форма Бойса-Кодда (НФБК). Отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом. Для проверки принадлежности отношения к НФБК необходимо найти все его детерминанты и убедиться в том, что они являются потенциальными ключами.Напомним, что детерминантом является один атрибут или группа атрибутов, от которой полностью функционально зависит другой атрибут.Различие между ЗНФ и НФБК заключается в том, что функциональная зависимость А—≫В допускается в отношении ЗНФ, если атрибут В является первичным ключом, а атрибут А не обязательно является потенциальным ключом. Тогда как в отношении НФБК эта зависимость допускается только тогда, когда атрибут А является потенциальным ключом. Следовательно, нормальная форма Бойса-Кодда является более строгой версией формы ЗНФ, поскольку каждое отношение НФБК является также отношением ЗНФ, но не всякое отношение ЗНФ является отношением НФБК.

Четвертая нормальная форма (4НФ)

Как было сказано выше, НФБК позволяет устранить любые аномалии, вызванные функциональными зависимостями. Однако в результате теоретических исследований был выявлен еще один тип зависимости — многозначная зависимость (Multi-Valued Dependency — MVD), которая при проектировании отношений также может вызвать проблемы, связанные с избыточностью данных.В этом разделе кратко описываются многозначная зависимость и связь зависимости этого типа с четвертой нормальной формой (4НФ).

Многозначная зависимость . Представляет такую зависимость между атрибутами отношения (например, А, В и С), что каждое значение А представляет собой множество значений для а и множество значений для с. Однако множества значений для в и с не зависят друг от друга.

Многозначная зависимость между атрибутами А, В и С некоторого отношения дальше будет обозначаться следующим образом:

А -> В

А -> С

Определение четвертой нормальной формы

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

Пятая нормальная форма (5НФ)

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

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

Определение пятой нормальной формы (5НФ)

Пятая нормальная форма (5НФ). Отношение без  зависимостей соединения. Пятая нормальная форма (5НФ), которая также называется проективносоединительной нормальной формой, или ЯСЯФ (Project-Join Normal Form -PJNF), означает, что отношение в такой форме не имеет зависимостей соединения.

Зависимость соединения. Представляет собой одну из разновидностей зависимости. Например, если рассматривается отношение R с подмножествами атрибутов R, обозначенными как A, B, ....; Z, то отношение R удовлетворяет зааисимость соединения, если и только если каждое допустимое значение R равно соединению его проекций на атрибуты A, B, ..., Z .