5.2 Алгоритм приведения отношений к третьей нормальной форме.

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

Алгоритм: 1) Если существует некоторый атрибут в R, который не участвует в функциональных зависимостях из F, то он образует функциональные значения и исключается из множества F

Замечание: Если какой-то атрибут или несколько атрибутов нужно включить в БД, то вводится атрибут (тета) и функциональная зависимость A(тета), где А - множество атрибутов, которые не входят в множество атрибутов R. После авершения проектирования, атрибут (тета) исключается из БД.

2) Если в одной функциональной зависимости участвуют все атрибуты из R, то на выходе получим R и декомпозиция не продолжается. 3) Декомпозиция, которая образует схему БД, состоит из схемы - XA, для каждой функциональной зависимости XA. Т. о. получаем столько отношений, сколько было в функциональной зависимости.

4) Если в F есть функциональные зависимости: XA1,..,XAk, с одинаковыми дискриминантами - X, то для них используется схема: XA1...Ak, т. е. если у нас есть функциональная зависимость с одинаковыми ключами, то мы их объединяем в одну таблицу(1:1).Справедливы две теоремы:

а) приведенный алгоритм дает на выходе отношение в 3НФ и сохраняет функциональные зависимости.

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

Пример1: Пример2: Рассмотрим предметную модель. Есть атрибуты, описание.

Супер - таблица -" лекции".

Лекции(Предмет, препод-ль, время, аудит-я, студент, оценка).

Предмет  преподаватель  Читает(предмет, преподаватель)

Время, аудитория  предмет  Расписание(время, аудитория, предмет)

Время, преподаватель  аудитория  Расписание(время, преподаватель, аудитория)

Предмет, студент  оценка  Ведомость(предмет, студент, оценка) 

Время, студент  аудитория  Расписание, студент(время, студент, аудитория) 

Рассмотрим алгоритм приведения НФБК, обеспечивающий соединение без потерь. 

1.Задана схема отношений F(F1...Fm) и множество функциональных зависимостей. Обозначим декомпозицию на каждом

аге алгоритма, который выполняется -интерактивно.

Пусть XY-это функциональная зависимость не содержит ключа отношения R. XY-дискриминант не включает ключ R. Тогда R не включает атрибут, не принадлежащий отношению XY, иначе X будет содержать ключ R. Произведем декомпозицию: причем

Т. к. пересечение R1 и R2 -это X и X определяет R1-R2Y, то согласно теореме Хеза, декомпозиция обладает соединением без потерь. (уравнение)

2.Проверяем отношения R1 и R2 на условие НФБК и если условие нарушается для какого-нибудь отношения, возвращаемся к п.1 и производим декомпозицию (), до тех пор, пока все отношения не будут НФБК.

Рассмотрим пример на этот алгоритм.

Занятие(предмет, преподаватель, время, аудитория, студент, оценка).

1.предметпреподаватель 2.время, аудиторияпредмет

3.время, преподавательаудитория

4.студент, предметоценка

5.время, студентаудитория

Приведем нормализацию по алгоритму приведения к НФБК:

Время, студент - является чистым ключом.

1) 2) XA, в S1 выделяют зависимости, которые и содержат (ya) время, студент.

Зависимости XA не содержат - должность, время, студент, аудитория.

Успеваемость = S1(предмет, студент, аудитория); Учеба = R1(время, студент, аудитория, предмет, преподаватель)

Читает = S2(предмет, преподаватель); Расписание = R2(время, студент, аудитория, предмет)

Занятие, аудитория =S3 (время, аудитория, предмет); Место, аудитория = R3(время, студент. аудитория)