Основные понятия теории баз данных.

Сном, Проект, Квартал®Вклад

 

	Все шесть функциональных зависимостей изображены на рисунке 6.1 с помощью  диаграммы функциональных зависимостей.
Рис. 6.1 Диаграмма функциональных зависимостей.

 

5. Нормальные формы отношений

Первая нормальная форма

 

Атрибут называется простым, если значение его атомарно, т.е. неделимо (пример простых атрибутов: табельный номер сотрудника, фамилия сотрудника, оклад). Атрибут называется сложным, если его значение представляет собой объединение значений различных атрибутов (на Пример: атрибут Адрес [индекс, город, улица, дом, квартира]). Отношение называется отношением в первой нормальной форме, если все его атрибуты простые. Отношение “начальник отдела” находится в первой нормальной форме.

Вторая нормальная форма

 

Полная функциональная зависимость. Пусть А – это некоторый атрибут, Х – это набор атрибутов. Говорят, что А функционально полно зависит от Х, если Х ® А, Y        А, где Y любое подмножество Х. Набор атрибутов Х называют детерминантом отношения. Отношение находится во второй нормальной форме, если оно находится в первой нормальной форме, и каждый неключевой атрибут функционально полно зависит от возможного ключа. Так, отношение с зависимостью Сном, Лном, Тном®Сном не находится во второй нормальной форме.

Третья нормальная форма

 

Транзитивная зависимость. Пусть X, Y, Z – наборы атрибутов некоторого отношения.

Если X®Y, Y®Z но Y Х то X®Z , тогда говорят что Z транзитивно зависит от X

 

Пример: транзитивной зависимости  Сном®Тном, Тном®Лном Þ Сном®Лном.

 

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

В общем случае отношение в третьей  нормальной форме содержит аномалии, но если в отношении только один ключ и имеются зависимости только от ключа, оно будет свободно от аномалий.

Третья усиленная форма или  нормальная форма Бойса–Кодда (НФБК)

 

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

 

Сном

Лном

Тном

Сфам, Проект, Квартал

 

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

 

6. Декомпозиция отношений

 

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

Например, было R(X,Y,Z), а в результате декомпозиции получили два R₁(X,Y), R₂(Y,Z).

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

Пусть R – отношение, не находящееся  в НФБК. Пусть a_j зависит от a_i (a_i ® a_j). Эта зависимость препятствует нахождению отношения в НФБК. Пусть a_i – некоторый атрибут, детерминант, но не являющийся возможным ключем . Отношение R(a₁,…,a_i,…,a_j) разбивают на два

R₁ (a₁,…,a_i,…,a_j-1) и R₂(a_i,a_j)

Отношение R₂ называется проекцией отношения R.

 

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

Теория реляционных баз данных говорит, что результаты запроса  будут совпадать, если декомпозиция выполнена способом, при котором соединение R₁ и R₂ дает в точности исходное соотношение R – это декомпозиция без потерь.

Если естественное соединение R₁ и R₂ в итоге дает больше кортежей, чем в R – то это декомпозиция с потерями.

Отсутствие потерь при декомпозиции отношения R(X,Y,Z) в R₁(X,Y), R₂(Y,Z) гарантируется при условии, что от общего атрибута (Y) функционально зависит хотя бы один атрибут из двух оставшихся.

 

Пример 1:
Таблица 6.13 R (X,Y,Z).
			X		Y																	Y			X		Y			Z
			1		2		3															2			1		2			3
			3		2		6															2			3		2			6
			5		4		2													Y        Х                      Y        Z
Декомпозиция
Таблица 6.14 R1 (X,Y).												Таблица 6.15 R2 (X,Z).
X	Y											Y			Z
1	2											2			3
3	2											2			6
5	4											4			2
Соединение
Таблица 6.16 R3 (X,Y,Z).
			X		Y		Z
			1		2		3
			1		2		6				лишний кортеж
			3		2		3				лишний кортеж
			3		2		6
			5		4		2
Так как Y						X,   Y			Z, то R ≠ R3.
Пример 2:
Если Y → Z, то разбивая отношение R, получим, что R = R3.
Таблица 6.17 R (X,Y,Z).
			X		Y		Z							Y			Z				Изменим строчку мешающую
			1		2		3							2			3				зависимости Y → Z
			3		2		3							2			6
			5		4		2
Декомпозиция
Таблица 6.18 R1 (X,Y).													Таблица 6.19 R2 (Y,Z).
X	Y												Y			Z
1	2												2			3
3	2												4			2
5	4
Соединение
Таблица 6.20 R3 (X,Y,Z).
			X		Y		Z
			1		2		3
			3		2		3
			5		4		2

 

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

 

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