7. Избыточные функциональные зависимости. Правила вывода

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

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

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

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

Правило 1. Транзитивные зависимости

Транзитивная зависимость является избыточной (рис. 6.6).

Рис. 6.6 Правило 1.

Транзитивные зависимости можно удалять, но только по одной (рис. 6.7):

Рис. 6.7 Удаление транзитивных зависимостей.

Первоначальные функциональные зависимости: A→B, A→C, A→D, C→D, B→C , B→D. Находим транзитивную зависимость, например: А→D, и удаляем её. Затем снова анализируем ситуацию, и находим следующую избыточную функциональную зависимость (например: А→С), удаляем её и так далее до тех пор, пока все транзитивные зависимости не будут удалены. В итоге получим

	R1 (C,D) C→D R2 (B,C) B→C R3 (A,B) A→B
Рис. 6.8 Отношения с удаленными транзитивными зависимостями.

Правило 2. Корректные, но избыточные зависимости

а) Если существует А→ В, то зависимость A,Z→B – корректная, но избыточная.

б) Если существует А→В, то зависимость A,Z→B,Z – корректная, но избыточная.

a)		б)
Рис. 6.9 Правило 2.

Правило 3. Объединение функциональных зависимостей

Объединение функциональных зависимостей.

Если А→В и А→С, то А→В,С

	a)
	б)
Рис. 6.10 Правило 3: объединение функциональных зависимостей.

Правило 4. Декомпозиция функциональных зависимостей

Декомпозиция функциональных зависимостей.

Если А→В,С , то А→В и А→С

Рис. 6.11 Правило 4: декомпозиция функциональных зависимостей.

Правило 5. Псевдотранзитивность

Если X→Y и Y,W→Z то зависимость X,W→Z, называется псевдотранзитивной и является избыточной функциональной зависимостью.

Рис. 6.12 Правило 5: Псевдотранзитивная зависимость.

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

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

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

Для построения отношений базы данных произведем следующие действия:

1. Из атрибутов предметной области сформируем универсальное отношение.

2. Из универсального отношения выделим ряд функциональны зависимостей.

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

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

5. Удалим все избыточные зависимости по одной.

На рисунке 6.13 изображена диаграмма функциональных зависимостей универсального отношения.

	A → B,C A → K A → D B,C → D B → D K → C
Рис 6.13 Диаграмма функциональных зависимостей универсального отношения

Шаг первый: Рассмотрим фрагмент диаграммы универсального отношения.			По правилу 2 зависимость BC → D является корректной, но избыточной. Производим ее удаление.
	B,C → D B → D			B → D
Рис. 6.14 Фрагмент диаграммы B,C → D, B → D Рис. 6.15 Удаление избыточной зависимости B,C → D

В результат действий первого шага получаем следующую диаграмму:

	A → B,C A → K A → D B → D K → C
Рис. 6.16 Диаграмма после удаления избыточной зависимости B,C → D

Шаг второй: Рассмотрим фрагмент диаграммы полученной на первом шаге.		По правилу 4 произведем декомпозицию зависимости A → B,C на A → B, A → C
	A → B,C			A → B
				A → C
Рис. 6.17 Фрагмент диаграммы A → B,C Рис. 6.18 Декомпозиция A → B,C на A → B, A → C

В результат действий второго шага получаем следующую диаграмму:

	A → B A → C A → D A → K B → D K → C
Рис. 6.19 Диаграмма после декомпозицию зависимости A → B,C на A → B, A → C

Шаг третий:: Рассмотрим фрагмент диаграммы полученной на втором шаге			По правилу 1 зависимость A → C является транзитивной и подлежит удалению.
	A → C A → K K → C			A → K K → C
Рис. 6.20 Фрагмент диаграммы A → C, A → K, K → C			Рис. 6.21 Удаление транзитивной зависимости A → C

В результат действий третьего шага получаем следующую диаграмму:

	A → B A → D A → K B → D K → C
Рис. 6.22 Диаграмма после удаление транзитивной зависимости A → C

Шаг четвертый:: Рассмотрим фрагмент иаграммы полученной на третьем шаге	По правилу 1 зависимость A → D транзитивная и подлежит удалению
A → B	A → B
A → D	B → D
B → D
Рис. 6.23 Фрагмент диаграммы A → B, A → D, B → D	Рис. 6.24 Удаление транзитивной зависимости A → D

В результат действий четвертого шага получаем следующую диаграмму:

	A → B A → K B → D K → C
Рис. 6.25 Диаграмма после удаление транзитивной зависимости A → D

После того как из диаграммы были удалены все избыточные зависимости, формируем следующие отношения:

R1 (B, D)

R2 (K, C)

R3 (A, B ,K)