Лекция №18

Название лекции: Нормальные формы более высокого порядка.

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

План:

1. Примеры составления множества нормализованных отношений и формализованных ФЗ.

2. Нормальные формы более высокого порядка. Многозначные зависимости.

3. Теорема Фейгина. Четверная нормальная форма.

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

1. Примеры составления множества нормализованных отношений и формализованных ФЗ.

Имеется иерархическое представление о информации, хранящейся в БД о персонале некоторой компании.

1) В компании имеется несколько отделов.

2) В каждом отделе есть несколько сотрудников, которые выполняют несколько проектов, каждый отдел занимает несколько комнат.

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

4) В каждой комнате есть несколько телефонов.

В базе данных должна хранится следующая информация:

1) Для каждого отдела: номер отдела (уникальный), бюджет, номер начальника отдела (уникальный).

2) Для каждого сотрудника: номер сотрудника (уникальный), номер проекта, номер комнаты, номер телефона, название выполняемой работы, дата и размер всех выплат полученных за выполнение данных работ;

3) Для каждого проекта: номер проекта (уникальный) и бюджет;

4) Для каждой комнаты: номер комнаты (уникальный) площадь в кв. метрах, номера (уникальные) всех телефонов установленных в этом кабинете.

Составить множество нормализованных отношений, а также формализованные ФЗ.

Решение:

Выскажем несколько утверждений, исходя из здравого смысла:

1) Ни один сотрудник не является начальником нескольких отделов.

2) Ни один сотрудник не работает одновременно более, чем в одном отделе.

3) Ни один сотрудник не работает одновременно более, чем с одним проектом.

4) Ни один сотрудник не может иметь рабочее место более, чем в одной комнате.

5) Ни один сотрудник не имеет более одного телефона.

6) Единицей измерения времени является день.

7) Ни один сотрудник не имеет одновременно более одного задания (т.е. не может получить в один день 2 -х сумм).

8) Ни одна комната не может относится более, чем к одному отделу.

Приведем ненормализованное исходное отношение:

Отдел0::={ номер-отдела, бюджет-отдела, номер-начальника, сотрудники0::={ номер-сотрудника, номер-проекта, номер-комнаты, номер-телефона, задание0::={ содержание-задания, список-выплат0::={ дата-выплаты, сумма}}}, проект0::={ номер-проекта, бюджет-проекта}, комната0::={ номер-комнаты, площадь, список-телефонов0::={ номер-телефона }}}.

Схема ФЗ.

Этап 1. Для простоты предполагаем, что каждое отношение имеет первичный ключ.

В отношении отдел0 два потенциальных ключа. Выберем один: номер-отдела, а номер-начальника - альтернативный ключ.

Выполним приведение к 1НФ по алгоритму, предложенному Коддом:

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

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

Получим:

отдел1::= {номер-отдела, бюджет-отдела, номер-начальника}

первичный ключ::=номер-отдела.

сотрудник1::={номер-отдела, номер-сотрудника, номер-проекта, номер-комнаты, номер-телефона}

первичный ключ::=номер-отдела, номер-сотрудника.

задание1::={номер-отдела, номер-сотрудника, содержание-задания}

первичный ключ::=номер-отдела, номер-сотрудника, задание.

список-выплат1::={номер-отдела, номер-сотрудника, содержание-задания, дата-выплаты, сумма}

проект1::={номер-отдела, номер-проекта, бюджет-проекта}

комната1::={номер-отдела, номер-комнаты, площадь}

список-телефонов::={номер-отдела, номер-комнаты, телефон}

Этап 2.

Отдел1 уже в 2НФ (все не ключевых, атрибутов, неприводимо зависимы от первичного ключа).

отдел2::={номер-отдела, бюджет-отдела, номер-начальника}

сотрудник1 – номер-отдела – избыточность в первичном ключе, сотрудник только в одном отделе.

сотрудник2::={номер-сотрудника, номер-отдела, номер-проекта, номер-комнаты, номер-телефона}

задание1 – номер-отдела – избыточный атрибут, удаляем его из первичного ключа. После этого в отношении есть первичный атрибут номер-отдела, который приводимо зависит от первичного ключа. Разобьем на две проекции.

задание2А::={номер-сотрудника, содержание-задания}

задание2В::={номер-сотрудника, номер-отдела}

задание2В является проекцией сотрудник2 и т.е. может не рассматриваться.

Рассмотрим список-выплат1 можно полностью удалить номер-отдела, т.к. номер-сотрудника→номер-отдела. И после разбиения на 2 проекции вторую проекцию исключаем (анологично задание2В), останется:

