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

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

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

Пример:

Пусть имеется отношение “Датчик” (шифр_датчика, местоположение, параметр).

Использование такого отношения порождает ряд проблем:

1) Избыточность данных. Информация о местоположении датчика повторяется каждый раз для каждого параметра.

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

3) Аномалия включения: В БД нельзя внести информацию о датчике, который устанавливается на объект, но временно не задействуется. Это связано с тем, что отсутствующие значения параметров можно отметить каким-либо образом, но если атрибут ключевой, то нарушается ограничение на корректность включения.

4) Аномалия удаления: при необходимости удаления всех параметров, в которых был использован некоторый датчик, мы полностью теряем информацию об этом датчике.

Перечисленные выше проблемы могут быть решены, если предложить другую схему, состоящую из двух отношений:

- Поставщик_информации (шифр_датчика, параметр);

- Датчик (шифр_датчика, местоположение).

В данном случае местоположение не вносит избыточности в БД.

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

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

Функциональные зависимости (ФЗ) являются отражением семантики взаимосвязи данных в предметной области. С каждым построенным отношением в БД связывается определенная совокупность функциональных зависимостей, которые являются в ряде случаев источником аномалий данных.

· Пусть r - отношение со схемой R - r(R), X Í R(подмножество), Y Í R. Говорят, что отношение r удовлетворяет ФЗ-ти X ® Y, если выполняется ограничение: имеется не более чем один кортеж для каждого значения X из r.

Простейший алгоритм для выявления фз

1) Отсортировать отношение r по столбцам X так, собрать кортежи с равными Х -значениями вместе.

2) Если каждая совокупность кортежей с равными Х - значениями имеет также Y-значения, то в отношении r соблюдается ФЗ X ® Y (из X в Y).

Пример:

Шифр_датчика	Местоположение	Параметр	Подсистема
А1	S1	P1	D
А2	S1	P1	D
А3	D1	P1	D
А4	D2	P3	B
А5	S2	P3	B
А6	S3	P3	B
А7	S3	P2	K

Функциональные зависимости:

а) Местоположение ® Параметр - нет ФЗ;

б) Местоположение ® Подсистема - нет ФЗ (из-за S₃);

в) Параметр ® - Подсистема - есть ФЗ.

Полное множество фз

· Для каждого отношения с приписанным ему некоторым набором ФЗ-тей существует вполне определенное множество ФЗ-тей, называемое полным.

· Пусть задано отношение r (A₁,... An) и известно, что в r существуют ФЗ-ти, составляющие множество F.

· Полное множество всех ФЗ-тей, полученное на основе множества F называется замыканием множества F и обозначается F⁺, причем F Í F⁺.

Чтобы построить F⁺ необходимо знать правила вывода одних ФЗ-тей из других.

· Эти правила вывода называют аксиомами вывода функциональных зависимостей.

Аксиомы вывода f - зависимостей

Пусть r (R), X, Y, Z, W Í R.

1. Рефлексивность X ® X.

2. Пополнение: если r удовлетворяет ФЗ-ти X ® Y, то оно удовлетворяет и ФЗ-ти XZ ® Y.

3. Аддитивность: если в отношении r заданы ФЗ-ти X ® Y и X®Z, то существует ФЗ-ть X ® YZ.

4. Проективность: если в отношении r задана ФЗ-ть X ® YZ, то существует ФЗ-ть X ® Y.

5. Транзитивность: если в отношении r заданы ФЗ-ти X ® Y и Y®Z, то существует ФЗ-ть X ® Z.

6. Псевдотранзитивность: если в отношении r заданы ФЗ-ти X®Y и YZ® W, то существует ФЗ-ть XZ ® W.

Данная система аксиом является полной и неизбыточной.

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