Избыточность данных и аномалии обновления

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

Сотрудник (Nсотр, ФИО, Адрес, Должность, З/П, Nотд)

Отдел (Nотд, Адрес, Nтел)

Сотрудники отдела (Nсотр, ФИО, Адрес, Должность, З/П, Nотд, Адрес_отд, Nтел_отд)

В отношении «Сотрудники отдела» есть избыточность данных.

Поскольку сведения об отделе будет повторяться для каждого сотрудника отдела. В связи с этим в «Сотрудники отдела» существует следующее отношения обновления.

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

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

При возникновении подобных аномалий рекомендуется отношение разбивать на две части. Для отношений «Сотрудники» и «Отдел» подобных аномалий уже не будет.

 

Функциональная зависимость

Функциональная зависимость описывает связь между отношениями: R(A,B) A->B.

Атрибут B функциональная зависимость от атрибута A, что означает, что каждое значение атрибута A связано только с одним значением атрибута B. При наличии функциональной зависимости атрибут или группа атрибутов, которые расположены слева от стрелки называются детерминантом.

Сотрудники_отделения:

Nсотр -> ФИО, Адрес, Должность, З/П, Nотд, Адрес_отд, Nтел_отд.

Nотд -> Адрес_отд, Nтел_отд.

Адрес_отд -> Nотд, Nтел_отд.

Nтел_отд -> Nотд, Адрес_отд.

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

I НФ

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

Ненормализованное отношение приводится к 1-ой НФ следующими способами:

- Выравнивание таблиц или добавление строк;

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

II НФ

2 - ая НФ – основывается на полной функциональной зависимости. Полная функциональная зависимость означает, что если атрибут B функционально зависит от некоторого значения атрибута A, то зависит от полного значения этого атрибута, а не какого-то его подмножества. Если имеет место полная функциональная зависимость между атрибутами A и B, то удаление какого-либо значения атрибута A приводит к полной потери этой зависимости. При частичной зависимости это сохраняется.               2-ая НФ применяется к отношениям с составными ключами. Считается, что отношение находится во 2-ой НФ, если оно удовлетворяет 1-ой НФ и каждый атрибут, который не входит в состав первичного ключа, функционально полно завит от первого ключа.

На этом этапе, если имеется частичная зависимость, они удаляются из отношения и помещаются в новое отношение вместе с копией их детерминанта.

Отношение «Клиент - аренда»

Первичный ключ: (N_клиента, N_объекта)

f1: N_клиента, N_объекта -> Нач_аренды, Кон_аренды

f2: N_клиента -> ФИО_клиента

f3: N_ объекта -> Адрес, Стоимость, N_владельца, ФИО_владельца

f4: N_клиента, Нач_аренды -> N_объекта, Адрес, Кон_аренды, Стоимость, N_владельца, ФИО_владельца

1 – для первичного ключа

Зависимость

2 – частичная

3 – частичная

4 – функциональная зависимость для потенциального ключа

 

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

f2: Клиент (N_клиента, ФИО_клиента)

f1: Аренда (N_клиента, N_объекта, Нач_аренды, Кон_аренды)

f3: Владелец объектов (N_объекта, Адрес, Стоимость, N_владельца, ФИО_владельца)

 

III НФ

Если имеет место

A->B

B->C

 то говорят, что атрибут C транзитивно зависит от A через атрибут B, при условии, что атрибут A функционально не зависит ни от атрибута B, ни от атрибута C.

N_сотрудника -> N_отдела

N_отдела -> N_адреса_отдела

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

Объекты (N_объекта, Адрес, Стоимость, N_владельца)

Владельцы (N_владельца, ФИО_владельца)

Т.о. общую схему декомпозиции отношения «Клиент_Аренда» мы можем представить следующим образом:

 

 

 

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

 

НФБК

Однако бывает необходимость введения более сильных зависимостей – НФ Бойса-Кодда (НФ БК).

НФ БК учитывает все потенциальные ключи, которые входят в отношения. Если отношение имеет единственный потенциальный ключ, то 3-я НФ и НФ БК – эквивалентны. Считается, что отношение находящееся в НФ БК, если каждый его детерминант является потенциальным ключом. Что бы убедиться, что отношение находится в НФ БК необходимо отыскать все его детерминанты и убедиться, что они являются потенциальными ключами.

Клиенты, Объекты, Владельцы удовлетворяют НФ БК.

(N_клиента, N_объекта)

(N_клиента, Нач_аренды)

(N_объекта, Нач_аренды)

Нарушение требований НФ БК происходит:

1 – если имеются два или более составных ключа;

2 – если перекрывается потенциальный ключ, т.е. если какой-то атрибут входит в несколько ключей.

Рассмотрим отношение «Собеседование».

(N_клиента, Дата_собеседования)

(N_сотрудника, Дата_собеседования, Время_собеседования)

