Аномалии модификации

Случается, что в реляционных таблицах, имеющих определенную структуру, называемую аномальной, операции модификации (вставка, удаление, редактирование) могут приводить к нежелательным последствиям. Рассмотрим пример. Простенькая база данных склада хозтоваров хранит, когда какой товар получен, и в каком количестве. По одному документу (накладной) на склад могут поступить несколько различных товаров. ER-модель состоит из одной сущности ПРИЁМ_ТОВАРА (рис.9, а), которая преобразуется в реляционную таблицу (рис.9, б).

(а)

Приём_Товара

(б)

Рис.9. а – ER-диаграмма; б – соответствующее ей отношение.

Если мы удалим строку, относящуюся к документу 59 (рис.9, б), то удалим не только информацию о том, что по документу получен шланг, но и то, шланг обычно измеряется в метрах. Удаляя факты, относящиеся к одной области (по накладной № 59 получен шланг), мы непроизвольно удаляем факты, относящиеся к другой области (единицей измерения шлангов является погонный метр). Это называется аномалией удаления (deletion anomaly).

Таблица Прием_товара имеет аномалию вставки (insertion anomaly). Аномалия вставки проявляется в том, что мы не можем записать в таблицу некоторый факт, не указав дополнительно другой факт. Предположим, мы хотим записать в базу, что фанера измеряется в листах, однако мы не можем внести эти данные в таблицу Прием_Товара, пока на склад не поступит хотя бы один лист фанеры.

Третий тип аномалий – аномалия обновления (update anomaly). Допустим, оператор ошибся при вводе, и документ 58 нужно было отнести не к 21, а к 22 октября 2004г. (рис.9, б). Чтобы исправить эту ошибку, нужно найти все строки, относящиеся к документу 58, и изменить в них ячейку Дата на '2004-10-22'. Здесь аномалия модификации проявляется в том, что при изменении одного факта (накладная №58 создана 21.10.2004), мы вынуждены модифицировать несколько строк таблицы.

Аномальная структура таблиц приводит к избыточности данных. Факт, что документ № 58 создан 21.10.2004, продублирован в нескольких строках. Избыточность не только тратит лишнюю память, но допускает существование противоречивых данных (один и тот же документ может относится к разным датам, если ошибиться при вводе).

Аномалии, присутствующие в таблице Прием_Товара, можно описать следующим образом: проблемы возникают из-за того, что таблица содержит факты, относящиеся к различным темам:

1. в каких единицах измеряет товар;

2. когда создан документ;

3. какие товары получены по данному документу.

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

Суть нормализации состоит в том, чтобы разбивать таблицы, содержащие несколько тем, на две или более таблицы, каждая из которых будет содержать ровно одну тему. Так, аномальную таблицу Приём_Товара можно было бы разбить на три таблицы:

Товары (Товар(PK), Единица измерения)

Документы (Номер документа(PK), Дата)

Поступления (Товар (FK), Номер документа (FK), Количество)

Нетрудно проверить, что полученные таблицы лишены аномалий.

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

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

Рис.10 – Нормальные формы

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

Таблица находится в 1НФ, если она удовлетворяет определению отношения.

Таблица, находящаяся в 1НФ может быть подвержена аномалиям. Более старшие нормальные формы позволяют избежать определенных типов аномалий.

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

Функциональная зависимость (functional dependency) – такая логическая связь между атрибутами отношения, при которой по известному значению одного атрибута можно найти (или вычислить) значение другого атрибута. Например, зная название товара, по таблице Приём_товара (рис.10, б), можно определить единицу измерения этого товара, и это значение будет единственным: атрибут " Единица измерения " функционально зависит от атрибута " Товар ". Обратное утверждение, что " Товар " функционально зависит от " Единиц измерения ", не верно. Зная единицу измерения (например, куб.м), можно определить множество товаров, но не один единственный.

Функциональная зависимость обозначается стрелкой: Товар → Единица измерения. Атрибуты, стоящие слева от стрелки, называются детерминантом, справа от стрелки – зависимостью.

Более формально можно определить функциональную зависимость так: если А и В – атрибуты в таблице Т, то функциональная зависимость: А → В обозначает, что если две строки в таблице Т имеют одно и то же значение атрибута А, то они имеют одно и то же значение атрибута В. Это определение также применимо, если А и В – множества столбцов, а не просто отдельные столбцы.

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

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

Первичный ключ таблицы Приём_Товара составной – (Товар, Номер документа), от него зависят неключевые атрибуты:

(Товар, Номер документа) → Количество

(Товар, Номер документа) → Единица измерения

(Товар, Номер документа) → Дата

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

В таблице Приём_Товара такие зависимости есть:

Товар → Единица измерения

Номер документа → Дата

Для ликвидации аномалий исходную таблицу следует разбить на более мелкие так, чтобы детерминанты функциональных зависимостей образовали первичные ключи этих таблиц В нашем примере три детерминанта: Товар, Номер документа и (Товар, Номер документа), – образуют первичные ключи трех таблиц:

Т1(Товар, Единица измерения)

Т2(Номер документа, Дата)

Т3(Товар, Номер документа, Количество)

Получившийся результат совпадает с полученным из интуитивных соображений (п.5.1). Таблицы Т1, Т2, Т3 лишены аномалий, они соответствуют второй нормальной форме.

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

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

Третья нормальная форма (3 d normal form) – 3НФ

