Нормализация данных. Пятая нормальная форма.

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

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

- исключение некоторых типов избыточности;

- устранение некоторых аномалий обновления;

- разработка проекта базы данных, который является достаточно «качественным» представлением реального мира, интуитивно понятен и может служить хорошей основой для последующего расширения;

- упрощение процедуры применения необходимых ограничений целостности.

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

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

Декомпозиция без потерь

Декомпозицией отношения R называется замена R на совокупность отношений {R1, R2,..., Rn} такую, что каждое из них есть проекция R, и каждый атрибут R входит хотя бы в одну из проекций декомпозиции.

Например, для отношения R с атрибутами {a, b, c} существуют следующие основные варианты декомпозиции:

{a}, {b}, {c}

{a}, {b, c}

{a, b}, {c}

{b}, {a, c}

{a, b}, {b, c}

{a, b}, {a, c}

{b, c}, {a, c}

{a, b}, {b, c}, {a, c}

Рассмотрим теперь отношение R', которое получается в результате операции естественного соединения (NATURAL JOIN), применённой к отношениям, полученным в результате декомпозиции R.

Декомпозиция называется декомпозицией без потерь, если R' в точности совпадает с R.

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

Далеко не всякая декомпозиция является декомпозицией без потерь. Проиллюстрируем это на примере отношения R с атрибутами {a, b, c}, приведённом выше. Пусть отношение R имеет вид:

R

a b c

Москва Россия столица

Томск Россия не столица

Берлин Германия cтолица

Декомпозиция R1 = {a}, R2 = {b, c} имеет вид:

R1

a

Москва

Томск

Берлин

R2

b c

Россия столица

Россия не столица

Германия столица

Результат операции соединения этих отношений:

R' = R1 NATURAL JOIN R2

A b c

Москва Россия столица

Москва Россия не столица

Москва Германия столица

Томск Россия столица

Томск Россия не столица

Томск Германия столица

Берлин Россия столица

Берлин Россия не столица

Берлин Германия столица

Очевидно, что R' не совпадает с R, а значит такая декомпозиция не является декомпозицией без потерь. Рассмотрим теперь декомпозицию R1 = {a, b}, R2 = {a, c}:

R1

a b

Москва Россия

Томск Россия

Берлин Германия

R2

a c

Москва столица

Томск не столица

Берлин столица

 

Такая декомпозицией является декомпозицией без потерь, в чём читатель может убедиться самостоятельно.

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

Зависимость соединения

Пусть R — переменная отношения, а A, B,..., Z — некоторые подмножества множества ее атрибутов.

Если декомпозиция любого допустимого значения R на отношения, состоящие из множеств атрибутов A, B,..., Z, является декомпозицией без потерь, говорят, что переменная отношения R удовлетворяет зависимости соединения *{А, В,..., Z}.

Иными словами, переменная отношения R удовлетворяет зависимости соединения *{А, В,..., Z} тогда и только тогда, когда любое допустимое значение переменной отношения R эквивалентно соединению ее проекций по подмножествам A, B,..., Z множества атрибутов.

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

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

Зависимость соединения *{A, B,..., Z} является тривиальной тогда и только тогда, когда по крайней мере одно из подмножеств A, B,..., Z является множеством всех атрибутов отношения (включает все атрибуты). В противном случае зависимость соединения является нетривиальной.

Формулировка определения

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

Зависимость соединения *{A, B,..., Z} определяется потенциальным ключом (ключами) тогда и только тогда, когда каждое из подмножеств A, B,..., Z множества атрибутов является суперключом отношения.

Условие «каждое из подмножеств A, B,..., Z множества атрибутов является суперключом отношения» можно эквивалентно сформулировать так: «каждое из подмножеств A, B,..., Z множества атрибутов включает некоторый потенциальный ключ отношения».

Свойства 5НФ

 

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

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

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

Пример

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

Ассортимент (продавцы, фирмы, товары)

Продавец Фирма Товар

Иванов Рога и Копыта Пылесос

Иванов Рога и Копыта Хлебница

Петров Безенчук&Ко Сучкорез

Петров Безенчук&Ко Пылесос

Петров Безенчук&Ко Хлебница

Петров Безенчук&Ко Зонт

Сидоров Безенчук&Ко Пылесос

Сидоров Безенчук&Ко Телескоп

Сидоров Рога и Копыта Пылесос

Сидоров Рога и Копыта Лампа

Сидоров Геркулес Вешалка

Если дополнительных условий нет, то данное отношение, которое находится в 4-ой нормальной форме, является корректным и отражает все необходимые ограничения. Теперь предположим, что нужно учесть следующее ограничение: каждый продавец имеет в своём ассортименте ограниченный список фирм и ограниченный список типов товаров и предлагает товары из списка товаров, производимые фирмами из списка фирм.То есть продавец не имеет право торговать какими угодно товарами каких угодно фирм. Если продавец П имеет право торговать товарами фирмы Ф, и если продавец П имеет право торговать товарами типа Т, то в этом случае в ассортимент продавца П входят товары типа Т фирмы Ф при условии, что фирма Ф производит товары типа Т. Такое ограничение может быть вызвано, например, тем, что список типов товаров продавца ограничен имеющимися у него лицензиями, либо знаниями и квалификацией, необходимыми для их продажи, а список фирм каждого продавца определён партнёрскими соглашениями. В рассматриваемом примере, в частности, предполагается, что продавец Иванов имеет право торговать товарами только фирмы «Рога и Копыта», продавец Петров — товарами только фирмы «Безенчук&Ко», зато продавец Сидоров не имеет право торговать хлебницами и сучкорезами и т.д. Предложенное выше отношение не может исключить ситуации, при которых данное ограничение будет нарушено. Ничто не препятствует занести данные о торговле товаром, который данная фирма вообще не выпускает, либо данные о торговле товарами той фирмы, которую данный продавец не обслуживает, либо данные о торговле таким типом товара, который данный продавец не имеет право продавать.,Отношение не находится в 5NF, поскольку в нём есть нетривиальная зависимость соединения *{{Продавец, Фирма}, {Фирма, Товар}, {Продавец, Товар}}, однако подмножества {Продавец, Фирма}, {Фирма, Товар}, {Продавец, Товар} не являются суперключами исходного отношения. В данном случае для приведения к 5NF отношение должно быть разбито на три: {Продавец, Фирма}, {Фирма, Товар}, {Продавец, Товар}.

Товары продавцов

Продавец Товар

Иванов Пылесос

Иванов Хлебница

Петров Сучкорез

Петров Пылесос

Петров Хлебница

Петров Зонт

Сидоров Телескоп

Сидоров Пылесос

Сидоров Лампа

Сидоров Вешалка

Фирмы продавцов

Продавец Фирма

Иванов Рога и Копыта

Петров Безенчук&Ко

Сидоров Безенчук&Ко

Сидоров Рога и Копыта

Сидоров Геркулес

Товары фирм

Фирма Товар

Рога и Копыта Пылесос

Рога и Копыта Хлебница

Рога и Копыта Лампа

Безенчук&Ко Сучкорез

Безенчук&Ко Пылесос

Безенчук&Ко Хлебница

Безенчук&Ко Зонт

Безенчук&Ко Телескоп

Геркулес Вешалка