(N_комнаты, Время_собеседования, Дата_собеседования)

f1: N_клиента, Дата_собеседования - > Время_собеседования, N_сотрудника, N_комнаты

f2: N_сотрудника, Дата_собеседования, Время_собеседования -> N_клиента

f3: N_комнаты, Дата_собеседования, Время_собеседования -> N_сотрудника, N_клиента

f4: N_сотрудника, Дата_собеседования -> N_комнаты

Декомнозиция: Исходное отношение разбивается на два отношения:

 - Собеседование1

 - Место собеседования

Собеседование1(N_клиента, Дата_собеседования, Время_собеседования, N_сотрудника)

Место собеседования (N_сотрудника, Дата_собеседования, N_комнаты)

 

 

Обзор процесса нормализации

  Процесс нормализации отношения заключается в преобразовании ненормализованных отношений к требуемому уровню НФ. Рассмотрим последовательно весь процесс нормализации до НФ БК.

Результаты проверки объектов недвижимости

N_объекта	Адрес	Дата	Время	Комментарий	N_сотрудника	ФИО_сотредника	N_маш
01	Ленина 6-31	8,01,03 22,11,03 15,04,04	10:00 20:00 12:00	Требуется ремонт	37 311 312	Лис Крот Кот	03-12 07-11 21-13
02	……	……	……	……	……	……	……

Первый этап НФ – приведем к НФ. Для этого добавим новые строки. Определим потенциальные клюю отношения:

(N_объекта, Дата)

(N_сотрудника, Дата, Время)

(N_маш, Дата, Время)

Второй этап – приведение отношения ко 2-ой НФ. Для этого выписываются функциональные зависимости и устраняются частичные функциональные зависимости.

f1: N_объекта, Дата -> Время, Комментарий, N_сотрудника, ФИО_сотрудника, N_маш

f2: N_объекта -> Адрес

f3: N_сотрудника -> ФИО_сотрудника (транзитивная зависимость)

f4: N_сотрудника, Дата -> N_маш (частичная зависимость)

f5: N_маш, Дата, Время -> N_объекта, Адрес (для потенциальных ключей)

f6: N_сотрудника, Дата, Время -> N_объекта, Адрес, Комментарий.

Что бы привести отношение ко 2-ой НФ его необходимо будет разбить на три отношения:

Объект (N_объекта, Адрес)

Сотрудник (N_сотрудника, ФИО_сотрудника)

Проверка (N_объекта, Дата, Время, Комментарий, N_сотрудника, N_маш)

Полученное отношение удовлетворяет не только 2-ой НФ, но и 3-ей НФ.

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

Сотрудник – Машина

(N_сотрудника, N_маш, Дата)

Проверка – Дата

(N_объекта, Время, Комментарий, N_сотрудника)

  Четвертый этап – отношение многозначных зависимостей, которые позволяют избавиться от избыточности.

 

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

В ходе проектирования БД выявлен один тип зависимости - многозначная зависимость. Многозначные зависимости выявляет проблемы и избыточностью данных.

Отделение – Сотрудник – Клиент

N_отдела	ФИО_сотрудника	ФИО_клиента
011	Кот	Чижик
012	Крот	Лебедев
011	Кот	Гусев
012	Крот	Тупик

 

В данном отношении имеются многозначные зависимости типа один ко многим (1:N).

	1:N

N_отдела – ФИО_клиента

	1:N

N_отдела – ФИО_сотрудника

Если для каждого атрибута A имеется набор атрибутов B и C. Хотя атрибут B и C не зависят друг от друга.

Многозначная зависимость A -> B A -> C.

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

Для ликвидации многозначной зависимости необходимо привести отношения к 4НФ.

 

НФ

Отношение находится в 4-ой НФ, если оно удовлетворяет НФ БК и не содержит многозначных нетривиальных зависимостей.

Отделение – Сотрудник (N_отделения, ФИО_сотрудника)

Отделение – Клиент (N_отделения, ФИО_клиента)

Бывают случаи, когда необходимо выполнять декомпозицию на более чем два отношения. В этом случае необходимо учитывать зависимость соединения. Зависимость соединения - это свойство декомпозиции, которая вызывает генерацию ложных строк при обратном соединении декомпозированных отношений. Что бы не возникало зависимостей соединения, необходимо отношение приводить к 5-ой НФ.

 

НФ

Отношение в 5-ой НФ – это отношение без зависимостей соединения.

Например: Объект – Мебель – Поставщик

N_объекта	Мебель	N_поставщика
31	Стол	P1
31	Стул	P2
52	Стул	P3
52	Кровать	P1

Для того, что бы отношение удовлетворяло 5-ой НФ, необходимо его разбить на следующие отношения:

Объект – Мебель (N_объекта, Мебель)

Поставщик – Мебель (N_поставщика, Мебель)

Объекта - Поставщик (N_объекта, N_поставщика)