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

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

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

- Зависимость соединения *{ А, В, ..., Z } в переменной отношения R является тривиальной тогда и только тогда, когда по крайней мере одно из подмножеств А, В, ..., Z множества атрибутов является множеством всех атрибутов R.

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

Доменно-ключевая нормальная форма (DKNF)

Переменная отношения находится в ДКНФ тогда и только тогда, когда каждое наложенное на неё ограничение является логическим следствием ограничений доменов и ограничений ключей, наложенных на данную переменную отношения.

Ограничение домена – ограничение, предписывающее использовать для определённого атрибута значения только из некоторого заданного домена. Ограничение по своей сути является заданием перечня (или логического эквивалента перечня) допустимых значений типа и объявлением о том, что указанный атрибут имеет данный тип.

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

Любая переменная отношения, находящаяся в ДКНФ, обязательно находится в 5НФ. Однако не любую переменную отношения можно привести к ДКНФ.

Шестая нормальная форма (6NF)

Введена К. Дейтом как обобщение пятой нормальной формы для темпоральной базы данных.

Аксиомы Армстронга

Аксиомы Армстронга предоставляют возможность вывода всех возможных зависимостей из уже существующих.

Замыканием множества FD S является множество FD S+, включающее все FD, логически выводимые из FD множества S.

Для начала приведем два примера FD, из которых следуют (или выводятся) другие FD. Будем снова пользоваться отношением СЛУЖАЩИЕ_ПРОЕКТЫ. Для этого отношения выполняется, например, FD СЛУ_НОМ→{СЛУ_ЗАРП, ПРО_НОМ}. Из этой FD выводятся FD СЛУ_НОМ→СЛУ_ЗАРП и СЛУ_НОМ→ПРО_НОМ.

В отношении СЛУЖАЩИЕ_ПРОЕКТЫ имеется также пара FD СЛУ_НОМ→ПРО_НОМ и ПРО_НОМ→ПРОЕКТ_РУК. Из них выводится FD СЛУ_НОМ→ПРОЕКТ_РУК.

Заметим, что FD вида СЛУ_НОМ→ПРОЕКТ_РУК называются транзитивными, поскольку ПРОЕКТ_РУК зависит от СЛУ_НОМ "транзитивно", через ПРО_НОМ.

Подход к решению проблемы поиска замыкания S+ множества FD S впервые предложил Вильям Армстронг. Им был предложен набор правил вывода новых FD из существующих (эти правила обычно называют аксиомами Армстронга, хотя справедливость правил доказывается на основе определения FD ). Обычно принято формулировать эти правила вывода в следующей форме. Пусть A, B и C являются (в общем случае, составными) атрибутами отношения r. Множества A, B и C могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B. Тогда:

1. если B Є A, то A → B (рефлексивность);

2. если A → B, то AC → BC (пополнение);

3. если A → B и B → C, то A → C (транзитивность).

Истинность первой аксиомы Армстронга следует из того, что при B UNION A FD AB является тривиальной.

Справедливость второй аксиомы докажем от противного. Предположим, что FD AC → BC не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {AC} = t2 {AC} (a), но t1 {BC} != t2 {BC} (b) (здесь t {A} обозначает проекцию кортежа t на множество атрибутов A). По аксиоме рефлексивности из равенства (a) следует, что t1 {A} = t2 {A}. Поскольку имеется FD A → B, должно соблюдаться равенство t1 {B} = t2 {B}. Тогда из неравенства (b) следует, что t1 {C} != t2 {C}, что противоречит наличию тривиальной FD AC → C. Следовательно, предположение об отсутствии FD AC → BC не является верным, и справедливость второй аксиомы доказана.

Аналогично докажем истинность третьей аксиомы Армстронга. Предположим, что FD A → C не соблюдается. Это означает, что в некотором допустимом теле отношения найдутся два кортежа t1 и t2, такие, что t1 {A} = t2 {A}, но t1 {C} != t2 {C}. Но из наличия FD A → B следует, что t1 {B} = t2 {B}, а потому из наличия FD B → C следует, что t1 {C} = t2 {C}. Следовательно, предположение об отсутствии FD A → C не является верным, и справедливость третьей аксиомы доказана.

Можно доказать, что система правил вывода Армстронга полна и совершенна (sound and complete) в том смысле, что для данного множества FD S любая FD, потенциально выводимая из S, может быть выведена на основе аксиом Армстронга, и применение этих аксиом не может привести к выводу лишней FD. Тем не менее Дейт по практическим соображениям предложил расширить базовый набор правил вывода еще пятью правилами:

1. A → A (самодетерминированность) – прямо следует из правила (1);

2. если A → BC, то A → B и A → C (декомпозиция) – из правила (1) следует, что BC → B; по правилу (3) A → B; аналогично, из BC → С и правила (3) => A → C;

3. если A → B и A → C, то A → BC (объединение) – из правила (2) следует, что A → AB и AB → BC; из правила (3) =>, что A → BC

4. если A → B и C → D, то AC → BD (композиция) – из правила (2) следует, что AС → BС и BC → BD; из правила (3) =>, что AC → BD

5. если A → BC и B → D, то A → BCD (накопление) – из правила (2) следует, что BС → BCD; из правила (3) =>, что A → BCD.