список-выплат2::={номер-сотрудника, дата, содержание-задания, сумма}

содержание-работы можно исключить из первичного ключа, т.к. есть ФЗ {номер-сотрудника, дата} → {содержание-работы}

Но отношение задание2А является проекцией отношения список-выплат2, т.е. его исключаем.

Проект1. Т.к. есть ФЗ {номер-проекта}→{номер-отдела}, то номер отдела не является ключевым атрибутом. Тогда проект1 находится в 2НФ.

Проект2::={номер-проекта, номер отдела, бюджет-проекта}.

Для комнаты1 аналогично проект1 получаем.

комната2::={номер-комнаты, номер-отдела, площадь}

Список-телефонов1 – номер-отдела переводим в не ключевой атрибут, далее этот атрибут остается первичным ключом {номер-комнаты, телефон}, но номер-отдела ФЗ от части первичного ключа (номер-комнаты проектируем).

список-телефонов2А {номер-комнаты, телефон}

список-телефонов2В {номер-комнаты, номер-отдела}

Последнее является проекцией комнота2 и исключается окончательно

список-телефонов2::={номер-комнаты, телефон}, первичный ключ – номер-телефона, т.к. есть ФЗ {телефон}→{номер-комнаты}

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

Этап 3. Все отношения, кроме сотрудники2, находятся в 3НФ. В отношении сотрудники2 атрибут номер-комнаты и номер-отдела транзитивно зависимы от первичного ключа номер-сатрудника. Номер-комнаты через номер-телефона, а номер-отдела через номер-проекта и через номер-комнаты, а следовательно через номер-телефона.

Номер-сотрудника→номер-телефона→номер-комнаты.

сотрудник3А::={номер-сотрудника, номер-отдела, номер-проекта, номер-телефона}.

сотрудник3В::={номер телефона, номер-комнаты} (совпадает список-телефонов2).

Для сотрудники3А: номер-сотрудника→номер-проекта→номер-отдела.

сотрудник3АА::={номер-сотрудника, телефон, номер-проекта}.

сотрудник3АВ::={номер-проекта, номер-отдела} это проекция проект2.

Итак сотрудник3::{номер-сотрудника, номер-проекта, номер-телефона} все остальные отношения второго уровня являются отношениями в 3НФ.

Все отношения уже находятся в НФБК. В некоторых случаях найти отношения НФБК можно по схеме ФЗ (в каждом отношении «стрелки» ФЗ должны выходить только от потенциальных ключей).

2. Нормальные формы более высокого порядка. Многозначные зависимости и четвертая нормальная форма.

Рассмотрим ненормализованное отношение:

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

Из этих условий видно, что никаких ФЗ в данном отношении нет.

Проведем нормализацию до 1НФ, получим:

R:

Курс	Преподаватель	Учебники
Физика Физика Физика Физика Математика Математика Математика	Иванов Иванов Петров Петров Иванов Иванов Иванов	Основы механики Оптика Основы механики Оптика Основы механики Векторный анализ Тригонометрия

Кортеж (c, t, b) включается в данное отношение, если курс c, читается преподавателем t по книге b.

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

Если есть два кортежа (c, t₁, b₁) и (c, t₂, b₂) то есть также кортежи (c, t₁, b₂) и (c, t₂, b₁)

((c, t₁, b₁)ÎR^(c, t₂, b₂)ÎR)Û ((c, t₁, b₂)ÎR^(c, t₂, b₁)ÎR)

Очевидно, что отношение обладает большой избыточностью, т.е. аномалиями обновления.

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

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

Предположим достаточно два кортежа: (Физика, Иванов, основы механики) и (Физика, Петров, оптика), чтобы получить: (Физика, Иванов, оптика) и (Физика, Петров, основы механики).

Но есть проблема: какие два кортежа выбрать и все аномалии обновления существуют.

Интуитивно ясно, что атрибуты преподаватели и учебники совершенно не зависят друг от друга.

Проблема может быть решена, если отношение R разбить на два отношения:

R₁: R₂:

Курс	Преподаватель		Курс	Учебники
Физика	Иванов	Физика	Основы механики
Физика	Петров	Физика	Оптика
Математика	Иванов	Математика	Основы механики
	Математика	Векторный анализ
Математика	Тригонометрия

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

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

Таким образом, если исходное ненормализованное отношение разбить на независимые группы. Далее эти отношения могут быть нормализованы.

Следует заметить, что декомпозиция R на R₁ и R₂ не может быть выполнена на основе функциональных зависимостей, т.к. их нет в этом отношении.

Дата добавления: 2014-01-05