Зависимость по соединению и пятая нормальная форма

Встроенные многозначные зависимости

Четвертая нормальная форма

Существует обобщение нормальной формы Бойса-Кодда, называемое четвертой нормальной формой, которое приме­няет­ся к схемам отношений с многозначными зависимостями.

Определение. Отношение R находится в четвертой нормальной форме – 4NF (forth normal form), если из существования в нем многозначной зависимости X ®® Y (где Y – не пусто и не является подмножеством Х и XY состоит не из всех атрибутов R ) следует, что Х является ключом отношения.

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

Следующее утверждение, доказанное Берри указывает путь возможного приведения отношения в 4NF.

Утверждение. Пусть отношение R состоит из атрибутов (или множеств атрибутов) А, В, С. Зависимость А ®® В имеет место в R тогда и только тогда, когда R = R[A, B] * R[A, C].

Алгоритм приведения к 4NF. Пусть задано отношение R с атрибутами А, В, С, и имеется многозначная зависимость R.A ®® R.B Тогда отношение R декомпозируются на следующие два отношения: R[A, B] и R[B, С]. Если результирующие отношения все еще не находятся в 4NF, то к ним опять применяется этот алгоритм.

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

Определение. Пусть R является отношением с атрибутами (множествами атрибутов) А1, А2, …, Аn. Отношение R обладает зависимостью по соединению (join dependency) относительно А1, А2, …, Аn, что обозначается как *(А1, А2,…, Аn), если отношение R равно естественному соединению его проекций на А1, А2, …, Аn, то есть:

Û R = R[A1] * R[A2]*…*R[An])

Зависимость по соединению является тривиальной, если один из Ri является R.

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

Каждая зависимость по соединению вида *(R1, R2) в отношении со схемой R является эквивалентной многознач­ным зависимостям R1 ∩ R2 →→ R1 и R1 ∩ R2 →→ R2. Однако, существуют зависимости по соединению, которые не являются эквивалентными никакой многозначной зависимости. Простейшим примером такой зависимости по соединению на схеме R = (A, B, C) является *((A,B), (B, C), (A,C)). Она не является эквивалентной никакой многозначной зависимости.

На приведенном справа примере отношение содержит зависимость по соединению *((A,B), (B, C), (A,C)), что можно проверить, вычислив выражение: . Однако никакой нетривиальной многозначной зависимости в нем нет. В этом можно убедиться, проверив, что ни одна из следующих зависимостей не удовлетворяется: A →→B, A →→C, B →→A, B →→C, C →→A,C →→B.  
A B C
a1 b1 c2
a2 b1 c1
a1 b2 c1
a1 b1 c1

 

Между многозначными зависимостями и зависимостями по соединению существует следующая аналогия: если многозначная зависимость устанавливает отсутствие непосредственной зависимости между двумя парами атрибу­тов/множеств атрибутов, то зависимость по соединению указывает на независимость некоторой совокупности атрибутов/множества атрибутов.

Определение. Отношение со схемой R находится в пятой нормальной форма (fifth normal form – 5NF) по отношению ко множеству D функциональных, многозначных зависимостей и зависимостей по соединению, тогда и только тогда, когда для всех зависимостей по соединению в D+ вида *(R1, R2,…, Rn), где для любого Ri ⊆R и R = R1 R2 Rn, выполняется по крайней мере одно из следующих условий:

· *(R1, R2,…, Rn), является тривиальной зависимостью по соединению

· Каждый из Ri является суперключом для R.

Эта нормальная форма также получила название проекционно-соединительной нормальной формы (ptoject-join normal form - PJNF).

Так как любая многозначная зависимость является также и зависимостью по соединению, то любая схема отношения, находящаяся в PJNF (5NF) также находится и в 4NF.