Рассмотрим отношение

Поставщики (Имя, Город, Страна, Код межгорода, Телефон).

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

Имя → Город /* вытекает из определения первичного ключа */

Имя → Страна /* вытекает из определения первичного ключа */

Имя → Код межгорода /* из определения первичного ключа */

Имя → Телефон /* из определения первичного ключа */

Город → Страна

Город → Код межгорода

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

Город → Страна

Город → Код межгорода

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

Для ликвидации аномалий таблицу Поставщики следует разбить на две таблицы:

Города (Город, Страна, Код межгорода)

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

Город → Страна, Город → Код межгорода, итаблицу

Поставщики (Имя, Город (FK), Телефон)

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

Имя → Город, Имя → Телефон

Каждая из полученных таблиц находится в 3НФ и лишена аномалий модификации.

Нормальная форма Бойса-Кодда (Boyce-Codd normal form, BC/NF) – НФБК

Первичный ключ таблицы Города – это строковый столбец. С целью экономии памяти введем числовой первичный ключ КодГор:

Города (КодГор, Город (Unique), Страна, Код межгорода)

Выпишем функциональные зависимости:

/* из определения первичного ключа следует: */

КодГор → Город

КодГор → Страна

КодГор → Код межгорода

/* прежние функциональные зависимости остались в силе: */

Город → Страна,

Город → Код межгорода

/* поскольку Город и КодГор взаимозаменяемы: */

Город → КодГор

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

КодыГородов (КодГор, Город (Unique))

СведенияОГородах (КодГор, Страна, Код межгорода),

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

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

Таблица Города находится в НФБК, поскольку КодГор и Город являются возможными ключами отношения.

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

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

В отношениях возможны другие виды аномалий, связанные с наличием многозначных зависимостей (multivalue dependency) между атрибутами. По определению, атрибут А многозначно определяет атрибут В той же таблицы, если для каждого значения атрибута А существует хорошо определенное множество соответствующих значений В (обозначается А ®> В, читается: "атрибут А многозначно определяет В ").

Например, в таблице Города по названию страны можно было определить множество названий (или кодов) городов, следовательно, Страна ®> Город (Страна ®> КодГор). При рассмотрении 2НФ, 3НФ, НФБК мы не обращали внимания на многозначные зависимости в таблицах Приём_Товара, Поставщики, хотя они и были: Единица измерения ®> Товар, (Номер документа, Дата) ®> Товар, Страна ®> Город. Здесь аномалии были вызваны наличием нежелательных функциональных зависимостей.

В модели "сущность-связь" вводилось понятие многозначных атрибутов (см. с.9). Многозначный атрибут – это массив однотипных значений. Например, список ключевых слов сущности КНИГА (рис.4). При переходе от ER-модели к реляционной многозначные атрибуты выносятся в отдельную таблицу, связанную связью М:1 с таблицей, представляющей сущность (п.4.3,(2)). Если этого не сделать, а поместить многозначные атрибуты вместе с однозначными в одну таблицу, то возникает избыточность и, возможно, аномалии. Например, если все атрибуты сущности КНИГА (рис.4) поместить в одну таблицу

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

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

Проекты (Код, Название, Исполнители (FK), Партнёры (FK), Начало, Окончание)

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

Код ® Название

Код ® Начало

Код ® Окончание

Код ®> Исполнители

Код ®> Партнёры

Заполнение строк таблицы данными, если исполнителей три, а организаций-партнеров две, выглядит так:

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

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

Аномалии в таблице Проекты обусловлены наличием двух многозначных зависимостей в одной таблице Код ®> Исполнители и Код ®> Партнёры. Многозначные атрибуты Исполнители и Партнеры зависят от общего атрибута Код, и не зависят друг от друга.

Определение: отношение находится в четвертой нормальной форме (4НФ), если оно находится в НФБК, и содержит единственную многозначную зависимость А ®> B, где А – возможный ключ отношения.

Чтобы привести таблицу Проекты к 4НФ, ее нужно разбить на две таблицы (по числу многозначных зависимостей): в одну вынести Код – Исполнители, во вторую Код – Партнеры.

Т1 (Код, Название, Исполнители (FK), Начало, Окончание)

Т2 (Код, Партнёры (FK))

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

Проекты (Код, Название, Начало, Окончание)

Участники (Код (FK), Исполнители (FK))

Организации (Код (FK), Партнёры (FK))

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

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

Обучение (Специальность, Дисциплина, Семестр, Преподаватель)

три многозначных атрибута:

1) Дисциплина – список дисциплин, изучаемых специальностью;

2) Семестр – список семестров, в которых дисциплина изучается на данной специальности (например, Информатика на "ВМ" изучается в 1,2 семестрах, на "ПО" – в 1 семестре, на "ЭК" – во 2 и 3 семестрах);

3) Преподаватель – список преподавателей, которые ведут занятия по данной дисциплине у соответствующей специальности.

Многозначные зависимости:

Специальность ®> Дисциплина

(Специальность, Дисциплина) ®> Семестр

(Преподаватель, Специальность) ®> Дисциплина

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

Т1(Код 1, Специальность, Дисциплина)

/* Код1 – заменитель пары значений (Специальность, Дисциплина) */

Т2(Код 1(FK), Семестр)

Т3(Код 1(FK), Преподаватель)

Доменно-ключевая нормальная форма (domain/key normal form) [6] – ДКНФ

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

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