Нормализация отношений. 1, 2, 3, 4, 5 нормальные формы отношений

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

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

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

Если А = А₁А₂…А_к и А ® В, то есть В функционально зависит от всей группы атрибутов А, то говорят, что В функционально полно зависит от А.

Если А = А₁А₂…А_к и А_i…А_j ® В и i, j < k, то между А и В имеется частичная функциональная зависимость.

Если А « В, то А и В взаимозависимые атрибуты.

Взаимозависимость также может быть полной и частичной.

Если для атрибутов А, В и С выполняется условие А ® В и В ® С, но обратной связи нет, то говорят, что С транзитно зависит от А.

Атрибут В многозначно зависит от А, А ®® В, если каждому значению А соответствует множество значений В, никак не связанных с другими атрибутами отношения.

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

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

Аппарат нормализации отношений разработан Коддом. В нем определены различные нормальные формы отношений. Каждая нормальная форма ограничивает типы допустимых функциональных зависимостей отношений. Кодд выделил три нормальные формы: 1, 2, 3НФ, а сегодня определены 4НФ, 5НФ.

Следует отметить, что нормализация или иначе декомпозиция должна быть обратимой, то есть выполняться без потерь информации. Вопрос о том, происходит ли утрата информации при декомпозиции, тесно связан с концепцией функциональной зависимости. В качестве примера рассмотрим отношение поставщик (номер поставщика, статус поставщика, город проживания поставщика). В отношении 2 кортежа:(«S1, 30, Париж», «S2, 30, Лондон»). Выполним 2 варианта декомпозиции исходного отношения:

а) R1(номер, статус), R2(номер, город); б) R1(номер, статус), R2(статус, город). Первая декомпозиция получилась без потерь, а другая с потерей информации. Операция декомпозиции выполнялась путём применения дважды операции проекции к исходному отношению. В случае а) при обратном соединении полученных отношений получается исходное отношение. В случае б) при соединении полученных отношений исходное отношение не получается, а значит некоторая информация утрачена. Это произошло из-за потери одной функциональной зависимости (ФЗ), присутствующей в исходном отношении. Действительно, в исходном отношении имеются следующие ФЗ: номер → статус и номер → город. В случае а) обе функциональные зависимости сохраняются, в б) вторая ФЗ потеряна, в результате чего при выполнении операции соединения R1 и R2 произойдет потеря информации, так как неизвестно в каком городе проживают поставщики с одинаковыми статусами, но разными номерами. Зависимость между декомпозицией без потерь ФЗ подтверждается теоремой Хеза.

Теорема Хеза: Пусть R(A,B,C) является отношением с атрибутами A,B,C. Если оно удовлетворяет зависимости A → B, то R равно соединению его проекций (A,B) и (A,C).

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

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

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

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

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

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

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

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

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

Для рассмотренного примера в результате нормализации получим отношения R₁ (поставщик, товар) и R₂ (товар, цена). Отношение R1 имеет кортежи:<Иванов, мыло >, <Иванов, сахар>, <Петров, мыло >, <Петров, сыр>; отношение R2 имеет кортежи: <мыло,2000>, <сахар, 2500>, <сыр, 20000>. Анализируя возможность работы с базой данных «Поставки» при наличии двух отношений, видно, что можно добавить сведения о товаре и его цене до того, как кто-то начинает поставлять этот товар, сведения о товаре и его цене хранится в базе один раз. То есть избыточность хранения устранена, аномалии устранены, кроме этого декомпозиция выполнена без потери информации.

3НФ – Отношение находится в третьей нормальной форме, если оно находится во второй нормальной форме, и отсутствуют транзитивные зависимости атрибутов, не входящих в ключ от ключа. Иными словами, если выполняется совокупность условий:

A → B; В → С;

С → А; В → А; С → B,

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

Рассмотрим пример отношения «Хранение» с информацией о наименовании фирмы, о наименовании складов, принадлежащих фирмам и объеме продукции на складах, причем каждая фирма получает товары с одного склада, склад определяется объемом. Таблица «Хранение» выглядит следующим образом:

В данном отношении имеется один атомарный ключ <фирма>. Выполняются следующие функциональные зависимости: <фирма> ® <склад>;<склад> ® <объем>, <объем> ® <фирма>;<склад> ® <фирма>; <объем> ® <склад>.

По определению, это отношение не находится в 3 НФ, в результате чего возникает избыточность хранения информации (если несколько фирм хранят товар на складе, то в данном отношении несколько раз повторяется информация об объеме склада) и аномалии:

Аномалия включения – Если надо ввести объем склада, а нет фирмы, получающей товар со склада, то добавление невозможно.

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

Аномалия обновления – Если объем склада изменился, то надо просмотреть всё отношение и изменить все кортежи для фирм, связанных с этим складом, а это не эффективно.

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

Для рассмотренного примера выполнение правила приведения к третьей нормальной форме приведет к замене исходного отношения на два следующих отношения: R₁(фирма, склад); R₂(склад, объем). Такое разбиение является разбиением без потери информации. Если бы мы выполнили декомпозицию таким образом: R₁(фирма, склад); R₂(фирма, объем), то при соединении этих отношений было бы непонятно, к какому складу относится фирма, если склад имеет одинаковый объем, то есть происходит потеря информации.

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

Рассмотрим пример отношения «Преподаватель»:

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

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

дети ®® шифр курса, то есть отношение не находится в четвертой нормальной форме.

В результате нормализации получим: R1(номер преподавателя, дети); R2(номер преподавателя, шифр курса).

В отношениях со многими многозначными зависимостями 4НФ может не устранять избыточности, а вместе с тем и аномалий обновления. Тогда применяется 5 НФ.

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

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

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

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

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